Java 集合
环境：Java7/Java8
容器介绍
容器，就是可以容纳其他Java对象的对象。*Java Collections Framework(JCF)*为Java开发者提供了通用的容器，其始于JDK 1.2，优点是:
- 降低编程难度
- 提高程序性能
- 提高API间的互操作性
- 降低学习难度
- 降低设计和实现相关API的难度
- 增加程序的重用性
Java容器里只能放对象，对于基本类型(int, long, float, double等)，需要转换成包装类型后(Integer, Long, Float, Double等)才能放到容器里。很多时候装箱和拆箱能够自动完成，虽然会导致额外的性能和空间开销，但简化了设计和编程。
泛型（Generics）
Java容器能够容纳任何类型的对象，这一点表面上是通过泛型机制完成，Java泛型不是什么神奇的东西，只是编译器为我们提供的一个“语法糖”（ java 在编译泛型代码后会执行泛型擦除的动作，即泛型信息在编译为字节码之后就丢失了，实际的类型都当做了 Object 类型来处理，取值时，编译器真正生成的字节码中，还要额外做一个类型转换的操作），泛型本身并不需要Java虚拟机的支持，只需要在编译阶段做一下简单的字符串替换即可。实质上Java的单继承机制才是保证这一特性的根本，因为所有的对象都是Object的子类，容器里只要能够存放Object对象就行了。 事实上，所有容器的内部存放的都是Object对象，泛型机制只是简化了编程，由编译器自动帮我们完成了强制类型转换而已。JDK 1.4以及之前版本不支持泛型，类型转换需要程序员显式完成。
内存管理
Java GC自动包揽了一切，Java程序并不需要处理令人头疼的内存问题，因此JCF并不像C++ STL那样需要专门的空间适配器（alloctor）。 另外，由于Java里对象都在堆上，且对象只能通过引用（reference，跟C中的引用不是同一个概念，可以理解成经过包装后的指针）访问，容器里放的其实是对象的引用而不是对象本身，也就不存在C容器的复制拷贝问题。
迭代器（Iterator）
JCF的迭代器（Iterator）为我们提供了遍历容器中元素的方法。只有容器本身清楚容器里元素的组织方式，因此迭代器只能通过容器本身得到。每个容器都会通过内部类的形式实现自己的迭代器。
Iterator<String> it = list.iterator();//得到迭代器
while(it.hasNext()){
String weekday = it.next();//访问元素
System.out.println(weekday);
}
用for-each写法能很简化迭代器的使用：
for(String weekday : list){//enhanced for statement
System.out.println(weekday);
}
总体框架
大致层次结构：
大致说明：
看上面的框架图，先抓住它的主干，即Collection和Map（两者性质有较大的区别，Collection存一个单独对象，Map存储方式是K-V结构），Map不是Collection的子接口！！
- Collection是一个接口，是高度抽象出来的集合，包含了集合的基本操作和属性。Collection包含了List和Set两大分支：
- List是一个有序的队列，每一个元素都有它的索引，首元素的index是0。List的实现类有LinkedList, ArrayList, Vector（三者都继承抽象类AbstractList）, Stack（基于Vector实现，但JDK1.6后出现Deque，官方就不推荐用Stack，推荐用Deque来实现栈）。
- Set是一个不允许有重复元素的集合。Set的实现类有HastSet和TreeSet（两者都继承抽象类AbstractSet）。HashSet基于HashMap实现；TreeSet基于TreeMap实现。
2、Map是一个映射接口，即key-value键值对。实现类有HashMap，TreeMap，WeakHashMap（三者都继承抽象类AbstractMap），Hashtable（虽然继承于Dictionary，但它实现了Map接口，线程安全，但比较老旧，基本弃用）。
3、再看Iterator。它是遍历集合的工具，我们通常通过Iterator迭代器来遍历集合。Collection的实现类都要实现iterator()函数，返回一个Iterator迭代器对象。ListIterator专门用来遍历List。
4、再看Enumeration，它是JDK 1.0引入的抽象类。作用和Iterator一样，也是遍历集合；但是Enumeration的功能要比Iterator少。在上面的框图中，Enumeration只能在Hashtable, Vector, Stack中使用。
5、最后，看Arrays和Collections。它们分别是操作数组、集合的两个工具类。
ArrayList
ArrayList是动态数组，实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。每个ArrayList都有一个容量（capacity），表示底层数组的实际大小，容器内存储元素的个数（size）不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。
-
ArrayList支持随机访问，也就是可以可以通过index直接访问。
-
ArrayList线程不安全。
底层数据结构
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*
* 存储 ArrayList 元素的数组缓冲区。 ArrayList 的容量就是这个数组缓冲区的长度。当添加第一个元素时，
* 任何具有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都将扩展为 DEFAULT_CAPACITY 。
*/
transient Object[] elementData; // non-private to simplify nested class access 非私有以简化嵌套类访问。
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
-
底层的数据结构就是一个叫 elementData 的 Object[] 数组（所以可使用泛型）。
-
默认容量DEFAULT_CAPACITY=10。
-
EMPTY_ELEMENTDATA（EE）是为了优化创建ArrayList空实例时产生不必要的空数组，使得所有ArrayList空实例都指向同一个空数组。DEFAULTCAPACITY_EMPTY_ELEMENTDATA（DEE）是为了确保无参构成函数创建的实例在添加第一个元素时，会进行扩容，扩容到默认的容量大小10。
/**
* Shared empty array instance used for empty instances.
*
* 用于空实例的共享空数组实例
*/
private static final Object[] EMPTY_ELEMENTDATA = {}; // 纯粹就是一个空数组，用于带参数的构造函数，但参数显式地为0或空集合。包括所有要用到空实例的地方都指向这个空数组。
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*
* 用于默认大小的空实例的共享空数组实例。我们将其与 EMPTY_ELEMENTDATA 区分开来，以了解添加第一个元素时要膨胀多少。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 是为了存东西的，在加入第一个元素之后就会扩容，主要是用于无参构造函数，因为无参就是默认，所以多了个DEFAULT
构造函数
- 无参，创建DEE空数组
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- 带容量参数，就会创建相应大小的数组，若参数为0，创建EE
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
- 集合参数，先把集合转换成数组，再赋给elementData，如果集合长度为0，创建EE
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
自动扩容
每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法**ensureCapacity(int minCapacity)**来实现，最终的扩容方法是grow。在实际添加大量元素前，我们也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。
数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。**当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。**或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。
/**
* Increases the capacity of this ArrayList instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
如有必要，增加此ArrayList实例的容量，以确保它至少可以容纳最小容量参数指定的元素数量。
参数：minCapacity – 所需的最小容量
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
增加容量以确保它至少可以容纳最小容量参数指定的元素数量。
参数：minCapacity – 所需的最小容量
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量约为原容量1.5倍
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
add(), addAll()
这两个方法都是向容器中添加新元素，这可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!! // 剩余空间检查
elementData[size++] = e;
return true;
}
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index); // 检查下标是否符合要求
ensureCapacityInternal(size + 1); // Increments modCount!! // 剩余空间检查
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
add( E e)在末尾添加元素add(int index, E e)需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度O（n）。
- 在末尾添加的
addAll(Collection<? extends E> c)方法 - 从指定位置**开始插入的
addAll(int index, Collection<? extends E> c)方法。
跟add()方法类似，在插入之前也需要进行空间检查，如果需要则自动扩容；如果从指定位置插入，也会存在移动元素的情况。 addAll()的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关。
拼接和复制数组用的是System.arraycopy(a, 0, elementData, index, numNew)，这是一个本地方法。
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
set()
这个简单
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index); // 检查是否越界
E oldValue = elementData(index); // 返回index处的元素
elementData[index] = element; // 替换index处元素
return oldValue; // 返回老的元素
}
get()
这个也简单，因为支持随机访问，所以时间复杂度为O(1)
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
remove()
remove(int index)删除指定位置的元素，返回删除的元素remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程，需要将删除点之后的元素向前移动一个位置。支持传入null，移除null。返回是否删除成功。
需要注意的是为了让GC起作用，必须显式的为最后一个位置赋null值，如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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 //为最后一个位置赋null，清除该位置的引用，让GC起作用
return oldValue;
}
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
跳过边界检查且不返回已删除值的私有删除方法。其实就是把remove(int index)中除了rangeCheck(index)的代码做一层封装，加快移除速度
*/
private void fastRemove(int index) {
modCount++;
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
}
trimToSize()
将底层数组的容量调整为当前列表保存的实际元素的大小。
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
将此ArrayList实例的容量修剪为列表的当前大小。应用程序可以使用此操作来最小化ArrayList实例的存储。
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
indexOf(), lastIndexOf()
indexOf()获取元素的第一次出现的index
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
lastIndexOf()获取元素的最后一次出现的index
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Fail-Fast机制
ArrayList是线程不安全的，所以也采用了快速失败的机制，通过记录modCount参数来实现。当在用迭代器遍历时，若出现并发的修改该容器时，迭代器立刻失败，抛出 ConcurrentModifificationException，不再继续遍历。
Vector
与ArrayList非常相似，但是Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。
LinkedList
LinkedList是双向链表，同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(Stack)。这样看来，LinkedList简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类(它只是个接口)。关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList(当作栈或队列使用时)有着更好的性能。
-
LinkedList不支持随机访问，必须通过顺序访问，也就是链表的访问，通过迭代器从头一个一个往下找，因为这是双向链表，所以可以从头或尾遍历列表（从靠近指定索引的一端），通过下标来get元素的时间复杂度是O（n）。
-
LinkedList线程不安全，解决办法是用Collections.synchronizedList()对其包装:
List list = Collections.synchronizedList(new LinkedList(...));
底层数据结构
双向链表的每个节点用内部类Node表示，通过first和last引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元，当链表为空的时候first和last都指向null。
transient int size = 0;
/**
* 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;
其中Node是私有的内部类:
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
构造函数
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
get()，getFirst(), getLast()
- 通过index获取节点的元素值
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
上面代码中的node(int index)函数有一点小小的trick，因为链表双向的，可以从开始往后找，也可以从结尾往前找，具体朝那个方向找取决于条件index < (size >> 1)，也即是index是靠近前端还是后端。从这里也可以看出，linkedList通过index检索元素的效率没有arrayList高。
- 获取第一个节点的元素值， 和获取最后一个节点的元素值，时间复杂度O(1)
/**
* Returns the first element in this list.
*
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
/**
* Returns the last element in this list.
*
* @return the last element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
removeFirst(), removeLast(), remove(e), remove(index)
removeFirst()删除头节点，注意有显式对头节点赋null，让gc起作用
/**
* Removes and returns the first element from this list.
*
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC // 这两步让gc对该节点起作用
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
removeLast()删除尾节点，跟删除头节点是一样的
/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* Unlinks non-null last node l.
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
remove(e)删除跟指定元素相等的第一个元素，如果没有这个元素，则返回false；判断的依据是equals方法， 如果equals，则直接unlink这个node；由于LinkedList可存放null元素，故也可以删除第一次出现null的元素；同样有help gc的步骤
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null; // help gc
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null; // help gc
}
x.item = null; // help gc
size--;
modCount++;
return element;
}
remove(int index)使用的是下标计数， 只需要判断该index是否有元素即可，如果有则直接unlink这个node。
/**
* Removes the element at the specified position in this list. Shifts any
* subsequent elements to the left (subtracts one from their indices).
* Returns the element that was removed from the list.
*
* @param index the index of the element to be removed
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
add()，addAll()
添加节点需要new一个Node出来
add(E e)，末尾插入元素，因为有last指向链表末尾，在末尾插入元素的花费是常数时间，只需要简单修改几个相关引用即可。
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 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++;
}
add(int index, E element)，在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作，当index==size时，等同于add(E e); 如果不是，则分两步: 1.先根据index找到要插入的位置,即node(index)方法；2.修改引用，完成插入操作
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
- addAll(index, c) 实现方式并不是直接调用add(index,e)来实现，主要是因为效率的问题，另一个是要求fail-fast中modCount只增加1次
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
addAll(Collection<? extends E> c)在末尾添加集合
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the specified
* collection's iterator. The behavior of this operation is undefined if
* the specified collection is modified while the operation is in
* progress. (Note that this will occur if the specified collection is
* this list, and it's nonempty.)
*
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
clear()
删除该链表中所有元素，为了让GC更快可以回收删除的元素，需要将node之间的引用关系赋空
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
get()
将某个位置的元素重新赋值，返回老值
/**
* Replaces the element at the specified position in this list with the
* specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
查询元素操作
indexOf(Object o)查找第一次出现该元素的index, 如果找不到返回-1
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
lastIndexOf(Object o)查找该元素最后一次出现的index, 如果找不到返回-1
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @return the index of the last occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
Queue 方法
LinkedList实现Deque接口，而Deque又继承Queue接口，所以不同的引用类型的LinkedList对象能拥有它们这两个接口各自的方法。
若Queue<Object> que = new LinkedList<>();，则可使用这些方法，同时应该把它看成一个队列，而不是双向链表（虽然底层实现仍然是这样）
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
*/
public E element() {
return getFirst();
}
/**
* Retrieves and removes the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/**
* Retrieves and removes the head (first element) of this list.
*
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
*/
public E remove() {
return removeFirst();
}
/**
* Adds the specified element as the tail (last element) of this list.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Queue#offer})
* @since 1.5
*/
public boolean offer(E e) {
return add(e);
}
在 Java Queue 上 add/offer ,element/peek , remove/poll 中三个方法均为重复方法 , 在选择使用时不免有所疑惑 , 这是简单说明下 :
1. add() 和 offer() 的区别
add()和offer()都是向队列中添加一个元素 . 一些队列有大小限制,因此如果想在已满的队列加入一个新队列, 调用add()方法就会抛出一个unchecked异常, 而调用offer()方法返回 flase . 因此就可以在程序中进行有效的判断 .
2. poll() 和 remove() 的区别
poll()和remove()方法都是从队列中删除第一个元素. 如果队列元素为空 ,调用remove()的行为与 Collection 接口的版本相似会抛出异常 . 但是新的poll()方法会在用空集合调用时只会返回 null . 因此新的方法更适合容易出现异常条件的情况.
3. element() 和 peek() 的区别
element()和peek()用于在队列的头部查询元素. 与remove()方法类似 , 在队列为空时 ,element ()抛出一个异常 , 而peek()返回 null .
Deque 方法
若Queue<Object> que = new LinkedList<>();
其中的push()和pop()方法是实现了栈的效果的
/**
* Inserts the specified element at the front of this list.
*
* @param e the element to insert
* @return {@code true} (as specified by {@link Deque#offerFirst})
* @since 1.6
*/
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
/**
* Inserts the specified element at the end of this list.
*
* @param e the element to insert
* @return {@code true} (as specified by {@link Deque#offerLast})
* @since 1.6
*/
public boolean offerLast(E e) {
addLast(e);
return true;
}
/**
* Retrieves, but does not remove, the first element of this list,
* or returns {@code null} if this list is empty.
*
* @return the first element of this list, or {@code null}
* if this list is empty
* @since 1.6
*/
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* Retrieves, but does not remove, the last element of this list,
* or returns {@code null} if this list is empty.
*
* @return the last element of this list, or {@code null}
* if this list is empty
* @since 1.6
*/
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
/**
* Retrieves and removes the first element of this list,
* or returns {@code null} if this list is empty.
*
* @return the first element of this list, or {@code null} if
* this list is empty
* @since 1.6
*/
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/**
* Retrieves and removes the last element of this list,
* or returns {@code null} if this list is empty.
*
* @return the last element of this list, or {@code null} if
* this list is empty
* @since 1.6
*/
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
/**
* Pushes an element onto the stack represented by this list. In other
* words, inserts the element at the front of this list.
*
* <p>This method is equivalent to {@link #addFirst}.
*
* @param e the element to push
* @since 1.6
*/
public void push(E e) {
addFirst(e);
}
/**
* Pops an element from the stack represented by this list. In other
* words, removes and returns the first element of this list.
*
* <p>This method is equivalent to {@link #removeFirst()}.
*
* @return the element at the front of this list (which is the top
* of the stack represented by this list)
* @throws NoSuchElementException if this list is empty
* @since 1.6
*/
public E pop() {
return removeFirst();
}
/**
* Removes the first occurrence of the specified element in this
* list (when traversing the list from head to tail). If the list
* does not contain the element, it is unchanged.
*
* @param o element to be removed from this list, if present
* @return {@code true} if the list contained the specified element
* @since 1.6
*/
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
/**
* Removes the last occurrence of the specified element in this
* list (when traversing the list from head to tail). If the list
* does not contain the element, it is unchanged.
*
* @param o element to be removed from this list, if present
* @return {@code true} if the list contained the specified element
* @since 1.6
*/
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
Stack & Queue
Java里有一个叫做Stack的类，却没有叫做Queue的类(它是个接口名字)。当需要使用栈时，Java已不推荐使用Stack，而是推荐使用更高效的ArrayDeque；既然Queue只是一个接口，当需要使用队列时也就首选ArrayDeque了(次选是LinkedList)。
Queue
Queue接口继承自Collection接口，除了最基本的Collection的方法之外，它还支持额外的insertion, extraction和inspection操作。这里有两组格式，共6个方法，一组是抛出异常的实现；另外一组是返回值的实现(没有则返回null)。
| Throws exception | Returns special value | |
|---|---|---|
| Insert | add(e) | offer(e) |
| Remove | remove() | poll() |
| Examine | element() | peek() |
Deque
Deque是"double ended queue", 双向队列，英文读作"deck". Deque 继承自Queue接口，除了支持Queue的方法之外，还支持insert, remove和examine操作，由于Deque是双向的，所以可以对队列的头和尾都进行操作，它同时也支持两组格式，一组是抛出异常的实现；另外一组是返回值的实现(没有则返回null)。共12个方法如下:
| First Element - Head | Last Element - Tail | |||
|---|---|---|---|---|
| Throws exception | Special value | Throws exception | Special value | |
| Insert | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| Remove | removeFirst() | pollFirst() | removeLast() | pollLast() |
| Examine | getFirst() | peekFirst() | getLast() | peekLast() |
当把Deque当做FIFO的queue来使用时，元素是从deque的尾部添加，从头部进行删除的； 所以deque的部分方法是和queue是等同的。具体如下:
| Queue Method | Equivalent Deque Method |
|---|---|
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
Deque既可以当作栈使用，也可以当作队列使用。下表列出了Deque与Queue相对应的接口:
| Queue Method | Equivalent Deque Method | 说明 |
|---|---|---|
add(e) |
addLast(e) |
向队尾插入元素，失败则抛出异常 |
offer(e) |
offerLast(e) |
向队尾插入元素，失败则返回false |
remove() |
removeFirst() |
获取并删除队首元素，失败则抛出异常 |
poll() |
pollFirst() |
获取并删除队首元素，失败则返回null |
element() |
getFirst() |
获取但不删除队首元素，失败则抛出异常 |
peek() |
peekFirst() |
获取但不删除队首元素，失败则返回null |
下表列出了Deque与Stack对应的接口:
| Stack Method | Equivalent Deque Method | 说明 |
|---|---|---|
push(e) |
addFirst(e) |
向栈顶插入元素，失败则抛出异常 |
| 无 | offerFirst(e) |
向栈顶插入元素，失败则返回false |
pop() |
removeFirst() |
获取并删除栈顶元素，失败则抛出异常 |
| 无 | pollFirst() |
获取并删除栈顶元素，失败则返回null |
peek() |
getFirst() |
获取但不删除栈顶元素，失败则抛出异常 |
| 无 | peekFirst() |
获取但不删除栈顶元素，失败则返回null |
上面两个表共定义了Deque的12个接口。添加，删除，取值都有两套接口，它们功能相同，区别是对失败情况的处理不同。一套接口遇到失败就会抛出异常，另一套遇到失败会返回特殊值(false或null)。除非某种实现对容量有限制，大多数情况下，添加操作是不会失败的。虽然Deque的接口有12个之多，但无非就是对容器的两端进行操作，或添加，或删除，或查看。明白了这一点讲解起来就会非常简单。
ArrayDeque
ArrayDeque和LinkedList是Deque的两个通用实现，由于官方更推荐使用ArrayDeque用作栈和队列。
从名字可以看出ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组(circular array)，也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是非线程安全的(not thread-safe)，当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入null元素。
上图中我们看到，head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位。因为是循环数组，所以**head不一定总等于0，tail也不一定总是比head大**。
ArrayDeque方法剖析
构造方法
- 无参，默认是容量大小为16的数组
/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold 16 elements.
*/
public ArrayDeque() {
elements = new Object[16];
}
- 指定容量大小，最小的初始容量大小MIN_INITIAL_CAPACITY是8，如果参数比它小就是用8，如果比它大，就会寻找最合适的2的指数倍的容量来容纳元素。所以ArrayDeque的容量至少是8，而且必须是2的指数倍。
/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold the specified number of elements.
*
* @param numElements lower bound on initial capacity of the deque
*/
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
/**
* Allocates empty array to hold the given number of elements.
*
* @param numElements the number of elements to hold
*/
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
/**
* The minimum capacity that we'll use for a newly created deque.
* Must be a power of 2.
*/
private static final int MIN_INITIAL_CAPACITY = 8;
private static int calculateSize(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
return initialCapacity;
}
- 集合参数
/**
* Constructs a deque containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator. (The first element returned by the collection's
* iterator becomes the first element, or <i>front</i> of the
* deque.)
*
* @param c the collection whose elements are to be placed into the deque
* @throws NullPointerException if the specified collection is null
*/
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
addFirst()
在head的前面插入元素，在空间足够且下标没有越界的情况下，只需要将elements[--head] = e即可。
实际需要考虑:
- 空间是否够用
- 下标是否越界
上图中，如果head为0之后接着调用addFirst()，虽然空余空间还够用，但head为-1，下标越界了。下列代码很好的解决了这个问题。
//addFirst(E e)
public void addFirst(E e) {
if (e == null)//不允许放入null
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;//2.下标是否越界 //插入元素
if (head == tail)//1.空间是否够用，当head和tail缠绕成相等时，空间就不够了
doubleCapacity();//扩容
}
空间问题是在插入之后解决的，因为tail总是指向下一个可插入的空位，也就意味着elements数组至少有一个空位，所以插入元素的时候不用考虑空间问题。
下标越界的处理解决起来非常简单，head = (head - 1) & (elements.length - 1)就可以了，这段代码相当于head = (head - 1) % (elements.length - 1)取余，同时解决了**head为负值的情况。因为elements.length必需是2的指数倍，elements - 1就是二进制低位全1，跟head - 1相与之后，head - 1的高位全被抹掉，就起到了取余**的作用，如果head - 1为负数(其实只可能是-1)，则相当于对其取相对于elements.length的补码。
下面再说说扩容函数doubleCapacity()，其逻辑是申请一个是原数组两倍大小的新数组，然后将原数组复制过去。过程如下图所示:
图中我们看到，复制分两次进行，第一次复制head右边的元素，第二次复制head左边的元素。
//doubleCapacity()
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // head右边元素的个数
int newCapacity = n << 1;//原空间的2倍
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);//复制右半部分，对应上图中绿色部分
System.arraycopy(elements, 0, a, r, p);//复制左半部分，对应上图中灰色部分
elements = (E[])a;
head = 0;
tail = n;
}
addLast()
addLast(E e)的作用是在Deque的尾端插入元素，也就是在tail的位置插入元素，由于tail总是指向下一个可以插入的空位，因此只需要elements[tail] = e;即可。插入完成后再检查空间，如果空间已经用光，则调用doubleCapacity()进行扩容。
public void addLast(E e) {
if (e == null)//不允许放入null
throw new NullPointerException();
elements[tail] = e;//赋值
if ( (tail = (tail + 1) & (elements.length - 1)) == head)//下标越界处理
doubleCapacity();//扩容
}
下标越界处理方式addFirt()中已经讲过，不再赘述。
pollFirst()
删除并返回head位置处的元素。如果容器不空，只需要直接返回elements[head]即可，当然还需要处理下标的问题。由于ArrayDeque中不允许放入null，当elements[head] == null时，意味着容器为空。
public E pollFirst() {
int h = head;
E result = elements[head];
if (result == null)//null值意味着deque为空
return null;
elements[h] = null;//let GC work
head = (head + 1) & (elements.length - 1);//下标越界处理
return result;
}
pollLast()
删除并返回tail位置前面的那个元素。
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);//tail的上一个位置是最后一个元素
E result = elements[t];
if (result == null)//null值意味着deque为空
return null;
elements[t] = null;//let GC work
tail = t;
return result;
}
peekFirst()
返回但不删除head位置处的元素，直接返回elements[head]即可。
public E peekFirst() {
return elements[head]; // elements[head] is null if deque empty
}
peekLast()
返回但不删除tail位置前面的那个元素。
public E peekLast() {
return elements[(tail - 1) & (elements.length - 1)];
}
PriorityQueue
PriorityQueue，即优先队列。java的优先队列的作用是能保证每次取出的元素都是队列中最小的。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器(Comparator)。
Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树(complete binary tree)实现的小顶堆(任意一个非叶子节点的权值，都不大于其左右子节点的权值)，也就意味着可以通过数组来作为PriorityQueue的底层实现。
上图中我们给每个元素按照层序遍历的方式进行了编号，如果你足够细心，会发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系:
leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2
通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。
PriorityQueue的peek()和element()操作是O(1)，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是O(logN)。
该数组默认大小为11。
方法剖析
add()和offer()
add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。对于PriorityQueue这两个方法其实没什么差别。
新加入的元素可能会破坏小顶堆的性质，因此需要进行必要的调整。
//offer(E e)
public boolean offer(E e) {
if (e == null)//不允许放入null元素
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);//自动扩容
size = i + 1;
if (i == 0)//队列原来为空，这是插入的第一个元素
queue[0] = e;
else
siftUp(i, e);//调整
return true;
}
上述代码中，扩容函数grow()类似于ArrayList里的grow()函数，就是再申请一个更大的数组，并将原数组的元素复制过去，这里不再赘述。需要注意的是siftUp(int k, E x)方法，该方法用于插入元素x并维持堆的特性。
//siftUp()
private void siftUp(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)//调用比较器的比较方法
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
新加入的元素x可能会破坏小顶堆的性质，因此需要进行调整。调整的过程为 : 从指定位置k开始，将x逐层与当前点的parent进行比较并交换，直到满足x >= queue[parent]为止。注意这里的比较可以是元素的自然顺序，也可以是依靠比较器的顺序。
element()和peek()
element()和peek()的语义完全相同，都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者唯一的区别是当方法失败时前者抛出异常，后者返回null。根据小顶堆的性质，堆顶那个元素就是全局最小的那个；由于堆用数组表示，根据下标关系，0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可。
代码也就非常简洁:
//peek()
public E peek() {
if (size == 0)
return null;
return (E) queue[0];//0下标处的那个元素就是最小的那个
}
remove()和poll()
remove()和poll()方法的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null。由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。
代码如下:
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];//0下标处的那个元素就是最小的那个
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);//调整
return result;
}
上述代码首先记录0下标处的元素，并用最后一个元素替换0下标位置的元素，之后调用siftDown()方法对堆进行调整，最后返回原来0下标处的那个元素(也就是最小的那个元素)。重点是siftDown(int k, E x)方法，该方法的作用是从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任何一个为止。
//siftDown()
private void siftDown(int k, E x) {
int half = size >>> 1;
while (k < half) {
//首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
int child = (k << 1) + 1;//leftNo = parentNo*2+1
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;//然后用c取代原来的值
k = child;
}
queue[k] = x;
}
remove(Object o)
remove(Object o)方法用于删除队列中跟o相等的某一个元素(如果有多个相等，只删除一个)，该方法不是Queue接口内的方法，而是Collection接口的方法。由于删除操作会改变队列结构，所以要进行调整；又由于删除元素的位置可能是任意的，所以调整过程比其它函数稍加繁琐。具体来说，remove(Object o)可以分为2种情况:
- 删除的是最后一个元素。直接删除即可，不需要调整。
- 删除的不是最后一个元素，从删除点开始以最后一个元素为参照调用一次
siftDown()即可。此处不再赘述。
具体代码如下:
/**
* Removes a single instance of the specified element from this queue,
* if it is present. More formally, removes an element {@code e} such
* that {@code o.equals(e)}, if this queue contains one or more such
* elements. Returns {@code true} if and only if this queue contained
* the specified element (or equivalently, if this queue changed as a
* result of the call).
*
* @param o element to be removed from this queue, if present
* @return {@code true} if this queue changed as a result of the call
*/
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
// 通过遍历数组的方式找到第一个满足o.equals(queue[i])元素的下标
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}
/**
* Removes the ith element from queue.
*
* Normally this method leaves the elements at up to i-1,
* inclusive, untouched. Under these circumstances, it returns
* null. Occasionally, in order to maintain the heap invariant,
* it must swap a later element of the list with one earlier than
* i. Under these circumstances, this method returns the element
* that was previously at the end of the list and is now at some
* position before i. This fact is used by iterator.remove so as to
* avoid missing traversing elements.
*/
@SuppressWarnings("unchecked")
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element //情况1
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved); //情况2
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
Java7 HashMap
概述
之所以把HashSet和HashMap放在一起讲解，是因为二者在Java里有着相同的实现，前者仅仅是对后者做了一层包装，也就是说HashSet里面有一个HashMap(适配器模式)。
-
HashMap实现了Map接口，即允许放入
key为null的元素，也允许插入value为null的元素。 -
除该类未实现同步外，其余跟
Hashtable（基本弃用）大致相同。 -
跟TreeMap不同，HashMap不保证元素顺序。
-
根据对哈希冲突的处理方式不同，哈希表有两种实现方式
- 一种是开放地址方式(Open addressing)
- 另一种是冲突链表方式(Separate chaining with linked lists)。Java7 HashMap采用的是冲突链表方式。
如果选择合适的哈希函数，put()和get()时间复杂度为O(1)。但在对HashMap进行遍历时，需要遍历整个table以及后面跟的冲突链表。因此对于迭代比较频繁的场景，不宜将HashMap的初始大小设的过大。
有两个参数可以影响HashMap的性能:
- 初始容量(inital capacity)，默认为16，且必须为2的幂。
- 负载系数(load factor)，默认0.75。
初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希，容量扩大为原来的两倍。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。
将对象放入到HashMap或HashSet中时，有两个方法需要特别关心: hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到HashMap或HashSet中，需要**@Override** hashCode()和equals()方法。
get()
get(Object key)方法根据指定的key值返回对应的value，该方法调用了getEntry(Object key)得到相应的entry，然后返回entry.getValue()。因此getEntry()是算法的核心，其思想是首先通过hash()函数得到对应bucket的下标，然后依次遍历冲突链表，通过key.equals(k)方法来判断是否是要找的那个entry。
上图中hash(k)&(table.length-1)等价于hash(k)%table.length，原因是HashMap要求table.length必须是2的指数，因此table.length-1就是二进制低位全是1，跟hash(k)相与会将哈希值的高位全抹掉，剩下的就是余数了。
//getEntry()方法
final Entry<K,V> getEntry(Object key) {
......
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[hash&(table.length-1)];//hash值取余求得冲突链表
e != null; e = e.next) {//依次遍历冲突链表中的每个entry
Object k;
//依据equals()方法判断是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
put()
put(K key, V value)方法是将指定的key, value对添加到map里。具体步骤：
-
该方法首先会对
map用类似getEntry()的方式做一次查找，看是否包含该entry，如果已经包含则直接返回。 -
如果没有找到，则会通过
addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry，java7插入方式为头插法。
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
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;
}
//addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//entry数量超过阈值，自动扩容（容量扩大为原来的两倍），
hash = (null != key) ? hash(key) : 0; // 并rehash
bucketIndex = hash & (table.length-1);//hash%table.length，更新后用新的hash算bucketindex
}
//在冲突链表头部插入新的entry
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
// 若元素数量超过阈值，需要扩容至原来的两倍
void resize(int newCapacity) {
// 获取旧的 table 数组
Entry[] oldTable = table;
// 获取旧的数组的长度
int oldCapacity = oldTable.length;
// 极端情况，如果旧的长度已经是最大容量
if (oldCapacity == MAXIMUM_CAPACITY) {
// 直接等于最大容量
threshold = Integer.MAX_VALUE;
return;
}
// 1.初始化一个新的 Entry 数组，传入的参数是旧的数组的两倍
Entry[] newTable = new Entry[newCapacity];
// 2.将键值对转移到新的 Entry 数组
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 3.将新的数组赋值给旧的数组
table = newTable;
// 4.重新计算阀值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 数据转移函数
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历哈希表 table
for (Entry<K,V> e : table) {
while(null != e) {
// next 用来保存头节点的下一个节点
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 计算在元素在新的哈希表中的位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
remove()
remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry，然后删除该entry(修改链表的相应引用)。查找过程跟getEntry()过程类似。
//removeEntryForKey()
final Entry<K,V> removeEntryForKey(Object key) {
......
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);//hash&(table.length-1)
Entry<K,V> prev = table[i];//得到冲突链表
Entry<K,V> e = prev;
while (e != null) {//遍历冲突链表
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {//找到要删除的entry
modCount++; size--;
if (prev == e) table[i] = next;//删除的是冲突链表的第一个entry
else prev.next = next;
return e;
}
prev = e; e = next;
}
return e;
}
Java8 HashMap
Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。
根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。
为了降低这部分的开销，在 Java8 中，当链表中的元素达到 8 个（即大于7个）时，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。当红黑树的节点减少到6个（即小于7个）时，会将红黑树转换为链表。这个7就是为了来个缓冲，防止临界太小导致频繁的转换结构。
来一张图简单示意一下吧：
注意，上图是示意图，主要是描述结构，不会达到这个状态的，因为这么多数据的时候早就扩容了。
下面，我们还是用代码来介绍吧，个人感觉，Java8 的源码可读性要差一些，不过精简一些。
Java7 中使用 Entry 来代表每个 HashMap 中的数据节点，Java8 中使用 Node，基本没有区别，都是 key，value，hash 和 next 这四个属性，不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。
我们根据数组元素中，第一个节点数据类型是 Node 还是 TreeNode 来判断该位置下是链表还是红黑树的。
put 过程分析
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 第四个参数 onlyIfAbsent 如果是 true，那么只有在不存在该 key 时才会进行 put 操作
// 第五个参数 evict 我们这里不关心
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 第一次 put 值的时候，会触发下面的 resize()，类似 java7 的第一次 put 也要初始化数组长度
// 第一次 resize 和后续的扩容有些不一样，因为这次是数组从 null 初始化到默认的 16 或自定义的初始容量
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 找到具体的数组下标，如果此位置没有值，那么直接初始化一下 Node 并放置在这个位置就可以了
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {// 数组该位置有数据
Node<K,V> e; K k;
// 首先，判断该位置的第一个数据和我们要插入的数据的key 是不是"相等"，如果是，取出这个节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果该节点是代表红黑树的节点，调用红黑树的插值方法，本文不展开说红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 到这里，说明数组该位置上是一个链表
for (int binCount = 0; ; ++binCount) {
// 插入到链表的最后面(Java7 是插入到链表的最前面)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD 为 8，所以，如果新插入的值是链表中的第 8 个
// 会触发下面的 treeifyBin，也就是将链表转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果在该链表中找到了"相等"的 key(== 或 equals)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 此时 break，那么 e 为链表中[与要插入的新值的 key "相等"]的 node
break;
p = e;
}
}
// e!=null 说明存在旧值的key与要插入的key"相等"
// 对于我们分析的put操作，下面这个 if 其实就是进行 "值覆盖"，然后返回旧值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果 HashMap 由于新插入这个值导致 size 已经超过了阈值，需要进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Java8和 Java7 稍微有点不一样的地方就是:
-
Java7 是先扩容后插入新值的，Java8 先插值再扩容。
-
Java7插入方法为头插法，Java8为尾插法。为什么要变成尾插法？
- 在并发情况下两个线程都来插入，都造成了扩容，1.7在数据转移transfer时，头插法会改变原链中元素原本的顺序，会出现链表成环的情况；而1.8则采用将原链平分成高分位和低分位链，让它们分别转移至上半数组和下半数组，尾插法能保持原本的顺序，不会出现链表成环。可以说1.8是对1.7的优化。
- 这并不是说1.8的hashmap就是线程安全的，它仅仅解决1.7的链表成环问题，但在读写并发时还是不安全的，put操作也会使前一个key被后一个key覆盖；而且由于有扩容机制存在，会出现A线程进行扩容后，B线程执行get方法出现失误的情况。需要用concurrentHashmap。
-
1.7扩容是整条链迁移过来，需要rehash；1.8则分成两链，不需要要rehash。
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // MIN_TREEIFY_CAPACITY = 64
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
还有需要注意的是，将链表转换成红黑树(也就是上面的treeifyBin)前会判断是否真的需要转换成树，如果当前数组的长度小于 64，那么会选择进行数组扩容，而不是转换为红黑树。
数组扩容
resize() 方法用于初始化数组或数组扩容，扩容后容量为原来的 2 倍，并进行数据迁移。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 对应数组扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 将数组大小扩大一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 将阈值扩大一倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 对应使用 new HashMap(int initialCapacity) 初始化后，第一次 put 的时候
newCap = oldThr;
else {// 对应使用 new HashMap() 初始化后，第一次 put 的时候
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 用新的数组大小初始化新的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 如果是初始化数组，到这里就结束了，返回 newTab 即可
// resize()方法内就包括了数据转移，往下就是数据转移部分
if (oldTab != null) {
// 开始遍历原数组，进行数据迁移。
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果该数组位置上只有单个元素，那就简单了，简单迁移这个元素就可以了
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是红黑树，具体我们就不展开了
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 这块是处理链表的情况，
// 需要将此链表拆成两个链表，放到新的数组中，并且保留原来的先后顺序
// loHead、loTail 对应一条链表，hiHead、hiTail 对应另一条链表，代码还是比较简单的
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
// 第一条链表
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 第二条链表的新的位置是 j + oldCap，这个很好理解
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
get 过程分析
相对于 put 来说，get 真的太简单了。
-
计算 key 的 hash 值，根据 hash 值找到对应数组下标: hash & (length-1)
-
判断数组该位置处的元素是否刚好就是我们要找的，如果不是，走第三步
-
判断该元素类型是否是 TreeNode，如果是，用红黑树的方法取数据，如果不是，走第四步
-
遍历链表，直到找到相等(==或equals)的 key
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判断第一个节点是不是就是需要的
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 判断是否是红黑树
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 链表遍历
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
HashSet
前面已经说过HashSet是对HashMap的简单包装，存储思想就是entry的key存具体要存的对象，而key就用同一个空Object对象“占位置”，对HashSet的函数调用都会转换成合适的HashMap方法，因此HashSet的实现非常简单，只有不到300行代码。这里不再赘述。
//HashSet是对HashMap的简单包装
public class HashSet<E>
{
......
private transient HashMap<E,Object> map;//HashSet里面有一个HashMap
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
......
public boolean add(E e) {//简单的方法转换
return map.put(e, PRESENT)==null;
}
......
}
TreeMap
之所以把TreeSet和TreeMap放在一起讲解，是因为二者在Java里有着相同的实现，前者仅仅是对后者做了一层包装，也就是说TreeSet里面有一个TreeMap(适配器模式)。
Java TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序，key大小的评判可以通过其本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器(Comparator)。
**TreeMap底层通过红黑树(Red-Black tree)实现，每一个key-value节点作为红黑树的一个节点。**意味着containsKey(), get(), put(), remove()都有着log(n)的时间复杂度。其具体算法实现参照《算法导论》。
出于性能原因，TreeMap是非同步的，线程不安全，如果需要在多线程环境使用，需要程序员手动同步；或者通过如下方式将TreeMap包装成(wrapped)同步的:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍。具体来说，红黑树是满足如下条件的二叉查找树(binary search tree):
- 每个节点要么是红色，要么是黑色。
- 根节点必须是黑色
- 红色节点不能连续(也即是，红色节点的孩子和父亲都不能是红色)。
- 对于每个节点，从该点至
null(树尾端)的任何路径，都含有相同个数的黑色节点。
在树的结构发生改变时(插入或者删除操作)，往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的约束条件。
红黑树预备知识
关于红黑树详细的讲解看https://aobing.blog.csdn.net/article/details/109503539这篇文章讲得比较好。
前文说到当查找树的结构发生改变时，红黑树的约束条件可能被破坏，需要通过调整使得查找树重新满足红黑树的约束条件。调整可以分为两类: 一类是颜色调整，即改变某个节点的颜色；另一类是结构调整，集改变检索树的结构关系。结构调整过程包含两个基本操作 :
- 左旋(Rotate Left)
- 右旋(RotateRight)
左旋
左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。
TreeMap中左旋代码如下:
//Rotate Left
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
右旋
右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。
TreeMap中右旋代码如下:
//Rotate Right
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
寻找节点后继
对于一棵二叉查找树，给定节点t，其后继(树中比t大的最小的那个元素)可以通过如下方式找到:
-
t的右子树不空，则t的后继是其右子树中最小的那个元素。
-
t的右孩子为空，则t的后继是其第一个向左走的祖先（向左走是对于祖先而言，例如下面的35向左走是18）。
后继节点在红黑树的删除操作中将会用到。
TreeMap中寻找节点后继的代码如下:
// 寻找节点后继函数successor()
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {// 1. t的右子树不空，则t的后继是其右子树中最小的那个元素
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {// 2. t的右孩子为空，则t的后继是其第一个向左走的祖先
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
方法剖析
get()
get(Object key)方法根据指定的key值返回对应的value，该方法调用了getEntry(Object key)得到相应的entry，然后返回entry.value。因此getEntry()是算法的核心，其思想是根据key的自然顺序(或者比较器顺序)对二叉查找树进行查找，直到找到满足**k.compareTo(p.key) == 0**的entry。
具体代码如下:
//getEntry()方法
final Entry<K,V> getEntry(Object key) {
......
if (key == null)//不允许key值为null
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;//使用元素的自然顺序
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)//向左找
p = p.left;
else if (cmp > 0)//向右找
p = p.right;
else
return p;
}
return null;
}
put()
put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于getEntry()方法；如果没有找到则会在红黑树中插入新的entry，如果插入之后破坏了红黑树的约束条件，还需要进行调整(旋转，改变某些节点的颜色)。
public V put(K key, V value) {
......
int cmp;
Entry<K,V> parent;
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;//使用元素的自然顺序
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0) t = t.left;//向左找
else if (cmp > 0) t = t.right;//向右找
else return t.setValue(value);
} while (t != null);
Entry<K,V> e = new Entry<>(key, value, parent);//创建并插入新的entry
if (cmp < 0) parent.left = e;
else parent.right = e;
fixAfterInsertion(e);//调整
size++;
return null;
}
上述代码的插入部分并不难理解: 首先在红黑树上找到合适的位置，然后创建新的entry并插入(当然，新插入的节点一定是树的叶子)。难点是调整函数fixAfterInsertion()，前面已经说过，调整往往需要1.改变某些节点的颜色，2.对某些节点进行旋转。
调整函数fixAfterInsertion()的具体代码如下，其中用到了上文中提到的rotateLeft()和rotateRight()函数。通过代码我们能够看到，情况2其实是落在情况3内的。情况4～情况6跟前三种情况是对称的，因此图解中并没有画出后三种情况，读者可以参考代码自行理解。
//红黑树调整函数fixAfterInsertion()
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK); // 情况1
setColor(y, BLACK); // 情况1
setColor(parentOf(parentOf(x)), RED); // 情况1
x = parentOf(parentOf(x)); // 情况1
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x); // 情况2
rotateLeft(x); // 情况2
}
setColor(parentOf(x), BLACK); // 情况3
setColor(parentOf(parentOf(x)), RED); // 情况3
rotateRight(parentOf(parentOf(x))); // 情况3
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK); // 情况4
setColor(y, BLACK); // 情况4
setColor(parentOf(parentOf(x)), RED); // 情况4
x = parentOf(parentOf(x)); // 情况4
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x); // 情况5
rotateRight(x); // 情况5
}
setColor(parentOf(x), BLACK); // 情况6
setColor(parentOf(parentOf(x)), RED); // 情况6
rotateLeft(parentOf(parentOf(x))); // 情况6
}
}
}
root.color = BLACK;
}
remove()
remove(Object key)的作用是删除key值对应的entry，该方法首先通过上文中提到的getEntry(Object key)方法找到key值对应的entry，然后调用deleteEntry(Entry<K,V> entry)删除对应的entry。由于删除操作会改变红黑树的结构，有可能破坏红黑树的约束条件，因此有可能要进行调整。
getEntry()函数前面已经讲解过，这里重点放deleteEntry()上，该函数删除指定的entry并在红黑树的约束被破坏时进行调用fixAfterDeletion(Entry<K,V> x)进行调整。
由于红黑树是一棵增强版的二叉查找树，红黑树的删除操作跟普通二叉查找树的删除操作也就非常相似，唯一的区别是红黑树在节点删除之后可能需要进行调整。现在考虑一棵普通二叉查找树的删除过程，可以简单分为两种情况:
-
删除点p的左右子树都为空，或者只有一棵子树非空。
-
删除点p的左右子树都非空。
对于上述情况1，处理起来比较简单，直接将p删除(左右子树都为空时)，或者用非空子树替代p(只有一棵子树非空时)；对于情况2，可以用p的后继s(树中大于x的最小的那个元素)代替p，然后使用情况1删除s(此时s一定满足情况1.可以画画看)。
基于以上逻辑，红黑树的节点删除函数deleteEntry()代码如下:
// 红黑树entry删除函数deleteEntry()
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
if (p.left != null && p.right != null) {// 2. 删除点p的左右子树都非空。
Entry<K,V> s = successor(p);// 后继
p.key = s.key;
p.value = s.value;
p = s;
}
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {// 1. 删除点p只有一棵子树非空。
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
if (p.color == BLACK)
fixAfterDeletion(replacement);// 调整
} else if (p.parent == null) {
root = null;
} else { // 1. 删除点p的左右子树都为空
if (p.color == BLACK)
fixAfterDeletion(p);// 调整
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
上述代码中占据大量代码行的，是用来修改父子节点间引用关系的代码，其逻辑并不难理解。下面着重讲解删除后调整函数fixAfterDeletion()。首先请思考一下，删除了哪些点才会导致调整？只有删除点是BLACK的时候，才会触发调整函数，因为删除RED节点不会破坏红黑树的任何约束，而删除BLACK节点会破坏规则4。
跟上文中讲过的fixAfterInsertion()函数一样，这里也要分成若干种情况。记住，无论有多少情况，具体的调整操作只有两种: 1.改变某些节点的颜色，2.对某些节点进行旋转。
上述图解的总体思想是: 将情况1首先转换成情况2，或者转换成情况3和情况4。当然，该图解并不意味着调整过程一定是从情况1开始。通过后续代码我们还会发现几个有趣的规则: a).如果是由情况1之后紧接着进入的情况2，那么情况2之后一定会退出循环(因为x为红色)；b).一旦进入情况3和情况4，一定会退出循环(因为x为root)。
删除后调整函数fixAfterDeletion()的具体代码如下，其中用到了上文中提到的rotateLeft()和rotateRight()函数。通过代码我们能够看到，情况3其实是落在情况4内的。情况5～情况8跟前四种情况是对称的，因此图解中并没有画出后四种情况，读者可以参考代码自行理解。
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry<K,V> sib = rightOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK); // 情况1
setColor(parentOf(x), RED); // 情况1
rotateLeft(parentOf(x)); // 情况1
sib = rightOf(parentOf(x)); // 情况1
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED); // 情况2
x = parentOf(x); // 情况2
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK); // 情况3
setColor(sib, RED); // 情况3
rotateRight(sib); // 情况3
sib = rightOf(parentOf(x)); // 情况3
}
setColor(sib, colorOf(parentOf(x))); // 情况4
setColor(parentOf(x), BLACK); // 情况4
setColor(rightOf(sib), BLACK); // 情况4
rotateLeft(parentOf(x)); // 情况4
x = root; // 情况4
}
} else { // 跟前四种情况对称
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK); // 情况5
setColor(parentOf(x), RED); // 情况5
rotateRight(parentOf(x)); // 情况5
sib = leftOf(parentOf(x)); // 情况5
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED); // 情况6
x = parentOf(x); // 情况6
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK); // 情况7
setColor(sib, RED); // 情况7
rotateLeft(sib); // 情况7
sib = leftOf(parentOf(x)); // 情况7
}
setColor(sib, colorOf(parentOf(x))); // 情况8
setColor(parentOf(x), BLACK); // 情况8
setColor(leftOf(sib), BLACK); // 情况8
rotateRight(parentOf(x)); // 情况8
x = root; // 情况8
}
}
}
setColor(x, BLACK);
}
TreeSet
前面已经说过TreeSet是对TreeMap的简单包装，对TreeSet的函数调用都会转换成合适的TreeMap方法，因此TreeSet的实现非常简单。这里不再赘述。
// TreeSet是对TreeMap的简单包装
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
......
private transient NavigableMap<E,Object> m;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public TreeSet() {
this.m = new TreeMap<E,Object>();// TreeSet里面有一个TreeMap
}
......
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
......
}
LinkedHashMap
LinkedHashSet和LinkedHashMap在Java里也有着相同的实现，前者仅仅是对后者做了一层包装，也就是说LinkedHashSet里面有一个LinkedHashMap(适配器模式)。
LinkedHashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素。从名字上可以看出该容器是linked list和HashMap的混合体，也就是说它同时满足HashMap和linked list的某些特性。可将LinkedHashMap看作采用linked list增强的HashMap。
事实上LinkedHashMap是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。上图给出了LinkedHashMap的结构图，主体部分跟HashMap完全一样，多了header指向双向链表的头部(是一个哑元)，该双向链表的迭代顺序就是entry的插入顺序。
除了可以保迭代历顺序，这种结构还有一个好处 : 迭代LinkedHashMap时不需要像HashMap那样遍历整个table（bucket+entry），而只需要直接遍历header指向的双向链表即可。
有两个参数可以影响LinkedHashMap的性能:
- 初始容量(inital capacity)
- 负载系数(load factor)。
初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。
将对象放入到LinkedHashMap或LinkedHashSet中时，有两个方法需要特别关心: hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到LinkedHashMap或LinkedHashSet中，需要@Override hashCode()和equals()方法。
通过如下方式可以得到一个跟源Map 迭代顺序一样的LinkedHashMap:
void foo(Map m) {
Map copy = new LinkedHashMap(m);
...
}
出于性能原因，LinkedHashMap是非线程安全的，如果需要在多线程环境使用，需要程序员手动同步；或者通过如下方式将LinkedHashMap包装成(wrapped)同步的:
Map m = Collections.synchronizedMap(new LinkedHashMap(...));
方法剖析
get()
get(Object key)方法根据指定的key值返回对应的value。该方法跟HashMap.get()方法的流程几乎完全一样，这里不再赘述。
put()
put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于get()方法；如果没有找到，则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry。
注意，这里的插入有两个步骤:
-
从
table的角度（那个bucket所在的那条单向链表）看，新的entry需要插入到对应的bucket里，当有哈希冲突时，采用头插法（java7是头插，java8是尾插）将新的entry插入到冲突链表的头部。 -
从
header的角度（所有entry组成的双向链表，为了保持顺序）看，新的entry需要插入到双向链表的尾部。
addEntry()代码如下:
// LinkedHashMap.addEntry()
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 = hash & (table.length-1);// hash%table.length
}
// 1.在冲突链表头部插入新的entry
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
// 2.在双向链表的尾部插入新的entry
e.addBefore(header);
size++;
}
上述代码中用到了addBefore()方法将新entry e插入到双向链表头引用header的前面，这样e就成为双向链表中的最后一个元素。addBefore()的代码如下:
// LinkedHashMap.Entry.addBefor()，将this插入到existingEntry的前面
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
上述代码只是简单修改相关entry的引用而已。
remove()
remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry，然后删除该entry(修改链表的相应引用)。查找过程跟get()方法类似。
注意，这里的删除也有两个步骤:
- 从
table的角度看，需要将该entry从对应的bucket里删除，如果对应的冲突链表不空，需要修改冲突链表的相应引用。 - 从
header的角度来看，需要将该entry从双向链表中删除，同时修改链表中前面以及后面元素的相应引用。
removeEntryForKey()对应的代码如下:
// LinkedHashMap.removeEntryForKey()，删除key值对应的entry
final Entry<K,V> removeEntryForKey(Object key) {
......
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);// hash&(table.length-1)
Entry<K,V> prev = table[i];// 得到冲突链表
Entry<K,V> e = prev;
while (e != null) {// 遍历冲突链表
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry
modCount++; size--;
// 1. 将e从对应bucket的冲突链表中删除
if (prev == e) table[i] = next;
else prev.next = next;
// 2. 将e从双向链表中删除
e.before.after = e.after;
e.after.before = e.before;
return e;
}
prev = e; e = next;
}
return e;
}
LinkedHashMap经典用法
LinkedHashMap除了可以保证迭代顺序外，还有一个非常有用的用法: 可以轻松实现一个采用了FIFO替换策略的缓存。具体说来，LinkedHashMap有一个子类方法protected boolean removeEldestEntry(Map.Entry<K,V> eldest)，该方法的作用是告诉Map是否要删除“最老”的Entry，所谓最老就是当前Map中最早插入的Entry，如果该方法返回true，最老的那个元素就会被删除。在每次插入新元素之后LinkedHashMap会自动询问removeEldestEntry()是否要删除最老的元素。这样只需要在子类中重写该方法，当元素个数超过一定数量时让removeEldestEntry()返回true，就能够实现一个固定大小的FIFO策略的缓存。示例代码如下:
/** 一个固定大小的FIFO替换策略的缓存 */
class FIFOCache<K, V> extends LinkedHashMap<K, V>{
private final int cacheSize;
public FIFOCache(int cacheSize){
this.cacheSize = cacheSize;
}
// 当Entry个数超过cacheSize时，删除最老的Entry
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > cacheSize;
}
}
LinkedHashSet
前面已经说过LinkedHashSet是对LinkedHashMap的简单包装，对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法，因此LinkedHashSet的实现非常简单，这里不再赘述。
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
......
// LinkedHashSet里面有一个LinkedHashMap
public LinkedHashSet(int initialCapacity, float loadFactor) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
......
public boolean add(E e) {//简单的方法转换
return map.put(e, PRESENT)==null;
}
......
}
WeakHashMap
WeakHashMap其实就是在HashMap的基础上用弱引用来管理entry，在没有外部的强引用引用该entry时（即只有弱引用引用该entry），无论内存是否充足，gc都会回收该entry
WeakHashMap 的这个特点特别适用于需要缓存的场景。在缓存场景下，由于内存是有限的，不能缓存所有对象；对象缓存命中可以提高系统效率，但缓存MISS也不会造成错误，因为可以通过计算重新得到。
没有直接的WeakHashSet类
既然有 WeakHashMap，是否有 WeekHashSet 呢? 答案是没有。不过Java Collections工具类给出了解决方案，Collections.newSetFromMap(Map<E,Boolean> map)方法可以将任何 Map包装成一个Set。通过如下方式可以快速得到一个 Weak HashSet:
// 将WeakHashMap包装成一个Set
Set<Object> weakHashSet = Collections.newSetFromMap(
new WeakHashMap<Object, Boolean>());
不出你所料，newSetFromMap()方法只是对传入的 Map做了简单包装:
// Collections.newSetFromMap()用于将任何Map包装成一个Set
public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
return new SetFromMap<>(map);
}
private static class SetFromMap<E> extends AbstractSet<E>
implements Set<E>, Serializable
{
private final Map<E, Boolean> m; // The backing map
private transient Set<E> s; // Its keySet
SetFromMap(Map<E, Boolean> map) {
if (!map.isEmpty())
throw new IllegalArgumentException("Map is non-empty");
m = map;
s = map.keySet();
}
public void clear() { m.clear(); }
public int size() { return m.size(); }
public boolean isEmpty() { return m.isEmpty(); }
public boolean contains(Object o) { return m.containsKey(o); }
public boolean remove(Object o) { return m.remove(o) != null; }
public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
public Iterator<E> iterator() { return s.iterator(); }
public Object[] toArray() { return s.toArray(); }
public <T> T[] toArray(T[] a) { return s.toArray(a); }
public String toString() { return s.toString(); }
public int hashCode() { return s.hashCode(); }
public boolean equals(Object o) { return o == this || s.equals(o); }
public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
public boolean removeAll(Collection<?> c) {return s.removeAll(c);}
public boolean retainAll(Collection<?> c) {return s.retainAll(c);}
// addAll is the only inherited implementation
......
}
ConcurrentHashMap - JDK 1.7
JDK1.5~1.7 都是分段锁机制实现ConcurrentHashMap，使用ReentrantLock对每个分段加锁 。
ConcurrentHashMap对象是一个Segment数组，即将整个Hash表划分为多个分段；每个分段也是一个数组（HashEntry数组），类似于一个Hashtable；这样，在执行put操作时首先根据hash算法定位到元素属于哪个Segment，对该Segment加锁即可。因此，ConcurrentHashMap在多线程并发编程中可是实现多线程put操作，其最高的并发度为segment的个数（默认16）。
数据结构
ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承 ReentrantLock 来加锁，每次需要加锁的操作锁住的是一个 segment，只要保证每个 Segment 是局部线程安全的，也就实现了全局线程安全。
concurrencyLevel：并行级别/并发数/Segment 数，默认是 16，即 ConcurrentHashMap 默认有 16 个 Segments，理论上最多可同时支持 16 个线程并发写，只要它们的操作分布在不同的 Segment 上。该值可在初始化时设置为其他值，但一旦初始化，segment数组不可以扩容（segment元素才可扩容）。
每个 Segment 很像 HashMap，不过要保证线程安全，具体操作要麻烦些。
一些属性
//所有段中的HashEntry数组的总长度
static final int DEFAULT_INITIAL_CAPACITY = 16;
//默认的负载因子，是final修饰的，所以ConcurrentHashMap的负载因子是不可以指定的
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//并发级别，跟Segment数组的长度有关
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
//HashEntry数组的最大总长度
static final int MAXIMUM_CAPACITY = 1 << 30;
//每个Segment中HashEntry数组的最小长度
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
//最大的segment数组的长度
static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
//没有获取到锁时自旋的重试次数
static final int RETRIES_BEFORE_LOCK = 2;
内部类HashEntry
value和next都是volatile修饰的，对所有线程可见。同样，hashEntry数组也是volatile修饰的。
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
final void setNext(HashEntry<K,V> n) {
UNSAFE.putOrderedObject(this, nextOffset, n);
}
// Unsafe mechanics
static final sun.misc.Unsafe UNSAFE;
static final long nextOffset;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class k = HashEntry.class;
nextOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField("next"));
} catch (Exception e) {
throw new Error(e);
}
}
}
初始化
- initialCapacity：初始容量，这个值指的是整个 ConcurrentHashMap 的初始容量，实际操作的时候需要平均分给每个 Segment。
- loadFactor：负载因子，Segment 数组不可以扩容，所以负载因子是给每个 Segment 使用的。
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// Find power-of-two sizes best matching arguments
int sshift = 0;
//这个变量用于保存segment数组的容量
int ssize = 1;
//根据并发级别生成segment数组的容量
while (ssize < concurrencyLevel) {
++sshift;
//每次循环都左移一位，等价于乘以2，保证segment数组是2的n次方
ssize <<= 1;
}
//这是为了散列分布更加均匀的偏移量
this.segmentShift = 32 - sshift;
//数组长度减1，就是length-1。i = hash & (length - 1)得到下标，是一个掩码
this.segmentMask = ssize - 1;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//用总容量除以segment数组的个数，那么就得到每个segment里面的HashEntry数组的大小
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
//每次循环都左移，保证HashEntry数组的长度是2的n次方
cap <<= 1;
// create segments and segments[0]
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
//初始化一个segment数组
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
//使用Unsafe类的方法将segment数组的第一个元素赋值为s0
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
一般使用 new ConcurrentHashMap() 无参构造函数进行初始化：
- concurrentLevel决定segment数组的长度，segment数组的长度是大于等于concurrentLevel的最小的2的n次方。concurrentLevel默认是16，所以Segment数组默认大小为 16，不可扩容。
- Segment[i] 的默认初始大小为 2，负载因子是 0.75，所以插入第一个元素不会触发扩容，插入第二个会进行第一次扩容。
- HashEntry数组的长度也是2的n次方。
- 只初始化了 segment[0]，其他位置还是 null，在要使用到这些位置的时候再初始化segment对象，是延时初始化的思想。
- 当前 segmentShift 的值为 32 - 4 = 28，segmentMask 为 16 - 1 = 15，把它们简单翻译为移位数和掩码。segmentShift 是为了hash分布更加均匀。
put 过程分析
先执行ConcurrentHashMap对象的put方法，根据 hash 值找到相应的 Segment，再执行 Segment 的 put 操作。
- value的值不能为null。
- 根据hash值找到对应的segment的下标。
- 判断该下标位置有没有segment对象。因为在构造方法中虽然创建了一个segment数组，但是只有下标为0的位置才有对象。如果没有对象，那么就调用ensureSegemnt方法在数组的对应位置创建一个segemnt对象，确保这个下标对应的位置是有对象的。
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
//通过一系列操作，得到一个hash值，目的是为了减少hash冲突
int hash = hash(key);
//hash值右移，让高位参与运算，也是为了减少hash冲突
int j = (hash >>> segmentShift) & segmentMask;
//通过下标与偏移量直接查找segment数组上的对象
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
//如果不存在，创建一个segment对象
s = ensureSegment(j);
//调用segment对象的put方法
return s.put(key, hash, value, false);
}
Segment 的 put方法：
-
先尝试获取锁（是该segment的锁），获取成功把node赋值为null，继续执行；如果获取锁失败，会调用scanAndLockForPut方法。
-
获取到锁后，根据hash值得到下标（算上前面一次，一共要2次hash寻址）。
-
得到下标后获取这个下标锁对应的桶的元素，遍历该链表。
-
如果发现了一个重复的key，那么就覆盖旧value。
-
如果遍历到链表的尾部都没有发现到一个重复的key，那么就把node插入到链表的头部（头插法），然后判断是否需要扩容，需要扩容就调用rehash方法进行扩容。如果不需要，把新插入的结点（链表头）放入桶中。
-
-
最后释放锁，返回旧的value。
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
//尝试获取锁
HashEntry<K,V> node = tryLock() ? null : //获取成功，结点为null
scanAndLockForPut(key, hash, value); //获取失败，调用这个方法
V oldValue;
try {
HashEntry<K,V>[] tab = table;
//定位数组下标
int index = (tab.length - 1) & hash;
//得到链表第一个结点
HashEntry<K,V> first = entryAt(tab, index);
//遍历链表
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
//如果找到一个重复的key，覆盖
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
//如果没有找到重复的key
else {
//如果node不是null，直接插入在链表的头部
if (node != null)
node.setNext(first);
//如果是null，创建一个node结点
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
//判断是否需要扩容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
//扩容
rehash(node);
else
//头插，并将插入的结点放入桶中
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
//释放锁
unlock();
}
return oldValue;
}
ConcurrentHashMap中的put是没有加锁的，而在Segment中的put才通过ReentrantLock加锁，具体获取锁在后面介绍。
初始化segment: ensureSegment
ConcurrentHashMap 初始化的时候会初始化第一个槽 segment[0]，而其他槽会在插入第一个值的时候就会调用ensureSegment()进行初始化。
这里需要考虑并发，因为很可能会有多个线程同时进来初始化同一个槽 segment[k]，不过只要有一个成功就可以了。
private Segment<K,V> ensureSegment(int k) {
final Segment<K,V>[] ss = this.segments;
long u = (k << SSHIFT) + SBASE; // raw offset
Segment<K,V> seg;
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
// 这里看到为什么之前要初始化 segment[0] 了，
// 使用当前 segment[0] 处的数组长度和负载因子来初始化 segment[k]
// 为什么要用“当前”，因为 segment[0] 可能早就扩容过了
Segment<K,V> proto = ss[0];
int cap = proto.table.length;
float lf = proto.loadFactor;
int threshold = (int)(cap * lf);
// 初始化 segment[k] 内部的数组
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) { // 再次检查一遍该槽是否被其他线程初始化了。
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
// 使用 while 循环，内部用 CAS，当前线程成功设值或其他线程成功设值后，退出
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
return seg;
}
获取写入锁: scanAndLockForPut
在往某个 segment 中 put 的时候，首先会调用 node = tryLock() ? null : scanAndLockForPut(key, hash, value)，即先进行一次 tryLock() 快速获取该 segment 的独占锁，如果失败，就进入到 scanAndLockForPut 这个方法来获取锁。
-
先定位到要要访问或者是操作的桶。定义了一个redtries变量，这个变量一开始为 -1，为-1时表示还在判断是否需要预先创建结点。
-
自旋获取锁。如果获取锁失败，并且retries = -1，那么就会遍历链表，判断是插入操作还是覆盖操作。如果是插入操作，那么就预先创建一个结点。把retries变量赋值为0，此时这个变量表示的就是重试次数。
-
在遍历链表之后，每重试两次就会判断头结点是否改变，如果改变，那么就重新遍历结点，判断这时是否需要预先创建结点，因为重复的key的结点可能会被删除。
-
重复这个过程，直到重试次数达到上限。
ScanAndlocKForPut方法就是让没有获取到锁的线程自旋的尝试获取锁，在自旋的过程中会给需要创建结点的线程预先创建结点，那么等到获取锁的时候就不需要创建结点了。这种预先创建的方式也在一定程度上提高了并发效率。
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
//定位要操作的数据在hash表的那个桶中
HashEntry<K,V> first = entryForHash(this, hash);
HashEntry<K,V> e = first;
HashEntry<K,V> node = null;
//重试次数
int retries = -1; // negative while locating node
//尝试自旋的获取锁
while (!tryLock()) {
HashEntry<K,V> f; // to recheck first below
//在这个if语句中，遍历链表
if (retries < 0) {
//如果遍历到链表尾部都没有找到一个重复的key，那么就new一个node
if (e == null) {
if (node == null) // speculatively create node
node = new HashEntry<K,V>(hash, key, value, null);
retries = 0;
}
//如果找到一个重复的key，那么就把retries = 0，这是retries表示的就是重试次数
else if (key.equals(e.key))
retries = 0;
else
e = e.next;
}
//运行到这里，如果需要预先创建结点，那么就已经创建好了，
//如果自旋获取锁的次数达到了上限
else if (++retries > MAX_SCAN_RETRIES) {
//调用lock方法，如果不能获取锁，就加入到AQS同步队列中
lock();
//跳出循环
break;
}
//每自增两次，检查头结点是否改变
else if ((retries & 1) == 0 &&
(f = entryForHash(this, hash)) != first) {
//如果头结点改变，把retries赋值为-1，表示需要遍历结点判断是否需要创建结点
e = first = f; // re-traverse if entry changed
retries = -1;
}
}
//返回创建的结点
return node;
}
这个方法有两个出口，一个是 tryLock() 成功了，循环终止，另一个就是重试次数超过了 MAX_SCAN_RETRIES，进到 lock() 方法阻塞等待，直到成功拿到独占锁。
扩容: rehash
segment 数组不能扩容，扩容的是hashEntry数组，扩容为原来的 2 倍。先扩容后插值。
该方法不需要考虑并发，因为到这里还是持有该 segment 独占锁的。
-
先创建一个容量为原容量两倍的数组。
-
遍历HashEntry数组
-
如果桶中没有元素，跳过
-
如果桶中只有一个元素，把这个元素重新定位，hash & （length - 1）.
-
如果有一个链表，那么找到最后一段重新定位在同一个桶中的第一个结点，把这个结点移到新数组对应的桶中（把这段链表移过去，就不需要逐个搬）
-
最后将剩下来的元素遍历，一个一个的复制到新数组中。
-
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;
//遍历HashEntry数组
for (int i = 0; i < oldCapacity ; i++) {
HashEntry<K,V> e = oldTable[i];
if (e != null) {
HashEntry<K,V> next = e.next;
int idx = e.hash & sizeMask;
if (next == null) // Single node on list
newTable[idx] = e;
else { // Reuse consecutive sequence at same slot
//这部分逻辑是遍历链表，找到最后的一组重新定位在同一个数组下标的元素
HashEntry<K,V> lastRun = e;
int lastIdx = idx;
for (HashEntry<K,V> last = next;
last != null;
last = last.next) {
int k = last.hash & sizeMask;
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
//把这段元素的第一个元素放到新位置，那么后面的元素也等于放到了新位置
newTable[lastIdx] = lastRun;
// Clone remaining nodes
//然后从头开始遍历，把每个元素一个一个的插入到新位置的链表头部
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);
}
}
}
}
//在新的数组加上新插入的结点
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
上面有两个挨着的 for 循环，第一个 for 有什么用呢?
-
如果没有第一个 for ，也是可以工作的，但如果 lastRun 的后面还有比较多的节点，那么这次for就是值得的。因为我们只需要复制 lastRun 节点到新数组，后面的一串节点跟着 lastRun 走，不需要做任何操作。
-
但最坏的情况是每次 lastRun 都是链表的最后一个元素或者很靠后的元素，那么第一个for就有点浪费了。不过 Doug Lea 也说了，根据统计，如果使用默认的阈值，大约只有 1/6 的节点需要逐个复制到新数组，第一个for就是有意义的。
get 过程分析
-
获取hash值，定位到对应的segment对象
-
通过Unsafe类的getObjectVolatile方法并发安全的获取segment对象。如果获取的值为null，那么直接返回null。
-
通过hash值定位到hash表中的桶，同样通过getObjectVolatile方法获取桶中的结点，如果为null，直接返回。如果不为null，遍历链表，如果存在返回对应的value。不存在，返回null。
get方法是不加锁的，主要靠Unsafe类的方法来保证线程安全地获取数据，而且HashEntry数组、结点中的value，next都是volatile修饰的，修改对所有线程可见，保证获取到最新的值。
public V get(Object key) {
Segment<K,V> s;
HashEntry<K,V>[] tab;
//得到hash值
int h = hash(key);
//得到这个对象在数组上的偏移量
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
//通过Unsafe方法得到segment对象
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
//同理得到hashEntry表上桶中的对象
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
//判断是否存在要获取的对象
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
并发问题分析
get 过程中是没有加锁的，自然就需要去考虑并发问题。
put 和remove操作都是要加 segment 上的独占锁的，所以它们不会有问题，需要考虑的是 get 的同时发送 put 或 remove。
- put 操作的线程安全性。
- 初始化槽，这个我们之前就说过了，使用了 CAS 来初始化 Segment 中的数组。
- 添加节点到链表的操作是插入到表头的，所以，如果这个时候 get 操作在链表遍历的过程已经到了中间，是不会影响的。当然，另一个并发问题就是 get 操作在 put 之后，需要保证刚刚插入表头的节点被读取，这个依赖于 setEntryAt 方法中使用的 UNSAFE.putOrderedObject。
- 扩容。扩容是新创建了数组，然后进行迁移数据，最后面将 newTable 设置给属性 table。所以，如果 get 操作此时也在进行，那么也没关系，如果 get 先行，那么就是在旧的 table 上做查询操作；而 put 先行，那么 put 操作的可见性保证就是 table 使用了 volatile 关键字。
- remove 操作的线程安全性。
- get 操作需要遍历链表，但是 remove 操作会"破坏"链表。
- 如果 remove 破坏的节点 get 操作已经过去了，那么这里不存在任何问题。
- 如果 remove 先破坏了一个节点，分两种情况考虑。 1、如果此节点是头节点，那么需要将头节点的 next 设置为数组该位置的元素，table 虽然使用了 volatile 修饰，但是 volatile 并不能提供数组内部操作的可见性保证，所以源码中使用了 UNSAFE 来操作数组，请看方法 setEntryAt。2、如果要删除的节点不是头节点，它会将要删除节点的后继节点接到前驱节点中，这里的并发保证就是 next 属性是 volatile 的。
虽然get没加锁，但还是线程安全的。
ConcurrentHashMap - JDK 1.8
1.8的设计与1.7有了比较大的差别，1.8是选择了数组+链表+红黑树的方式实现，结构与hashmap几乎一样，采用CAS（unsafe类的方法）和synchronized给数组元素/链表加锁。虽然是用synchronized加锁，但锁粒度要比1.7小很多，这么小粒度的锁大大降低了并发冲突的概率，性能不差。
JDK1.8为什么用synchronized来代替ReentrantLock，可能原因：
-
锁粒度降低了，低粒度加锁时synchronized并不比ReentrantLock差，在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界，更加的灵活，而在低粒度中，Condition的优势就没有了
-
1.6之后synchronized就有了多级的锁，在偏向锁或轻量级锁的时候，性能比ReentrantLock好，而且使用关键字比使用API更加自然
-
在大量的数据操作下，基于API的ReentrantLock会开销更多的内存，虽然不是瓶颈，但是也是一个选择依据
数据结构
重要属性
//底层数组，是volatile修饰的
transient volatile Node<K,V>[] table;
//扩容时的新数组，也是volatile修饰的
private transient volatile Node<K,V>[] nextTable;
//用来统计结点个数
private transient volatile long baseCount;
/*
ConcurrentHashMap中比较重要的属性，主要用于并发控制和状态标记
1.在指定初始化容量时，会保存初始化容量
2.如果 sizeCtl = 0,表示正要初始化数组，还没有线程初始化
3.sizeCtl = -1，表示有线程正在初始化数组
4.表示扩容阈值
5.sizeCtl < -1，表示当前线程正在扩容。
*/
private transient volatile int sizeCtl;
//这个属性在扩容时数据转移时使用，表示的是这个索引前面的数组元素还没有分配线程进行转移。
private transient volatile int transferIndex;
//是counterCells的标记位，类似于一把锁，表示counterCells正在被访问。
private transient volatile int cellsBusy;
//用于计数，每个线程都会分配到一个CounterCell，里面保存了线程对hash表的添加数据的个数
private transient volatile CounterCell[] counterCells;
//初始化容量
private static final int DEFAULT_CAPACITY = 16;
//最大长度
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//默认并发级别
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
//负载因子，是final修饰的，已经指定为0.75，不可以再指定。
private static final float LOAD_FACTOR = 0.75f;
//树化阈值
static final int TREEIFY_THRESHOLD = 8;
//解除树化阈值
static final int UNTREEIFY_THRESHOLD = 6;
//最小树化容量
static final int MIN_TREEIFY_CAPACITY = 64;
//最小传输步长，后面会讲到
private static final int MIN_TRANSFER_STRIDE = 16;
//结点的hash值，如果Hash值是-1，表示这个结点是forwarding结点，表示这个数组正在扩容。
static final int MOVED = -1; // hash for forwarding nodes
//表示一颗红黑树，
static final int TREEBIN = -2; // hash for roots of trees
内部类Node
val和next都是volatile修饰的，对所有线程可见。同样，Node数组也是volatile修饰的。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return val; }
public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
public final String toString(){ return key + "=" + val; }
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
public final boolean equals(Object o) {
Object k, v, u; Map.Entry<?,?> e;
return ((o instanceof Map.Entry) &&
(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
(v = e.getValue()) != null &&
(k == key || k.equals(key)) &&
(v == (u = val) || v.equals(u)));
}
/**
* Virtualized support for map.get(); overridden in subclasses.
*/
Node<K,V> find(int h, Object k) {
Node<K,V> e = this;
if (k != null) {
do {
K ek;
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
} while ((e = e.next) != null);
}
return null;
}
}
重要方法
// 获取 Node[] 中第 i 个 Node
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i)
// cas 修改 Node[] 中第 i 个 Node 的值, c 为旧值, v 为新值
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v)
// 直接修改 Node[] 中第 i 个 Node 的值, v 为新值
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v)
初始化
无参构造：方法体为空，只是创建了一个对象，没有初始化数组，数组也是等到使用到的时候再初始化，也是一种延时初始化思想。
public ConcurrentHashMap() {
}
有参构造，同样没有初始化数组
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
通过提供初始容量，计算了 sizeCtl，sizeCtl = 【 (1.5 * initialCapacity + 1)，然后向上取最近的 2 的 n 次方】。如 initialCapacity 为 10，那么得到 sizeCtl 为 16，如果 initialCapacity 为 11，得到 sizeCtl 为 32。
put 过程分析
-
key和value都不能为null。1.7是value值不能为null。
-
自旋插入，保证一定会插入成功（for()死循环）。判断底层数组是否为null，如果为null，那么就调用initTable方法初始化数组，后面会介绍。
-
通过hash&(length-1)找到对应的桶位
-
如果该桶中为null，就直接使用CAS操作式插入节点。如果发生了线程竞争的话，使用CAS操作只会有一个线程成功。
-
如果该桶中的结点是一个forwarding结点，即该结点hash值为-1，表明数组正在扩容转移数据，当前线程就会调用helpTransfer方法帮组扩容。也就是说，在JDK1.8中的ConcurrentHashMap是支持多线程对同一个数组扩容的。实际上也可以说JDK1.7中的ConcurrentHashMap支持多线程扩容，但是对不同HashEntry数组扩容。
-
如果该桶中有链表或树节点，就使用synchronized上锁。锁对象就是桶中的第一个结点对象。然后判断该节点是链表节点还是红黑树节点来决定用什么方式插入。
-
如果是链表结点，就遍历链表，并用binCount记录遍历过的结点个数（包括要插入的节点）。如果发现存在重复的key，就覆盖旧值。否则，就把结点插入到链表的尾部（尾插法）。插入完后，如果binCount大于等于树化阈值（8，和hashmap一样），就转换为红黑树。
-
如果是红黑树节点（TreeBin），将值添加到红黑树结点中（存在就覆盖，不存在就添加）。
小细节：JDK1.8中，有两种红黑树结点：TreeBin和TreeNode，如果桶中是红黑树，那么该桶中第一个结点是TreeBin，其余结点是TreeNode。TreeBin并不存放数据，指向红黑树的根节点，TreeNode就是真正的红黑树节点。如果没有TreeBin，在往红黑树中插入结点时，红黑树会有旋转、变色等操作，根节点就可能因此发生改变。而加锁又是锁第一个节点，如果第一个结点发生改变，线程就不安全了。
-
-
-
调用addCount方法，将size++，并判断是否要扩容（先插值后扩容）。
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
//key和value都不能为null
if (key == null || value == null) throw new NullPointerException();
//计算出hash值
int hash = spread(key.hashCode());
int binCount = 0;
//这是一个死循环，表示一定要加入成功才能后退出
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//如果还没有数组，初始化数组
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//如果定位到的桶中没有数据，那么直接使用CAS的方式将结点插入
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
/*
如果定位到的桶中的结点hash值是MOVED=-1，表示正在扩容，并且已经将这个桶中的数据
转移到新数组了
*/
else if ((fh = f.hash) == MOVED)
//当前线程帮助扩容
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//使用synchronized加锁，锁对象就是桶中的第一个结点对象
synchronized (f) {
//判断在加锁的过程中桶中第一个结点有没有改变，相当于双重检测机制
if (tabAt(tab, i) == f) {
//结点的hash值大于等于0，说明这是一个链表结点
if (fh >= 0) {
binCount = 1;
//遍历链表，binCount最终会变成遍历过的结点个数
for (Node<K,V> e = f;; ++binCount) {
K ek;
//如果找到重复的key，覆盖
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
//没有找到，就将结点插入到链表的尾部
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//如果是红黑树结点
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
//如果找到了重复的就覆盖，没有找到就插入
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
//如果遍历过的结点数大于树化阈值，那么就会树化
if (binCount >= TREEIFY_THRESHOLD)
//树化
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//类似于size++操作，然后还要判断是否需要扩容
addCount(1L, binCount);
return null;
}
为什么1.8中 key 和 value 都不能为 null？
在 HashMap 中，key 和 value 都是可以为 null 的，而 ConcurrentHashMap 1.8中则key和value都不能为空。
作者 Doug Lea 认为在并发编程中，null 值容易引来歧义，例如调用get(key)返回value=null，我们是无法判断是key 对应的 value 本身放的就是 null，还是key根本就不存在，这会引起歧义。在非并发编程中，可以进一步通过调用 containsKey(key)来进行判断，但在并发编程中无法保证get和containsKey中间没有其他线程来修改 key 值，所以就直接禁止了 null 值的存在。
而且作者 Doug Lea 本身也认为，假如允许在集合，如 map 和 set 等存在 null 值的话，即使在非并发集合中也出现上面的歧义，这也是 Doug Lea 和 Josh Bloch（HashMap作者之一） 在设计问题上少数不同意见之一，而 ConcurrentHashMap 是 Doug Lea 一个人开发的，所以就直接禁止了 null 值的存在。
初始化数组: initTable
-
判断链表是不是为null。如果为null，就循环地创建，直到不为null。
-
如果sizeCtl<0，表示有线程已经通过CAS操作将sizeCtl修改为-1并正在初始化数组。其他线程将会让出他们的cpu时间片，尽可能的让初始化数组的线程抢到更多的cpu时间片，提高初始化数组的效率。
-
如果sizeCtl不小于0，说明此时还没有线程初始化数组，该线程通过CAS操作将sizeCtl修改为-1，修改成功的线程去初始化数组。最后将扩容阈值保存在sizeCtl中。其他线程继续循环。
因为这里不是阻塞等待，循环死等，线程较多时，可能会导致cpu空转。
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
//判断数组是不是为null，是null就循环，直到不为null。
while ((tab = table) == null || tab.length == 0) {
//此时sizeCtl<0，让出cpu时间片
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
//否则，使用CAS操作将sizeCtl修改为-1
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
//初始化数组
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
//sc = 3/4 * n，表示扩容阈值
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
链表转红黑树: treeifyBin
treeifyBin 不一定就会进行红黑树转换，如果数组长度小于64，仅仅做数组扩容。
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
// MIN_TREEIFY_CAPACITY 为 64
// 所以，如果数组长度小于 64 的时候，其实也就是 32 或者 16 或者更小的时候，会进行数组扩容
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
// 后面我们再详细分析这个方法
tryPresize(n << 1);
// b 是头节点
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
// 加锁
synchronized (b) {
if (tabAt(tab, index) == b) {
// 下面就是遍历链表，建立一颗红黑树
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
// 将红黑树设置到数组相应位置中
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
树化扩容: tryPresize
在treeifyBin转换成红黑树的方法中，如果数组长度小于64，就会在treeifyBin中调用tryPresize进行扩容，而普通情况下的扩容则是addCount函数，后面会介绍。扩容为原来的 2 倍。
核心在于对 sizeCtl 的操作，首先将其设置为一个负数，然后执行 transfer(tab, null)，在下一个循环将 sizeCtl 加 1，并执行 transfer(tab, nt)，之后可能是继续 sizeCtl 加 1，并执行 transfer(tab, nt)。也就是执行 1 次 transfer(tab, null) + 多次 transfer(tab, nt)，具体怎么结束循环得看 transfer 源码。
// 首先要说明的是，方法参数 size 传进来的时候就已经翻了倍了
private final void tryPresize(int size) {
// c: size 的 1.5 倍，再加 1，再往上取最近的 2 的 n 次方。
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
// 这个 if 分支和之前说的初始化数组的代码基本上是一样的，在这里，我们可以不用管这块代码
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
sc = n - (n >>> 2); // 0.75 * n
}
} finally {
sizeCtl = sc;
}
}
}
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) { //这段代码和addCount后部分代码是一样的，做辅助扩容操作
//生成一个扩容的标志，标识每一次扩容
int rs = resizeStamp(n);
//如果是一个负数
if (sc < 0) {
Node<K,V>[] nt;
//这一串是扩容结束的条件
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 2. 用 CAS 将 sizeCtl 加 1，然后执行 transfer 方法
// 此时 nextTab 不为 null
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
// 扩容，数据迁移
transfer(tab, nt);
}
// 1. 将 sizeCtl 设置为 (rs << RESIZE_STAMP_SHIFT) + 2)，结果是一个比较大的负数
// 调用 transfer 方法，此时 nextTab 参数为 null
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}
普通情况扩容：addCount
我们常说的扩容就是指这个函数。
扩容为原来的2倍，时机是先插值后扩容。
这个方法是让size+1的方法，加1后判断是否需要扩容。并发环境下会有很多线程添加数据使size+1，如果所有都必须要排队修改这个size，效率就会很低，所以在ConcurrentHashMap中对这种情况做了一些优化：
- 定义一个共享变量baseCount，如果线程插入了一条数据，那么可以通过修改这个变量来达到加一的操作
- 也可以不修改baseCount，jdk提供了一个CounterCell（计数格）数组，这个数组就是一个hash表，每个线程都可以定位到数组中的一个CounterCell对象，这个对象里面仅有一个volatile修饰的value属性。当线程插入数据需要将size+1时，可以定位到对应的CounterCell对象，将这个对象中的value+1。
使用这种方法，在让size+1时：
- 若没有线程竞争：baseCount累加计数即可
- 有线程竞争：访问CounterCells数组，不同的线程访问不同的CounterCell对象，将其value累加计数，减少了锁的冲突，提高了并发的效率（counterCells 初始有两个 cell。如果竞争比较激烈，会多创建 cell 来累加计数）。
@sun.misc.Contended static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
//判断counterCells数组是不是为null，如果为null，修改baseCount的值
// 如果as不为null，直接进入分支，不会调用U.compareAndSwapLong修改baseCount
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
//如果as不为null或者修改baseCount失败
CounterCell a; long v; int m;
boolean uncontended = true;
//如果as为null或者修改CounterCell失败
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
//执行这个方法，就是完成结点+1的操作
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
//统计结点的个数
s = sumCount();
}
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
//判断结点是不是需要扩容，需要扩容，进入循环。
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
//生成一个扩容的标志，标识每一次扩容
int rs = resizeStamp(n);
//如果是一个负数
if (sc < 0) {
//这一串是扩容结束的条件
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
//如果扩容没有结束
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
//扩容
transfer(tab, nt);
}
//把sizeCtl改成rs左移16位加上2.得到的是一个负数。
// 第一个来扩容的线程走这个分支
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}
流程：
-
先让size加1，就有两种加1的方式：
- 如果CounterCell数组存在，就调用fullAddCount使用CAS的操作将其对应的CounterCell对象的value+1。
- 如果不存在，就用CAS的操作更新baseCount（先尝试在数组中加，因为冲突更少）。如果更新失败，就调用fullAddCount方法。
-
加1后，统计map总结点数，如果发现需要扩容，那么就进入到扩容的逻辑。为此次扩容生成一个扩容标记，这个扩容标记仅仅跟当前的容量有关，用来标识这一次扩容。多个线程来扩容，第一个扩容的线程用CAS操作将sizeCtl修改为（rs << RESIZE_STAMP_SHIFT + 2），这是一个负数。修改成功的线程先去初始化扩容时的新数组，并开始扩容。
-
如果其他线程没有CAS成功，或者sizeCtl为负数，判断是否扩容完成，扩容完成就退出循环，没有扩容完成就扩容，并将sizeCtl+1，调用transfer方法进行数据迁移。
-
transfer完后，统计map总结点数，多线程环境下可能刚完成扩容，又达到了扩容阈值，又需要进行扩容，所以是一个while循环判断是否需要扩容。
在这个方法中，第一个扩容的线程将sizeCtl复制为扩容标志rs左移16位再加2。其他线程在进入扩容时都是将sizeCtl+1。那么这个sizeCtl高16位保存的就是扩容的标志，低16位就是扩容的线程数+1（因为第一个线程进入扩容时加2）。
size统计
当需要统计ConcurrentHashMap中有多少结点时，遍历CounterCell数组，将所有value累加，最后再加上baseCount的值，就是Map中的结点个数。
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
// 将 baseCount 计数与所有 cell 计数累加
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
数据迁移: transfer
将原来的 tab 数组的元素迁移到新的 nextTab 数组中。
此方法支持多线程执行，外围调用此方法的时候，会保证第一个发起数据迁移的线程的nextTab 参数为 null，后面的线程的nextTab 不为 null。
阅读源码之前，先要理解并发操作的机制。原数组长度为 n，所以我们有 n 个迁移任务，让每个线程每次负责一个小任务是最简单的，每做完一个任务再检测是否有其他没做完的任务，帮助迁移就可以了，而 Doug Lea 使用了 stride（步长，最小为16），每个线程每次负责迁移其中的一部分。所以就需要一个全局的调度者来安排哪个线程执行哪几个任务，这个就是属性 transferIndex 的作用。
第一个发起数据迁移的线程会将 transferIndex 指向原数组最后的位置（从后往前分配），然后从后往前的 stride 个任务属于第一个线程，然后将 transferIndex 指向新的位置，再往前的 stride 个任务属于第二个线程，依此类推。（第二个线程不是真的一定指代了第二个线程，也可以是同一个线程，本质就是将一个大的迁移任务分为了一个个小的任务包）。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
//得到一个步长
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range‘’
//如果新数组还没有初始化，初始化新数组，一般是由第一个线程来做的
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
//扩容为原来的两倍
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
//这个元素表示的是从后往前分配，分配到了那个下标了，从n开始
transferIndex = n;
}
int nextn = nextTab.length;
//创建一个forwarding结点，用于占位。当别的线程发现这个槽位中是 fwd 类型的节点，则跳过这个节点。
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
//advance，表示是否向前遍历，如果等于 true，说明需要再次推进一个下标（i--），反之，如果是 false，那么就不能推进下标，需要将当前的下标处理完毕才能继续推进
boolean advance = true;
//数组中的数据是否全部分配完毕
boolean finishing = false; // to ensure sweep before committing nextTab
//自旋
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
//i在这里改变，如果i大于这个步长中的边界值，表示这个步长还没有处理完
if (--i >= bound || finishing)
advance = false;
//判断是不是所有的数据都分配完了
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
//使用CAS操作修改transferIndex的值，哪个线程修改成功，哪个线程就负责转移这一个步长的数据
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
//这一段步长的边界
bound = nextBound;
//开始转移的下标
i = nextIndex - 1;
//先跳出循环，转移数据
advance = false;
}
}
//i<0不一定就全部转移成功，而是表示已经全部分配完成
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
//判断是否全部转移成功
if (finishing) {
nextTable = null;
//将引用指向新数组
table = nextTab;
//sizeCtl保存扩容阈值
sizeCtl = (n << 1) - (n >>> 1);
return;
}
//转移成功的线程把sizeCtl-1，表示正在扩容的线程少1
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
//如果 sizeCtl = rs << RESIZE_STAMP_SHIFT + 2，表示只剩下最后一个线程，
//这个线程也扩容完成
//把finishing设置为true
finishing = advance = true;
//重新检查，看还有没有没有处理的，顺便把空节点都放置一个fwd结点
i = n; // recheck before commit
}
}
//如果遍历到的桶为null，那么就在这里放一个forwarding结点
else if ((f = tabAt(tab, i)) == null)
//如果成功advance为true，进入循环，转移前面一个结点
advance = casTabAt(tab, i, null, fwd);
//如果已经被转移，那么也转移前面一个结点
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
//如果有结点
else {
//上锁
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
//如果是链表结点
if (fh >= 0) {
int runBit = fh & n;
Node<K,V> lastRun = f;
//这个循环找到定位在同一个桶中的最长链表后缀
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
//要么放在原来的位置
if (runBit == 0) {
ln = lastRun;
hn = null;
}
//放在 原来位置+老数组长度 的位置
else {
hn = lastRun;
ln = null;
}
//遍历剩下的结点
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
//头插
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
//把它放在对应的位置
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
//如果是树
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
//遍历所有结点
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
//放在原来的位置
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
//放在高位
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
//判断是否要树化
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
//放置到对应的位置
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
流程：
-
第一个扩容的线程创建新数组，为原容量的2倍。
-
每个线程来扩容时，都会被分配Hash表中的一段数据，让这个线程把这一段数据从老数组转移到新数组中。
-
如果遍历到空桶，那么通过CAS操作在这个桶中放一个forwarding结点。
-
如果遍历到forwarding结点，跳过这个结点，处理前一个结点。
-
如果桶中存在需要转移的结点，synchronized对第一个结点加锁。判断是链表还是红黑树。
-
链表，先找到定位到同一个桶中的最长链表后缀。再遍历剩下的结点，使用头插法将结点插入到和它定位在同一个桶中的链表上。最后将链表放在桶中。
-
红黑树，遍历所有结点，把结点放在和它定位在同一个桶中的链表上。遍历完成后，判断要不要转化成红黑树。最后将数据放入桶中。
-
-
如果一个线程把自己要处理的步长转移完了，就会去重新尝试获取步长。如果还有数据没有转移，即transferIndex > 0，就重复上面的过程。如果 transferIndex <= 0，即hash表分配完了，该线程退出扩容，将sizeCtl减1。通过transferIndex这个共享变量来保证给每个线程分配到不同的任务。
-
如果sizeCtl等于 rs << 16 + 2，就说明只剩下最后一个线程了。如果该线程扩容成功，就会将引用指向新数组，sizeCtl赋值为扩容阈值，完成扩容。
transfer 并没有实现所有的迁移任务，每次调用这个方法只实现了 transferIndex 往前 stride 个位置的迁移工作，多个线程多次调用transfer来实现并发扩容。这个时候，再回去仔细看 tryPresize 和addCount可能就会更加清晰一些了。
sizeCtl的表达意义
-
ConcurrentHashMap指定了初始化容量但还没初始化数组，sizeCtl表示初始化的容量。sizeCtl=0，即数组长度为默认初始值。
-
当要初始化底层数组时，sizeCtl = -1，表示有一个线程正在初始化数组。
-
当要初始化底层数组时，sizeCtl >= 0，表示还没有线程在初始化数组，应该有一个线程要去初始化数组。
-
当在扩容时，sizeCtl的高16位表示扩容标志(rs)，低16位表示正在进行扩容的线程数+1。
-
初始化数组完成或扩容结束后，sizeCtl会保存数组的扩容阈值（数组长度 n 乘 loadFactor）。
get 过程分析
- 根据hash值通过getObjectVolatile方法得到对应桶中的第一个结点。
- 如果桶为null，返回null
- 看第一个结点是不是要找的结点，是就返回
- 如果不是，判断是链表还是红黑树。遍历链表或者红黑树，返回值。
get过程同样没有加锁，与1.7一样，使用unsafe类的线程安全的方法获取第一个节点，数组、node的key和value都是volatile修饰的。
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
//tabAt方法：底层调用了getObjectVolatile方法
(e = tabAt(tab, (n - 1) & h)) != null) {
// 判断头节点是否就是我们需要的节点
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// 如果头节点的 hash 小于 0，说明 正在扩容，或者该位置是红黑树
else if (eh < 0)
// 参考 ForwardingNode.find(int h, Object k) 和 TreeBin.find(int h, Object k)
return (p = e.find(h, key)) != null ? p.val : null;
// 遍历链表
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
简单说一句，此方法的大部分内容都很简单，只有正好碰到扩容的情况，ForwardingNode.find(int h, Object k) 稍微复杂一些。
HT、1.7和1.8CHM对比总结
HashTable：synchronized关键字锁整张表ConcurrentHashMap JDK1.7：分段锁机制，ReentrantLock 加锁ConcurrentHashMap JDK1.8：数组+链表+红黑树数据结构和CAS+synchronized加锁
参考文章：