java集合学习总结

集合的根接口：Collection和 Map

Collection接口的常用子接口：List, Set

List接口的常用实现类：ArrayList, LinkedList, Stack, Vector

Set接口的常用实现类：HashSet, TreeSet

Map接口的常用实现类：HashMap, Hashtable, TreeMap

一、ArrayList

1. ArrayList允许包括 null 在内的所有元素。

2. ArrayList是有序的，因为ArrayList的大小可变是通过数组实现的。数组的数据结构是顺序表（线性表的一种），即内存中连续的一块存储空间，顺序和物理地址相同，这样只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

添加的算法：

一般情况下，在第i ( 1 ≤ i ≤ n)个元素之前插入一个元素时，需要将n至第i（共n-i+1）个元素向后移动一个位置。

删除的算法：

一般情况下，删除第i ( 1 ≤ i ≤ n)个元素时，需将从第i+1至第n（共n-i）个元素依此向前移动一个位置。

3. ArrayList中的元素可以重复。

4. 在添加大量元素前，应用程序可以使用 ensureCapacity(int minCapacity) 方法操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。因为

int newCapacity = (oldCapacity * 3)/2 + 1; //每次只扩展1.5陪，当list添加大量数据就要多次执行这个复制数组的操作

if (newCapacity < minCapacity)

newCapacity = minCapacity;

//通过对数组的不断复制达到List长度的可变

elementData = Arrays.copyOf(elementData, newCapacity);

5. 此实现不是同步的（也就是非线程安全的）。如果多个线程同时访问一个 ArrayList 实例，而其中至少一个线程从结构上修改了列表，那么它必须 保持外部同步。（结构上的修改是指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法将该列表“包装”起来。这最好在创建时完成，以防止意外对列表进行不同步的访问： List list = Collections.synchronizedList(new ArrayList(...));

二、 Vector

Vector和ArrayList是相同的，不同是Vector是线程安全的，同时也带来同步操作也花费大量的时间。同样是有序，可以有重复元素

三、 LinkedList

1. 允许包括 null 在内的所有元素。

2. LinkedList是有序的，LinkedList的数据结构是双向链表（线性表的一种），存储单元是任意的，可以连续，也可以不连续。双向链表的线性结构依靠节点前后的指针域来维护。因此在元素查询时效率比较低，因为要从头开始遍历每一个元素的指针域（指针域指向他的直接前驱和后继，或者说指针域中存储着直接前驱和后继的地址）去确定查找的元素。但是，双向链表的插入和删除操作效率比较高。

双向链表中插入节点：

双向链表删除节点：

3. LinkedList中的元素可以重复。

4. 此实现不是同步的（也就是非线程安全的）。

四、 Stack

1. 栈的数据结构介绍
   栈是限定仅在表尾插入或删除操作的线性表。表尾端叫做栈顶，表头端叫做栈底。栈又称为后进先出（Last Into First Out），简称LIFO结构。

2. stack通过五个操作对类 Vector 进行了扩展，是Vector的子类。

Set接口：一个不包含重复元素的 collection。更确切地讲，set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2，并且最多包含一个 null 元素。

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数

• 若结构中存在关键字和K相等的记录，则必定存储在f(K）的位置上。由此，不需比较便可直接取得所查记录。这个对应关系f称为散列函数(Hash function），按这个思想建立的表为散列表。

• 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2），这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。

• 综上所述，根据散列函数H(key）和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”， 作为这条记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。这个现象也叫散列桶，在散列桶中，只能通过顺序的方式来查找，一般只需要查找三次就可以找到。科学家计算过，当负载因子(load factor)（也叫装填因子）不超过75%，查找效率最高。因此再散列的条件也是当装填因子大于0.75。

这是一个链表数组，数组的每一个元素是一个链表的hashcode。当产生冲突，采用再散列法，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。再散列如果散列表太满就要创建一个桶数量更多的表，并将所有元素插入到这个新表中，然后丢弃原来的表。

五、 HashSet

此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。

1. HashSet无序。

2. HashSet中元素不能重复，如果add()两个相同的元素，只保存一个。

3. HashSet是非线程安全的。

4. 如果迭代性能很重要，则不要将初始容量（桶数量）设置得太高（或将加载因子设置得太低）。

六、 TreeSet

1. TreeSet是有序的，顺序是自然顺序，是自动完成排序的。

2. TreeSet中元素不可以重复，如果添加两个相同的元素，只保留一个。

3. TreeSet非线程安全的

七、HashMap

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

1. 如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

2. HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。通常，默认加载因子 (0.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。

3. 非线程安全。

4. 无序的。

5. 键值不可以重复。如果重复，后边的值会覆盖掉早前的值。

6. Map 接口提供三种collection 视图，允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。

keySet() 返回此映射中包含的键的 Set 视图。

values() 返回此映射中包含的值的 Collection 视图。

entrySet() 返回此映射中包含的映射关系的 Set 视图。

八、 HashTable

1. 和HashMap大体类似，区别：HashTable任何非 null 对象都可以用作键或值。还有就是线程安全的。

2. 为了成功地在哈希表中存储和获取对象，用作键的对象必须实现 hashCode 方法和 equals 方法。

String、Integer、Double等等这些类都是覆盖了hashcode()方法的，也就是我们可以不用写。

equals()相等的两个对象，hashcode()一定相等； equals（）不相等的两个对象，却并不能证明他们的hashcode()不相等。换句话说，equals()方法不相等的两个对象，hashcode()有可能相等。（我的理解是由于哈希码在生成的时候产生冲突造成的）。

九、 TreeMap

1. 非线程安全

2. 有序，自然顺序，自动完成排序。

3. 不可以重复，重复保留后来的。