Java容器
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java容器，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含24644字，纯文字阅读大概需要36分钟。
内容图文
本文纯属自己照着cs-notes的知识一个一个自己打字出来的，结合了一点点自己的看法，详细请看原文：
cs-notes Java容器
文章目录
概览
容器主要包括Collection和Map两种，Collection存储着对象的集合，而Map存储着键值对（两个对象）的映射表。
Collection
可以看出，Collection体系主要有三个部分：Set、List和Queue组成
Set
- TreeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作，但是查找效率不如HashSet，HashSet查找的时间复杂度是O（1），TreeSet的红黑树底层使其的查找时间为O（Logn）。
- HashSet：基于hashMap实现，支持快速查找，但不支持有序性操作，并且失序，也就是在插入之后失去了元素的顺序，同时用Iterator遍历的时候其结果是不一定的。
- LinkedHashSet：具有HashSet的查找效率，同时使用内部使用双向链表维护元素的插入顺序。
List
- ArrayList：基于动态数组实现，支持随机访问（数组的特性）
- LinkList：基于双向链表实现，只能顺序访问，不支持随机访问，插入和删除比较块。并且LinkList还可以用作栈’队列和双向队列。
- Vector：和ArrayList类似，但是是线程安全的。（源码要着重看）
Queue
- LinkedList（支持访问有序的队列）：可以用它来实现双向队列
- PriorityQueue：基于堆结构实现的队列，可以实现优先队列（每次取对的最顶元素，用最小堆和最大堆来区分）
Map
Map的键值对存放的，一般无序的，元素只能由一个nullkey的，可以实现随机访问的数据结构。
- TreeMap：基于红黑树实现。
- HashMap：基于Hash表实现
- HashTable：是一种线程安全的HashMap，也就是在多个线程访问时能够保证数据一致。是遗留类不应该去使用它，而是使用ConcurrentHashMap来支持线程安全，并且ConcurrentHashMap效率更高，其内部使用了分段锁来实现。
- LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。
容器中的设计模式：
主要由迭代器模式和适配器模式：
适配器模式：
java.util.Arrays#asList() 可以把数组类型转换为 List 类型。（其内部就是使用了适配器模式）
源码分析：
Arraylist
概览
容器主要包括Collection和Map两种，Collection存储着对象的集合，而Map存储着键值对（两个对象）的映射表。## Collection?可以看出，Collection体系主要有三个部分：Set、List和Queue组成### Set- TreeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作，但是查找效率不如HashSet，HashSet查找的时间复杂度是O（1），TreeSet的红黑树底层使其的查找时间为O（Logn）。- HashSet：基于hashMap实现，支持快速查找，但不支持有序性操作，并且失序，也就是在插入之后失去了元素的顺序，同时用Iterator遍历的时候其结果是不一定的。- LinkedHashSet：具有HashSet的查找效率，同时使用内部使用双向链表维护元素的插入顺序。### List- ArrayList：基于动态数组实现，支持随机访问（数组的特性）- LinkList：基于双向链表实现，只能顺序访问，不支持随机访问，插入和删除比较块。并且LinkList还可以用作栈’队列和双向队列。- Vector：和ArrayList类似，但是是线程安全的。（源码要着重看）### Queue- LinkedList（支持访问有序的队列）：可以用它来实现双向队列- PriorityQueue：基于堆结构实现的队列，可以实现优先队列（每次取对的最顶元素，用最小堆和最大堆来区分）## Map?Map的键值对存放的，一般无序的，元素只能由一个nullkey的，可以实现随机访问的数据结构。- TreeMap：基于红黑树实现。- HashMap：基于Hash表实现- HashTable：是一种线程安全的HashMap，也就是在多个线程访问时能够保证数据一致。是遗留类不应该去使用它，而是使用ConcurrentHashMap来支持线程安全，并且ConcurrentHashMap效率更高，其内部使用了分段锁来实现。- LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。## 容器中的设计模式：主要由迭代器模式和适配器模式：?适配器模式：java.util.Arrays#asList() 可以把数组类型转换为 List 类型。（其内部就是使用了适配器模式）
源码分析：
ArrayList
1.概览：
因为ArrayList是基于数组实现的，所以它支持随机访问，同时其内部实现了RandomAccess接口，标志着其该类支持快速随机访问：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
在其初始化时，若指定的大小小于10或者没有指定大小就将其设置为10
private static final int DEFAULT_CAPACITY = 10;
2.扩容：
在进行添加元素时，会先判断当前空间是否足够ensureCapacityInternal() ，若不足够会进行扩容，扩容的大小大概是原来的1.5倍。
在扩容操作中需要使用数组的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.删除元素
删除某个位置元素后需要调用Sysytem.arraycopy()将index+1位置的元素都复制到index位置上，因此需要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;
}
4.序列化
ArrayList基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，因此序列化的过程不能将其全部序列化，而是只序列化有数据的元素。
保存数组的ElementData用transient修饰，该关键字声明数组默认不会被序列化。
ArrayList实现了writeObject（）和readObject（）来控制只序列化数组中有元素填充的那部分。
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();
}
}
5.Fail-Fast
modCount用来记录ArrayList结构发生变化的次数，结构发生变化值得是添加或者删除元素，对于设置元素不算是结构发生变化。或者调整数组内部的大小。
每次进行序列化或者迭代等操作时都会在操作先后检查modecount是否发生变化，这也是迭代时不能修改的原理所在。
Vector
1.同步
Vector的同步实现与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的内部扩容可以指定每次扩容的大小（在构造函数中放入），如果没有指定每次就会扩容一倍。
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) {
// 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);
}
在扩容时同样使用了cocy函数，因此其代价较高，最好在使用前就扩容好。
3.比较ArrayList
- Vector是同步的，但是由于锁的关系，其效率较低。最好使用ArrayLsit而不是Vector，因为同步操作可以由程序员自己来控制
- Vector每次扩容请求其大小的2倍或者自己指定。ArraList就是1.5倍。
CopyOnWriteArrayList
一个同步的ArrayList，最大的特点就是读写分离。
1.读写分离
写操作在一个复制的数组上进行，读操作还是在原来的数组进行，因此将读跟写进行了分离。互不影响。
写操作需要加锁，读操作不需要加锁，加锁防止并发写入时导致数据丢失。
写操作结束后要把原始数组指向新的数组。（抛弃掉原始数组）
public boolean add(E e) {
final ReentrantLock lock = this.lock; //使用的是ReentrantLock可重用锁
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];
}
2.使用场景
CopyOnWriteArrayList在写操作的同时可以进行读操作，大大提高了读的效率。因此适合读多写少的需求。
但是由于读写分离，写的数据有时候会比较晚更新到读中，因此不适合实时性和敏感性很高的场景。
并且在写的时候需要开新的数组，内存占用很高。
LinkedList：
1.概览
基于双向链表实现，使用Node存储链表节点信息。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
每个节点放入了fist和last指针，因此可以作为双向队列。
transient Node<E> first; //这个也是不能直接序列化，可能也是为了提高效率。
transient Node<E> last;
2.与ArrayList的比较
ArrayList基于动态数组实现，LinkedList基于双向链表实现。ArrayList 和 LinkedList 的区别可以归结为数组和链表的区别：
- 数组支持随机访问，但是插入和删除的代价很高，需要移动大量指针。
- 链表不支持随机访问，但是插入删除只需要改变指针
HashMap
本次源码分析采用JDK1.7。
HashMap的核心就是要如何将元素散列化。
1.存储结构
内部包含了一个Entry类型的数组table。Entry存储着键值对。包含了四个字段（hash值、key、value、next指针），从next指针中我们可以看出Entry实际上是一个链表。即每个数组位置都背当成一个桶，一个桶存放着一个链表（Entry链表）。
HashMap使用拉链法来解决冲突，同一个链表存放hash值和散列桶取模运算结果相同的Entry。
transient Entry[] table;
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();
}
}
2.拉链法的工作原理
HashMap<String, String> map = new HashMap<>();
map.put("K1", "V1");
map.put("K2", "V2");
map.put("K3", "V3");
- 新建一个HashMap，默认大小为16
- 插入 <K1,V1> 键值对，先计算 K1 的 hashCode 为 115，使用除留余数法得到所在的桶下标 115%16=3。
- 插入 <K2,V2> 键值对，先计算 K2 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118%16=6。
- 插入 <K3,V3> 键值对，先计算 K3 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118%16=6，插在 <K2,V2> 前面。
值得注意的是，其采用的是头插法，每次都把元素插入到头部。
查找需要分为两步进行：
- 计算hash值找桶
- 在桶中找链表，很明显可以看出来，查找的长度和链表的长度成正比
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 的键值对，如果存在的话就更新这个键值对的值为 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;
}
HashMap允许插入键为null的键值对，但是由于无法调用null的hashCode方法，因此无法确定其键值对的桶下标，只能强制通过指定一个桶下标来存放。HashMap中用0元素下标来存放null的键值对，这也是HashMap中只能存放一个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;
}
增加元素时使用的是头插法而不是尾插法。
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++;
}
4.确定桶下标
也就是HashMap得核心部分，确定hash值。
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();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
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 = 1 << 4,即x为2得四次方，具有以下性质：
x : 00010000
x-1 : 00001111 //减1时可以拥有更多有效位数。
令一个数y与x-1做与运算，可以取出y位级别表示第4为以上数字，这样子可以让更多得数字参加hash计算，如果只用x(小于16)，只会使得参加的位数过少。
这个性质跟y对x取模是一样得:
y : 10110010
x-1 : 00001111
y&(x-1) : 00000010
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）
为了让查找的成本降低，也就是O（N/M）的复杂度降低，要是M的值尽量增大。
HashMap采用动态扩容来根据当前的N值来调整M值，使得空间和时间的效率都能得到一定保证。
了解扩容机制之前先了解几个参数：
capacity：table的容量，默认为16。需要注意的是capacity的大小必须保证是2的n次方
size：键值对数量。（也就是上面的n的数量）
threshold：size的临界值，也就是size大于threshold时就必须进行扩容操作
loadFactor：装载因子，table能够使用的比例，跟size的临界值有关：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;
从下面添加元素代码可以看出，需要扩容时增加为原来的两倍：
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() 实现，值得注意的是，扩容操作同样需要把oldTable的所有键值对重新插入到newTale中，这步是很费时的
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);
}
}
}
6.扩容-重新计算下标
在进行扩容时，需要把键值对重新计算桶下标，从而放到对应的桶上。
此时其容量大小的2的n次方倍就出现用途了：
HashMap直接使用hash%capacity来确定桶下标。HashMapcapacity为2的n次方这个特点能够极大降低重新计算桶下标操作的复杂度。
假设原数组长度为capacity16，扩容后为32：
则有:
capacity : 00010000
new capacity : 00100000
在上面的情况下，对于一个Key，他的哈希值在第五位的情况：
- 为 0，那么 hash%00010000 = hash%00100000，桶位置和原来一致； //取余就是0改成1，1改成0
- 为 1，hash%00010000 = hash%00100000 + 16，桶位置是原位置 + 16。
7.计算数组容量
HashMap构造函数允许用户传入的容量不是2的n次方，因为他可以自动的转为2的n次方。
转为2的n次方可以使用二进制数的掩码+1来实现，掩码如下：
对于 10010000，它的掩码为 11111111，可以使用以下方法得到：
mask |= mask >> 1 11011000
mask |= mask >> 2 11111110
mask |= mask >> 4 11111111
mask+1 是大于原始数字的最小的 2 的 n 次方。
num 10010000
mask+1 100000000
在HashMap中计算数组容量的代码：
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;
}
8.链表转红黑树
从JDK1.8开始，一个桶存储的链表长度大于等于8时会将链表转为红黑树。
ConcurrentHashMap：
实现并发的hashMap
1.存储结构：
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
}
可以看到，这里最显著的区别就是给value跟next指针加上了volatile关键词。做出了线程安全的处理。
ConcurrentHashMap 和HashMap在实现上类似，最主要的差别就是ConcurrentHashMap 采用了分段锁（Segment），每个分段锁维护着几个桶，多个线程可以同时访问不同分段锁上的桶，使其并发度更高，这里的并发度就是segment的个数。
Segment 继承自 ReentrantLock。（可重入锁）
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;
2.size操作
每个Segment维护了一个count变量来统计键值对的个数。
/**
* 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时先尝试不加锁（乐观），如果两次不加锁得到的结果一致，那么可以认为这个结果是正确的。
尝试次数使用 RETRIES_BEFORE_LOCK 定义，该值为 2，retries 初始值为 -1，因此尝试次数为 3。
如果尝试次数太多，就需要对每个segmen进行加锁。
/**
* 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;
}
- JDK1.8的改动
JDK1.7使用分段锁机制来实现并发更新操作，核心类是segment，继承自重入锁ReentrantLock，并发度与segment数量相等。
在JDK1.8中，换成了CAS操作来支持更高的并发度，在CAS操作失败是使用内置锁synchronized。
并且在JDK1.8实现也是在链表过长时转换为红黑树。
LinkedHashMap
存储结构:
由于是继承自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;
accessOrder决定的是顺序，默认为false，此时维护的是插入顺序。
false表示插入顺序，true表示LRU顺序，把没使用过的放入到链表最后。
final boolean accessOrder;
LinkedHashMap最重要的是以下用来维护顺序的函数，他们会在put、get等方法中调用。
void afterNodeAccess(Node<K,V> p) { } //get后操作，可能是把元素放到末尾
void afterNodeInsertion(boolean evict) { } //put操作，此时会把元素放到链表头
afterNodeAccess()：
当一个节点被访问后，如果accessOrder的值是true，则会将其放到链表尾部，保证链表尾部的是最近访问的节点，链表首部就是最近最久未使用的节点（LRU）。
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;
}
}
afterNodeInsertion():
在put等操作执行之后，当调用removeEldestEntry()方法放回true时会移除最晚的节点，也就是链表首部节点first。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
evict只有在构建Map的时候才为false，在这里为true。
这个参数在默认为false，如果需要让他为true，需要继承LinkedHashMap并且覆盖这个方法的实现，这在实现LRU的缓存中特别有用，通过已出最近最久未使用的点，从而抱枕缓存空间足够并且缓存的数据都是热点数据。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
LRU缓存：
以下是使用LinkedHsahMap实现的一个LRU缓存步骤：
- 先设定最大缓存空间MAX_ENTRIES为N
- 使用LinkedHashMap的构造函数将accessOrder设置为true，开启LRU
- 覆盖removeElderstEntry（）方法，在节点多余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());
}
WeakHashMap
存储结构
WeakHashMap的Entry继承自WeakReference，被WeakHashMap关联的对象在下一次垃圾回收时会被回收。
WeakHashMap主要用来实现缓存，通过使用WeakHashMap来引用缓存对象，由JVM对这部分缓存进行回收。
ConcurrentCache：
Tomcat 中的 ConcurrentCache 使用了 WeakHashMap 来实现缓存功能。
ConcuurentCache使用的时分代缓存：
- 经常使用的对象放入eden（老年区），eden中用ConcurrentHashMap实现，不用担心会被回收
- 不常用的对象放入longterm，longterm使用WeakHashMap实现，垃圾收集器算法一调用就会被回收
- 当调用get（）方法时，会先从eden区回去，如果没有找到再从longterm区读取，这样子也能提高效率。当longtrem获取到时就把对象放入eden中，从而保证经常被访问的节点不被回收。
- 当调用 put() 方法时，如果 eden 的大小超过了 size，那么就将 eden 中的所有对象都放入 longterm 中，利用虚拟机回收掉一部分不经常使用的对象。
public final class ConcurrentCache<K, V> {
private final int size;
private final Map<K, V> eden;
private final Map<K, V> longterm;
public ConcurrentCache(int size) {
this.size = size;
this.eden = new ConcurrentHashMap<>(size);
this.longterm = new WeakHashMap<>(size);
}
public V get(K k) {
V v = this.eden.get(k);
if (v == null) {
v = this.longterm.get(k);
if (v != null)
this.eden.put(k, v);
}
return v;
}
public void put(K k, V v) {
if (this.eden.size() >= size) {
this.longterm.putAll(this.eden);
this.eden.clear();
}
this.eden.put(k, v);
}
}
内容总结
以上是互联网集市为您收集整理的Java容器全部内容，希望文章能够帮你解决Java容器所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。