1.List
- ArrayList:
基于动态数组实现，支持随机访问。是线程不安全的。多线程应使用Collections.synchronizedList()或者JUC包下的CopyOnWriteArrayList。支持动态扩容，在容量不足的时候会扩为当前容量的1.5倍，即会创建新的List，再把旧的复制上去；删除的时候需要将删除位置后面的元素逐个前移，正因如此，不适合插入以及删除。查找的时间复杂度为O（1）。其空间的浪费主要体现在list会预留一定的空间。 - Vector：
和ArrayList类似，但使用Synchronized进行同步，单线程环境下优先使用ArrayList，可以传入参数指定扩容大小，如果这个参数小于等于0，则每次扩容都翻倍。 - LinkedList:
基于双向链表实现，JDK1.6之前为循环链表，JDK1.7取消了循环。
可以看看LinkedList的代码（JDK1.8）：
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
/**
* Links e as first element.
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
可以看到LinkedList实现了在头部和尾部插入，且同时有指针指向了头结点和尾结点，没有必要再使用双向的循环链表。所以LinkedList可以快速的在链表中插入和删除元素。还可以用作栈、队列和双向队列。它是线程不安全的。它的空间花费体现在它的每一个元素都需要消耗比ArrayList更多的空间。
- CopyOnWriteArrayList:
写操作在一个复制的数组上进行，读操作在原始数组中进行，读写分离，互不影响。写操作需要加锁，结束后把原始数组指向新的复制数组。适合读多写少的场景，内存占用大，不保证实时性。
2.Set
- HashSet:
基于哈希表实现，支持快速查找，但不支持有序性操作，插入时，先比较两个元素的哈希值，如果哈希值一致，再比较equals方法，其中的数据不可以重复。 - TreeSet:
基于红黑树实现，支持有序性操作，但查找效率不如HashSet，时间复杂度为O(logN)。 - LinkedHashSet:
使用LinkedHashMap来保存元素，继承HashSet，其操作方法和HashSet相同。
3.Map
- HashMap:
基于哈希表实现，使用拉链法解决哈希冲突。部分源码如下：
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
其中有一个Entry数组，每个数组通过链表来维护。插入元素时，首先通过hash计算出Entry数组的下标，然后使用头插法插入到链表中。JDK1.8以后，链表长度大于等于8会将链表转换为红黑树。(为什么这个临界值为8呢？因为hashmap满足泊松分布，当结点个数为8时，出现的几率是亿分之6，这个几率非常小，常见的情况是桶的个数小于8的情况，此时链表的查询性能和红黑树相差不多，因此转化为树还需要时间和空间，就没有转化为树的必要)
采用动态扩容，默认的table容量为16，每次扩容都会翻倍。如果给定了容量的初始值，HashMap也会将其扩充为2的幂次方大小，以次来保证HashMap的长度一致是2的幂次方。(为什么？下面来解答)
HashMap中采用hash&(length-1)来计算Entry的下标，可以知道2的幂次方-1得到的二进制值每一位都是1。这样就能保证相与后可以最大限度的用到Entry的位置。举个例子，如果长度不为2的幂次方，比如说为10，那么length-1=9=1001，则相与后第二第三位永远是0，则类似101,110这样的下标就永远不会被使用到，造成了空间的浪费。
put()方法：
* * * * * *
* jdk 1.7 *
* * * * * *
public V put(K key, V value) {
//懒加载
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 键为 null 单独处理
if (key == null)
return putForNullKey(value);
int hash = hash(key);
// 确定桶下标
int i = indexFor(hash, table.length);
// 先找出是否已经存在键为 key 的键值对，如果存在的话就更新这个键值对的值为 value
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 插入新键值对
addEntry(hash, key, value, i);
return null;
}
使用头插法插入链表：
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
// 头插法，链表头部指向新的键值对
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
扩容：resize()
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//创建新table
Entry[] newTable = new Entry[newCapacity];
//移动到新table中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//指向新table
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
transfer()：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
//获取链表的头节点e
while(null != e) {
//获取要转移的下一个节点next
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//计算要转移的节点在新的Entry数组newTable中的位置
int i = indexFor(e.hash, newCapacity);
//使用头插法将要转移的节点插入到newTable原有的单链表中
e.next = newTable[i];
//将newTable的hash桶的指针指向要转移的节点
newTable[i] = e;
//转移下一个需要转移的节点e
e = next;
}
}
}
扩容时可能出现的死循环情况：假设现有两个线程实现扩容，假设某个桶中有A->B->C，此时，两个线程都完成第一步扩容，A到了新的entry[]中，接下来对B进行transfer，线程1完成了前两步，计算B的新下标，同时将B的next指向A，此时线程1用完了CPU时间，线程2获得时间，此时再获得的Next是A，在完成了B的transfer后，会再次对A进行transfer，A会插在B的头部，此时，就形成了死循环。
loadFactor：加载因子，控制着Hash表中元素填满的程度，在HashMap中，默认的加载因子是0.75，最大容量是16，因此可以得知在16*0.75=12的时候，就需要扩容了。
HashMap是线程不安全的。其中null可以作为键，但这样的键只能有一个。
- HashTable：
和HashMap类似，但它是线程安全的，但它已经被淘汰，现在使用ConcurrentHashMap来保证线程安全。 - ConcurrentHashMap：
ConcurrentHashMap中引入了分段锁，每个分段锁维护几个HashEntry，多个线程可以同时访问不同的Entry，使其并发度更高，分段锁的默认个数为16个。JDK1.8后就不适用分段锁了，直接用node数组+链表+红黑树的结构，并发控制使用synchronized和CAS来实现。
扩容：
private void rehash(HashEntry<K,V> node) {
HashEntry<K,V>[] oldTable = table;
int oldCapacity = oldTable.length;
// 新的大小
int newCapacity = oldCapacity << 1;
//新的阈值大小
threshold = (int)(newCapacity * loadFactor);
// 创建新数组
HashEntry<K,V>[] newTable =
(HashEntry<K,V>[]) new HashEntry[newCapacity];
int sizeMask = newCapacity - 1;
// 遍历原数组
for (int i = 0; i < oldCapacity ; i++) {
// e 是链表的第一个元素
HashEntry<K,V> e = oldTable[i];
if (e != null) {
HashEntry<K,V> next = e.next;
// 计算应该放置在新数组中的位置，
int idx = e.hash & sizeMask;
if (next == null) // 该位置处只有一个元素，那比较好办
newTable[idx] = e;
else { // Reuse consecutive sequence at same slot
// e 是链表表头
HashEntry<K,V> lastRun = e;
// idx 是当前链表的头结点 e 的新位置
int lastIdx = idx;
// 下面这个 for 循环会找到一个 lastRun 节点，这个节点之后的所有元素是将要放到一起的
for (HashEntry<K,V> last = next;
last != null;
last = last.next) {
int k = last.hash & sizeMask;
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
// 将 lastRun 及其之后的所有节点组成的这个链表放到 lastIdx 这个位置
newTable[lastIdx] = lastRun;
// 下面的操作是处理 lastRun 之前的节点，
// 这些节点可能分配在另一个链表中，也可能分配到上面的那个链表中
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
V v = p.value;
int h = p.hash;
int k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
}
}
}
}
// 将新来的 node 放到新数组中刚刚的 两个链表之一 的 头部
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
- TreeMap：
可排序，基于红黑树实现，默认按键值升序排序，key必须实现Comparable接口。 - LinkedHashMap:
继承了HashMap，因此具有和 HashMap 一样的快速查找特性。当一个节点被访问时，如果 accessOrder 为 true，则会将该节点移到链表尾部。也就是说指定为 LRU 顺序之后，在每次访问一个节点时，会将这个节点移到链表尾部，保证链表尾部是最近访问的节点，那么链表首部就是最近最久未使用的节点。
网友评论