JAVA 集合整理
JAVA集合总结
List:
1.概括
* 1. List 是一个接口，它继承于Collection的接口。它代表着有序的队列。
* 2. AbstractList 是一个抽象类，它继承于AbstractCollection。AbstractList实现List接口中除size()、get(int location)之外的函数。
* 3. AbstractSequentialList 是一个抽象类，它继承于AbstractList。AbstractSequentialList 实现了“链表中，根据index索引值操作链表的全部函数”
* 4. ArrayList, LinkedList, Vector, Stack是List的4个实现类。
* ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。
* LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率低。
* Vector 是矢量队列，和ArrayList一样，它也是一个动态数组，由数组实现。但是ArrayList是非线程安全的，而Vector是线程安全的(加了锁)
* Stack 是栈，它继承于Vector。它的特性是：先进后出(FILO, First In Last Out) 栈也是线程安全的。
2.使用场景
* 1. 快速插入，删除元素，使用LinkedList
* 2. 快速随机访问元素，使用ArrayList
* 3. 多线程操作环境下为了保证数据安全应该使用Vector 3.详细介绍
* ArrayList:
* ArrayList基于数组实现，是一个动态的数组队列，他的 初始容量=10 他的容量可以自动增长 新的容量=1.5*原始容量
```java
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 每次扩容 原始容量+原始容量/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 将数据copy 到新的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
```
* ArrayList继承了AbstractList，实现了RandomAccess、Cloneable和Serializable接口
```java
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
```
* 实现了RandomAccess接口，提供了随机访问功能，实际上就是通过下标序号进行快速访问。
* 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
* 实现了Serializable接口，支持序列化.
* ArrayList非线程安全 * LinkedList:
* LinkedList 是基于链表实现的，是一个双向链表，可以用作堆栈，队列，双端队列，线程不安全，继承AbstractSequentialList实现List、Deque、Cloneable、Serializable。
```java
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
```
*LinkedList继承AbstractSequentialList，AbstractSequentialList 实现了get(int index)、set(int index, E element)、addint index, Eelement) 和remove(int index)这些函数。这些接口都是随机访问List的 随机访问效率很低
* LinkedList 实现 List 接口，能对它进行队列操作。
* LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
* LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
* LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输 * Vector:
* Vector和ArrayList差不多都是基于数组实现的
* Vector和ArrayList的方法基本一样 但是 Vector 在方法中加了synchronized 修饰 所以Vector是线程安全的，当我们用多线程时考虑数据安全，应该使用 Vector
* Vector默认大小是 10 当Vector 扩容时 若容量增加系数 大于0，则将容量的值增加“容量增加系数”；否则，将容量大小增加一倍。
```java
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
``` Map:
1.概括:
* Map是“键值对”映射的抽象接口。
* AbstractMap实现了Map中的绝大部分函数接口。它减少了“Map的实现类”的重复编码。
* SortedMap有序的“键值对”映射接口。
* NavigableMap是继承于SortedMap的，支持导航函数的接口。
* HashMap, Hashtable, TreeMap, WeakHashMap这4个类是“键值对”映射的实现类。它们各有区别
* HashMap 是基于“拉链法”实现的散列表。一般用于单线程程序中。
* Hashtable 也是基于“拉链法”实现的散列表。它一般用于多线程程序中。
* WeakHashMap也是基于“拉链法”实现的散列表，它一般也用于单线程程序中。相比HashMap，WeakHashMap中的键是“弱键”，当“弱键”被GC回收时，它对应的键值
对也会被从WeakHashMap中删除；而HashMap中的键是强键。
* TreeMap 是有序的散列表，它是通过红黑树实现的。它一般用于单线程中存储有序的映射。2.使用场景
* HashMap、WeakHashMap、TreeMap 非线程安全
* Hashtable 在方法中加了synchronized修饰 线程安全
* HashMap Hashtable 是无序的
* TreeMap 是有序的3.详细介绍
HashMap
1.HashMap通过拉链法：通过table数组存储，数组的每一个元素都是一个Entry；而一个Entry就是一个单向链表，Entry链表中的每一个节点就保存了 key-value键值对数据。 2. 添加key-value键值对首先，根据key值计算出哈希值，再计算出数组索引(即，该key-value在table中的索引)。然后，根据数组索引找到Entry(即，单向链表 )再遍历单向链表，将key和链表中的每一个节点的key进行对比。若key已经存在Entry链表中，则用该value值取代旧的value值；若key不存在Entry链表中 ，则新建一个key-value节点,并将该节点插入Entry链表的表头位置。 删除key-value键值对：删除键值对，相比于“添加键值对”来说，简单很多。首先，还是根据key计算出哈希值，再计算出数组索引(即，该key-value在table中的索引)。然后，根据索引找出Entry(即，单向链表)。若节点key-value存在与链表Entry中，则删除链表中的节点即可。 3. HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。 ``` public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { ... } ``` 4. 实现了Map接口，支持key-value键值对操作。支持“添加key-value键值对”、“获取key”、“获取value”、“获取map大小”、“清空map”等基本的key-value键值对 操作 5. 实现了Cloneable接口，意味着能被克隆。 6. 实现了java.io.Serializable接口，意味着支持序列化，能通过序列化去传输。 7. 线程不安全 8. HashMap 的初始容量是 16 扩展的时候 每次扩展二倍 ``` void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length);//容量扩为原来容量的2倍。 hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } ``` 9. HashMap 添加元素时 使用的自定义的哈希算法 ``` static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } // 将“key-value”添加到HashMap中 public V put(K key, V value) { // 若“key为null”，则将该键值对添加到table[0]中。 if (key == null) return putForNullKey(value); // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！ if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 若“该key”对应的键值对不存在，则将“key-value”添加到table中 modCount++; addEntry(hash, key, value, i); return null; } ``` 10. HashMap key-value 存储数据是允许key-value 为空 key为null 时会添加到 table 的第一个位置 11. HashMap不支持contains(Object value)方法，没有重写toString()方法。
- Hashtable
1. Hashtable 基本和HashMap 差不多
2. Hashtable 的默认大小为11 每次扩充 新容量=旧容量*2+1
@SuppressWarnings("unchecked")
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
//每次扩充 *2 +1
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
3. Hashtable 线程安全
4. Hashtable 没有自定义hash 算法
```JAVA
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode(); //直接采用的hashcode
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
5. Hashtable支持contains(Object value)方法，而且重写了toString()方法- TreeMap
* TreeMap 是一个有序的 key-value 基于红黑树的 NavigableMap 实现
* TreeMap 可以被克隆 实现了Cloneable 接口
* TreeMap 支持序列化
* TreeMap containKey get put remove 的时间复杂度都是 log
* TreeMap 可以创建时根据提供的Comparator 进行排序- WeakHashMap
1. WeakHashMap 继承于AbstractMap，实现了Map接口。
2. 和HashMap一样，WeakHashMap 也是一个散列表，它存储的内容也是键值对(key-value)映射，而且键和值都可以是null。
不过WeakHashMap的键是“弱键”。在 WeakHashMap 中，当某个键不再正常使用时，会被从WeakHashMap中被自动移除。更精确地说，对于一个给定的键，其映射
的存在并不阻止垃圾回收器对该键的丢弃，这就使该键成为可终止的，被终止，然后被回收。某个键被终止时，它对应的键值对也就从映射中有效地移除了。
3. 弱键回收的步骤：
通过WeakReference和ReferenceQueue实现的
(1)新建WeakHashMap，将“键值对”添加到WeakHashMap中。实际上，WeakHashMap是通过数组table保存Entry键值对；每一个Entry实际上是一个单向链表，
即Entry是键值对链表。
(2) 当某“弱键”不再被其它对象引用，并被GC回收时。在GC回收该“弱键”时，这个“弱键”也同时会被添加到ReferenceQueue(queue)队列中。
(3) 当下一次我们需要操作WeakHashMap时，会先同步table和queue。table中保存了全部的键值对，而queue中保存被GC回收的键值对；同步它们就是删除ta
ble中被GC回收的键值对。
4. 默认容量和加载因子和HashMap一样
5. 线程不安全
Set
1.概括
1.Set 是继承于Collection的接口。它是一个不允许有重复元素的集合。
2.AbstractSet 是一个抽象类，它继承于AbstractCollection，AbstractCollection实现了Set中的绝大部分函数，为Set的实现类提供了便利。
3.HastSet 和 TreeSet 是Set的两个实现类。
- HashSet依赖于HashMap，它实际上是通过HashMap实现的。HashSet中的元素是无序的。
- TreeSet依赖于TreeMap，它实际上是通过TreeMap实现的。TreeSet中的元素是有序的。
2.使用场景
hashSet 无序
TreeSet 有序
3.详细介绍
HashSet
HashSet 是一个没有重复元素的集合
它是由HashMap实现的，不保证元素的顺序，而且HashSet允许使用 null 元素。
HashSet是非同步的。如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么它必须 保持外部同步。这通常是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSet 方法来“包装” set。最好在创建时完成这一操作，以防止对该 set 进行意外的不同步访问：Set s = Collections.synchronizedSet(new HashSet(...));
> TreeSet
TreeSet 是一个有序的集合，它的作用是提供有序的Set集合。它继承于AbstractSet抽象类，实现了NavigableSet<E>, Cloneable, java.io.Serializable接口。
TreeSet 继承于AbstractSet，所以它是一个Set集合，具有Set的属性和方法。
TreeSet 实现了NavigableSet接口，意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。
TreeSet 实现了Cloneable接口，意味着它能被克隆。
TreeSet 实现了java.io.Serializable接口，意味着它支持序列化。
TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
TreeSet为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。
另外，TreeSet是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。
