3.集合与列表

列表"/>

3.集合与列表

目录

一、集合、列表的区别。

二、List列表：允许重复元素。

ArrayList：

LinkedList：

三、集合（在java中集合列表都可以叫集合，知道区别就行）。

一、Collection ------List接口和Set接口的根接口。（相当于父类的作用吧）

(一)List接口：

1.ArrayList-----（适合大量遍历和查找元素的情况）

2.LinkedList–适合大量增删元素的情况

(二)Set接口：

1.HashSet

2.TreeSet

二、Map

（一）HashMap

（二）TreeMap

一、集合、列表的区别。

简单的来讲,集合和列表最大的区别就是集合无序、不可重复；而列表有序、可以重复。

二、List列表：允许重复元素。

ArrayList：

以数组实现，不支持同步利用索引快速定位访问插入删除慢，因为每次插入/删除将会使后面元素向后/前移动适合变动不大，主要用于查询的数据和数组相比，其容量大小可动态调整

LinkedList：

以双向链表实现，不支持同步可被当作堆栈、队列、双端队列进行操作顺序访问高效，随机访问差插入和删除高效，因为只需改变元素指针，而无需移动元素适用于经常变化的数据

三、集合（在java中集合列表都可以叫集合，知道区别就行）。

java集合按照其存储结构可以分为两大类，一个是单列集合Collection和双列集合Map。

一、Collection ------List接口和Set接口的根接口。（相当于父类的作用吧）

(一)List接口：

List集合的特点是元素有序、元素可重复；
List接口继承自Collection接口，在List集合中允许出现重复的元素、所有的元素都是以一种线性方式存储的，程序中可通过索引（下标）来访问集合中的指定元素。List集合的元素有序，即元素的取出顺序和存入顺序一致！

1.ArrayList-----（适合大量遍历和查找元素的情况）

ArrayList内部封装了一个长度可变的数组对象，当存入的元素超过数组的长度时，ArrayList会在内存中分配更大的数组来存储这些元素，故ArrayList可以看为是一个长度可变的数组。.ArrayList内部存储结构形式导致了.ArrayList在增加或者删除元素的时候会创建新的数组效率比较低，故不适合大量的增删操作。 

2.LinkedList–适合大量增删元素的情况

LinkedList的内部结构是有两个Node类型的first和last属性维护一个双向循环链表，链表中的每一个元素都用引用的方式来记住它的前一个元素和后一个元素。

(二)Set接口：

Set集合的特点是元素无序、不可重复；
Set接口同样是继承自Collection接口，与Collection接口中的方法基本一致。Set接口中的元素无序，并且会以某种规则保证存入的元素不出现重复。

1.HashSet

HashSet是根据对象的哈希值来确定元素在集合中的存储的位置，具有优秀的存取和查找能力。所存储的元素是不可重复的，元素是无序的。
存储过程：向HashSet集合对象添加一个元素的时候，首先调用该元素的hashCode()方法返回对应的哈希值进行计算确定元素的存储位置，然后再去调用元素的equals()方法保证没有重复元素。

2.TreeSet

TreeSet是以二叉树的方式来存储元素，可以实现对集合的的元素进行排序！
TreeSet的内部结构存储是平衡二叉树，使用平衡二叉树可以保证TreeSet中没有重复的元素，还可以对元素进行排序。
这个过程是 存入新元素的时候，这个元素会跟最顶层元素相比较，若小于最顶层元素，则进入左边分支，继续执行（继续比较）下去，直到最后一个元素，如果小于最后一个元素则放在其左子树上，如果大于最后一个元素则放在右子树上； 若大于则进入右分支，道理和左边的一样。
当向TreeSet中存入一个元素时，会调用Comparable接口中的compareTo方法将该元素与其它元素进行比较，最后将它插入到有序的对象序列中；当然，也可以自己指定排序的规则，就是使用Comparator接口重写compare方法。

二、Map

Map接口是双列集合，key-value型，也就是映射关系。一个键对象key唯一对应一个值对象value，但是一个值对象value可以有多个键对象key。此外，key和value可以是任意数据类型，键对象key不允许重复。

（一）HashMap

HashMap存储键值映射关系，该集合的键和值允许为空（键可以为null，值也可以为null，如果有两个键都为null，那么会覆盖第一个null键），但是键不能重复，而且集合中的元素是无序的。
HashMap的底层存储结构：由哈希表结构（大致就是数组+链表，主体结构是数组）组成，链表主要是为了解决哈希值冲突而存在的分支的结构，HashMap对于元素的增删查改的操作效率都比较高。

（二）TreeMap（值可以为null，键不能）

TreeMap是用来存储键值对映射关系的，并且不允许出现重复的键。
TreeMap内部结构：二叉树（可保证键的唯一性，因为一个顶点的位置是不能存在两个点的），与TreeSet集合存储的原理是一样的按照某种顺序排列。与TreeSet一样，TreeMap可以通过自定义比较器的方式对所有的键进行定制排序。

我们来总结一下：

当未实现 Comparator 接口时，key 不可以为null，否则抛 NullPointerException 异常；

当实现 Comparator 接口时，若未对 null 情况进行判断，则可能抛 NullPointerException 异常。如果针对null情况实现了，可以存入，但是却不能正常使用get()访问，只能通过遍历去访问。