北京网站开发怎么样,网站关键词设置多少个,提升审美网站,网站建设定做目录
一、概览
1.1 Collection
1. Set
2. List
3. Queue
1.2 Map
二、容器中的设计模式
迭代器模式
适配器模式
三、源码分析
ArrayList
1. 概览
2. 扩容
3. 删除元素
4. 序列化
5. Fail-Fast
Vector
1. 同步
2. 扩容
3. 与 ArrayList 的比较
4. 替代方案…目录
一、概览
1.1 Collection
1. Set
2. List
3. Queue
1.2 Map
二、容器中的设计模式
迭代器模式
适配器模式
三、源码分析
ArrayList
1. 概览
2. 扩容
3. 删除元素
4. 序列化
5. Fail-Fast
Vector
1. 同步
2. 扩容
3. 与 ArrayList 的比较
4. 替代方案
CopyOnWriteArrayList
1. 读写分离
2. 适用场景
LinkedList
1. 概览
2. 与 ArrayList 的比较
HashMap
1. 存储结构
2. 拉链法的工作原理
3. put 操作
4. 确定桶下标
5. 扩容-基本原理
6. 与 Hashtable 的比较
7. 对象作为key存储
ConcurrentHashMap
1. 存储结构
2. size 操作
3. JDK 1.8 的改动
LinkedHashMap
存储结构
afterNodeAccess()
afterNodeInsertion() Java容器是一套工具用于存储数据和对象。可以与C的STL类比。Java容器也称为Java Collection Framework (JCF)。除了存储对象的容器之外还提供了一套工具类用于处理和操作容器中的对象。总体来说这是一个框架它包含了Java对象容器和工具类。 一、概览 容器主要包括 Collection 和 Map 两种Collection 存储着对象的集合而 Map 存储着键值对两个对象的映射表。 1.1 Collection
1. Set
TreeSet基于红黑树实现支持有序性操作例如根据一个范围查找元素的操作。但是查找效率不如 HashSetHashSet 查找的时间复杂度为 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 类似但它是线程安全的这意味着同一时刻多个线程同时写入 HashTable 不会导致数据不一致。它是遗留类不应该去使用它而是使用 ConcurrentHashMap 来支持线程安全ConcurrentHashMap 的效率会更高因为 ConcurrentHashMap 引入了分段锁。LinkedHashMap使用双向链表来维护元素的顺序顺序为插入顺序或者最近最少使用LRU顺序。
二、容器中的设计模式
迭代器模式
Collection 继承了 Iterable 接口其中的 iterator() 方法能够产生一个 Iterator 对象通过这个对象就可以迭代遍历 Collection 中的元素。
从 JDK 1.5 之后可以使用 foreach 方法来遍历实现了 Iterable 接口的聚合对象。
ListString list new ArrayList();
list.add(a);
list.add(b);
for (String item : list) {System.out.println(item);
}
适配器模式
java.util.Arrays#asList() 可以把数组类型转换为 List 类型。
SafeVarargs
public static T ListT asList(T... a)
应该注意的是 asList() 的参数为泛型的变长参数不能使用基本类型数组作为参数只能使用相应的包装类型数组。
Integer[] arr {1, 2, 3};
List list Arrays.asList(arr);
也可以使用以下方式调用 asList()
List list Arrays.asList(1, 2, 3);
三、源码分析
如果没有特别说明以下源码分析基于 JDK 1.8。
在 IDEA 中 double shift 调出 Search EveryWhere查找源码文件找到之后就可以阅读源码。
ArrayList
1. 概览
因为 ArrayList 是基于数组实现的所以支持快速随机访问。RandomAccess 接口标识着该类支持快速随机访问。
public class ArrayListE extends AbstractListEimplements ListE, RandomAccess, Cloneable, java.io.Serializable 数组的默认大小为 10。
private static final int DEFAULT_CAPACITY 10;
2. 扩容 添加元素时使用 ensureCapacityInternal() 方法来保证容量足够如果不够时需要使用 grow() 方法进行扩容新容量的大小为 oldCapacity (oldCapacity 1)即 oldCapacityoldCapacity/2。其中 oldCapacity 1 需要取整所以新容量大约是旧容量的 1.5 倍左右。oldCapacity 为偶数就是 1.5 倍为奇数就是 1.5 倍-0.5 扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中这个操作代价很高因此最好在创建 ArrayList 对象时就指定大概的容量大小减少扩容操作的次数。 public boolean add(E e) {ensureCapacityInternal(size 1); 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;if (minCapacity - elementData.length 0)grow(minCapacity);
}
private void grow(int minCapacity) {int oldCapacity elementData.length;int newCapacity oldCapacity (oldCapacity 1);if (newCapacity - minCapacity 0)newCapacity minCapacity;if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);elementData Arrays.copyOf(elementData, newCapacity);
}
3. 删除元素
需要调用 System.arraycopy() 将 index1 后面的元素都复制到 index 位置上该操作的时间复杂度为 O(N)可以看到 ArrayList 删除元素的代价是非常高的。
public E remove(int index) {rangeCheck(index);modCount;E oldValue elementData(index);int numMoved size - index - 1;if (numMoved 0)System.arraycopy(elementData, index1, elementData, index, numMoved);elementData[--size] null; return oldValue;
}
4. 序列化
ArrayList 基于数组实现并且具有动态扩容特性因此保存元素的数组不一定都会被使用那么就没必要全部进行序列化。
保存元素的数组 elementData 使用 transient 修饰该关键字声明数组默认不会被序列化。
transient Object[] elementData;
ArrayList 实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。
private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {elementData EMPTY_ELEMENTDATA;s.defaultReadObject();s.readInt(); if (size 0) {ensureCapacityInternal(size);Object[] a elementData;for (int i0; isize; i) {a[i] s.readObject();}}
}
private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{int expectedModCount modCount;s.defaultWriteObject();s.writeInt(size);for (int i0; isize; i) {s.writeObject(elementData[i]);}if (modCount ! expectedModCount) {throw new ConcurrentModificationException();}
}
序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法原理类似。
ArrayList list new ArrayList();
ObjectOutputStream oos new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(list);
5. Fail-Fast fail-fast 机制是 Java 集合 Collection 中的一种错误机制。当多个线程对同一个集合的内容进行 操作时就可能会产生 fail-fast 事件。 例如当某一个线程 A 通过 iterator 去遍历某集合的过程中若该集合的内容被其他线程所改变 了那么线程 A 访问集合时就会抛出 ConcurrentModifificationException 异常产生 fail-fast 事 件。这里的操作主要是指 add 、 remove 和 clear 对集合元素个数进行修改。 解决办法建议使用 “java.util.concurrent 包下的类 ” 去取代 “java.util 包下的类 ” 。 可以这么理解在遍历之前把 modCount 记下来 expectModCount 后面 expectModCount 去 和 modCount 进行比较如果不相等了 证明已并发了被修改了于是抛出 ConcurrentModifificationException 异常并发修改异常 Vector
1. 同步
它的实现与 ArrayList 类似但是使用了 synchronized 进行同步。
public synchronized boolean add(E e) {modCount;ensureCapacityHelper(elementCount 1);elementData[elementCount] e;return true;
}
public synchronized E get(int index) {if (index elementCount)throw new ArrayIndexOutOfBoundsException(index);return elementData(index);
}
2. 扩容
Vector 的构造函数可以传入 capacityIncrement 参数它的作用是在扩容时使容量 capacity 增长 capacityIncrement。如果这个参数的值小于等于 0扩容时每次都令 capacity 为原来的两倍。
public Vector(int initialCapacity, int capacityIncrement) {super();if (initialCapacity 0)throw new IllegalArgumentException(Illegal Capacity: initialCapacity);this.elementData new Object[initialCapacity];this.capacityIncrement capacityIncrement;
}private void grow(int minCapacity) {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);
}//调用没有 capacityIncrement 的构造函数时
capacityIncrement 值被设置为 0也就是说默认情况下 Vector 每次扩容时容量都会翻倍。public Vector(int initialCapacity) {this(initialCapacity, 0);
}
public Vector() {this(10);
}
3. 与 ArrayList 的比较
Vector 是同步的因此开销就比 ArrayList 要大访问速度更慢。最好使用 ArrayList 而不是 Vector因为同步操作完全可以由程序员自己来控制Vector 每次扩容请求其大小的 2 倍也可以通过构造函数设置增长的容量而 ArrayList 是 1.5 倍。
4. 替代方案
可以使用 Collections.synchronizedList(); 得到一个线程安全的 ArrayList。
ListString list new ArrayList();
ListString synList Collections.synchronizedList(list);
也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。
ListString list new CopyOnWriteArrayList();
CopyOnWriteArrayList
1. 读写分离
写操作在一个复制的数组上进行读操作还是在原始数组中进行读写分离互不影响。
写操作需要加锁防止并发写入时导致写入数据丢失。
写操作结束之后需要把原始数组指向新的复制数组。
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;
}
2. 适用场景
CopyOnWriteArrayList 在写操作的同时允许读操作大大提高了读操作的性能因此很适合读多写少的应用场景。
但是 CopyOnWriteArrayList 有其缺陷
内存占用在写操作时需要复制一个新的数组使得内存占用为原来的两倍左右数据不一致读操作不能读取实时性的数据因为部分写操作的数据还未同步到读数组中。
所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。
LinkedList
1. 概览
基于双向链表实现使用 Node 存储链表节点信息。
private static class NodeE {E item;NodeE next;NodeE prev;
}每个链表存储了 first 和 last 指针transient NodeE first;
transient NodeE last;
2. 与 ArrayList 的比较
ArrayList 基于动态数组实现LinkedList 基于双向链表实现。ArrayList 和 LinkedList 的区别可以归结为数组和链表的区别
数组支持随机访问但插入删除的代价很高需要移动大量元素链表不支持随机访问但插入删除只需要改变指针。
HashMap
为了便于理解以下源码分析以 JDK 1.7 为主。
1. 存储结构
内部包含了一个 Entry 类型的数组 table。Entry 存储着键值对。它包含了四个字段从 next 字段我们可以看出 Entry 是一个链表。即数组中的每个位置被当成一个桶一个桶存放一个链表。HashMap 使用拉链法来解决冲突同一个链表中存放哈希值和散列桶取模运算结果相同的 Entry。
transient Entry[] table;static class EntryK,V implements Map.EntryK,V {final K key;V value;EntryK,V next;int hash;Entry(int h, K k, V v, EntryK,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();}
}
2. 拉链法的工作原理
HashMapString, String map new HashMap();
map.put(K1, V1);
map.put(K2, V2);
map.put(K3, V3);
新建一个 HashMap默认大小为 16插入 K1,V1 键值对先计算 K1 的 hashCode 为 115使用除留余数法得到所在的桶下标 115%163。插入 K2,V2 键值对先计算 K2 的 hashCode 为 118使用除留余数法得到所在的桶下标 118%166。插入 K3,V3 键值对先计算 K3 的 hashCode 为 118使用除留余数法得到所在的桶下标 118%166插在 K2,V2 前面。
应该注意到链表的插入是以头插法方式进行的例如上面的 K3,V3 不是插在 K2,V2 后面而是插入在链表头部。
查找需要分成两步进行
计算键值对所在的桶在链表上顺序查找时间复杂度显然和链表的长度成正比。
3. put 操作
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 的键值对如果存在的话就更新这个键值对的值为 valuefor (EntryK,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;
} HashMap 允许插入键为 null 的键值对。但是因为无法调用 null 的 hashCode() 方法也就无法确定该键值对的桶下标只能通过强制指定一个桶下标来存放。HashMap 使用第 0 个桶存放键为 null 的键值对。
private V putForNullKey(V value) {for (EntryK,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;
}
使用链表的头插法也就是新的键值对插在链表的头部而不是链表的尾部。
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) {EntryK,V e table[bucketIndex];// 头插法链表头部指向新的键值对table[bucketIndex] new Entry(hash, key, value, e);size;
}Entry(int h, K k, V v, EntryK,V n) {value v;next n;key k;hash h;
}
4. 确定桶下标
很多操作都需要先确定一个键值对所在的桶下标。
int hash hash(key);
int i indexFor(hash, table.length);
4.1 计算 hash 值
final int hash(Object k) {int h hashSeed;if (0 ! h k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^ k.hashCode();h ^ (h 20) ^ (h 12);return h ^ (h 7) ^ (h 4);
}public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);
}
4.2 取模
令 x 14即 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我们知道位运算的代价比求模运算小的多因此在进行这种计算时用位运算的话能带来更高的性能。确定桶下标的最后一步是将 key 的 hash 值对桶个数取模hash%capacity如果能保证 capacity 为 2 的 n 次方那么就可以将这个操作转换为位运static int indexFor(int h, int length) {return h (length-1);
}
5. 扩容-基本原理
设 HashMap 的 table 长度为 M需要存储的键值对数量为 N如果哈希函数满足均匀性的要求那么每条链表的长度大约为 N/M因此查找的复杂度为 O(N/M)。
为了让查找的成本降低应该使 N/M 尽可能小因此需要保证 M 尽可能大也就是说 table 要尽可能大。HashMap 采用动态扩容来根据当前的 N 值来调整 M 值使得空间效率和时间效率都能得到保证。
和扩容相关的参数主要有capacity、size、threshold 和 load_factor。
参数含义capacitytable 的容量大小默认为 16。需要注意的是 capacity 必须保证为 2 的 n 次方。size键值对数量。thresholdsize 的临界值当 size 大于等于 threshold 就必须进行扩容操作。loadFactor装载因子table 能够使用的比例threshold (int)(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) {EntryK,V e table[bucketIndex];table[bucketIndex] new Entry(hash, key, value, e);if (size threshold)resize(2 * table.length);
}
扩容使用 resize() 实现需要注意的是扩容操作同样需要把 oldTable 的所有键值对重新插入 newTable 中因此这一步是很费时的。
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) {EntryK,V e src[j];if (e ! null) {src[j] null;do {EntryK,V next e.next;int i indexFor(e.hash, newCapacity);e.next newTable[i];newTable[i] e;e next;} while (e ! null);}}
}
6. 与 Hashtable 的比较
Hashtable 使用 synchronized 来进行同步。HashMap 可以插入键为 null 的 Entry。HashMap 的迭代器是 fail-fast 迭代器。HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的
7. 对象作为key存储
重写hashCode()和equals()方法以确保Map能够正确地操作和检索对象。确保对象的不可变性以避免在对象作为键后修改对象的状态。可选地实现Comparable接口以支持对键的排序。设计良好的hashCode()方法以减少哈希冲突的可能性。避免使用可变对象作为键并在必要时及时更新Map中的键。
ConcurrentHashMap
1. 存储结构
static final class HashEntryK,V {final int hash;final K key;volatile V value;volatile HashEntryK,V next;
}
ConcurrentHashMap 和 HashMap 实现上类似最主要的差别是 ConcurrentHashMap 采用了分段锁Segment每个分段锁维护着几个桶HashEntry多个线程可以同时访问不同分段锁上的桶从而使其并发度更高并发度就是 Segment 的个数。
Segment 继承自 ReentrantLock。
static final class SegmentK,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 HashEntryK,V[] table;transient int count;transient int modCount;transient int threshold;final float loadFactor;
}final SegmentK,V[] segments;默认的并发级别为 16也就是说默认创建 16 个 Segment。static final int DEFAULT_CONCURRENCY_LEVEL 16;
2. size 操作
每个 Segment 维护了一个 count 变量来统计该 Segment 中的键值对个数。
transient int count;
在执行 size 操作时需要遍历所有 Segment 然后把 count 累计起来。
ConcurrentHashMap 在执行 size 操作时先尝试不加锁如果连续两次不加锁操作得到的结果一致那么可以认为这个结果是正确的。
尝试次数使用 RETRIES_BEFORE_LOCK 定义该值为 2retries 初始值为 -1因此尝试次数为 3。
如果尝试的次数超过 3 次就需要对每个 Segment 加锁。
static final int RETRIES_BEFORE_LOCK 2;
public int size() {final SegmentK,V[] segments this.segments;int size;boolean overflow; long sum; long last 0L; int retries -1;try {for (;;) {// 超过尝试次数则对每个 Segment 加锁if (retries RETRIES_BEFORE_LOCK) {for (int j 0; j segments.length; j)ensureSegment(j).lock(); }sum 0L;size 0;overflow false;for (int j 0; j segments.length; j) {SegmentK,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;
}
3. JDK 1.8 的改动
JDK 1.7 使用分段锁机制来实现并发更新操作核心类为 Segment它继承自重入锁 ReentrantLock并发度与 Segment 数量相等。
JDK 1.8 使用了 CAS 操作来支持更高的并发度在 CAS 操作失败时使用内置锁 synchronized。
并且 JDK 1.8 的实现也在链表过长时会转换为红黑树。
LinkedHashMap
存储结构
继承自 HashMap因此具有和 HashMap 一样的快速查找特性。
public class LinkedHashMapK,V extends HashMapK,V implements MapK,V
内部维护了一个双向链表用来维护插入顺序或者 LRU 顺序。
transient LinkedHashMap.EntryK,V head;
transient LinkedHashMap.EntryK,V tail;
accessOrder 决定了顺序默认为 false此时维护的是插入顺序。
final boolean accessOrder;
LinkedHashMap 最重要的是以下用于维护顺序的函数它们会在 put、get 等方法中调用。
void afterNodeAccess(NodeK,V p) { }
void afterNodeInsertion(boolean evict) { }
afterNodeAccess()
当一个节点被访问时如果 accessOrder 为 true则会将该节点移到链表尾部。也就是说指定为 LRU 顺序之后在每次访问一个节点时会将这个节点移到链表尾部保证链表尾部是最近访问的节点那么链表首部就是最近最久未使用的节点。
void afterNodeAccess(NodeK,V e) { LinkedHashMap.EntryK,V last;if (accessOrder (last tail) ! e) {LinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,V)e, b p.before, a p.after;p.after null;if (b null)head a;elseb.after a;if (a ! null)a.before b;elselast b;if (last null)head p;else {p.before last;last.after p;}tail p;modCount;}
}
afterNodeInsertion()
在 put 等操作之后执行当 removeEldestEntry() 方法返回 true 时会移除最晚的节点也就是链表首部节点 first。
evict 只有在构建 Map 的时候才为 false在这里为 true。
void afterNodeInsertion(boolean evict) { LinkedHashMap.EntryK,V first;if (evict (first head) ! null removeEldestEntry(first)) {K key first.key;removeNode(hash(key), key, null, false, true);}
}removeEldestEntry() 默认为 false如果需要让它为 true需要继承 LinkedHashMap 并且覆盖这个方法的实现这在实现 LRU 的缓存中特别有用通过移除最近最久未使用的节点从而保证缓存空间足够并且缓存的数据都是热点数据。protected boolean removeEldestEntry(Map.EntryK,V eldest) {return false;
}
