Java-集合
Java-集合
标签（空格分隔）： Java
1. 概述
容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。
1.1 Collection
1）Set
- TreeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。
- HashSet：基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
- LinkedHashSet：具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序。
2）List
- ArrayList：基于动态数组实现，支持随机访问。
- Vector：和 ArrayList 类似，但它是线程安全的。
- LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。
3）Queue
- LinkedList：可以用它来实现双向队列。
- PriorityQueue：基于堆结构实现，可以用它来实现优先队列。
1.2 Map
- TreeMap：基于红黑树实现。
- HashMap：基于哈希表实现。
- HashTable：和 HashMap 类似，但它是线程安全的，它是遗留类，不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
- LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。
2. 涉及设计模式
2.1 迭代器模式
实现Iterable接口的类必须重写iterator方法，并返回一个Iterator对象，这个类包含了迭代器的基本操作。
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
// prevent creating a synthetic constructor
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
} jdk1.5后foreach方法可以遍历实现了Iterable接口的类的实例对象。
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for (String item : list) {
System.out.println(item);
} 2.2 适配器模式
java.util.Arrays#asList() 可以把数组类型转换为 List 类型。
@SafeVarargs public static <T> List<T> asList(T... a)
应该注意的是 asList() 的参数为泛型的变长参数，不能使用基本类型数组作为参数，只能使用相应的包装类型数组。
经过它转换的list是一个长度不可变的列表，传入参数的数组有多长，其返回的列表就只能是多长
Integer[] arr = {1, 2, 3};
List list = Arrays.asList(arr); 3. ArrayList
3.1 添加元素与扩容
数组的默认大小为10。
private static final int DEFAULT_CAPACITY = 10;
添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)。扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，代价高，因此最好在创建时就指定容量大小，减少扩容操作的次数。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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:
elementData = Arrays.copyOf(elementData, newCapacity);
} 3.2 删除元素
需要调用System.arraycopy()将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，代价是非常高的。
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
} 3.3 序列化
支持序列化、随机访问、克隆
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable ArrayList基于动态数组，不需要完全序列化，可以只序列化已存的数据，由此实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。
transient Object[] elementData; // non-private to simplify nested class access
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
} private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
} 序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出，writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化，如果没有该方法则调用默认的writeObject()，readObject()同理。
ArrayList list = new ArrayList(); ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file)); oos.writeObject(list);
3.4 Fail-Fast
modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。
在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException。
这是因为ArrayList是线程不安全容器，直接抛出异常提醒用户存在并发导致数据不一致。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
} 3.5 ArrayList与Vector
- Vector 是同步的，使用了 synchronized 进行同步，因此开销就比 ArrayList 要大，访问速度更慢。最好使用 ArrayList 而不是 Vector，因为同步操作可以自己操作。
- Vector 每次扩容请求其大小的
2倍空间，而 ArrayList 是1.5倍。
4. CopyOnWriteArrayList
4.1 概览
CopyOnWrite并发容器也是一种读写分离的思想。
当我们往一个容器添加元素的时候，需要加锁，不然会出现多个并发复制的数组，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用（保证可见性）指向新的容器。
对CopyOnWrite容器进行并发的读的时候，不需要加锁，因为当前容器不会添加任何元素。
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
final void setArray(Object[] a) {
array = a;
} @SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
return (E) a[index];
} 4.2 适用场景
CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。
但是 CopyOnWriteArrayList 的延时更新的策略是通过在写的时候针对的是不同的数据容器来实现的，放弃数据实时性以及多增加了空间使用来达到数据的最终一致性；而且内存多占用了一个数组大小。
所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。
5. LinkedList
5.1 概览
基于双向链表实现，使用 Node 存储链表节点信息。每个链表存储了 first 和 last 头尾指针。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
transient Node<E> first;
transient Node<E> last; 
5.2 LinkedList与ArrayList
- ArrayList 基于动态数组实现，LinkedList 基于双向链表实现；
- ArrayList 支持随机访问，LinkedList 不支持，但在任意位置添加删除元素更快；
6. HashMap
以下源码分析基于基于JDK1.7
6.1 存储结构
内部包含了一个 Entry 类型的数组 table。
transient Node[] table;
Entry 存储着键值对，它包含了四个字段，从 next 字段我们可以看出 Entry 是一个链表。
数组中的每个位置被当成一个桶，一个桶存放一个链表，HashMap 使用拉链法来解决冲突，同一个链表中存放哈希值相同的 Entry。
从 JDK 1.8 开始，一个桶存储的链表长度大于 8 时会将链表转换为红黑树。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
} 6.2 构造函数
public HashMap(int initialCapacity, float loadFactor) {
...
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
} 1）loadFactor与threshold
loadFactor是装载因子，扩容使用。
threshold是HashMap判断size是否需要扩容的阈值。
见下文扩容。
2）tableSizeFor(initialCapacity)
tableSizeFor方法保证函数返回值是大于等于给定参数initialCapacity最小的2的幂次方的数值。
大致实现：二进制上来看initialCapacity最高位为1的左移一位，就是说只要取得initialCapacity的掩码后加一即可。
源码分析：
int n = cap - 1
给定的cap减1，是为了避免参数cap本来就是2的幂次方，这样一来，经过后续的未操作的，cap将会变成2 * cap,是不符合我们预期的。n |= n >>> 1
n >>> 1，n无符号右移1位，即n二进制最高位的1右移一位；
n | (n >>> 1)，导致的结果是n二进制的高2位值为1;
目前n的高1~2位均为1。n |= n >>> 2
n继续无符号右移2位。
n | (n >>> 2)，导致n二进制表示高34位经过运算值均为1；4位均为1。
目前n的高1
...
- n |= n >>> 16
n继续无符号右移16位。
n | (n >>> 16)，导致n二进制表示高1732位经过运算值均为1；32位均为1（
目前n的高1int长度为32位）。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
} 3）capacity保持为2的幂次方原因
在JDK1.8中，在HashMap存储数据的时候，为了数据能够均匀分布，以避免哈希冲突，采用了取得哈希码后进行取余。取余(%)操作中如果除数是2的幂次方则等同于与其除数减一的与(&)操作。采用二进制位操作&，相对于%，能够提高运算效率，这就是要求cap的值被要求为2幂次方的原因。
见下文添加元素。
6.3 添加元素
1）计算hash值
由于cap是2的幂次方，那么cap的高位应该全部为0。如果key的hash值只用自身的hashcode的话，那么cap只会和key的hash低位做&操作。这样一来，cap的值就只有低位参与运算，高位毫无存在感，从而会带来哈希冲突的风险。
所以在计算key的哈希值的时候，用其自身hashcode值与其低16位做异或操作。这也就让高位参与到index的计算中来了，并且使用异或的原因是如果有一位发生改变，hashcode就发生改变，这样降低了哈希冲突的风险。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} public final int hashCode() { //重写equals和hashcode便于put的时候进行找下标和判断是否key值相同
return Objects.hashCode(key) ^ Objects.hashCode(value);
} 2）取模计算桶下标
令 x = 1<<4，即 x 为 2 的 4 次方，它具有以下性质：
x : 00010000 x-1 : 00001111
令一个数 y 与 x-1 做与运算，可以去除 y 位级表示的第 4 位以上数：
y : 10110010 x-1 : 00001111 y&(x-1) : 00000010
这个性质和 y 对 x 取模效果是一样的：
y : 10110010 x : 00010000 y%x : 00000010
位运算的代价比求模运算小的多，因此在进行这种计算时用位运算的话能带来更高的性能，如果能保证 capacity 为 2 的 n 次方，那么就可以将这个操作转换为位运算。
static int indexFor(int h, int length) {
return h & (length-1);
} 3）插入元素
HashMap 允许插入键为 null 的键值对，但是因为无法调用 null 的 hashCode() 方法，无法确定该键值对的桶下标，只能通过强制指定一个桶下标来存放，HashMap 使用第 0 个桶存放键为 null 的键值对。
查询是否已经存在键为key的键值对，有则更新，没有插入。
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;
} private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
} 使用链表的头插法，也就是新的键值对插在链表的头部，而不是链表的尾部。JDK1.8起使用链表的尾插法，很大一部分原因是因为1.8起链表长度超过8转为红黑树。
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++;
} 6.4 扩容
1）动态扩容
设 HashMap 的 table 长度为 M，需要存储的键值对数量为 N，如果哈希函数满足均匀性的要求，那么每条链表的长度大约为 N/M，因此平均查找次数的复杂度为 O(N/M)。
为了让查找的时间效率提高，需要保证 M 尽可能大，也就是说 table要尽可能大，但是又不能太大，如果多了许多空余的数组位那么空间就会浪费。
HashMap 采用动态扩容来根据当前的 N 值来调整 M 值，使得空间效率和时间效率都能得到保证。
和扩容相关的参数主要有：capacity、size、threshold 和 load_factor。
| 参数 | 含义 |
|---|---|
| capacity | table 的容量大小，默认为 16。需要注意的是 capacity 必须保证为 2 的 n 次方。 |
| size | table 的实际使用量。 |
| threshold | size 的临界值，size 必须小于 threshold，如果大于等于，就必须进行扩容操作。 |
| loadFactor | 装载因子，table 能够使用的比例，threshold = capacity * loadFactor。 |
static final int DEFAULT_INITIAL_CAPACITY = 16; static final int MAXIMUM_CAPACITY = 1 << 30; static final float DEFAULT_LOAD_FACTOR = 0.75f; transient Entry[] table; transient int size; int threshold; final float loadFactor; transient int modCount;
从下面的添加元素代码中可以看出，当需要扩容时，令 capacity 为原来的两倍。
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
} 扩容使用 resize() 实现，大概是创建一个新的扩容的table再将旧数据插入，费时。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
} 2）重新计算元素位置
扩容时将旧数据放入扩容后的数组中，需要把键值对重新放到对应的桶上。
已知扩容两倍大小，即旧容量左移一位：
capacity : 00010000 //16 new capacity : 00100000 //32
要取新的桶位置就需要容量减一 并和哈希值取与：
capacity - 1 : 00001111 newcapacity - 1 : 00011111
可以发现：原本只是取了四位，扩容后多了一位，故这个元素的新位置就取决于哈希码的这多出来的一位（即第5位）。
如果为0那么取模得到的结果和之前一样；如果为 1，那么得到的结果为原来的结果+16。
3）负载因子的选择
如果负载因子是0.5（过低），那么就意味着数组超过一半时就需要扩容，那么在达到一定的数量级，扩容的速度非常频繁，且浪费大量的空间，如果是0.9（过高），意味着数组到达数组90%才扩容，有可能会造成大数据下的数组越界，0.75应该是综合所以因素选择的最优负载因子。
6.5 查找元素
查找需要分成两步进行：
- 计算键值对所在的桶；
- 在链表上顺序查找，时间复杂度显然和链表的长度成正比。
6.6 hashmap与hashtable
- HashTable 使用 synchronized 来进行同步。
- HashMap 可以插入键为 null 的 Entry。
- HashMap 的迭代器是 fail-fast 迭代器。
- HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的。
7. ConcurrentHashMap
源码基于jdk1.7
7.1 存储结构
ConcurrentHashMap 和 HashMap 实现上类似，最主要的差别是 ConcurrentHashMap 采用了分段锁（Segment），每个分段锁维护着几个桶（HashEntry），多个线程可以同时访问不同分段锁上的桶，从而使其并发度更高（并发度就是 Segment 的个数）。
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
} static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
static final int MAX_SCAN_RETRIES =
Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
transient volatile HashEntry<K,V>[] table;
transient int count;
transient int modCount;
transient int threshold;
final float loadFactor;
} final Segment<K,V>[] segments;
默认的并发度为16，也就是说默认创建16个Segment。
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
7.2 size、get、put操作
1）size
每个 Segment 维护了一个 count 变量来统计该 Segment 中的键值对个数。
/** * The number of elements. Accessed only either within locks * or among other volatile reads that maintain visibility. */ transient int count;
在执行 size 操作时，需要遍历所有 Segment 然后把 count 累计起来。
ConcurrentHashMap 在执行 size 操作时先尝试不加锁，如果连续两次不加锁操作得到的结果一致，那么可以认为这个结果是正确的。如果尝试的次数超过 3 次，就需要对每个 Segment 加锁。
/**
* Number of unsynchronized retries in size and containsValue
* methods before resorting to locking. This is used to avoid
* unbounded retries if tables undergo continuous modification
* which would make it impossible to obtain an accurate result.
*/
static final int RETRIES_BEFORE_LOCK = 2;
public int size() {
// Try a few times to get accurate count. On failure due to
// continuous async changes in table, resort to locking.
final Segment<K,V>[] segments = this.segments;
int size;
boolean overflow; // true if size overflows 32 bits
long sum; // sum of modCounts
long last = 0L; // previous sum
int retries = -1; // first iteration isn't retry
try {
for (;;) {
// 超过尝试次数，则对每个 Segment 加锁
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
sum += seg.modCount;
int c = seg.count;
if (c < 0 || (size += c) < 0)
overflow = true;
}
}
// 连续两次得到的结果一致，则认为这个结果是正确的
if (sum == last)
break;
last = sum;
}
} finally {
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
return overflow ? Integer.MAX_VALUE : size;
} 2）get、put
在put的时候需要ReentrantLock锁住Segment，get时候不加锁，使用volatile来保证可见性。
7.3 JDK1.8的改动
JDK 1.7 使用分段锁机制来实现并发更新操作，核心类为 Segment，它继承自重入锁 ReentrantLock，并发度与 Segment 数量相等。
JDK 1.8 使用了 CAS 操作来支持更高的并发度，在 CAS 操作失败时使用内置锁 synchronized。
JDK8不采用segment而采用node，锁住node来实现减小锁粒度；
使用3个CAS操作来确保node的一些操作的原子性，这种方式代替了锁；
采用synchronized而不是ReentrantLock，在 CAS 操作失败时使用内置锁 synchronized；
链表过长时会转换为红黑树。
探索 ConcurrentHashMap 高并发性的实现机制
8. LinkedHashMap
8.1 存储结构
继承自 HashMap，因此具有和 HashMap 一样的快速查找特性。
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
内部维护了一个双向链表，用来维护插入顺序或者 LRU 顺序。
/** * The head (eldest) of the doubly linked list. */ transient LinkedHashMap.Entry<K,V> head; // 头指针 /** * The tail (youngest) of the doubly linked list. */ transient LinkedHashMap.Entry<K,V> tail; // 尾指针
next是用于维护HashMap指定table位置上连接的Entry的顺序的，before、After是用于维护Entry插入的先后顺序的。
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
} accessOrder 决定了顺序，默认为 false，所有的Entry按照插入的顺序排列；如果为true，所有的Entry按照访问的顺序排列。
true的意思是，如果有1 2 3这3个Entry，那么访问了1，就把1移到尾部去，即2 3 1。每次访问都把访问的那个数据移到双向队列的尾部去，那么每次要淘汰数据的时候，双向链表最头的那个数据就是要淘汰的数据。（LRU）
final boolean accessOrder;
LinkedHashMap 最重要的是以下用于维护顺序的函数，它们会在 put、get 等方法中调用。
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { } 8.2 afterNodeAccess()
当一个节点被get访问时，如果 accessOrder 为 true，则会将该节点移到链表尾部。也就是说指定为 LRU 顺序之后，在每次get访问一个节点时，会将这个节点移到链表尾部，保证链表尾部是最近访问的节点，那么链表首部就是最近最久未使用的节点。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
} 8.3 afterNodeInsertion()
在put等操作之后执行，当 removeEldestEntry() 方法返回 true 时会移除最晚的节点，也就是链表首部节点 first。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//evict 只有在构建 Map 的时候才为 false，在这里为 true。
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
} removeEldestEntry() 默认为 false，如果需要让它为 true，需要继承 LinkedHashMap 并且覆盖这个方法的实现，这在实现 LRU 的缓存中特别有用，通过让其为true，然后其会移除最近最久未使用的节点，从而保证缓存空间足够，并且缓存的数据都是热点数据。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
} 8.4 LRU 缓存
1）LRU介绍
LRU(Least Recently Used)算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
2）LRU实现
利用链表和hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表尾部，如果不存在，则新建一个节点，放到链表尾部，若缓存满了，则把链表第一个节点删除即可。
3）LinkedHashMap实现
以下是使用 LinkedHashMap 实现的一个 LRU 缓存：
- 设定最大缓存空间 MAX_ENTRIES 为 3；
- 使用 LinkedHashMap 的构造函数将 accessOrder 设置为 true，开启 LRU 顺序；
- 覆盖 removeEldestEntry() 方法实现，在节点多于 MAX_ENTRIES 就会将最近最久未使用的数据移除。
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private static final int MAX_ENTRIES = 3;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
LRUCache() {
super(MAX_ENTRIES, 0.75f, true);
}
} public static void main(String[] args) {
LRUCache<Integer, String> cache = new LRUCache<>();
cache.put(1, "a");
cache.put(2, "b");
cache.put(3, "c");
cache.get(1);
cache.put(4, "d");
System.out.println(cache.keySet());
} [3, 1, 4]
9. 参考资料
- Eckel B. Java 编程思想 [M]. 机械工业出版社, 2007.
- Cay S. Horstmann.JAVA核心技术（卷1）[M]. 机械工业出版社, 2008.
- CyC的CS-Notes:Java篇
查看24道真题和解析