集合类
上面的图展示了整个集合大家族的成员以及它们之间的关系。下面就对上面的各个接口、基类做一些简单的介绍（主要介绍各个集合的特点、区别）。
Collection接口
Collection接口是最基本的集合接口，它不提供直接的实现，Java SDK提供的类都是继承自Collection的”子接口“如List和Set。Collection所代表的是一种规则，它所包含的元素都必须遵循一条或者多条规则。如有些允许重复而有些则不能重复、有些必须按照顺序插入而有些则是散列...
List接口
List接口为Collection的直接接口。List所代表的的是有序的Collection，即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。
ArrayList
- ArrayList底层是一个基于数组的非同步实现，是线程不安全的，它的操作基本上都是基于对数组的操作。
- 允许包括null在内的所有元素，ArrayList擅长随机访问，所以对于元素的查询快，增删慢，在ArrayList的中间插入或删除一个元素，该位置后面的元素都会被移动，查询的时间复杂度为O(1)，插入和删除的时间复杂度为O(n)。
- 初始容量为10，数组扩容时，会将旧数组中的元素重新拷贝一份到新的数组中，每次数组容量增长大约是其容量的1.5倍，这种操作的代价很高。所以如果明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。
- 采用了Fail-Fast机制，面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
- remove方法会让下标到数组末尾的元素向前移动一个单位，并把最后一位的值置空，方便GC。
size、isEmpty、get、set、iterator和listIterator操作都以固定时间运行。add操作以分摊的固定时间运行，也就是说，添加n个元素需要O(n)时间（由于要考虑到扩容，所以这不只是添加元素会带来分摊固定时间开销那样简单）
LinkedList
- LinkedList是基于双链表的非同步实现，所以是线程不安全的；
- 允许包括null在内的所有元素
- LinkedList不能随机访问，在查找元素的时候，需要从开头或结尾遍历列表（先判断index是在链表的哪一半，然后再去对应区域查找，这样最多只要遍历链表的一半节点即可）。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。
- 虽然LinkedList对元素的查询慢，时间复杂度为O(n)，但是对元素的增删快，插入或删除元素只需要修改元素的指针，时间复杂度为O(1)
Vector
- 与ArrayList相似，但是Vector是同步的，底层使用synchronize进行加锁。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。
- 初始容量是10，扩容时，Vector的容量增加capacityIncrement，如果没有指定capacityIncrement，则将容量增加为原来的两倍
Stack
- Stack继承自Vector，实现一个后进先出的堆栈。所以用法、线程安全什么的跟Vector都差不多，Stack刚创建后是空栈。
- Stack还提供5个额外的方法使其得以被当做堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。
Map接口
Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到Value的映射。同时它也没有继承Collection。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value，所以它不能存在相同的key值，当然value值可以相同。实现map的有：HashMap、TreeMap、HashTable、Properties、EnumMap。
HashMap(JDK1.8及以上)
-
HashMap是基于哈希表的Map接口的非同步实现，允许使用null值和null键，但不保证映射的顺序，它是为快速查询而设计的。
-
数据结构可以看成数组+链表+红黑树。底层使用数组实现，数组中每一项是个单向链表，即数组和链表的结合体；当链表长度大于一定阈值时，链表转换为红黑树，可以减少链表查询时间。
-
HashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Node对象。HashMap底层采用一个Node[]数组来保存所有的key-value对，当需要存储一个Node对象时，也会根据key的hash算法来决定其在数组中的存储位置，再根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Node时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Node。
-
HashMap进行数组扩容需要重新计算扩容后每个元素在数组中的位置，很耗性能。
HashMap的扩容代价非常大，要生成一个新的桶数组，然后要把所有元素都重新Hash落桶一次，集合等于重新执行了一次所有元素的put。所以如果我们对Map的大小有一个范围的话，可以在构造时给定大小，一般大小设置为：(int) ((float) expectedSize / 0.75F + 1.0F)。 -
采用了Fail-Fast机制，通过一个MODCount值记录修改次数，对HashMap内容的修改都将增加这个值。迭代器初始化过程中会将这个值赋给迭代器的expectedModCount，在迭代过程中，判断MODCount跟expectedModCount是否相等，如果不相等就表示已经有其它线程修改了Map，马上抛出异常。
HashTable
- Hashtable是基于哈希表的Map接口的同步实现，使用synchronize实现线程安全，即每次锁住整张表让线程独占
- 底层使用数组实现，数组中每一项是个单链表，即数组和链表的结合体，采用链表法解决哈希冲突
- 不允许使用null值和null键
- HashTable在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。HashTable底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，也会根据key的hash算法来决定其在数组中的存储位置，再根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
ConcurrentHashMap(JDK1.7版本)
- ConcurrentHashMap允许多个修改操作并发执行，其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同段进行修改，每个段其实就是一个小的hashtable，它们有各自的锁。只要多个并发发生在不同的段上，它们就可以并发进行。
- 与HashMap不同的是，ConcurrentHashMap使用多个子Hash表，也就是段（Segment），ConcurrentHashMap完全允许多个读操作并发进行，读操作并不需要加锁，但在HashMap的实现中，因为允许在hash链的中间添加或删除元素，读操作不加锁将得到不一致的数据。
- ConcurrentHashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。ConcurrentHashMap底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，也会根据key的hash算法来决定其在数组中的存储位置，再根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
- 在JDK1.8之后的版本中，抛弃了Segment锁分段的概念，而是采用CAS算法，保存并发安全性，同时底层数据结构可以看成数组+链表+红黑树。
TreeMap
键以某种排序规则排序，内部以红黑树数据结构实现，实现了SortedMap接口。
LinkedHashMap
- LinkedHashMap继承于HashMap，底层使用哈希表和双向链表来保存所有元素，并且它是非同步，允许使用null值和null键。
- 基本操作与父类HashMap相似，通过重写HashMap相关方法，重新定义了数组中保存的元素Entry，来实现自己的链接列表特性。该Entry除了保存当前对象的引用外，还保存了其上一个元素和下一个元素的引用，从而构成了双向链接列表。
WeakHashMap
WeakHashMap与HashMap的用法基本相同，区别在于：后者的key保留对象的强引用，即只要HashMap对象不被销毁，其对象所有key所引用的对象不会被垃圾回收，HashMap也不会自动删除这些key所对应的键值对对象。但WeakHashMap的key所引用的对象没有被其它强引用对象所引用，则这些key所引用的对象可能被回收。WeakHashMap中的每个key对象保存了实际对象的弱引用，当回收了该key所对应的实际对象后，WeakHashMap会自动删除该key所对应的键值对。
Set接口
set是一种不包括重复元素的Collection。它维持它自己的内部排序，所以随机访问没有任何意义。与List一样，它同样允许null的存在但是仅有一个。由于Set接口的特殊性，所有传入Set集合中的元素都必须不同，同时要注意任何可变对象，如果在对集合中元素进行操作时，导致e1.equals(e2)==true，则必定会产生某些问题。实现了Set接口的集合有：EnumSet、HashSet、TreeSet。
HashSet
- HashSet基于HashMap实现，API也是对HashMap的行为进行了封装
- HashSet堪称查询速度最快的集合，因为其内部是以HashCode来实现的。它内部元素的顺序是由哈希码来决定的，所以它不保证set的迭代顺序，特别是它不保证该顺序恒久不变，并允许使用null元素。
LinkedHashSet
- 对于LinkedHashSet而言，它继承于HashSet、又基于LinkedHashMap来实现
- LinkedHashSet底层使用LinkedHashMap来保存所有元素，它继承于HashSet，其所有的方法操作上又与HashSet相同
TreeSet
基于TreeMap，生成一个总是处于排序状态的set，内部以TreeMap来实现的。它是使用元素的自然排序对元素进行排序，或者根据创建Set时提供的Comparator进行排序，具体取决于使用的构造方法。
EnumSet
枚举的专用Set，所有的元素都是枚举类型的。
Queue
队列，它主要分为两大类，一类是阻塞式队列，队列满了以后再插入元素则会抛出异常，主要包括ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。另一种队列则是双端队列，支持在头、尾两端插入和移除元素，主要包括：ArrayDeque、LinkedBlockingDeque、LinkedList。
相关问题
Set集合是如何保证对象不重复的?
Set集合不允许有重复出现的对象，且最终的判断是根据equals()的。其原理是：HashSet的底层是采用HashMap来存放数据，HashMap的put()方法是这样的：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());//----------1----------
int i = indexFor(hash, table.length);//-----------2---------
for (Entry<K,V> e = table[i]; e != null; e = e.next) {//-----------3---------
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;
}
}//------------------4--------------------
modCount++;
addEntry(hash, key, value, i);
return null;
}
当向HashMap中添加元素的时候，首先计算元素的hashCode值，然后根据1处的代码计算出HashCode的值，再根据2处的代码计算出这个元素的存储位置，如果这个位置为空，就将元素添加进去；如果不为空，则看3-4的代码，遍历索引为i的链上的元素，如果key重复，则替换并返回oldValue值。
集合类排序问题
一种情况是集合类本身自带排序功能，如前面说过的TreeSet、SortedSet、SortedMap等，另一种就是本身不带排序功能，我们通过为需要排序的类实现Comparable或者Comparator接口来实现。
先来看两个例子，一个是实现Comparable的，一个是实现Comparator的：
实现Comparable的：
package com.xtfggef.list.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
@SuppressWarnings("unchecked")
public class ComparableTest {
public static void main(String[] args) {
// User[] users = { new User("egg", 23), new User("niuniu", 22),
// new User("qing", 28) };
// Arrays.sort(users);
// for (User user : users) {
// System.out.println(user.getName() + " " + user.getAge());
// }
List<User> users = new ArrayList<User>();
users.add(new User("egg", 23));
users.add(new User("niu", 22));
users.add(new User("qing", 28));
Collections.sort(users);
for (User user : users) {
System.out.println(user.getName() + " " + user.getAge());
}
}
}
@SuppressWarnings("unchecked")
class User implements Comparable {
private String name;
private int age;
public User(String name, int age) {
super();
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public int compareTo(Object o) {
return this.age - ((User) o).getAge();
}
}
实现Comparator接口：
package com.xtfggef.comparator.test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class ComparatorTest {
public static void main(String[] args) {
List<User> users = new ArrayList<User>();
users.add(new User("egg", 21));
users.add(new User("niu", 22));
users.add(new User("gg", 29));
UserComparator comparator = new UserComparator();
Collections.sort(users, comparator);
for (User user : users) {
System.out.println(user.getUsername() + " " + user.getAge());
}
}
}
class User {
private String username;
private int age;
public User(String username, int age) {
super();
this.username = username;
this.age = age;
}
public String getUsername() {
return username;
}
public void setUsername(String username) {
this.username = username;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
}
class UserComparator implements Comparator<User> {
@Override
public int compare(User user1, User user2) {
int age1 = user1.getAge();
int age2 = user2.getAge();
if (age1 < age2) {
return 1;
}
return 0;
}
}
通过上面的这两个小例子可以看出，Comparator和Comparable用于不同的场景，实现对对象的比较从而进行排序。
相同点：二者都可以实现对象的排序，不论用Arrays的方法还是用Collections的sort()方法。
不同点：
- 实现Comparable接口的类，似乎是预先知道该类将要进行排序，需要排序的类实现Comparable接口，是一种“静态绑定排序”。
- 实现Comparator的类，设计者无需事先为需要排序的类实现任何接口。
- Comparator接口里有两个抽象方法compare()和equals()，而Comparable接口里只有一个方法compareTo()。
- Comparator接口无需改变排序类的内部，也就是说实现算法和数据分离，是一个良好的设计，是一种“动态绑定排序”。
- Comparator接口可以使用多种排序标准，比如升序、降序等。
使用for循环删除元素陷阱：
public class Test {
public static void main(String[] args) {
List<String> list = new LinkedList<String>();
list.add("A");
list.add("B");
list.add("C");
for(int i=0; i<list.size(); i++){
list.remove(i);
}
for(String item:list){
System.out.println(item);
}
}
}
按照思路应该是输不出什么，但是执行它却输出了B。分析一下这个程序，当第一步remove完后，集合内还剩两个元素，此时i为1，而list.size()的值为2，从0开始的话，i为1时，正好指向第二个元素C，也就是说当remove完A后，直接就跳到C了，将B漏了。
public class Test {
public static void main(String[] args) {
List<String> list = new LinkedList<String>();
list.add("A");
list.add("B");
list.add("C");
for(int i=0; i<list.size(); i++){
list.remove(i);
i -= 1;//每次删除完后，i减少1
}
for(String item:list){
System.out.println(item);
}
}
}
参考：
ArrayList详解
ArrayList是实现了List接口的动态数组，所谓动态数组就是它的大小是可变的。实现了所有可选列表操作，并允许包括Null在内的所有元素。
每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小，默认初始容量是10。随着ArrayList中元素的增加，它的容量也会不断的自动增长。在每次添加元素时，ArrayList都会检查是否需要进行扩容操作，扩容操作将数据向新数组中拷贝，所以如果知道具体业务数据量，在构造ArrayList时，可以给ArrayList指定一个初始容量，这样就会减少扩容时的拷贝问题。当然在添加大量元素之前，应用程序也可以使用ensureCapacity方法来增加ArrayList实例的容量，这可以减少递增式再分配的数量。
ArrayList的实现不是同步的，如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。所以为了保持同步，最好的办法是在创建时完成，以防止意外对列表进行不同步的访问：
List list = Collections.synchronizedList(new ArrayList(...));
ArrayList源码分析
底层使用数组：
private transient Object[] elementData;
transient为java关键字，表示此实例变量不会被序列化。此处的Object[ ] elementData就是ArrayList的容器，下面介绍的基本操作都是基于该elementData变量来操作的。
构造函数：
-
ArrayList()：默认构造函数，提供初始容量为10的空列表。
-
ArrayList(int initialCapacity)：构造一个具有指定初始容量的空列表
-
ArrayList(Collection<? extends E> c)：构造一个包含指定collection的元素的列表，这些元素是按照该Collection的迭代器返回的顺序排列的。
/** * 构造一个初始容量为 10 的空列表 */ public ArrayList() { this(10); } /** * 构造一个具有指定初始容量的空列表。 */ public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); this.elementData = new Object[initialCapacity]; } /** * 构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }
新增：
ArrayList提供了add(E e)、add(int index,E element)、addAll(Collection<? extends E> c)、addAll(int index,Collection<? extends E> c)、set(int index,E element)这五个方法来实现ArrayList增加。
-
add(E e)：将指定的元素添加到此列表的尾部。
public boolean add(E e) { ensureCapacity(size + 1); // Increments modCount!! elementData[size++] = e; return true; }ensureCapacity()方法是对ArrayList集合进行扩容操作，elementData[size++] = e,将列表末尾元素指向e
-
add(int index,E element)：将指定的元素插入此列表中的指定位置
public void add(int index, E element) { //判断索引位置是否正确 if (index > size || index < 0) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); //扩容检测 ensureCapacity(size+1); /* * 对源数组进行复制处理（位移），从index + 1到size-index。 * 主要目的就是空出index位置供数据插入， * 即向右移动当前位于该位置的元素以及所有后续元素。 */ System.arraycopy(elementData, index, elementData, index + 1, size - index); //在指定位置赋值 elementData[index] = element; size++; }在这个方法中最根本的方法就是System.arraycopy()方法，该方法的根本目的就是将index位置空出来以供新数据插入，这里需要进行数组数据的右移，这是非常麻烦和耗时的，所以如果指定的数据集合需要进行大量插入（中间插入）操作，推荐使用LinkedList。
-
addAll(Collection<? extends E> c)：按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。
public boolean addAll(Collection<? extends E> c) { // 将集合C转换成数组 Object[] a = c.toArray(); int numNew = a.length; // 扩容处理，大小为size + numNew ensureCapacity(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; }这个方法无非就是使用System.arraycopy()方法将C集合（先转换为数组）里面的数据复制到elementData数组中。System.arraycopy()的原型为：public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)。它的根本目的就是进行数组元素的复制。将原数组src从srcPos位置开始复制到dest数组中，复制长度为length，数据从dest的destPos位置开始粘贴。
-
addAll(int index, Collection<? extends E> c)：从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。
public boolean addAll(int index, Collection<? extends E> c) { //判断位置是否正确 if (index > size || index < 0) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); //转换成数组 Object[] a = c.toArray(); int numNew = a.length; //ArrayList容器扩容处理 ensureCapacity(size + numNew); // Increments modCount //ArrayList容器数组向右移动的位置 int numMoved = size - index; //如果移动位置大于0，则将ArrayList容器的数据向右移动numMoved个位置，确保增加的数据能够增加 if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); //添加数组 System.arraycopy(a, 0, elementData, index, numNew); //容器容量变大 size += numNew; return numNew != 0; } -
set(int index,E element)：用指定的元素替代此列表中指定位置上的元素。
public E set(int index, E element) { //检测插入的位置是否越界 RangeCheck(index); E oldValue = (E) elementData[index]; //替代 elementData[index] = element; return oldValue; }
删除：
ArrayList提供了remove(int index)、remove(Object o)、removeRange(int fromIndex, int toIndex)、removeAll()四个方法进行元素的删除。
-
remove(int index)：移除此列表中指定位置上的元素。
public E remove(int index) { //位置验证 RangeCheck(index); modCount++; //需要删除的元素 E oldValue = (E) elementData[index]; //向左移的位数 int numMoved = size - index - 1; //若需要移动，则想左移动numMoved位 if (numMoved > 0) System.arraycopy(elementData, index + 1, elementData, index, numMoved); //置空最后一个元素 elementData[--size] = null; // Let gc do its work return oldValue; } -
remove(Object o)：移除此列表中首次出现的指定元素（如果存在）。
public boolean remove(Object o) { //因为ArrayList中允许存在null，所以需要进行null判断 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; }其中fastRemove()方法用于移除指定位置的元素。如下：
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; // Let gc do its work } -
removeRange(int fromIndex, int toIndex)：移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。
protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System .arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // Let gc do its work int newSize = size - (toIndex - fromIndex); while (size != newSize) elementData[--size] = null; } -
removeAll()：是继承自AbstractCollection的方法，ArrayList本身并没有提供实现。
public boolean removeAll(Collection<?> c) { boolean modified = false; Iterator<?> e = iterator(); while (e.hasNext()) { if (c.contains(e.next())) { e.remove(); modified = true; } } return modified; }
查找：
ArrayList提供了get(int index)用于读取ArrayList中的元素。由于ArrayList是动态数组，所以完全可以根据下标来获取ArrayList中的元素，而且速度还比较快，故ArrayList擅长于随机访问。
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
扩容：
在上面的新增方法的源码中可以发现每个方法中都存在这个方法：ensureCapacity()，该方法就是ArrayList的扩容方法。在前面就提过ArrayList每次新增元素时都会需要进行容量检测判断，若新增元素后元素的个数会超过ArrayList的容量，就会进行扩容操作来满足新增元素的需求。所以当清楚的知道业务数据量或者需要插入大量元素前，可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。
public void ensureCapacity(int minCapacity) {
//修改计时器
modCount++;
//ArrayList容量大小
int oldCapacity = elementData.length;
/*
* 若当前需要的长度大于当前数组的长度时，进行扩容操作
*/
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
//计算新的容量大小，为当前容量的1.5倍
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
//数组拷贝，生成新的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
1.5倍是扩容最好的倍数，既能满足性能需求，也不会造成很大的内存消耗。
除了ensureCapacity()这个扩容数组外，ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize()方法来实现。该方法可以最小化ArrayList实例的存储量。
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
LinkedList源码解析
详情请看此博客：LinkedList源码分析_张维鹏的博客-CSDN博客
Vector
-
Vector可以实现可增长的对象数组。与数组一样，可以使用整数索引进行访问。不过，Vector的大小是可以增加或者减小的，以便使用创建Vector后进行添加或者删除操作。
-
同时Vector是线程安全的！底层使用的是synchronize进行加锁。
-
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable- 实现List接口，继承AbstractList类，所以可以将其看做队列，支持相关的添加、删除、修改、遍历等功能。
- 实现RandomAccess接口，即提供了随机访问功能，可直接访问元素。
- 实现了Cloneable接口，支持clone()，可以被克隆。
- 实现了Serializable接口，因此可以进行序列化
-
成员变量方面，Vector提供了elementData , elementCount， capacityIncrement三个成员变量。其中
- elementData：“Object [] 类型的数组”，它保存了Vector中的元素，是一个动态数组，可以随着元素的增加而动态的增长（具体增长方式在ensureCapacity方法中）。如果在初始化Vector时没有指定容器大小，则使用默认大小为10。
- elementCount：Vector对象中的元素个数。
- capacityIncrement：向量的大小大于其容量时，容量自动增加的量。如果在创建Vector时，指定了capacityIncrement的大小，则每次当Vector中动态数组容量增加时，增加的大小都是capacityIncrement。如果容量的增量小于等于零，则每次需要增大容量时，向量的容量将增大一倍。
Stack
在java中Stack类表示后进先出的对象堆栈。栈是一种非常常见的数据结构，它采用典型的先进后出的操作方式完成的。每一个栈都包含一个栈顶，每次出栈是将栈顶的数据取出，如下：
Stack通过五个操作对Vector进行扩展，允许将向量视为堆栈。这五个操作如下：
| 操作 | 操作 |
|---|---|
| empty() | 测试堆栈是否为空。 |
| peek() | 查看堆栈顶部的对象，但不从堆栈中移除它。 |
| pop() | 移除堆栈顶部的对象，并作为此函数的值返回该对象。 |
| push(E item) | 把对象压入堆栈顶部。 |
| search(Object o) | 返回对象在堆栈中的位置，以 1 为基数。 |
Stack继承了Vector，对Vector进行了简单的扩展：
public class Stack<E> extends Vector<E>
Stack的实现非常简单，仅有一个构造方法，五个实现方法（从Vector继承而来的不算与其中），同时其实现的源码非常简单：
/**
* 构造函数
*/
public Stack() {
}
/**
* push函数：将元素存入栈顶
*/
public E push(E item) {
// 将元素存入栈顶。
// addElement()的实现在Vector.java中
addElement(item);
return item;
}
/**
* pop函数：返回栈顶元素，并将其从栈中删除
*/
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
// 删除栈顶元素，removeElementAt()的实现在Vector.java中
removeElementAt(len - 1);
return obj;
}
/**
* peek函数：返回栈顶元素，不执行删除操作
*/
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
// 返回栈顶元素，elementAt()具体实现在Vector.java中
return elementAt(len - 1);
}
/**
* 栈是否为空
*/
public boolean empty() {
return size() == 0;
}
/**
* 查找“元素o”在栈中的位置：由栈底向栈顶方向数
*/
public synchronized int search(Object o) {
// 获取元素索引，elementAt()具体实现在Vector.java中
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
注：Stack类的设计是有缺陷的，不应该使用Stack类，而是使用LinkedList构建栈。
集合细节
详情请阅读此博客：集合细节：为集合指定初始容量、asList的缺陷、subList的缺陷_张维鹏的博客-CSDN博客
HashMap原理详解(JDK1.7及之前的版本)
有关HashMap的源码都是基于JDK1.6的
简单来说，HashMap是基于哈希表的Map接口的实现，以Key-Value的形式存在，即存储的对象是Entry（同时包含了key和value）。在HashMap中，其会根据hash算法来计算key-value的存储位置并进行快速存取。特别地，HashMap最多只允许一条Entry的键为null，但允许多条Entry的值为Null。此外，HashMap是Map的一个非同步的实现。
必须指出的是，虽然容器号称存储的是Java对象，但实际上并不会真正将Java对象放入容器中，只是在容器中保留这些对象的引用。也就是说，Java容器实际上包含的是引用变量，而这些引用变量指向了要实际保存的Java对象。
HashMap在JDK中的定义
HashMap实现了Map接口，并继承AbstractMap抽象类，其中Map接口定义了键值映射规则。AbstractMap抽象类提供了Map接口的骨干实现，以最大限度地减少实现Map接口所需的工作。HashMap在JDK中的定义为：
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable{
...
}
HashMap的构造函数
HashMap一共提供了四个构造函数，其中默认无参的构造函数和参数为Map的构造函数为Java Collection Frameword规范的推荐实现，其余两个构造函数则是HashMap专门提供的。
-
HashMap()：该构造函数意在构造一个具有默认初始容量（16）和默认负载因子（0.75）的空HashMap，其源码如下：
/** * Constructs an empty HashMap with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { //负载因子:用于衡量的是一个散列表的空间的使用程度 this.loadFactor = DEFAULT_LOAD_FACTOR; //HashMap进行扩容的阈值，它的值等于 HashMap 的容量乘以负载因子 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); // HashMap的底层实现仍是数组，只是数组的每一项都是一条链 table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); } -
HashMap(int initialCapacity, float loadFactor)：该构造函数意在构造一个指定初始容量和指定负载因子的空HashMap，其源码如下：
/** * Constructs an empty HashMap with the specified initial capacity and load factor. */ public HashMap(int initialCapacity, float loadFactor) { //初始容量不能小于 0 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //初始容量不能超过 2^30 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; //负载因子不能小于 0 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // HashMap 的容量必须是2的幂次方，超过 initialCapacity 的最小 2^n int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; //负载因子 this.loadFactor = loadFactor; //设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行自动扩容操作 threshold = (int)(capacity * loadFactor); // HashMap的底层实现仍是数组，只是数组的每一项都是一条链 table = new Entry[capacity]; init(); } -
HashMap(int initialCapacity)：该构造函数意在构造一个指定初始容量和默认负载因子（0.75）的空HashMap，其源码如下：
// Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75) public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); // 直接调用上述构造函数 } -
HashMap(Map<? extends K, ? extends V> m)：该构造函数意在构造一个与指定Map具有相同映射的HashMap，其初始容量不小于16，负载因子是0.75，其源码如下：
// Constructs a new HashMap with the same mappings as the specified Map. // The HashMap is created with default load factor (0.75) and an initial capacity // sufficient to hold the mappings in the specified Map. public HashMap(Map<? extends K, ? extends V> m) { // 初始容量不小于 16 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); putAllForCreate(m); }
初始容量和负载因子，这两个参数是影响HashMap性能的重要参数。其中，容量表示哈希表中桶的数量（table数组的大小），初始容量是创建哈希表时桶的数量；负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之越小。
对于使用拉链法的哈希表来说，查找一个元素的平均时间是O(1+a)，a指的是链的长度，是一个常数。特别地，若负载因子越大，那么对空间的利用更充分，但查找效率也就越低；若负载因子越小，那么哈希表的数据将越稀疏，堆空间造成的浪费也就越严重。系统默认负载因子为0.75，这是时间和空间成本上的一种折中，一般情况下是无需修改的。
HashMap的数据结构
哈希的相关概念：
Hash就是把任意长度的输入（又叫做预映射），通过哈希算法，变换成固定长度的输出（通常是整型），该输出就是哈希值。这种转换是一种压缩映射，也就是说，散列值的空间通常远小于输入的空间。不同的输入可能会散列成相同的输出，从而不可能用散列值来唯一的确定输入值。简单的说，就是一种将任意长度的消息压缩到某一固定长度的消息摘要函数。
哈希的应用：数据结构
可以从上图看到，左边很明显是个数组，数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针，用于元素间的链接。根据元素的自身特征把元素分配到不同的链表中，反过来也正是通过这些特征找到正确的链表，再从链表中找出正确的元素。其中，根据元素特征计算元素数组下标的的方法就是哈希算法。
HashMap的数据结构：
从上图中，可以形象地看出HashMap底层实现还是数组，只是数组的每一项都是一条链。其中参数initialCapacity就代表了该数组的长度，也就是桶的个数。从构造方法的源码中可以知道，每次新建一个HashMap时，都会初始化一个Entry类型的table数组，其中Entry类型的定义如下：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; // 键值对的键
V value; // 键值对的值
Entry<K,V> next; // 下一个节点
final int hash; // hash(key.hashCode())方法的返回值
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) { // Entry 的构造函数
value = v;
next = n;
key = k;
hash = h;
}
......
}
其中，Entry为HashMap的内部类，实现了Map.Entry接口，其包含了键key、值value、下一个节点next、以及hash值四个属性。事实上，Entry是构成哈希表的基石，是哈希表所存储的元素的具体形式。
HashMap的存储实现：
在HashMap中，键值对的存储是通过put(key,value)方法来实现的，其源码如下：
/**
* 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 key, or null if there was no mapping for key.
* Note that a null return can also indicate that the map previously associated null with key.
*/
public V put(K key, V value) {
//当key为null时，调用putForNullKey方法，并将该键值对保存到table的第一个位置
if (key == null)
return putForNullKey(value);
//根据key的hashCode计算hash值
int hash = hash(key.hashCode()); // ------- (1)
//计算该键值对在数组中的存储位置（哪个桶）
int i = indexFor(hash, table.length); // ------- (2)
//在table的第i个桶上进行迭代，寻找 key 保存的位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) { // ------- (3)
Object k;
//判断该条链上是否存在hash值相同且key值相等的映射，若存在，则直接覆盖 value，并返回旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue; // 返回旧值
}
}
modCount++; //修改次数增加1，快速失败机制
//原HashMap中无该映射，将该添加至该链的链头
addEntry(hash, key, value, i);
return null;
}
通过上述源码可以清楚了解到HashMap保存数据的过程。首先，判断Key是否为null，若为null，则直接调用putForNullKey方法；若不为空，则先计算key的hash值，然后根据hash值搜索在table数组中的索引位置，如果table数组在该位置处有元素，则查找是否存在相同的key，若存在则覆盖原来的key的value，否则将该元素保存在链头（最先保存的元素放在链尾）。此外，若table在该处没有元素，则直接保存。
在源码（3）处，此处迭代的原因就是为了防止存在相同的key值。如果发现两个hash值（key）相同时，HashMap的处理方式是用新value替换旧value，这里并没有处理key，这正好解释了HashMap中没有两个相同的key。
对null键的特别处理：putForNullKey()
/**
* Offloaded version of put for null keys
*/
private V putForNullKey(V value) {
// 若key==null，则将其放入table的第一个桶，即 table[0]
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) { // 若已经存在key为null的键，则替换其值，并返回旧值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++; // 快速失败
addEntry(0, null, value, 0); // 否则，将其添加到 table[0] 的桶中
return null;
}
通过上述源码可以清楚知道，HashMap中可以保存键为NULL的键值对，且该键值对是唯一的。若再次向其中添加键为NULL的键值对，将覆盖其原值。此外，如果HashMap中存在键为NULL的键值对，那么一定在第一个桶中。
HashMap中的哈希策略（算法）
在上述的put(key,value)方法的源码中，标出了HashMap中的哈希策略（即(1)、(2)处），hash()方法用于对key的hashCode进行重新计算，而indexFor()方法用于生成这个Entry对象的插入位置。当计算出来的hash值与HashMap的(length - 1)做了&运算后，会得到位于区间[0,length - 1]的一个值。特别地，这个值分布的越均匀，HashMap的空间利用率也就越高，存取效率也就越好。
**hash()**方法，该方法为一个纯粹的数学计算，用于进一步计算key的hash值，源码如下：
/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits.
*
* Note: Null keys always map to hash 0, thus index 0.
*/
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
使用hash()方法对一个对象的hashCode进行重新计算是为了防止质量低下的hashCode()函数实现。由于HashMap的支撑数组长度总是2的幂次，通过右移使低位的数据尽量的不同，从而使hash值的分布尽量均匀。
通过上述hash()方法计算得到key的哈希数值后，怎么才能保证元素均匀分布到table的每个桶中呢？可以采用取模，但是由于取模的效率较低，HashMap是通过调用(2)处的indexFor()方法处理的，其不但简单而且效率很高，对应源码如下：
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1); // 作用等价于取模运算，但这种方式效率更高
}
因为HashMap的底层数组长度总是2的n次方。当length为2的n次方时，h&(length - 1)就相当于对length取模，而且速度比直接取模要快得多，这是HashMap在速度上的一个优化。
总而言之，上述的hash()方法和indexFor()方法的作用只有一个：保证元素均匀分布到table的每个桶中以便充分利用空间。
HashMap中键值对的添加：addEntry()
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*
* 永远都是在链表的表头添加新元素
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//获取bucketIndex处的链表
Entry<K,V> e = table[bucketIndex];
//将新创建的 Entry 链入 bucketIndex处的链表的表头
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//若HashMap中元素的个数超过极限值 threshold，则容量扩大两倍
if (size++ >= threshold)
resize(2 * table.length);
}
通过上述源码可以清楚地了解到链的产生时机。HashMap总是将新的Entry对象添加到bucketIndex处，若bucketIndex处已经有了Entry对象，那么新添加的Entry对象将指向原有的Entry对象，并形成一条新的以它为链头的Entry链；但是，若bucketIndex处原先没有Entry对象，那么新添加的Entry对象将指向null，也就生成了一条长度为1的全新的Entry链。HashMap永远都是在链表的表头添加新元素。此外，若HashMap中元素的个数超过极限值threshold，其将进行扩容操作，一般情况下，容量将扩大至原来的两倍。
HashMap的扩容：resize()
随着HashMap中元素的数量越来越多，发生碰撞的概率将越来越大，所产生的的子链长度就会越来越长，这样势必会影响HashMap的存取速度。为了保证HashMap的效率，系统必须要在某个临界点进行扩容处理，该临界点就是HashMap中元素的数量在数值上等于threshold（table数组长度*加载因子）。但是，扩容是一个非常耗时的过程，因为它需要重新计算这些元素在新table数组中的位置并进行复制处理。所以，如果能够提前预知HashMap中的元素的个数，那么在构造HashMap时预设元素的个数能够有效的提高HashMap的性能。
/**
* Rehashes the contents of this map into a new array with a
* larger capacity. This method is called automatically when the
* number of keys in this map reaches its threshold.
*
* If current capacity is MAXIMUM_CAPACITY, this method does not
* resize the map, but sets threshold to Integer.MAX_VALUE.
* This has the effect of preventing future calls.
*
* @param newCapacity the new capacity, MUST be a power of two;
* must be greater than current capacity unless current
* capacity is MAXIMUM_CAPACITY (in which case value
* is irrelevant).
*/
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// 若 oldCapacity 已达到最大值，直接将 threshold 设为 Integer.MAX_VALUE
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return; // 直接返回
}
// 否则，创建一个更大的数组
Entry[] newTable = new Entry[newCapacity];
//将每条Entry重新哈希到新的数组中
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor); // 重新设定 threshold
}
HashMap的重哈希：transfer()
重哈希主要是一个重新计算原HashMap中的元素在新table数组中的位置并进行复制处理的过程。
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable) {
// 将原数组 table 赋给数组 src
Entry[] src = table;
int newCapacity = newTable.length;
// 将数组 src 中的每条链重新添加到 newTable 中
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null; // src 回收
// 将每条链的每个元素依次添加到 newTable 中相应的桶中
do {
Entry<K,V> next = e.next;
// e.hash指的是 hash(key.hashCode())的返回值;
// 计算在newTable中的位置，注意原来在同一条子链上的元素可能被分配到不同的子链
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
特别需要注意的是，在重哈希的过程中，原属于一个桶中的Entry对象可能被分到不同的桶，因为HashMap的容量发生了变化，那么h&(length - 1)的值也会发生相应的变化。
HashMap的读取实现：
HashMap只需通过key的hash值定位到table数组的某个特定的桶，然后查找并返回该key对应的value即可，源码如下：
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
// 若为null，调用getForNullKey方法返回相对应的value
if (key == null)
// 从table的第一个桶中寻找 key 为 null 的映射；若不存在，直接返回null
return getForNullKey();
// 根据该 key 的 hashCode 值计算它的 hash 码
int hash = hash(key.hashCode());
// 找出 table 数组中对应的桶
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//若搜索的key与查找的key相同，则返回相对应的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
其中，针对键为NULL的键值对，HashMap提供了专门的处理：getForNullKey()，其源码如下：
/**
* Offloaded version of get() to look up null keys. Null keys map
* to index 0. This null case is split out into separate methods
* for the sake of performance in the two most commonly used
* operations (get and put), but incorporated with conditionals in
* others.
*/
private V getForNullKey() {
// 键为NULL的键值对若存在，则必定在第一个桶中
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
// 键为NULL的键值对若不存在，则直接返回 null
return null;
}
因此，调用HashMap的get(Object key)方法后，若返回值是NULL，则存在如下两种可能：
- 该key对应的值就是null
- Hashmap中不存在该key
HashMap的底层数组长度为何总是2的n次方？
原因是HashMap在其构造函数HashMap(int initialCapacity,float loadFactor)中作了特别的处理，如下面的代码所示。当底层数组的length为2的n次方时，h&(length - 1)就相当于对length取模，其效率要比直接取模高得多，这是HashMap在效率上的一个优化。
// HashMap 的容量必须是2的幂次方，超过 initialCapacity 的最小 2^n
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
HashMap的底层数组长度总是2的n次方的主要原因是什么呢？
假设length分别为16（2^4）和15，h分别为5、6、7。
可以看到，当n=15时，6和7的结果一样，即它们位于table的同一个桶中，也就是产生了碰撞，6、7就会在这个桶中形成链表，这样就会导致查询速度降低。诚然这里只分析了三个数字，那么再看看h分别取0-15时的情况。
从上面的图表中可以看到，当length为15时总共发生了8次碰撞，同时发现空间浪费非常大，因为在1、3、5、7、9、11、13、15这八处没有存放数据。这是因为hash值在与14（即1110）进行&运算时，得到的结果最后一位永远都是0，即 0001、0011、0101、0111、1001、1011、1101、1111位置处是不可能存储数据的。这样，空间的减少会导致碰撞几率的进一步增加，从而就会导致查询速度慢。
而当length为16时，length-1=15，即1111，那么，在进行低位&运算时，值总是与原来hash值相同，而进行高位运算时，其值等于其低位运算。所以，当length=2^n时，不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布交均匀，查询速度也较快。
因此，总的来说，HashMap的底层数组长度总是2的n次方的原因有两个，即当length=2^n时：
- 不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，空间利用率较高，查询速度也较快；
- h&(length - 1)就相当于对length取模，而且在速度、效率上比直接取模要快得多，即二者是等价不等效的，这是HashMap在速度和效率上的一个优化。
参考：HashMap原理详解（JDK1.7及之前的版本）_张维鹏的博客-CSDN博客
HashMap原理详解(JDK1.8)
JDK1.8对HashMap进行了比较大的优化，底层实现由之前的“数组”+“链表”改为“数组”+“链表”+“红黑树”。JDK1.8的HashMap的数据结构如下图所示，当链表节点较少时仍然是以链表存在的，当链表节点较多时（大于8）会转为红黑树。
基本属性
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认负载因子0.75
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8; // 链表节点转换红黑树节点的阈值, 8个节点转
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6; // 红黑树节点转换链表节点的阈值, 6个节点转
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64; // 转红黑树时, table的最小长度
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> { // 基本hash节点, 继承自Entry
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {// 红黑树节点
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
// ...
}
定位哈希桶数组索引位置
// 代码1
static final int hash(Object key) { // 计算key的hash值
int h;
// 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 代码2
int n = tab.length;
// 将(tab.length - 1) 与 hash值进行&运算
int index = (n - 1) & hash;
其基本操作和JDK1.7及之前版本大致相同，不过在JDK1.8版本中，还优化了高位运算的算法，将HashCode的高16位与hashCode进行异或运算，主要是为了在table的length较小的时候，让高位也参与运算，并且不会有太大的开销。
下面是一个简单的例子，table长度为16：
扩容后，节点重hash为什么只可能分布在原索引位置与原索引+oldCap位置？
扩容代码后，使用e节点的hash值跟oldCap进行位与运算，以此决定将节点分布到原索引位置或者原索引+oldCap位置上，这是为什么呢？
假设老表的容量为16，即oldCap=16，则新表容量为16*2=32，假设节点1的hash值为为0000 0000 0000 0000 0000 1111 0000 1010，节点2的hash值为0000 0000 0000 0000 0000 1111 0001 1010，则节点1和节点2在老表的索引位置计算如下图计算1，由于老表的长度限制，节点1和节点2的索引位置只取决于节点hash值的最后4位。再看计算2，计算2为新表的索引计算，可以知道如果两个节点在老表的索引位置相同，则新表的索引位置只取决于节点hash值倒数第5位的值，而此位置的值刚好为老表的容量值16，此时节点在新表的索引位置只有两种情况：原索引位置和原索引位置+oldCop位置（在此例中即为10和10+16=26）。由于结果只取决于节点hash值的倒数第5位，而此位置的值刚好为老表的容量值16，因此此时新表的所有位置的计算可以替换为计算3，直接使用节点的hash值与老表的容量16进行位与运算，如果结果为0则该节点在新表的索引位置为原索引位置，否则该节点在新表的索引位置为原索引位置+oldCap位置。
死循环问题
JDK1.8之前，导致死循环的主要原因是扩容后，节点的顺序会反掉，如下图：在并发的情况下，扩容后插入新数组时采用的是头插法导致了死循环的发生。
JDK1.8扩容过程，采用的是尾插法将死循环问题解决。
可以看出扩容后，节点A和节点C的先后顺序跟扩容前是一样的。因此，即使此时有多个线程并发扩容，也不会出现死循环的情况。当然，这仍然改变不了HashMap是非并发安全的，在并发下，还是要使用ConcurrentHashMap来代替。
死循环过程详情见此博客： HashMap死循环问题_DreamMakers的博客-CSDN博客
扩展：
-
HashMap有threshold属性和loadFactor属性，但是没有capacity属性。初始化时，如果传了初始化容量值，该值是存放在threshold变量中，并且Node数组在第一次put时才会进行初始化，初始化时将此时的threshold值作为新表的capacity值，然后用capacity和loadFactor计算新表的真正threshold值。
JDK1.8之后将带有初始化容量的构造函数做了改动：
// 指定“容量大小”和“加载因子”的构造函数 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } -
当同一个索引位置的节点在增加到8个时，会触发链表节点（Node）转红黑树节点（TreeNode，间接继承Node），转成红黑树节点后，其实链表的结构还存在，通过next属性维持。链表节点转红黑树节点的具体方法为源码中的treeifyBin(Node<K,V>[] tab, int hash)方法。补充：只有当数组长度大于或者等于64的情况下，才会执行转换红黑树操作。
-
当同一个索引位置的结点在移除后达到6个时，并且该索引位置的结点为红黑树节点，会触发红黑树节点转链表节点。红黑树节点转链表节点的具体方法为源码中的untreeify(HashMap<K,V> map)方法。
参考：HashMap原理详解（JDK1.8）_张维鹏的博客-CSDN博客
ConcurrentHashMap详解(JDK1.6)
（本文有关ConcurrentHashMap的源码都是基于JDK1.6的）
ConcurrentHashMap是JUC(java.util.concurrent)的重要成员，它是HashMap的一个线程安全的、支持高效并发的版本。在默认理想状态下，ConcurrentHashMap可以支持16个线程执行并发写操作以及任意数量线程的读操作。
如下图所示，ConcurrentHashMap本质上是一个Segment数组，而一个Segment实例又包含若干个桶，每个桶都包含一条由若干个HashEntry对象链接起来的链表。ConcurrentHashMap的高效并发机制是通过以下三方面来保证的（具体细节见后文阐述）：
- 通过锁分段技术保证并发环境下的写操作；
- 通过HashEntry的不变性、volatile变量的内存可见性和加锁重读机制保证高效、安全的读操作；
- 通过不加锁和加锁两种方案控制跨段操作的安全性。
HashMap线程不安全的典型表现
详情请参考此博客中的第二小节：ConcurrentHashMap详解（JDK1.6）_张维鹏的博客-CSDN博客
ConcurrentHashMap在JDK中的定义
ConcurrentHashMap类中包含两个静态内部类HashEntry和Segment，其中HashEntry用来封装具体的key-value，是个典型的四元组；Segment用来充当锁的角色，每个Segment对象守护整个ConcurrentHashMap的若干个桶（可以把Segment看做是一个小型的哈希表），其中每个桶是由若干个HashEntry对象链接起来的链表。总的来说，一个ConcurrentHashMap实例中包含由若干个Segment实例组成的数组，而一个Segment实例又包含有若干个桶，每个桶中都包含一条由若干个HashEntry对象链接起来的链表。特别地，ConcurrentHashMap在默认并发级别下会创建16个Segment对象的数组，如果键能均匀散列，每个Segment大约守护整个散列表中桶总数的1/16。
类结构定义：
ConcurrentHashMap继承了AbstractMap并实现了ConcurrentMap接口，其在JDK中的定义为：
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
implements ConcurrentMap<K, V>, Serializable {
...
}
成员变量定义：
与HashMap相比，ConcurrentHashMap增加了两个属性用于定位段，分别是segmentMask和segmentShift。此外，ConcurrentHashMap底层结构是一个Segment数组，而不是Object数组，具体源码如下：
/**
* Mask value for indexing into segments. The upper bits of a
* key's hash code are used to choose the segment.
*/
final int segmentMask; // 用于定位段，大小等于segments数组的大小减 1，是不可变的
/**
* Shift value for indexing within segments.
*/
final int segmentShift; // 用于定位段，大小等于32(hash值的位数)减去对segments的大小取以2为底的对数值，是不可变的
/**
* The segments, each of which is a specialized hash table
*/
final Segment<K,V>[] segments; // ConcurrentHashMap的底层结构是一个Segment数组
段的定义：Segment
Segment类继承于ReentrantLock类，从而使得Segment对象能充当锁的角色。在Segment类中，count变量是一个计数器，它表示每个Segment对象管理的table数组包含的HashEntry对象的个数，也就是Segment中包含的HashEntry对象的总数。特别需要注意的是，之所以在每个Segment对象中包含一个计数器，而不是在ConcurrentHashMap中使用全局的计数器，是对ConcurrentHashMap并发性的考虑：因为这样当需要更新计数器时，不用锁定整个ConcurrentHashMap。事实上，每次对段进行结构上的改变，如在段中进行增加/删除节点（修改节点的值不算结构上的改变），都要更新count的值，此外，在JDK的实现中每次读取操作开始都要先读取count的值。特别需要注意的是，count是volatile的，这使得对count的任何更新对其它线程都是立即可见的。
modCount用于统计段结构改变的次数，主要是为了检测对多个段进行遍历过程中某个段是否发生改变。threshold用来表示段需要进行重哈希的阈值。loadFactor表示段的负载因子，其值等同于ConcurrentHashMap的负载因子的值。table是一个典型的链表数组，而且也是volatile的，这使得对table的任何更新对其它线程也都是立即可见的。段（Segment）的定义如下：
/**
* Segments are specialized versions of hash tables. This
* subclasses from ReentrantLock opportunistically, just to
* simplify some locking and avoid separate construction.
*/
static final class Segment<K,V> extends ReentrantLock implements Serializable {
/**
* The number of elements in this segment's region.
*/
transient volatile int count; // Segment中元素的数量，可见的
/**
* Number of updates that alter the size of the table. This is
* used during bulk-read methods to make sure they see a
* consistent snapshot: If modCounts change during a traversal
* of segments computing size or checking containsValue, then
* we might have an inconsistent view of state so (usually)
* must retry.
*/
transient int modCount; //对count的大小造成影响的操作的次数（比如put或者remove操作）
/**
* The table is rehashed when its size exceeds this threshold.
* (The value of this field is always <tt>(int)(capacity *
* loadFactor)</tt>.)
*/
transient int threshold; // 阈值，段中元素的数量超过这个值就会对Segment进行扩容
/**
* The per-segment table.
*/
transient volatile HashEntry<K,V>[] table; // 链表数组
/**
* The load factor for the hash table. Even though this value
* is same for all segments, it is replicated to avoid needing
* links to outer object.
* @serial
*/
final float loadFactor; // 段的负载因子，其值等同于ConcurrentHashMap的负载因子
...
}
ConcurrentHashMap允许多个修改（写）操作并发进行，其关键在于使用了锁分段技术，它使用了不同的锁来控制对哈希表的不同部分进行的修改（写）,而ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分。实际上，每个段实质上就是一个小的哈希表，每个段都有自己的锁。这样，只要多个修改操作发生在不同的段上，它们就可以并发进行。
基本元素：HashEntry
在HashEntry类中，key，hash和next域都被声明为final的，value域被volatile所修饰。因此，HashEntry对象几乎是不可变的，这是ConcurrentHashMap读操作并不需要加锁的一个重要原因。next域被声明为final本身就意味着不能从hash链的中间或尾部添加或删除节点，因为这需要修改next引用值，因此所有的节点的修改只能从头开始。对于put操作，可以一律添加到Hash链的头部。但是对于remove操作，可能需要从中间删除一个节点，这就需要将要删除节点的前面所有节点整个复制（重新new）一遍，最后一个节点指向要删除节点的下一个节点。由于value域被volatile修饰，所以其可以确保被读线程读到最新的值，这是ConcurrentHashMap读操作并不需要加锁的另一个重要原因。
/**
* ConcurrentHashMap 中的 HashEntry 类
*
* ConcurrentHashMap list entry. Note that this is never exported
* out as a user-visible Map.Entry.
*
* Because the value field is volatile, not final, it is legal wrt
* the Java Memory Model for an unsynchronized reader to see null
* instead of initial value when read via a data race. Although a
* reordering leading to this is not likely to ever actually
* occur, the Segment.readValueUnderLock method is used as a
* backup in case a null (pre-initialized) value is ever seen in
* an unsynchronized access method.
*/
static final class HashEntry<K,V> {
final K key; // 声明 key 为 final 的
final int hash; // 声明 hash 值为 final 的
volatile V value; // 声明 value 被volatile所修饰
final HashEntry<K,V> next; // 声明 next 为 final 的
HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
this.key = key;
this.hash = hash;
this.next = next;
this.value = value;
}
@SuppressWarnings("unchecked")
static final <K,V> HashEntry<K,V>[] newArray(int i) {
return new HashEntry[i];
}
}
next域是final的，所以新节点只能在链表的表头处插入。
与HashEntry不同的是，HashMap中的Entry类结构如下所示：
/**
* HashMap 中的 Entry 类
*/
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
...
}
ConcurrentHashMap的构造函数
其一共提供了五个构造函数，其中默认无参的构造函数和参数为map的构造函数为 Java Collection Framework规范推荐实现，其余三个构造函数则是ConcurrentHashMap专门提供的。
-
**ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)：**该构造函数意在构造一个具有指定容量、指定负载因子和指定段数目/并发级别（若不是2的幂次方，则会调整为2的幂次方）的空ConcurrentHashMap，其相关源码如下：
/** * Creates a new, empty map with the specified initial * capacity, load factor and concurrency level. * * @param initialCapacity the initial capacity. The implementation * performs internal sizing to accommodate this many elements. * @param loadFactor the load factor threshold, used to control resizing. * Resizing may be performed when the average number of elements per * bin exceeds this threshold. * @param concurrencyLevel the estimated number of concurrently * updating threads. The implementation performs internal sizing * to try to accommodate this many threads. * @throws IllegalArgumentException if the initial capacity is * negative or the load factor or concurrencyLevel are * nonpositive. */ 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; // 大小为 lg(ssize) int ssize = 1; // 段的数目，segments数组的大小(2的幂次方) while (ssize < concurrencyLevel) { ++sshift; ssize <<= 1; } segmentShift = 32 - sshift; // 用于定位段 segmentMask = ssize - 1; // 用于定位段 this.segments = Segment.newArray(ssize); // 创建segments数组 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; int c = initialCapacity / ssize; // 总的桶数/总的段数 if (c * ssize < initialCapacity) ++c; int cap = 1; // 每个段所拥有的桶的数目(2的幂次方) while (cap < c) cap <<= 1; for (int i = 0; i < this.segments.length; ++i) // 初始化segments数组 this.segments[i] = new Segment<K,V>(cap, loadFactor); } -
**ConcurrentHashMap(int initialCapacity, float loadFactor)：**该构造函数意在构造一个具有指定容量、指定负载因子和默认并发级别(16)的空ConcurrentHashMap，其相关源码如下：
/** * Creates a new, empty map with the specified initial capacity * and load factor and with the default concurrencyLevel (16). * * @param initialCapacity The implementation performs internal * sizing to accommodate this many elements. * @param loadFactor the load factor threshold, used to control resizing. * Resizing may be performed when the average number of elements per * bin exceeds this threshold. * @throws IllegalArgumentException if the initial capacity of * elements is negative or the load factor is nonpositive * * @since 1.6 */ public ConcurrentHashMap(int initialCapacity, float loadFactor) { this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL); // 默认并发级别为16 } -
**ConcurrentHashMap(int initialCapacity)：**该构造函数意在构造一个具有指定容量、默认负载因子(0.75)和默认并发级别(16)的空ConcurrentHashMap，其相关源码如下：
/** * Creates a new, empty map with the specified initial capacity, * and with default load factor (0.75) and concurrencyLevel (16). * * @param initialCapacity the initial capacity. The implementation * performs internal sizing to accommodate this many elements. * @throws IllegalArgumentException if the initial capacity of * elements is negative. */ public ConcurrentHashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); } -
ConcurrentHashMap()：该构造函数意在构造一个具有默认初始容量(16)、默认负载因子(0.75)和默认并发级别(16)的空ConcurrentHashMap，其相关源码如下
/** * Creates a new, empty map with a default initial capacity (16), * load factor (0.75) and concurrencyLevel (16). */ public ConcurrentHashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); } -
**ConcurrentHashMap(Map<? extends K, ? extends V> m)：**该构造函数意在构造一个与指定 Map 具有相同映射的 ConcurrentHashMap，其初始容量不小于 16 (具体依赖于指定Map的大小)，负载因子是 0.75，并发级别是 16， 是 Java Collection Framework 规范推荐提供的，其源码如下：
/** * Creates a new map with the same mappings as the given map. * The map is created with a capacity of 1.5 times the number * of mappings in the given map or 16 (whichever is greater), * and a default load factor (0.75) and concurrencyLevel (16). * * @param m the map */ public ConcurrentHashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); putAll(m); }
初始容量、负载因子和并发级别，这三个参数是影响ConcurrentHashMap性能的重要参数。
ConcurrentHashMap的数据结构
通过使用段(Segment)将ConcurrentHashMap划分为不同的部分，ConcurrentHashMap就可以使用不同的锁来控制对哈希表的不同的修改，从而允许多个修改操作并发进行，这正是ConcurrentHashMap锁分段技术的核心内涵。进一步地，如果把整个ConcurrentHashMap看作是一个父哈希表的话，那么每个Segment就可以看作是一个子哈希表，如下图所示：
注意：假设ConcurrentHashMap一共分为2^n个段，每个段中有2^m个桶，那么段的定位方式是将key的hash值的高n位与(2^n-1)相与。在定位到某个段后，再将key的hash值的低m位与(2^m-1相与),定位到具体的桶位。
ConcurrentHashMap的并发存取
在ConcurrentHashMap中，线程对映射表做读操作时，一般情况下不需要加锁就可以完成，对容器做结构性修改的操作（比如put操作、remove操作等）才需要加锁。
用分段锁机制实现多个线程间的并发操作
ConcurrentHashMap的put操作对应的源码如下：
/**
* Maps the specified key to the specified value in this table.
* Neither the key nor the value can be null.
*
* <p> The value can be retrieved by calling the <tt>get</tt> method
* with a key that is equal to the original key.
*
* @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>
* @throws NullPointerException if the specified key or value is null
*/
public V put(K key, V value) {
if (value == null)
throw new NullPointerException();
int hash = hash(key.hashCode());
return segmentFor(hash).put(key, hash, value, false);
}
从上面的源码可以看出，ConcurrentHashMap不同于HashMap，它既不允许key值为null，也不允许value值为null。实际上对ConcurrentHashMap的put操作被委托给特定的段来实现。当向ConcurrentHashMap中put一个Key/Value对时，首先会获得key的哈希值并对其再次哈希，然后根据最终的hash值定位到这条记录所应该插入的段，定位段的SegmentFor()方法源码如下：
/**
* Returns the segment that should be used for key with given hash
* @param hash the hash code for the key
* @return the segment
*/
final Segment<K,V> segmentFor(int hash) {
return segments[(hash >>> segmentShift) & segmentMask];
}
SegmentFor()方法根据传入的hash值向右无符号右移segmentShift位，然后和segmentMask进行与操作就可以定位到特定的段。在这里，假设Segment的数量（Segment数组的长度）是2的n次方（Segment的数量总是2的倍数，具体见构造函数的实现），那么SegmentShift的值就是32-n（hash值的位数是32），而SegmentMask的值就是2^n-1(写成二进制的形式就是n个1)。可以得出以下结论：根据key的hash值的高n位就可以确定元素到底在哪一个Segment中。紧接着，调用这个段的put()方法来将目标Key/Value对插入到段中，段的put()方法的源码如下所示：
V put(K key, int hash, V value, boolean onlyIfAbsent) {
lock(); // 上锁
try {
int c = count;
if (c++ > threshold) // ensure capacity
rehash();
HashEntry<K,V>[] tab = table; // table是Volatile的
int index = hash & (tab.length - 1); // 定位到段中特定的桶
HashEntry<K,V> first = tab[index]; // first指向桶中链表的表头
HashEntry<K,V> e = first;
// 检查该桶中是否存在相同key的结点
while (e != null && (e.hash != hash || !key.equals(e.key)))
e = e.next;
V oldValue;
if (e != null) { // 该桶中存在相同key的结点
oldValue = e.value;
if (!onlyIfAbsent)
e.value = value; // 更新value值
}else { // 该桶中不存在相同key的结点
oldValue = null;
++modCount; // 结构性修改，modCount加1
tab[index] = new HashEntry<K,V>(key, hash, first, value); // 创建HashEntry并将其链到表头
count = c; //write-volatile，count值的更新一定要放在最后一步(volatile变量)
}
return oldValue; // 返回旧值(该桶中不存在相同key的结点，则返回null)
} finally {
unlock(); // 在finally子句中解锁
}
}
从源码中首先可以知道，ConcurrentHashMap对Segment的put操作是加锁完成的。Segment是ReentrantLock的子类，因此Segment本身就是一种可重入的Lock，所以可以直接调用其继承而来的lock()方法和unlock()方法对代码进行上锁/解锁。需要注意的是，这里的加锁操作是针对某个具体的Segment，锁定的也是该Segment而不是整个ConcurrentHashMap。因为插入键/值对操作只是在这个Segment包含的某个桶中完成，不需要锁定整个ConcurrentHashMap。因此，其它写线程对另外15个Segment的加锁并不会因为当前线程对这个Segment的加锁而阻塞。故而相比较于HashTable和由同步包装器包装的HashMap每次只能有一个线程执行读或写操作。在理想状态下，ConcurrentHashMap可以支持16个线程并发执行写操作，及任意数量线程的读操作。
在将key/value对插入到Segment之前，首先会检查本次插入会不会导致Segment中元素的数量超过阈值threshold，如果会，那么就先对Segment进行扩容和重哈希操作，然后再进行插入。第8行和第9行的操作就是定位到段中特定的桶并确定链表头部的位置。第12行的while循环用于检查该桶中是否存在相同key的节点，如果存在，就直接更新value值；如果没有找到，则进入21行生成一个新的HashEntry并且把它链到该桶中链表的表头，然后更新count的值（由于count是volatile变量，所以count值的更新一定要放在最后一步）。
ConcurrentHashMap的重哈希操作：rehash()
在ConcurrentHashMap中使用put操作插入Key/Value对之前，首先会检查本次插入会不会导致Segment中节点数量超过阈值threshold，如果会，那么就先对Segment进行扩容和重哈希操作。特别需要注意的是，ConcurrentHashMap的重哈希实际上是对ConcurrentHashMap的某个段的重哈希，因此ConcurrentHashMap的每个段所包含的桶位自然也就不尽相同。针对段进行rehash()操作的源码如下：
void rehash() {
HashEntry<K,V>[] oldTable = table; // 扩容前的table
int oldCapacity = oldTable.length;
if (oldCapacity >= MAXIMUM_CAPACITY) // 已经扩到最大容量，直接返回
return;
/*
* Reclassify nodes in each list to new Map. Because we are
* using power-of-two expansion, the elements from each bin
* must either stay at same index, or move with a power of two
* offset. We eliminate unnecessary node creation by catching
* cases where old nodes can be reused because their next
* fields won't change. Statistically, at the default
* threshold, only about one-sixth of them need cloning when
* a table doubles. The nodes they replace will be garbage
* collectable as soon as they are no longer referenced by any
* reader thread that may be in the midst of traversing table
* right now.
*/
// 新创建一个table，其容量是原来的2倍
HashEntry<K,V>[] newTable = HashEntry.newArray(oldCapacity<<1);
threshold = (int)(newTable.length * loadFactor); // 新的阈值
int sizeMask = newTable.length - 1; // 用于定位桶
for (int i = 0; i < oldCapacity ; i++) {
// We need to guarantee that any existing reads of old Map can
// proceed. So we cannot yet null out each bin.
HashEntry<K,V> e = oldTable[i]; // 依次指向旧table中的每个桶的链表表头
if (e != null) { // 旧table的该桶中链表不为空
HashEntry<K,V> next = e.next;
int idx = e.hash & sizeMask; // 重哈希已定位到新桶
if (next == null) // 旧table的该桶中只有一个节点
newTable[idx] = e;
else {
// Reuse trailing 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;
// 寻找k值相同的子链，该子链尾节点与父链的尾节点必须是同一个
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
// JDK直接将子链lastRun放到newTable[lastIdx]桶中
newTable[lastIdx] = lastRun;
// 对该子链之前的结点，JDK会挨个遍历并把它们复制到新桶中
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
int k = p.hash & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(p.key, p.hash,
n, p.value);
}
}
}
}
table = newTable; // 扩容完成
}
由于扩容是按照2的幂次方进行的，所以扩展前在同一个桶中的元素，要么还是在原来序号中，或者就是原来的序号再加上一个2的幂次方。因为链接指针next是final的，因此看起来好像只能把该桶的HashEntry链中的每个节点复制到新的桶中（这意味着要重新创建每个节点），但事实上JDK对其做了一定的优化。因为在理论上原桶里的HashEntry链可能存在一条子链，而且这个子链的尾节点必须与原hash链的尾节点是同一个，那么只需要把这个子链的头节点放到新的桶中，其后面跟的一串子节点自然也就连接上了。对于这个子链头节点之前的节点，JDK会挨个遍历并把它们复制到新桶的链头（只能在表头插入元素）。特别地，注意这段代码：
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;
在该代码段中，JDK直接将子链lastRun放到newTable[lastIdx]桶中，难道这个操作不会覆盖掉newTable[lastIdx]桶中原有的元素么？
事实上，这种情形是不可能出现的，因为桶newTable[lastIdx]在子链添加进去之前压根就不会有节点存在，这还是因为table的大小是按照2的幂次方的方式去扩展的。假设原来table的大小是2^k大小，而定位桶的方式是：
// sizeMask = newTable.length - 1，即 sizeMask = 11...1，共k+1个1。
int idx = e.hash & sizeMask;
因此这样得到的idx实际上就是key的hash值的低k+1位的值，而原table的sizeMask也全是1的二进制，不过总共是k位，那么原table的idx就是key的hash值的低k位的值。所以，如果元素的hashCode的第k+1位是0，那么元素在新桶的序号就是和原桶的序号是相等的；如果第k+1位的值是1，那么元素在新桶的序号就是原桶的序号加上2^k。因此，JDK直接将子链lastRun放到newTable[lastIndex]桶中就没问题，因为newTable中新序号处此时肯定是空的。
ConcurrentHashMap的读取实现：get(Object key)
与put操作类似，当从ConcurrentHashMap中查询一个指定key的键值对时，首先会定位其应该存在的段，然后查询请求委托给这个段进行处理，源码如下：
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code key.equals(k)},
* then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* @throws NullPointerException if the specified key is null
*/
public V get(Object key) {
int hash = hash(key.hashCode());
return segmentFor(hash).get(key, hash);
}
紧接着看Segment中get操作的源码：
V get(Object key, int hash) {
if (count != 0) { // read-volatile，首先读 count 变量
HashEntry<K,V> e = getFirst(hash); // 获取桶中链表头结点
while (e != null) {
if (e.hash == hash && key.equals(e.key)) { // 查找链中是否存在指定Key的键值对
V v = e.value;
if (v != null) // 如果读到value域不为 null，直接返回
return v;
// 如果读到value域为null，说明发生了重排序，加锁后重新读取
return readValueUnderLock(e); // recheck
}
e = e.next;
}
}
return null; // 如果不存在，直接返回null
}
了解了ConcurrentHashMap的put操作后，上述源码就很好理解了。但是有一个情况需要特别注意，就是链中存在指定Key的键值对并且其对应的Value值为null的情况。在剖析ConcurrentHashMap的put操作时，知道ConcurrentHashMap既不允许key值为null，也不允许value值为null。但是此处怎么会存在键值对存在且Value的值为null的情形呢？
JDK官方给出的解释是，这种情形发生的场景是：初始化HashEntry时发生的指令重排序导致的，也就是在HashEntry初始化完成之前便返回了它的引用。这时，JDK给出的解决之道就是加锁重读，源码如下：
/**
* Reads value field of an entry under lock. Called if value
* field ever appears to be null. This is possible only if a
* compiler happens to reorder a HashEntry initialization with
* its table assignment, which is legal under memory model
* but is not known to ever occur.
*/
V readValueUnderLock(HashEntry<K,V> e) {
lock();
try {
return e.value;
} finally {
unlock();
}
}
ConcurrentHashMap存取小结：
在ConcurrentHashMap进行存取时，首先会定位到具体的段，然后通过对具体段的存取来完成对整个ConcurrentHashMap的存取。特别地，无论是ConcurrentHashMap的读操作还是写操作都具有很高的性能：在进行读操作时不需要加锁，而在写操作时通过锁分段技术只对所操作的段加锁而不影响客户端对其它段的访问。
ConcurrentHashMap读操作不需要加锁的奥秘
因为HashEntry中的key、hash和next指针都是final的。这意味着，不能把节点添加到链表的中间和尾部，也不能在链表的中间和尾部删除节点。这个特性可以保证：在访问某个节点时，这个节点之后的连接不会被改变，这个特性可以大大降低处理链表时的复杂性。与此同时，由于HashEntry类的value字段被声明是Volatile的，因此Java的内存模型就可以保证：某个写线程对value字段的写入马上就可以被后续的某个读线程看到。此外，由于在ConcurrentHashMap中不允许用null作为键和值，所以当读线程读到某个HashEntry的value为null时，便知道产生了冲突——发生了重排序现象，此时便会加锁重新读取这个value值。这些特性互相配合，使得读线程即使在不加锁状态下，也能正确访问ConcurrentHashMap。总的来说，ConcurrentHashMap读操作不需要加锁的奥秘在于以下几点：
- 用HashEntry对象的不变性来降低读操作对加锁的需求；
- 用Volatile变量协调读写线程间的内存可见性；
- 若读时发生指令重排序线程，则加锁重读。
用HashEntry对象的不变性来降低读操作对加锁的需求
非结构性修改操作只是更改某个HashEntry的value字段的值。由于对Volatile变量的写入操作将与随后对这个变量的读操作进行同步，所以当一个写线程修改了某个HashEntry的value字段后，Java内存模型能够保证一定能读取到这个字段更新后的值。所以，写线程对链表的非结构性修改能够被后序不加锁的读线程看到。
对ConcurrentHashMap做结构性修改时，实质上是对某个桶指向的链表做结构性修改。如果能够确保在读线程遍历一个链表期间，写线程对这个链表所做的结构性修改不影响读线程继续正常遍历这个链表，那么读/写线程之间就可以安全并发访问这个ConcurrentHashMap。在ConcurrentHashMap中，结构性修改操作包括put操作、remove操作和clear操作，下面分别分析这三种操作：
-
clear操作只是把ConcurrentHashMap中所有的桶置空，每个桶之前引用的链表依然存在，只是桶不再引用这些链表而已，而链表本身的结构并没有发生任何修改。因此，正在遍历某个链表的读线程依然可以正常执行对该链表的遍历。
-
关于put操作的细节在上文已经单独介绍过，因为put操作在插入一个新节点到链表中时会在链表头部插入这个新节点，此时链表中的原有节点的链接并没有被修改。也就是说，插入新的键值对到链表中的操作不会影响读线程正常遍历这个链表。
-
下面分析remove操作，此操作源代码如下：
/** * Removes the key (and its corresponding value) from this map. * This method does nothing if the key is not in the map. * * @param key the key that needs to be removed * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt> * @throws NullPointerException if the specified key is null */ public V remove(Object key) { int hash = hash(key.hashCode()); return segmentFor(hash).remove(key, hash, null); }同样的，在ConcurrentHashMap中删除一个键值对时，首先需要定位到特定的段并将删除操作委派给该段。Segment的remove操作如下所示：
/** * Remove; match on key only if value null, else match both. */ V remove(Object key, int hash, Object value) { lock(); // 加锁 try { int c = count - 1; HashEntry<K,V>[] tab = table; int index = hash & (tab.length - 1); // 定位桶 HashEntry<K,V> first = tab[index]; HashEntry<K,V> e = first; while (e != null && (e.hash != hash || !key.equals(e.key))) // 查找待删除的键值对 e = e.next; V oldValue = null; if (e != null) { // 找到 V v = e.value; if (value == null || value.equals(v)) { oldValue = v; // All entries following removed node can stay // in list, but all preceding ones need to be // cloned. ++modCount; // 所有处于待删除节点之后的节点原样保留在新链表中 HashEntry<K,V> newFirst = e.next; // 所有处于待删除节点之前的节点被克隆到新链表中 for (HashEntry<K,V> p = first; p != e; p = p.next) newFirst = new HashEntry<K,V>(p.key, p.hash,newFirst, p.value); tab[index] = newFirst; // 将删除指定节点并重组后的链重新放到桶中 count = c; // write-volatile，更新Volatile变量count } } return oldValue; } finally { unlock(); // finally子句解锁 } }可以看出，删除节点C之后的所有节点原样保留到新链表中；删除节点C之前的每个节点被克隆到新链表中（它们在新链表中的链接顺序被反转了）。因此，在执行remove操作时，原始链表并没有被修改（因为只是将数据放到新链表中，而原数据并未改变），也就是说，读线程不会受同时执行remove操作的并发写线程的干扰。
综合上面的分析可以知道，无论写线程对某个链表进行结构性修改还是非结构性修改，都不会影响其它的并发读线程对这个链表的访问。
用Volatile变量协调读写线程间的内存可见性
一般地，由于内存可见性的问题，在未正确同步的情况下，对于写线程写入的值读线程可能并不能及时读到。下面以写线程M和读线程N来说明ConcurrentHashMap如何协调读/写线程间的内存可见性问题，如下图所示：
假设线程M在写入了volatile变量count后，线程N读取了这个volatile变量。根据 happens-before 关系法则中的程序次序法则，A appens-before 于 B，C happens-before D。根据 Volatile法则，B happens-before C。结合传递性，则可得到：A appens-before 于 B； B appens-before C；C happens-before D。也就是说，写线程M对链表做的结构性修改对读线程N是可见的。虽然线程N是在未加锁的情况下访问链表，但Java的内存模型可以保证：只要之前对链表做结构性修改操作的写线程M在退出写方法前写volatile变量count，读线程N就能读取到这个volatile变量count的最新值。
事实上，ConcurrentHashMap就是一个Segment数组，而每个Segment都有一个volatile变量count去统计Segment中的HashEntry的个数，并且，在ConcurrentHashMap中，所有不加锁读方法在进入读方法时，首先都会去读这个count变量。
小结：
在ConcurrentHashMap中，所有执行写操作的方法（put、remove和clear）在对链表做结构性修改之后，在退出写方法前都会去写这个count变量；所有未加锁的读操作（get、contains和containKey）在读方法中，都会首先去读取这个count变量。根据Java内存模型，对同一个volatile变量的写/读操作可以确保：写操作写入的值，能够被之后未加锁的读线程看到。这个特性和前面介绍的HashEntry对象的不变性相结合，使得在ConcurrentHashMap中读线程进行读取操作时基本不需要加锁就能成功获得需要的值。这两个特性以及加锁重读机制的互相配合，不仅减少了请求同一个锁的频率（读操作一般不需要加锁就能够成功获得值），也减少了持有同一个锁的时间（只有读到value域的值为null时，读线程才需要加锁后重读）。
ConcurrentHashMap的跨段操作
在ConcurrentHashMap中，有些操作需要涉及到多个段，比如size操作、containsValue操作等。以size操作为例，如果要统计整个ConcurrentHashMap里元素的大小，那么就必须统计所有Segment里元素的大小后求和。由于Segment里的全局变量count是一个volatile变量，那么在多线程场景下，是不是直接把所有Segment的count相加就可以得到整个ConcurrentHashMap大小了呢？
显然不能，虽然相加时可以获取每个Segment的count的最新值，但是拿到之后可能累加前使用的count发送了变化，那么统计结果就不准了。所以最安全的做法是在统计size的时候把所有Segment的put、remove和clear方法全部锁住，但是这种做法显然非常低效。
JDK实现size()方法的思路主要是先在没有锁的情况下对所有段大小求和，这种求和策略最多只需RETRIES_BEFORE_LOCK（默认是两次）：在没有达到RETRIES_BEFORE_LOCK之前，求和操作会不断尝试（这是因为遍历过程中可能有其它线程正在对已经遍历过的段进行结构性更新）；在超过RETRIES_BEFORE_LOCK之后，如果还不成功就在持有所有段锁的情况下再对所有段大小求和。事实上，在累加count操作的过程中，之前累加过的count发生变化的几率非常小，所以ConcurrentHashMap的做法是先尝试RETRIES_BEFORE_LOCK次通过不锁住Segment的方式来统计各个Segment大小，如果统计的过程中，容器的count发生了变化，则再采用加锁的方式来统计所有Segment的大小。
那么ConcurrentHashMap是如何判断在统计的时候容器的段发生了结构性更新呢？
Segment包含一个modCount成员变量，在会引起段发生结构性改变的所有操作（put、remove和clear操作）里，都会将变量modCount进行加1，因此，JDK只需要在统计size前后比较modCount是否发生变化就可以得知容器的大小是否发生变化。
参考：
ConcurrentHashMap详解（JDK1.6）_张维鹏的博客-CSDN博客
ConcurrentHashMap详解(JDK1.8)
本文分析的源码是JDK8的版本，与JDK6的版本有很大的差异。实现线程安全的思想也已经完全变了，它摒弃了Segment（锁段）的概念，而是启用了一种全新的方式实现，利用CAS算法。它沿用了与它同时期的HashMap版本的思想，底层依然由数组+链表+红黑树的方式实现，但是为了做到并发，又增加了很多辅助的类。
详情请阅读此博客（小声逼逼，这篇文章我没咋看明白...）：ConcurrentHashMap详解（JDK1.8）_张维鹏的博客-CSDN博客
Hashtable原理详解(JDK1.8)
（本文使用的源码基于JDK1.8的）
定义
Hashtable在Java中的定义如下：
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable
从中可以看出Hashtable继承Dictionary类，实现Map接口。其中Dictionary类是任何可将键映射到相应值的类。每个键和每个值都是一个对象。在任何一个Dictionary对象中，每个键至多与一个值相关联。Map是key-value键值对接口。
Hashtable采用拉链法实现哈希表，它定义了几个重要的参数：table、count、threshold、loadFactor、modCount。
- table：为一个Entry[]数组类型，Entry代表了拉链的节点，每一个Entry代表了一个键值对，哈希表的key-value键值对都是存储在Entry数组中的。
- count：Hashtable的大小，注意这个大小并不是Hashtable的容器大小，而是它所包含Entry键值对的数量。
- threshold：Hashtable的阈值，用于判断是否需要调整Hashtable的容量。threshold的值=容量*加载因子。
- loadFactor：加载因子。
- modCount：用来实现fail-fast机制的。所谓快速失败就是在并发集合中，其进行迭代操作时，若有其它线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出ConcurrentModificationException异常，而不是等到迭代完成之后才告诉你出错了。
构造方法
-
默认构造函数，容量为11，加载因子为0.75。
public Hashtable() { this(11, 0.75f); } -
用指定初始容量和默认的加载因子（0.75）构造一个新的空哈希表。
public Hashtable(int initialCapacity) { this(initialCapacity, 0.75f); } -
用指定初始容量和指定加载因子构造一个新的空哈希表。
public Hashtable(int initialCapacity, float loadFactor) { //验证初始容量 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); //验证加载因子 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal Load: "+loadFactor); if (initialCapacity==0) initialCapacity = 1; this.loadFactor = loadFactor; //初始化table，获得大小为initialCapacity的table数组 table = new Entry[initialCapacity]; //计算阀值 threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1); } -
构造一个与给定的Map具有相同映射关系的新哈希表。
public Hashtable(Map<? extends K, ? extends V> t) { //设置table容器大小，其值==t.size * 2 + 1 this(Math.max(2*t.size(), 11), 0.75f); putAll(t); }
主要方法
put方法：将指定key映射到此哈希表中的指定value。注意这里键key和值value都不可为空。
public synchronized V put(K key, V value) {
// 确保value不为null
if (value == null) {
throw new NullPointerException();
}
/*
* 确保key在table[]是不重复的
* 处理过程：
* 1、计算key的hash值，确认在table[]中的索引位置
* 2、迭代index索引位置，如果该位置处的链表中存在一个一样的key，则替换其value，返回旧值
*/
Entry tab[] = table;
int hash = hash(key); //计算key的hash值
int index = (hash & 0x7FFFFFFF) % tab.length; //确认该key的索引位置
//迭代，寻找该key，替换
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) { //如果容器中的元素数量已经达到阀值，则进行扩容操作
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// 在索引位置处插入一个新的节点
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
//容器中元素+1
count++;
return null;
}
put方法的整个处理流程是：计算key的hash值，根据hash值获得key在table数组中的索引位置，然后迭代该key处的Entry链表（暂且理解为链表），若该链表中存在一个这样的key对象，那么就直接替换其value值即可。否则，需要进行扩容操作，并将该key-value节点插入到扩容后的index索引位置处。
Hashtable的扩容操作，在put方法中，如果需要向table[]中添加Entry元素，会首先进行容量校验，如果容量已经达到了阈值，Hashtable就会进行扩容处理rehash()，源码如下：
protected void rehash() {
int oldCapacity = table.length;
//元素
Entry<K,V>[] oldMap = table;
//新容量=旧容量 * 2 + 1
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
return;
newCapacity = MAX_ARRAY_SIZE;
}
//新建一个size = newCapacity 的HashTable
Entry<K,V>[] newMap = new Entry[newCapacity];
modCount++;
//重新计算阀值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
//将原来的元素拷贝到新的HashTable中
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}
在这个rehash()方法中可以看到容量扩大两倍+1，同时需要将原来Hashtable中的元素一一复制到新的Hashtable中，这个过程是比较消耗时间的，同时还需要重新计算index，毕竟容量已经变了。
如果初始值为11、加载因子默认0.75，那么这个时候阈值threshold为8，当容器中的元素达到8时，Hashtable进行一次扩容操作，容量=8*2+1=17，而阈值threshold=17×0.75=13，当容器元素再一次达到阈值时，Hashtable还会进行扩容操作，依次类推。
get方法就会比较简单，处理过程就是计算key的hash值，判断在table数组中的索引位置，然后迭代链表，匹配直到找到相对应key的value，若没有找到返回null。
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}
Hashtable的三种遍历方式
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
public class HashTableTest {
public static void main(String args[]){
Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("zhangsan", 22);
table.put("lisi", 33);
table.put("wangwu", 44);
//[1]Iterator遍历方式1--键值对遍历entrySet()
Iterator<Entry<String, Integer>> iter = table.entrySet().iterator();
while(iter.hasNext()){
Map.Entry<String, Integer> entry = (Map.Entry<String, Integer>)iter.next();
String key = entry.getKey();
int value = entry.getValue();
System.out.println("entrySet:"+key+" "+value);
}
System.out.println("====================================");
//[2]Iterator遍历方式2--key键的遍历
Iterator<String> iterator = table.keySet().iterator();
while(iterator.hasNext()){
String key = (String)iterator.next();
int value = table.get(key);
System.out.println("keySet:"+key+" "+value);
}
System.out.println("====================================");
//[3]通过Enumeration来遍历Hashtable
Enumeration<String> enu = table.keys();
while(enu.hasMoreElements()) {
System.out.println("Enumeration:"+table.keys()+" "+enu.nextElement());
}
}
}
输出结果：
entrySet:zhangsan 22
entrySet:lisi 33
entrySet:wangwu 44
====================================
keySet:zhangsan 22
keySet:lisi 33
keySet:wangwu 44
====================================
Enumeration:java.util.Hashtable$Enumerator@139a55 zhangsan
Enumeration:java.util.Hashtable$Enumerator@1db9742 lisi
Enumeration:java.util.Hashtable$Enumerator@106d69c wangwu
Hashtable与HashMap的区别详解
-
**继承的父类不同：**Hashtable的是Dictionary类，HashMap继承的是AbstractMap，但两者都实现了Map接口。
-
**是否允许null：**HahsMap可以允许存在一个null的key和任意个null的value，不过建议尽量避免这样使用null作为key，HashMap以null作为key时，总是存储在table数组的第一个节点上；Hashtable中的key和value都不允许为null。
在HashMap中，当get()方法返回null值时，可能是HashMap中没有该键，也可能是该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键，而应该用containsKey()方法来判断。
-
当HashMap遇到为null的key时，它会调用putForNullKey方法来进行处理。对于value没有进行任何处理，只要是对象都可以。
if (key == null) return putForNullKey(value); -
如果在Hashtable中有类似put(null,null)的操作，编译时可以通过，因为key和value都是Object类型，但运行时会抛出NullPointerException异常。
if (value == null) { throw new NullPointerException(); }
-
-
**Hashtable的方法是线程安全的，底层的每个方法都是用synchronize的，而HashMap的方法为线程不安全。**虽然HashMap不是线程安全的，但是它的效率会比Hashtable要好很多。当需要多线程操作的时候可以使用线程安全的ConcurrentHashMap。ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。
-
遍历不同：HashMap仅支持Iterator的遍历方式，Hashtable支持Iterator和Enumeration两种遍历方式。
-
HashMap的Iterator使用的是fail-fast迭代器，当有其它线程改变了HashMap的结构，将会抛出ConcurrentModificationException。
-
JDK8之前的版本中，Hashtable是没有fast-fail机制的。在JDK8及以后的版本中，Hashtable也是使用fast-fail的，源码如下：
if (expectedModCount != modCount) { throw new ConcurrentModificationException(); }modCount的使用类似于并发编程中的CAS技术，每次在发生增删改操作的时候，都会出现modCount++动作，而modCount可以理解为是当前Hashtable的状态。每发生一次操作，状态+1，主要是用于Hashtable等容器在迭代时，判断数据是否过时时使用的。尽管Hashtable采用了原生的同步锁来保护数据安全。但是在出现迭代数据的时候，则无法保证边迭代，边正确操作。于是使用这个值来标记状态。一旦在迭代的过程中状态发生了改变，则会快速抛出一个异常，终止迭代行为。
-
-
是否提供contains方法：
- HashMap把Hashtable的contains()方法去掉了，改成containsValue和containsKey，因为contains()方法容易让人引起误解；
- Hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同。
-
内部实现使用的数据初始化和扩容方式不同：
- 两者的默认负载因子都是0.75，但Hashtable扩容时，容量变为原来的2倍+1，HashMap扩容时，将容量变成原来的2倍；Hashtable在不制定容量的情况下默认容量是11，也就是说Hashtable会尽量使用素数，而HahMap的默认容量为16，Hashtable不要求底层数组的容量为2的整数次幂，而HashMap要求一定为2的整数次幂。
- 之所以会有这样的不同，是因为Hashtable和HashMap设计时的侧重点不同。Hashtable的侧重点是哈希的结果更加均匀，使得哈希冲突减少。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。而HashMap则更加关注hash的计算效率问题。在取模计算时，如果模数是2的幂，那么可以直接使用位运算来得到结果，效率要大大高于做除法。HashMap为了加快hash的速度，将哈希表的大小固定为了2的幂。当然这引入了哈希分布不均匀的问题，所以HashMap为解决这个问题，又对hash算法做了一些改动。这从而导致了Hashtable和HashMap的计算hash值的方法不同。
-
hash值不同：
-
Hashtable直接使用Object的hashCode()，hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值，然后再使用取模来获得最终的位置。这里一般先用hash&0x7FFFFFFF后，再对length取模，&0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而hash&0x7FFFFFFF后，只有符号位改变，而后面的位都不变。Hashtable在计算元素的位置时需要进行一次除法运算，而除法运算是比较耗时的。
int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; -
为了提高计算效率，HashMap将哈希表的大小固定为了2的幂，这样在取模运算时，不需要做除法，只需要做位运算。位运算比除法的效率要高很多。HashMap的效率虽然提高了，但是hash冲突也增加了。因为它得出的hash值的低位相同的概率比较高。而计算位运算为了解决这个问题，HashMap重新根据hashCode计算hash值后，又对hash值做了一些运算来打散数据，使得取得的位置更加分散，从而减少了hash冲突。为了高效，HashMap只做了一些简单的位处理，从而不至于把使用2的幂次方带来的效率提升给抵消掉。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
-
Map常用遍历方式以及性能对比
详情请阅读此博客：Map常用遍历方式 以及 性能对比_张维鹏的博客-CSDN博客
Map总结
详情请阅读此博客：Map总结_张维鹏的博客-CSDN博客
HashSet
对于HashSet而言，它是基于HashMap来实现的，底层采用HashMap来保存元素。HashSet存储元素的顺序并不是按照存入顺序，是按照哈希值来存的，所以取数据也是按照哈希值来取的。HashSet集合元素不能是NULL（键可以为空）。
定义：
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
HashSet继承AbstractSet类，实现Set、Cloneable、Serializable接口。其中AbstractSet提供Set接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。Set接口是一种不包括重复元素的Collection，它维持它自己的内部排序，所以随机访问没有任何意义。
基本属性：
//基于HashMap实现，底层使用HashMap保存所有元素
private transient HashMap<E,Object> map;
//定义一个Object对象作为HashMap的value
private static final Object PRESENT = new Object();
构造函数：
/**
* 默认构造函数
* 初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。
*/
public HashSet() {
map = new HashMap<>();
}
/**
* 构造一个包含指定 collection 中的元素的新 set。
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
* 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和指定的加载因子
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
/**
* 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和默认的加载因子（0.75）。
*/
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
/**
* 在API中我没有看到这个构造函数，今天看源码才发现（原来访问权限为包权限，不对外公开的）
* 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
* dummy 为标识 该构造函数主要作用是对LinkedHashSet起到一个支持作用
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
HashSet所有的构造函数都是构造出一个新的HashMap，其中最后一个构造函数，为包访问权限是不对外公开的，仅仅只在使用LinkedHashSet时才会发生作用。
方法：
-
Iterator()方法：返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。底层调用HashMap的keySet返回所有的key，这点反应了HashSet中的所有元素都是保存在HashMap的key中，value则是使用的PRESENT对象，该对象为static final。
public Iterator<E> iterator() { return map.keySet().iterator(); } -
size()：返回此set中的元素的数量(set的容量)。底层调用HashMap的size方法，返回HashMap容器的大小。
public int size() { return map.size(); } -
isEmpty()：判断HashSet集合是否为空，为空返回true，否则返回false。
public boolean isEmpty() { return map.isEmpty(); } -
contains()：判断某个元素是否存在于HashSet()中，存在返回true，否则返回false。更加确切的讲应该是要满足这种关系才能返回true：(o==null ? e==null : o.equals(e))。底层调用containsKey判断HashMap的key值是否为空。
public boolean contains(Object o) { return map.containsKey(o); } -
add()：如果此set中尚未包含指定元素，则添加指定元素。如果此set没有包含满足(e==null ? e2==null : e.equals(e2)) 的e2时，则将e2添加到Set中，否则不添加且返回false。由于底层使用HashMap的put方法将key=e，value=PRESENT构建成key-value键值对，当此e存在于HashMap的key中，则value将会覆盖原有的value，但是key保持不变。所以如果将一个已经存在的e元素添加到HashSet中，新添加的元素是不会保存到HashMap中，所以这就满足了HashSet中元素不会重复的特性。
public boolean add(E e) { return map.put(e, PRESENT)==null; } -
remove：如果指定元素存在于此set中，则将其移除。底层使用HashMap的remove方法删除指定的Entry。
public boolean remove(Object o) { return map.remove(o)==PRESENT; } -
clear：从此set中移除所有元素。底层调用HashMap的clear方法清除所有的Entry。
public void clear() { map.clear(); } -
clone：返回此HashSet实例的浅表副本，并没有复制这些元素本身。
public Object clone() { try { HashSet<E> newSet = (HashSet<E>) super.clone(); newSet.map = (HashMap<E, Object>) map.clone(); return newSet; } catch (CloneNotSupportedException e) { throw new InternalError(); } }
参考：
fail-fast机制与fail-safe
“快速失败”也就是fail-fast，它是Java集合的一种错误检查机制。当多个线程对集合进行结构上的改变操作时，有可能会产生fail-fast机制。记住是有可能，而不是一定。例如，假设存在线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出ConcurrentModificationException异常，从而产生fail-fast机制。
fail-fast示例
public class FailFastTest {
private static List<Integer> list = new ArrayList<>();
/**
* @desc:线程one迭代list
*/
private static class threadOne extends Thread{
public void run() {
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
int i = iterator.next();
System.out.println("ThreadOne 遍历:" + i);
try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
/**
* @desc:当i == 3时，修改list
*/
private static class threadTwo extends Thread{
public void run(){
int i = 0 ;
while(i < 6){
System.out.println("ThreadTwo run：" + i);
if(i == 3){
list.remove(i);
}
i++;
}
}
}
public static void main(String[] args) {
for(int i = 0 ; i < 10;i++){
list.add(i);
}
new threadOne().start();
new threadTwo().start();
}
}
运行结构：
ThreadOne 遍历:0
ThreadTwo run：0
ThreadTwo run：1
ThreadTwo run：2
ThreadTwo run：3
ThreadTwo run：4
ThreadTwo run：5
Exception in thread "Thread-0" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
at java.util.ArrayList$Itr.next(Unknown Source)
at test.ArrayListTest$threadOne.run(ArrayListTest.java:23)
fail-fast产生的原因
通过上面的示例和讲解，初步知道fail-fast产生的原因就在于程序在对Collection进行迭代时，某个线程对该collection在结构上对其做了修改，这时迭代器就会抛出ConcurrentModificationException异常，从而产生fail-fast。
要了解fail-fast机制，首先要对ConcurrentModificationException异常有所了解。当方法检测到对象的并发修改，但又不允许这种修改时就抛出该异常。同时需要注意的是，该异常不会始终指出对象已经由不同线程并发修改，如果单线程违反了规则，同样也有可能会抛出该异常。
诚然，迭代器的快速失败行为无法得到保证，它不能保证一定会出现该错误，但是快速失败操作会尽最大努力抛出此异常，所以因此，为提高此类操作的正确性而编写一个依赖于此异常的程序是错误的做法，正确做法是将此异常仅用于检测bug。
fail-fast是在操作迭代器时产生的，现在来看看ArrayList中迭代器的源代码：
private class Itr implements Iterator<E> {
int cursor;
int lastRet = -1;
int expectedModCount = ArrayList.this.modCount;
public boolean hasNext() {
return (this.cursor != ArrayList.this.size);
}
public E next() {
checkForComodification();
/** 省略此处代码 */
}
public void remove() {
if (this.lastRet < 0)
throw new IllegalStateException();
checkForComodification();
/** 省略此处代码 */
}
final void checkForComodification() {
if (ArrayList.this.modCount == this.expectedModCount)
return;
throw new ConcurrentModificationException();
}
}
从以上的源码可以看出，迭代器在调用next()、remove()方法时都是调用checkForComodification()方法，该方法主要就是检测modCount==expectedModCount？若不等则抛出ConcurrentModificationException 异常，从而产生fail-fast机制，所以要弄清楚为什么会产生fail-fast机制，那就必须要弄明白为什么modCount != expectedModCount，它们的值在什么时候发生了改变。
expectedModCount是在Itr中定义的：int expectedModCount = ArrayList.this.modCount;所以它的值是不可能会修改的，所以会变的就是modCount。modCount是在AbstractList中定义的，为全局变量：
protected transient int modCount = 0;
再看看ArrayList的源码：
public boolean add(E paramE) {
ensureCapacityInternal(this.size + 1);
/** 省略此处代码 */
}
private void ensureCapacityInternal(int paramInt) {
if (this.elementData == EMPTY_ELEMENTDATA)
paramInt = Math.max(10, paramInt);
ensureExplicitCapacity(paramInt);
}
private void ensureExplicitCapacity(int paramInt) {
this.modCount += 1; //修改modCount
/** 省略此处代码 */
}
public boolean remove(Object paramObject) {
int i;
if (paramObject == null)
for (i = 0; i < this.size; ++i) {
if (this.elementData[i] != null)
continue;
fastRemove(i);
return true;
}
else
for (i = 0; i < this.size; ++i) {
if (!(paramObject.equals(this.elementData[i])))
continue;
fastRemove(i);
return true;
}
return false;
}
private void fastRemove(int paramInt) {
this.modCount += 1; //修改modCount
/** 省略此处代码 */
}
public void clear() {
this.modCount += 1; //修改modCount
/** 省略此处代码 */
}
从上面的源代码可以看出，ArrayList中无论add、remove、clear方法只要是涉及了改变ArrayList元素的个数的方法都会导致modCount的改变。所以这里可以初步判断由于expectedModCount的值与modCount的改变不同步，导致两者之间不等从而产生fail-fast机制。
fail-fast解决办法
- 在遍历过程中所有涉及到改变modCount值的地方全部加上Synchronize或者直接使用CollectionSynchronizedList，这样就可以解决问题，但是不推荐，因为增删造成的同步锁可能会阻塞遍历操作。
- 使用CopyOnWriteArrayList替换ArrayList，推荐使用该方案（即fail-safe）。
CopyOnWriteArrayList是ArrayList的一个线程安全的变体，其中所有可变的操作都是通过对底层数组进行一次新的复制来实现的。该类产生的开销比较大，但是在两种情况下，它非常适合使用。
- 在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时。
- 当遍历操作的数量远远超过可变操作的数量时。
那么为什么CopyOnWriteArrayList可以替代ArrayList呢？
- CopyOnWriteArrayList无论是从数据结构、定义都和ArrayList一样。同样是实现List接口，底层使用数组实现。在方法上也包含add、remove、clear等方法。
- CopyOnWriteArrayList根本不会产生CopyOnWriteArrayList异常，也就是它使用迭代器完全不会产生fail-fast机制。
private static class COWIterator<E> implements ListIterator<E> {
/** 省略此处代码 */
public E next() {
if (!(hasNext()))
throw new NoSuchElementException();
return this.snapshot[(this.cursor++)];
}
/** 省略此处代码 */
}
CopyOnWriteArrayList的方法根本就没有像ArrayList中使用checkForComodification方法来判断expectedModCount与modCount是否相等。以其Add方法为例说明：
public boolean add(E paramE) {
ReentrantLock localReentrantLock = this.lock;
localReentrantLock.lock();
try {
Object[] arrayOfObject1 = getArray();
int i = arrayOfObject1.length;
Object[] arrayOfObject2 = Arrays.copyOf(arrayOfObject1, i + 1);
arrayOfObject2[i] = paramE;
setArray(arrayOfObject2);
int j = 1;
return j;
} finally {
localReentrantLock.unlock();
}
}
final void setArray(Object[] paramArrayOfObject) {
this.array = paramArrayOfObject;
}
CopyOnWriterArrayList的add方法与ArrayList的add方法有一个最大的不同点就在于，下面三句代码：
Object[] arrayOfObject2 = Arrays.copyOf(arrayOfObject1, i + 1);
arrayOfObject2[i] = paramE;
setArray(arrayOfObject2);
此代码所展示的魅力就在于copy原来的array，再在copy数组上进行add操作，这样做就完全不会影响COWIterator中的array了。
所以，CopyOnWriterArrayList所代表的核心概念就是：任何对array在结构上有所改变的操作（add、remove、clear等），CopyOnWriterArrayList都会copy现有的数据，再在copy的数据上修改，这样就不会影响COWIterator中的数据了，修改完成之后改变原有数据的引用即可。同时这样造成的代价就是产生大量的对象，同时数组的copy也是相当有损耗的。
fail-safe机制
- fail-safe中任何对集合结构的修改都会在一个复制的集合上进行，因此不会抛出ConcurrentModificationException。
- fail-safe机制需要复制集合，产生大量的无效对象，开销大。无法保证读取到的数据是目前原始结构中的数据。
fail-safe例子：
import java.util.concurrent.ConcurrentHashMap;
import java.util.Iterator;
public class FailSafeExample
{
public static void main(String[] args)
{
ConcurrentHashMap<String,String> premiumPhone =
new ConcurrentHashMap<String,String>();
premiumPhone.put("Apple", "iPhone");
premiumPhone.put("HTC", "HTC one");
premiumPhone.put("Samsung","S5");
Iterator iterator = premiumPhone.keySet().iterator();
while (iterator.hasNext())
{
System.out.println(premiumPhone.get(iterator.next()));
premiumPhone.put("Sony", "Xperia Z");
}
}
}
运行结果：
S5
HTC one
iPhone
fail-fast和fail-safe的区别：
| Fail Fast Iterator | Fail Safe Iterator | |
|---|---|---|
| Throw ConcurrentModification Exception | Yes | No |
| Clone object | No | Yes |
| Memory Overhead | No | Yes |
参考：
fail-fast机制 与 fail-safe_张维鹏的博客-CSDN博客
集合之间的区别
详情请阅读此博客：ArrayList与LinkedList、Vector的区别 && HashMap与HashTable、HashSet的区别_张维鹏的博客-CSDN博客
京公网安备 11010502036488号