共计 41056 个字符，预计需要花费 103 分钟才能阅读完成。
作为一位小菜”一面面试官“，面试过程中，我必定会问 Java 汇合的内容，同时作为求职者，也必定会被问到汇合，所以整顿下 Java 汇合面试题
说说常见的汇合有哪些吧？
HashMap 说一下，其中的 Key 须要重写 hashCode()和 equals()吗？
HashMap 中 key 和 value 能够为 null 吗？容许几个为 null 呀？
HashMap 线程平安吗?ConcurrentHashMap 和 hashTable 有什么区别？
List 和 Set 说一下，当初有一个 ArrayList，对其中的所有元素依照某一属性大小排序，应该怎么做？
ArrayList 和 Vector 的区别
list 能够删除吗，遍历的时候能够删除吗，为什么
面向对象语言对事物的体现都是以对象的模式，所以为了不便对多个对象的操作，须要将对象进行存储，汇合就是存储对象最罕用的一种形式，也叫容器。
从下面的汇合框架图能够看到，Java 汇合框架次要包含两种类型的容器
- 一种是汇合（Collection），存储一个元素汇合
- 另一种是图（Map），存储键 / 值对映射。
Collection 接口又有 3 种子类型，List、Set 和 Queue，再上面是一些抽象类，最初是具体实现类，罕用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。
汇合框架是一个用来代表和操纵汇合的对立架构。所有的汇合框架都蕴含如下内容：
- 接口：是代表汇合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口，是为了以不同的形式操作汇合对象
- 实现（类）：是汇合接口的具体实现。从实质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。
- 算法：是实现汇合接口的对象里的办法执行的一些有用的计算，例如：搜寻和排序。这些算法被称为多态，那是因为雷同的办法能够在类似的接口上有着不同的实现。
说说罕用的汇合有哪些吧？
Map 接口和 Collection 接口是所有汇合框架的父接口：
- Collection 接口的子接口包含：Set、List、Queue
- List 是有序的容许有反复元素的 Collection，实现类次要有：ArrayList、LinkedList、Stack 以及 Vector 等
- Set 是一种不蕴含反复元素且无序的 Collection，实现类次要有：HashSet、TreeSet、LinkedHashSet 等
- Map 没有继承 Collection 接口，Map 提供 key 到 value 的映射。实现类次要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap 以及 Properties 等
ArrayList 和 Vector 的区别
相同点：
-
ArrayList 和 Vector 都是继承了雷同的父类和实现了雷同的接口（都实现了 List，有序、容许反复和 null）
extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable - 底层都是数组（Object[]）实现的
- 初始默认长度都为10
不同点：
- 同步性：Vector 中的 public 办法少数增加了 synchronized 关键字、以确保办法同步、也即是 Vector 线程平安、ArrayList 线程不平安
- 性能：Vector 存在 synchronized 的锁期待状况、须要期待开释锁这个过程、所以性能绝对较差
-
扩容大小：ArrayList 在底层数组不够用时在原来的根底上扩大 0.5 倍，Vector 默认是扩大 1 倍
扩容机制，扩容办法其实就是新创建一个数组，而后将旧数组的元素都复制到新数组外面。其底层的扩容办法都在 grow() 中（基于 JDK8）
-
ArrayList 的 grow()，在满足扩容条件时、ArrayList 以1.5 倍的形式在扩容（oldCapacity >> 1，右移运算，相当于除以 2，后果为二分之一的 oldCapacity）
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //newCapacity = oldCapacity + O.5*oldCapacity, 此处扩容 0.5 倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } -
Vector 的 grow()，Vector 比 ArrayList 多一个属性，扩大因子 capacityIncrement，能够扩容大小。当扩容容量增量大于 0 时、新数组长度为原数组长度 + 扩容容量增量、否则新数组长度为原数组长度的 2 倍
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
-
ArrayList 与 LinkedList 区别
- 是否保障线程平安：ArrayList 和 LinkedList 都是不同步的，也就是不保障线程平安；
- 底层数据结构 ：Arraylist 底层应用的是 Object 数组；LinkedList 底层应用的是 双向循环链表 数据结构；
-
插入和删除是否受元素地位的影响：
- ArrayList 采纳数组存储，所以插入和删除元素的工夫复杂度受元素地位的影响。 比方：执行
add(E e)办法的时候，ArrayList 会默认在将指定的元素追加到此列表的开端，这种状况工夫复杂度就是 O(1)。然而如果要在指定地位 i 插入和删除元素的话（add(intindex,E element)）工夫复杂度就为 O(n-i)。因为在进行上述操作的时候汇合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位 / 向前移一位的操作。 - LinkedList 采纳链表存储，所以插入，删除元素工夫复杂度不受元素地位的影响，都是近似 $O(1)$，而数组为近似 $O(n)$。
- ArrayList 个别利用于查问较多但插入以及删除较少状况，如果插入以及删除较多则倡议应用 LinkedList
- ArrayList 采纳数组存储，所以插入和删除元素的工夫复杂度受元素地位的影响。 比方：执行
- 是否反对疾速随机拜访 ：LinkedList 不反对高效的随机元素拜访，而 ArrayList 实现了 RandomAccess 接口，所以有随机拜访性能。疾速随机拜访就是通过元素的序号疾速获取元素对象(对应于
get(intindex)办法)。 - 内存空间占用：ArrayList 的空间节约次要体现在在 list 列表的结尾会预留肯定的容量空间，而 LinkedList 的空间破费则体现在它的每一个元素都须要耗费比 ArrayList 更多的空间（因为要寄存间接后继和间接前驱以及数据）。
高级工程师的我，可不得看看源码，具体分析下：
- ArrayList 工作原理其实很简略，底层是动静数组，每次创立一个 ArrayList 实例时会调配一个初始容量（没有指定初始容量的话，默认是 10），以 add 办法为例，如果没有指定初始容量，当执行 add 办法，先判断以后数组是否为空，如果为空则给保留对象的数组调配一个最小容量，默认为 10。当增加大容量元素时，会先减少数组的大小，以进步增加的效率；
- LinkedList 是有序并且反对元素反复的汇合，底层是基于双向链表的，即每个节点既蕴含指向其后继的援用也包含指向其前驱的援用。链表无容量限度，但双向链表自身应用了更多空间，也须要额定的链表指针操作。按下标拜访元素
get(i)/set(i,e)要喜剧的遍历链表将指针挪动到位 (如果 i > 数组大小的一半，会从开端移起)。插入、删除元素时批改前后节点的指针即可，但还是要遍历局部链表的指针能力挪动到下标所指的地位，只有在链表中间的操作add()，addFirst()，removeLast()或用iterator()上的remove()能省掉指针的挪动。此外 LinkedList 还实现了 Deque（继承自 Queue 接口）接口，能够当做队列应用。
不会囊括所有办法，只是为了学习，记录思维。
ArrayList 和 LinkedList 两者都实现了 List 接口
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable结构器
ArrayList 提供了 3 个结构器，①无参结构器 ②带初始容量结构器 ③参数为汇合结构器
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{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);
}
}
public ArrayList() {
// 默认为空数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {//...}
}LinkedList 提供了 2 个结构器，因为基于链表，所以也就没有初始化大小，也没有扩容的机制，就是始终在后面或者前面插插插~~
public LinkedList() {}
public LinkedList(Collection<? extends E> c) {this();
addAll(c);
}
// LinkedList 既然作为链表，那么必定会有节点
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;
}
}插入
ArrayList:
public boolean add(E e) {
// 确保数组的容量，保障能够增加该元素
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将该元素放入数组中
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 如果数组是空的，那么会初始化该数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// DEFAULT_CAPACITY 为 10, 所以调用无参默认 ArrayList 构造方法初始化的话，默认的数组容量为 10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 确保数组的容量，如果不够的话，调用 grow 办法扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 扩容具体的办法
private void grow(int minCapacity) {
// 以后数组的容量
int oldCapacity = elementData.length;
// 新数组扩容为原来容量的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新数组扩容容量还是比起码须要的容量还要小的话，就设置裁减容量为最小须要的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 判断新数组容量是否曾经超出最大数组范畴，MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
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);
}当然也能够插入指定地位，还有一个重载的办法 add(int index, E element)
public void add(int index, E element) {
// 判断 index 有没有超出索引的范畴
rangeCheckForAdd(index);
// 和之前的操作是一样的，都是保障数组的容量足够
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将指定地位及其前面数据向后挪动一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将该元素增加到指定的数组地位
elementData[index] = element;
// ArrayList 的大小扭转
size++;
}能够看到每次插入指定地位都要挪动元素，效率较低。
再来看 LinkedList 的插入，也有插入开端，插入指定地位两种，因为基于链表，必定得先有个 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;
}
}public boolean add(E e) {
// 间接往队尾加元素
linkLast(e);
return true;
}
void linkLast(E e) {
// 保留原来链表尾部节点，last 是全局变量，用来示意队尾元素
final Node<E> l = last;
// 为该元素 e 新建一个节点
final Node<E> newNode = new Node<>(l, e, null);
// 将新节点设为队尾
last = newNode;
// 如果原来的队尾元素为空，那么阐明原来的整个列表是空的，就把新节点赋值给头结点
if (l == null)
first = newNode;
else
// 原来尾结点的前面为新生成的结点
l.next = newNode;
// 节点数 +1
size++;
modCount++;
}
public void add(int index, E element) {
// 查看 index 有没有超出索引范畴
checkPositionIndex(index);
// 如果追加到尾部，那么就跟 add(E e) 一样了
if (index == size)
linkLast(element);
else
// 否则就是插在其余地位
linkBefore(element, node(index));
}
//linkBefore 办法中调用了这个 node 办法，相似二分查找的优化
Node<E> node(int index) {// assert isElementIndex(index);
// 如果 index 在前半段，从前往后遍历获取 node
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 如果 index 在后半段，从后往前遍历获取 node
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 保留 index 节点的前节点
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++;
}获取
ArrayList 的 get() 办法很简略，就是在数组中返回指定地位的元素即可，所以效率很高
public E get(int index) {
// 查看 index 有没有超出索引的范畴
rangeCheck(index);
// 返回指定地位的元素
return elementData(index);
}LinkedList 的 get() 办法，就是在外部调用了上边看到的 node() 办法，判断在前半段还是在后半段，而后遍历失去即可。
public E get(int index) {checkElementIndex(index);
return node(index).item;
}HashMap 的底层实现
什么时候会应用 HashMap？他有什么特点？
你晓得 HashMap 的工作原理吗？
你晓得 get 和 put 的原理吗？equals()和 hashCode()的都有什么作用？
你晓得 hash 的实现吗？为什么要这样实现？
如果 HashMap 的大小超过了负载因子 (load factor) 定义的容量，怎么办？
HashMap 在 JDK 7 和 JDK8 中的实现形式略有不同。离开记录。
深刻 HahsMap 之前，先要理解的概念
-
initialCapacity：初始容量。指的是 HashMap 汇合初始化的时候本身的容量。能够在构造方法中指定；如果不指定的话，总容量默认值是 16。须要留神的是初始容量必须是 2 的幂次方。（1.7 中，已知 HashMap 中将要寄存的 KV 个数的时候，设置一个正当的初始化容量能够无效的进步性能）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 - size：以后 HashMap 中曾经存储着的键值对数量，即
HashMap.size()。 - loadFactor：加载因子。所谓的加载因子就是 HashMap (以后的容量 / 总容量) 达到肯定值的时候，HashMap 会施行扩容。加载因子也能够通过构造方法中指定，默认的值是 0.75。举个例子，假如有一个 HashMap 的初始容量为 16，那么扩容的阀值就是 0.75 * 16 = 12。也就是说，在你打算存入第 13 个值的时候，HashMap 会先执行扩容。
- threshold：扩容阀值。即 扩容阀值 = HashMap 总容量 * 加载因子。以后 HashMap 的容量大于或等于扩容阀值的时候就会去执行扩容。扩容的容量为以后 HashMap 总容量的两倍。比方，以后 HashMap 的总容量为 16，那么扩容之后为 32。
- table：Entry 数组。咱们都晓得 HashMap 外部存储 key/value 是通过 Entry 这个介质来实现的。而 table 就是 Entry 数组。
JDK1.7 实现
JDK1.7 中 HashMap 由 数组 + 链表 组成（“链表散列” 即数组和链表的结合体），数组是 HashMap 的主体，链表则是次要为了解决哈希抵触而存在的（HashMap 采纳 “拉链法也就是链地址法” 解决抵触），如果定位到的数组地位不含链表（以后 entry 的 next 指向 null），那么对于查找，增加等操作很快，仅需一次寻址即可；如果定位到的数组蕴含链表，对于增加操作，其工夫复杂度仍然为 O(1)，因为最新的 Entry 会插入链表头部，即须要简略扭转援用链即可，而对于查找操作来讲，此时就须要遍历链表，而后通过 key 对象的 equals 办法逐个比对查找。
所谓 “拉链法” 就是将链表和数组相结合。也就是说创立一个链表数组，数组中每一格就是一个链表。若遇到哈希抵触，则将抵触的值加到链表中即可。
源码解析
构造方法
《阿里巴巴 Java 开发手册》举荐汇合初始化时，指定汇合初始值大小。（阐明：HashMap 应用 HashMap(int initialCapacity) 初始化）倡议起因：https://www.zhihu.com/question/314006228/answer/611170521
// 默认的构造方法应用的都是默认的初始容量和加载因子
// DEFAULT_INITIAL_CAPACITY = 16，DEFAULT_LOAD_FACTOR = 0.75f
public HashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 能够指定初始容量，并且应用默认的加载因子
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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;
threshold = initialCapacity;
// 空办法
init();}
public HashMap(Map<? extends K, ? extends V> m) {this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}HashMap 的前 3 个构造方法最初都会去调用 HashMap(int initialCapacity, float loadFactor)。在其外部去设置初始容量和加载因子。而最初的 init() 是空办法，次要给子类实现，比方 LinkedHashMap。
put() 办法
public V put(K key, V value) {
// 如果 table 数组为空时先创立数组，并且设置扩容阀值
if (table == EMPTY_TABLE) {inflateTable(threshold);
}
// 如果 key 为空时，调用 putForNullKey 办法非凡解决
if (key == null)
return putForNullKey(value);
// 计算 key 的哈希值
int hash = hash(key);
// 依据计算出来的哈希值和以后数组的长度计算在数组中的索引
int i = indexFor(hash, table.length);
// 先遍历该数组索引下的整条链表
// 如果该 key 之前曾经在 HashMap 中存储了的话，间接替换对应的 value 值即可
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 先判断 hash 值是否一样，如果一样，再判断 key 是否一样，不同对象的 hash 值可能一样
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 如果该 key 之前没有被存储过，那么就进入 addEntry 办法
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
// 以后容量大于或等于扩容阀值的时候，会执行扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
// 扩容为原来容量的两倍
resize(2 * table.length);
// 从新计算哈希值
hash = (null != key) ? hash(key) : 0;
// 重新得到在新数组中的索引
bucketIndex = indexFor(hash, table.length);
}
// 创立节点
createEntry(hash, key, value, bucketIndex);
}
// 扩容，创立了一个新的数组，而后把数据全副复制过来，再把新数组的援用赋给 table
void resize(int newCapacity) {Entry[] oldTable = table; // 援用扩容前的 Entry 数组
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {// 扩容前的数组大小如果曾经达到最大 (2^30) 了
threshold = Integer.MAX_VALUE; // 批改阈值为 int 的最大值(2^31-1)，这样当前就不会扩容了
return;
}
// 创立新的 entry 数组
Entry[] newTable = new Entry[newCapacity];
// 将旧 entry 数组中的数据复制到新 entry 数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 将新数组的援用赋给 table
table = newTable;
// 计算新的扩容阀值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable) {Entry[] src = table; //src 援用了旧的 Entry 数组
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { // 遍历旧的 Entry 数组
Entry<K,V> e = src[j]; // 获得旧 Entry 数组的每个元素
if (e != null) {src[j] = null;// 开释旧 Entry 数组的对象援用（for 循环后，旧的 Entry 数组不再援用任何对象）do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); //！！从新计算每个元素在数组中的地位
e.next = newTable[i]; // 标记[1]
newTable[i] = e; // 将元素放在数组上
e = next; // 拜访下一个 Entry 链上的元素
} while (e != null);
}
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
// 取出 table 中下标为 bucketIndex 的 Entry
Entry<K,V> e = table[bucketIndex];
// 利用 key、value 来构建新的 Entry
// 并且之前寄存在 table[bucketIndex]处的 Entry 作为新 Entry 的 next
// 把新创建的 Entry 放到 table[bucketIndex]地位
table[bucketIndex] = new Entry<>(hash, key, value, e);
// 以后 HashMap 的容量加 1
size++;
}最初的 createEntry() 办法就阐明了当 hash 抵触时，采纳的拉链法来解决 hash 抵触的，并且是把新元素插入到单链表的表头。
get() 办法
public V get(Object key) {
// 如果 key 是空的，就调用 getForNullKey 办法非凡解决
if (key == null)
return getForNullKey();
// 获取 key 绝对应的 entry
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();}
// 找到对应 key 的数组索引，而后遍历链表查找即可
final Entry<K,V> getEntry(Object key) {if (size == 0) {return null;}
// 计算 key 的哈希值
int hash = (key == null) ? 0 : hash(key);
// 失去数组的索引，而后遍历链表，查看是否有雷同 key 的 Entry
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
// 没有的话，返回 null
return null;
}JDK1.8 实现
JDK 1.7 中，如果哈希碰撞过多，拉链过长，极其状况下，所有值都落入了同一个桶内，这就进化成了一个链表。通过 key 值查找要遍历链表，效率较低。JDK1.8 在解决哈希抵触时有了较大的变动，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以缩小搜寻工夫。
TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺点，因为二叉查找树在某些状况下会进化成一个线性构造。
源码解析
构造方法
JDK8 构造方法改变不是很大
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}确定哈希桶数组索引地位（hash 函数的实现）
// 办法一：static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 为第一步 取 hashCode 值
// h ^ (h >>> 16) 为第二步 高位参加运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 办法二：static int indexFor(int h, int length) {//jdk1.7 的源码，jdk1.8 没有提取这个办法，而是放在了其余办法中，比方 put 的 p = tab[i = (n - 1) & hash]
return h & (length-1); // 第三步 取模运算
}HashMap 定位数组索引地位，间接决定了 hash 办法的离散性能。Hash 算法实质上就是三步：取 key 的 hashCode 值、高位运算、取模运算。
为什么要这样呢？
HashMap 的长度为什么是 2 的幂次方?
目标当然是为了缩小哈希碰撞，使 table 里的数据分布的更平均。
-
HashMap 中桶数组的大小 length 总是 2 的幂，此时，
h & (table.length -1)等价于对 length 取模h%length。但取模的计算效率没有位运算高，所以这是是一个优化。假如h = 185，table.length-1 = 15(0x1111)，其实散列真正失效的只是低 4bit 的无效位，所以很容易碰撞。 -
图中的 hash 是由键的 hashCode 产生。计算余数时，因为 n 比拟小，hash 只有低 4 位参加了计算，高位的计算能够认为是有效的。这样导致了计算结果只与低位信息无关，高位数据没发挥作用。为了解决这个缺点，咱们能够上图中的 hash 高 4 位数据与低 4 位数据进行异或运算，即
hash ^ (hash >>> 4)。通过这种形式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参加到计算中。此时的计算过程如下：在 Java 中，hashCode 办法产生的 hash 是 int 类型，32 位宽。前 16 位为高位，后 16 位为低位，所以要右移 16 位，即
hash ^ (hash >>> 16)。这样还减少了 hash 的复杂度，进而影响 hash 的散布性。
HashMap 的长度为什么是 2 的幂次方？
为了能让 HashMap 存取高效，尽量减少碰撞，也就是要尽量把数据调配平均，Hash 值的范畴是 -2147483648 到 2147483647，前后加起来有 40 亿的映射空间，只有哈希函数映射的比拟平均涣散，个别利用是很难呈现碰撞的，但一个问题是 40 亿的数组内存是放不下的。所以这个散列值是不能间接拿来用的。用之前须要先对数组长度取模运算，失去余数能力用来寄存地位也就是对应的数组小标。这个数组下标的计算方法是 (n-1)&hash，n 代表数组长度。
这个算法应该如何设计呢？
咱们首先可能会想到采纳 % 取余的操作来实现。然而，重点来了。
取余操作中如果除数是 2 的幂次则等价于其除数减一的与操作，也就是说 hash%length=hash&(length-1)，但前提是 length 是 2 的 n 次方，并且采纳 & 运算比 % 运算效率高，这也就解释了 HashMap 的长度为什么是 2 的幂次方。
get() 办法
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) {
// 如果 first 是 TreeNode 类型，则调用黑红树查找办法
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;
}put() 办法
public V put(K key, V value) {// 对 key 的 hashCode()做 hash
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
// tab 为空则创立
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算 index，并对 null 做解决
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 节点 key 存在，间接笼罩 value
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) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
// 链表长度大于 8 转换为红黑树进行解决
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key 曾经存在间接笼罩 value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超过最大容量 就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}HashMap 的 put 办法的具体流程？
①. 判断键值对数组 table[i]是否为空或为 null，否则执行 resize()进行扩容；
②. 依据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i]==null，间接新建节点增加，转向⑥，如果 table[i]不为空，转向③；
③. 判断 table[i]的首个元素是否和 key 一样，如果雷同间接笼罩 value，否则转向④，这里的雷同指的是 hashCode 以及 equals；
④. 判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则间接在树中插入键值对，否则转向⑤；
⑤. 遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 曾经存在间接笼罩 value 即可；
⑥. 插入胜利后，判断理论存在的键值对数量 size 是否超多了最大容量 threshold，如果超过，进行扩容。
resize() 扩容
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) {// 批改阈值为 int 的最大值(2^31-1)，这样当前就不会扩容了
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值，就裁减为原来的 2 倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的 resize 下限
if (newThr == 0) {float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 开始复制到新的数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 把每个 bucket 都挪动到新的 buckets 中
if (oldTab != null) {
// 循环遍历旧的 table 数组
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);
// 遍历链表，将原链表节点分成 lo 和 hi 两个链表
// 其中 lo 示意在原来的桶地位，hi 示意在新的桶地位
else { // preserve order 链表优化重 hash 的代码块
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;
}
// 原索引 +oldCap
else {if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到 bucket 里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引 +oldCap 放到 bucket 里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}HashMap 的扩容操作是怎么实现的？
- 在 jdk1.8 中，resize 办法是在 HashMap 中的键值对大于阀值时或者初始化时，就调用 resize 办法进行扩容；
- 每次扩大的时候，都是扩大 2 倍；
- 扩大后 Node 对象的地位要么在原地位，要么挪动到原偏移量两倍的地位。
在 putVal() 中，咱们看到在这个函数外面应用到了 2 次 resize() 办法，resize() 办法示意在进行第一次初始化时会对其进行扩容，或者当该数组的理论大小大于其扩容阈值（第一次为 0.75 * 16 = 12），这个时候在扩容的同时也会随同的桶下面的元素进行从新散发，这也是 JDK1.8 版本的一个优化的中央，在 1.7 中，扩容之后须要从新去计算其 Hash 值，依据 Hash 值对其进行散发，但在 1.8 版本中，则是依据在同一个桶的地位中进行判断 (e.hash & oldCap) 是否为 0，从新进行 hash 调配后，该元素的地位要么停留在原始地位，要么挪动到原始地位 + 减少的数组大小这个地位上
链表树化
当桶中链表长度超过 TREEIFY_THRESHOLD（默认为 8）时，就会调用 treeifyBin 办法进行树化操作。但此时并不一定会树化，因为在 treeifyBin 办法中还会判断 HashMap 的容量是否大于等于 64。如果容量大于等于 64，那么进行树化，否则优先进行扩容。
为什么树化还要判断整体容量是否大于 64 呢？
当桶数组容量比拟小时，键值对节点 hash 的碰撞率可能会比拟高，进而导致链表长度较长，从而导致查问效率低下。这时候咱们有两种抉择，一种是扩容，让哈希碰撞率低一些。另一种是树化，进步查问效率。
如果咱们采纳扩容，那么咱们须要做的就是做一次链表数据的复制。而如果咱们采纳树化，那么咱们须要将链表转化成红黑树。到这里，貌似没有什么太大的区别，但咱们让场景持续延长上来。当插入的数据越来越多，咱们会发现须要转化成树的链表越来越多。
到了肯定容量，咱们就须要进行扩容了。这个时候咱们有许多树化的红黑树，在扩容之时，咱们须要将许多的红黑树拆分成链表，这是一个挺大的老本。而如果咱们在容量小的时候就进行扩容，那么须要树化的链表就越少，咱们扩容的老本也就越低。
接下来咱们看看链表树化是怎么做的：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 1. 容量小于 MIN_TREEIFY_CAPACITY，优先扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 2. 桶不为空，那么进行树化操作
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
// 2.1 先将链表转成 TreeNode 示意的双向链表
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);
// 2.2 将 TreeNode 示意的双向链表树化
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}咱们能够看到链表树化的整体思路也比拟清晰。首先将链表转成 TreeNode 示意的双向链表，之后再调用 treeify() 办法进行树化操作。那么咱们持续看看 treeify() 办法的实现。
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// 1. 遍历双向 TreeNode 链表，将 TreeNode 节点一个个插入
for (TreeNode<K,V> x = this, next; x != null; x = next) {next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
// 2. 如果 root 节点为空，那么间接将 x 节点设置为根节点
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
// 3. 如果 root 节点不为空，那么进行比拟并在适合的中央插入
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
// 4. 计算 dir 值，-1 示意要从左子树查找插入点，1 示意从右子树
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
// 5. 如果查找到一个 p 点，这个点是叶子节点
// 那么这个就是插入地位
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 做插入后的动平衡
root = balanceInsertion(root, x);
break;
}
}
}
}
// 6. 将 root 节点挪动到链表头
moveRootToFront(tab, root);
}从下面代码能够看到，treeify() 办法其实就是将双向 TreeNode 链表进一步树化成红黑树。其中大抵的步骤为：
- 遍历 TreeNode 双向链表，将 TreeNode 节点一个个插入
- 如果 root 节点为空，那么示意红黑树当初为空，间接将该节点作为根节点。否则须要查找到适合的地位去插入 TreeNode 节点。
- 通过比拟与 root 节点的地位，一直寻找最合适的点。如果最终该节点的叶子节点为空，那么该节点 p 就是插入节点的父节点。接着，将 x 节点的 parent 援用指向 xp 节点，xp 节点的左子节点或右子节点指向 x 节点。
- 接着，调用 balanceInsertion 做一次动态平衡。
- 最初，调用 moveRootToFront 办法将 root 节点挪动到链表头。
对于 balanceInsertion() 动平衡能够参考红黑树的插入动平衡，这里暂不深刻解说。最初咱们持续看看 moveRootToFront 办法。
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
// 如果插入红黑树的 root 节点不是链表的第一个元素
// 那么将 root 节点取出来，插在 first 节点后面
if (root != first) {
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
// 上面的两个 if 语句，做的事件是将 root 节点取出来
// 让 root 节点的前继指向其后继节点
// 让 root 节点的后继指向其前继节点
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
// 这里间接让 root 节点插入到 first 节点后方
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}红黑树拆分
扩容后，一般节点须要从新映射，红黑树节点也不例外。依照个别的思路，咱们能够先把红黑树转成链表，之后再从新映射链表即可。但因为红黑树插入的时候，TreeNode 保留了元素插入的程序，所以间接能够依照插入程序还原成链表。这样就防止了将红黑树转成链表后再进行哈希映射，无形中进步了效率。
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// 1. 将红黑树当成是一个 TreeNode 组成的双向链表
// 依照链表扩容一样，别离放入 loHead 和 hiHead 结尾的链表中
for (TreeNode<K,V> e = b, next; e != null; e = next) {next = (TreeNode<K,V>)e.next;
e.next = null;
// 1.1. 扩容后的地位不变，还是原来的地位，该节点放入 loHead 链表
if ((e.hash & bit) == 0) {if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
// 1.2 扩容后的地位扭转了，放入 hiHead 链表
else {if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
// 2. 对 loHead 和 hiHead 进行树化或链表化
if (loHead != null) {
// 2.1 如果链表长度小于阈值，那就链表化，否则树化
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}从下面的代码咱们晓得红黑树的扩容也和链表的转移是一样的，不同的是其转化成 hiHead 和 loHead 之后，会依据链表长度抉择拆分成链表还是继承维持红黑树的构造。
红黑树链化
咱们在说到红黑树拆分的时候说到，红黑树结构在扩容的时候如果长度低于阈值，那么就会将其转化成链表。其实现代码如下：
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}因为红黑树中蕴含了插入元素的程序，所以当咱们将红黑树拆分成两个链表 hiHead 和 loHead 时，其还是放弃着原来的程序的。所以此时咱们只须要循环遍历一遍，而后将 TreeNode 节点换成 Node 节点即可。
HashMap 为什么线程不平安
- put 的时候导致的多线程数据不统一。
这个问题比拟好设想，比方有两个线程 A 和 B，首先 A 心愿插入一个 key-value 对到 HashMap 中，首先计算记录所要落到的桶的索引坐标，而后获取到该桶外面的链表头结点，此时线程 A 的工夫片用完了，而此时线程 B 被调度得以执行，和线程 A 一样执行，只不过线程 B 胜利将记录插到了桶外面，假如线程 A 插入的记录计算出来的桶索引和线程 B 要插入的记录计算出来的桶索引是一样的，那么当线程 B 胜利插入之后，线程 A 再次被调度运行时，它仍然持有过期的链表头然而它对此无所不知，以至于它认为它应该这样做，如此一来就笼罩了线程 B 插入的记录，这样线程 B 插入的记录就凭空隐没了，造成了数据不统一的行为。 -
另外一个比拟显著的线程不平安的问题是 HashMap 的 get 操作可能因为 resize 而引起死循环（cpu100%），具体分析如下：
上面的代码是 resize 的核心内容：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {while(null != e) {
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;
}
}
} 这个办法的性能是将原来的记录从新计算在新桶的地位，而后迁徙过来。
多线程 HashMap 的 resize
咱们假如有两个线程同时须要执行 resize 操作，咱们原来的桶数量为 2，记录数为 3，须要 resize 桶到 4，原来的记录别离为：[3,A],[7,B],[5,C]，在原来的 map 外面，咱们发现这三个 entry 都落到了第二个桶外面。
假如线程 thread1 执行到了 transfer 办法的 Entry next = e.next 这一句，而后工夫片用完了，此时的 e = [3,A], next = [7,B]。线程 thread2 被调度执行并且顺利完成了 resize 操作，须要留神的是，此时的 [7,B] 的 next 为 [3,A]。此时线程 thread1 从新被调度运行，此时的 thread1 持有的援用是曾经被 thread2 resize 之后的后果。线程 thread1 首先将[3,A] 迁徙到新的数组上，而后再解决 [7,B]，而[7,B] 被链接到了 [3,A] 的前面，解决完 [7,B] 之后，就须要解决 [7,B] 的 next 了啊，而通过 thread2 的 resize 之后，[7,B]的 next 变为了 [3,A]，此时，[3,A] 和[7,B]造成了环形链表，在 get 的时候，如果 get 的 key 的桶索引和 [3,A] 和[7,B]一样，那么就会陷入死循环。
如果在取链表的时候从头开始取（当初是从尾部开始取）的话，则能够保障节点之间的程序，那样就不存在这样的问题了。
HashMap：JDK1.7 VS JDK1.8
JDK1.8 次要解决或优化了一下问题：
- resize 扩容优化
- 引入了红黑树，目标是防止单条链表过长而影响查问效率
- 解决了多线程死循环问题，但仍是非线程平安的，多线程时可能会造成数据失落问题
| 不同 | JDK 1.7 | JDK 1.8 |
|---|---|---|
| 存储构造 | 数组 + 链表 | 数组 + 链表 + 红黑树 |
| 初始化形式 | 独自函数：inflateTable() | 间接集成到了扩容函数 resize()中 |
| hash 值计算形式 | 扰动解决 = 9 次扰动 = 4 次位运算 + 5 次异或运算 | 扰动解决 = 2 次扰动 = 1 次位运算 + 1 次异或运算 |
| 存放数据的规定 | 无抵触时，寄存数组；抵触时，寄存链表 | 无抵触时，寄存数组；抵触 & 链表长度 < 8：寄存单链表；抵触 & 链表长度 > 8：树化并寄存红黑树 |
| 插入数据形式 | 头插法（先将原地位的数据移到后 1 位，再插入数据到该地位） | 尾插法（直接插入到链表尾部 / 红黑树） |
| 扩容后存储地位的计算形式 | 全副依照原来办法进行计算（即 hashCode ->> 扰动函数 ->> (h&length-1)） | 依照扩容后的法则计算（即扩容后的地位 = 原地位 or 原地位 + 旧容量 |
Hashtable
Hashtable 和 HashMap 都是散列表，也是用”拉链法“实现的哈希表。保留数据和 JDK7 中的 HashMap 一样，是 Entity 对象，只是 Hashtable 中的简直所有的 public 办法都是 synchronized 的，而有些办法也是在外部通过 synchronized 代码块来实现，效率必定会升高。且 put() 办法不容许空值。
HashMap 和 Hashtable 的区别
- 线程是否平安： HashMap 是非线程平安的，HashTable 是线程平安的；HashTable 外部的办法根本都通过
synchronized润饰。（如果你要保障线程平安的话就应用 ConcurrentHashMap 吧！）； - 效率： 因为线程平安的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 根本被淘汰，不要在代码中应用它；
- 对 Null key 和 Null value 的反对： HashMap 中，null 能够作为键，这样的键只有一个，能够有一个或多个键所对应的值为 null。。然而在 HashTable 中 put 进的键值只有有一个 null，间接抛出 NullPointerException。
-
初始容量大小和每次裁减容量大小的不同：
① 创立时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次裁减，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次裁减，容量变为原来的 2 倍。
② 创立时如果给定了容量初始值，那么 Hashtable 会间接应用你给定的大小，而 HashMap 会将其裁减为 2 的幂次方大小。也就是说 HashMap 总是应用 2 的幂次方作为哈希表的大小, 前面会介绍到为什么是 2 的幂次方。
- 底层数据结构： JDK1.8 当前的 HashMap 在解决哈希抵触时有了较大的变动，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以缩小搜寻工夫。Hashtable 没有这样的机制。
- HashMap 的迭代器（
Iterator）是 fail-fast 迭代器，然而 Hashtable 的迭代器（enumerator）不是 fail-fast 的。如果有其它线程对 HashMap 进行的增加 / 删除元素，将会抛出ConcurrentModificationException，但迭代器自身的remove办法移除元素则不会抛出异样。这条同样也是 Enumeration 和 Iterator 的区别。
理解过 LinkedHashMap、TreeMap 吗
LinkedHashMap 属于 HashMap 的子类，与 HashMap 的区别在于 LinkedHashMap 保留了记录插入的程序。TreeMap 实现了 SortedMap 接口，TreeMap 有能力对插入的记录依据 key 排序，默认依照升序排序，也能够自定义比拟项，在应用 TreeMap 的时候，key 该当实现 Comparable。
ConcurrentHashMap
HashMap 在多线程状况下，在 put 的时候，插入的元素超过了容量（由负载因子决定）的范畴就会触发扩容操作，就是 resize，这个会从新将原数组的内容从新 hash 到新的扩容数组中，在多线程的环境下，存在同时其余的元素也在进行 put 操作，如果 hash 值雷同，可能呈现同时在同一数组下用链表示意，造成 闭环，导致在 get 时会呈现死循环，所以 HashMap 是线程不平安的。(可参考：https://www.jianshu.com/p/e2f75c8cce01）
Hashtable，是线程平安的，它在所有波及到多线程操作的都加上了 synchronized 关键字来锁住整个 table，这就意味着所有的线程都在竞争一把锁，在多线程的环境下，它是平安的，然而无疑是效率低下的。
JDK1.7 实现
Hashtable 容器在竞争强烈的并发环境下体现出效率低下的起因，是因为所有拜访 Hashtable 的线程都必须竞争同一把锁，那如果容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程拜访容器里不同数据段的数据时，线程间就不会存在锁竞争，这就是 ConcurrentHashMap 所应用的锁分段技术。
在 JDK1.7 版本中，ConcurrentHashMap 的数据结构是由一个 Segment 数组和多个 HashEntry 组成。Segment 数组的意义就是将一个大的 table 宰割成多个小的 table 来进行加锁。每一个 Segment 元素存储的是 HashEntry 数组 + 链表，这个和 HashMap 的数据存储构造一样。
ConcurrentHashMap 类中蕴含两个动态外部类 HashEntry 和 Segment。
HashEntry 用来封装映射表的键值对，Segment 用来充当锁的角色，每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中蕴含由若干个 Segment 对象组成的数组。每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行批改时，必须首先取得它对应的 Segment 锁。
Segment 类
Segment 类继承于 ReentrantLock 类，从而使得 Segment 对象能充当可重入锁的角色。一个 Segment 就是一个子哈希表，Segment 里保护了一个 HashEntry 数组，并发环境下，对于不同 Segment 的数据进行操作是不必思考锁竞争的。
从源码能够看到，Segment 外部类和咱们上边看到的 HashMap 很类似。也有负载因子，阈值等各种属性。
static final class Segment<K,V> extends ReentrantLock implements Serializable {
static final int MAX_SCAN_RETRIES =
Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
transient volatile HashEntry<K,V>[] table;
transient int count;
transient int modCount; // 记录批改次数
transient int threshold;
final float loadFactor;
Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
this.loadFactor = lf;
this.threshold = threshold;
this.table = tab;
}
//put 办法会有加锁操作，final V put(K key, int hash, V value, boolean onlyIfAbsent) {HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
// ...
}
@SuppressWarnings("unchecked")
private void rehash(HashEntry<K,V> node) {// ...}
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {//...}
private void scanAndLock(Object key, int hash) {//...}
final V remove(Object key, int hash, Object value) {//...}
final boolean replace(K key, int hash, V oldValue, V newValue) {//...}
final V replace(K key, int hash, V value) {//...}
final void clear() {//...}
}HashEntry 类
HashEntry 是目前最小的逻辑处理单元。一个 ConcurrentHashMap 保护一个 Segment 数组，一个 Segment 保护一个 HashEntry 数组。
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value; // value 为 volatie 类型，保障可见
volatile HashEntry<K,V> next;
//...
}ConcurrentHashMap 类
默认的状况下，每个 ConcurrentHashMap 类会创立 16 个并发的 segment，每个 segment 外面蕴含多个 Hash 表，每个 Hash 链都是由 HashEntry 节点组成的。
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
implements ConcurrentMap<K, V>, Serializable {
// 默认初始容量为 16，即初始默认为 16 个桶
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 默认并发级别为 16。该值示意以后更新线程的估计数
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
static final int RETRIES_BEFORE_LOCK = 2;
final int segmentMask; // 段掩码, 次要为了定位 Segment
final int segmentShift;
final Segment<K,V>[] segments; // 骨干就是这个分段锁数组
// 结构器
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
//MAX_SEGMENTS 为 1 <<16=65536，也就是最大并发数为 65536
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// 2 的 sshif 次方等于 ssize，例:ssize=16,sshift=4;ssize=32,sshif=5
int sshift = 0;
// ssize 为 segments 数组长度，依据 concurrentLevel 计算得出
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;
// 创立 segments 数组并初始化第一个 Segment，其余的 Segment 提早初始化
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
}put() 办法
- 定位 segment 并确保定位的 Segment 已初始化
- 调用 Segment 的 put 办法。
public V put(K key, V value) {
Segment<K,V> s;
//concurrentHashMap 不容许 key/value 为空
if (value == null)
throw new NullPointerException();
//hash 函数对 key 的 hashCode 从新散列，防止差劲的不合理的 hashcode，保障散列平均
int hash = hash(key);
// 返回的 hash 值无符号右移 segmentShift 位与段掩码进行位运算，定位 segment
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}get() 办法
get 办法无需加锁，因为其中波及到的共享变量都应用 volatile 润饰，volatile 能够保障内存可见性，所以不会读取到过期数据
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {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;
}JDK1.8 实现
ConcurrentHashMap 在 JDK8 中进行了微小改变，光是代码量就从 1000 多行减少到 6000 行！1.8 摒弃了 Segment(锁段) 的概念，采纳了 CAS + synchronized 来保障并发的安全性。
能够看到，和 HashMap 1.8 的数据结构很像。底层数据结构扭转为采纳 数组 + 链表 + 红黑树 的数据模式。
和 HashMap1.8 雷同的一些中央
- 底层数据结构统一
- HashMap 初始化是在第一次 put 元素的时候进行的，而不是 init
- HashMap 的底层数组长度总是为 2 的整次幂
- 默认树化的阈值为 8，而链表化的阈值为 6（当低于这个阈值时，红黑树转成链表）
- hash 算法也很相似，但多了一步
& HASH_BITS，该步是为了打消最高位上的负符号，hash 的负在 ConcurrentHashMap 中有非凡意义示意在 扩容或者是树节点
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
static final int spread(int h) {return (h ^ (h >>> 16)) & HASH_BITS;
}一些要害属性
private static final int MAXIMUM_CAPACITY = 1 << 30; // 数组最大大小 同 HashMap
private static final int DEFAULT_CAPACITY = 16;// 数组默认大小
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 数组可能最大值，须要与 toArray（）相干办法关联
private static final int DEFAULT_CONCURRENCY_LEVEL = 16; // 兼容旧版保留的值，默认线程并发度，相似信号量
private static final float LOAD_FACTOR = 0.75f;// 默认 map 扩容比例，理论用 (n << 1) - (n >>> 1) 代替了更高效
static final int TREEIFY_THRESHOLD = 8; // 链表转树阀值，大于 8 时
static final int UNTREEIFY_THRESHOLD = 6; // 树转链表阀值，小于等于 6（tranfer 时，lc、hc= 0 两个计数器别离 ++ 记录原 bin、新 binTreeNode 数量，<=UNTREEIFY_THRESHOLD 则 untreeify(lo)）。【仅在扩容 tranfer 时才可能树转链表】static final int MIN_TREEIFY_CAPACITY = 64;
private static final int MIN_TRANSFER_STRIDE = 16;// 扩容转移时的最小数组分组大小
private static int RESIZE_STAMP_BITS = 16;// 本类中没提供批改的办法 用来依据 n 生成地位一个相似工夫戳的性能
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; // 2^15-1，help resize 的最大线程数
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; // 32-16=16，sizeCtl 中记录 size 大小的偏移量
static final int MOVED = -1; // hash for forwarding nodes（forwarding nodes 的 hash 值）、标示位
static final int TREEBIN = -2; // hash for roots of trees（树根节点的 hash 值）static final int RESERVED = -3; // ReservationNode 的 hash 值
static final int HASH_BITS = 0x7fffffff; // 用在计算 hash 时进行安位与计算打消负 hash
static final int NCPU = Runtime.getRuntime().availableProcessors(); // 可用处理器数量
/* ---------------- Fields -------------- */
transient volatile Node<K,V>[] table; // 装载 Node 的数组，作为 ConcurrentHashMap 的数据容器，采纳懒加载的形式，直到第一次插入数据的时候才会进行初始化操作，数组的大小总是为 2 的幂次方。private transient volatile Node<K,V>[] nextTable; // 扩容时应用，平时为 null，只有在扩容的时候才为非 null
/**
* 实际上保留的是 hashmap 中的元素个数 利用 CAS 锁进行更新但它并不必返回以后 hashmap 的元素个数
*/
private transient volatile long baseCount;
/**
* 该属性用来管制 table 数组的大小，依据是否初始化和是否正在扩容有几种状况：* 当值为正数时：如果为 - 1 示意正在初始化，如果为 - N 则示意以后正有 N - 1 个线程进行扩容操作；* 当值为负数时：如果以后数组为 null 的话示意 table 在初始化过程中，sizeCtl 示意为须要新建数组的长度；若曾经初始化了，示意以后数据容器（table 数组）可用容量也能够了解成临界值（插入节点数超过了该临界值就须要扩容），具体指为数组的长度 n 乘以 加载因子 loadFactor；当值为 0 时，即数组长度为默认初始值。*/
private transient volatile int sizeCtl;put() 办法
- 首先会判断 key、value 是否为空，如果为空就抛异样！
spread()办法获取 hash，减小 hash 抵触- 判断是否初始化 table 数组，没有的话调用
initTable()办法进行初始化 - 判断是否能间接将新值插入到 table 数组中
- 判断以后是否在扩容，
MOVED为 - 1 阐明以后 ConcurrentHashMap 正在进行扩容操作，正在扩容的话就进行帮助扩容 -
当 table[i]为链表的头结点，在链表中插入新值，通过 synchronized (f)的形式进行加锁以实现线程安全性。
- 在链表中如果找到了与待插入的键值对的 key 雷同的节点，就间接笼罩
- 如果没有找到的话，就间接将待插入的键值对追加到链表的开端
- 当 table[i]为红黑树的根节点，在红黑树中插入新值 / 笼罩旧值
- 依据以后节点个数进行调整，否须要转换成红黑树 (个数大于等于 8，就会调用
treeifyBin办法将 tabel[i]第 i 个散列桶拉链转换成红黑树) - 对以后容量大小进行查看，如果超过了临界值（理论大小 * 加载因子）就进行扩容
final V putVal(K key, V value, boolean onlyIfAbsent) {
// key 和 value 均不容许为 null
if (key == null || value == null) throw new NullPointerException();
// 依据 key 计算出 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();
// f 即为以后 key 定位出的 Node，如果为空示意以后地位能够写入数据，利用 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
}
// 如果以后地位的 hashcode == MOVED == -1, 则须要进行扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 如果都不满足，则利用 synchronized 锁写入数据
else {
// 剩下状况又分两种，插入链表、插入红黑树
V oldVal = null;
// 采纳同步内置锁实现并发管制
synchronized (f) {if (tabAt(tab, i) == f) {
// 如果 fh=f.hash >=0，以后为链表，在链表中插入新的键值对
if (fh >= 0) {
binCount = 1;
// 遍历链表，如果找到对应的 node 节点，批改 value, 否则间接在链表尾部退出节点
for (Node<K,V> e = f;; ++binCount) {
K ek;
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;
}
}
}
// 对以后容量大小进行查看，如果超过了临界值（理论大小 * 加载因子）就须要扩容
addCount(1L, binCount);
return null;
}咱们能够发现 JDK8 中的实现也是 锁拆散 的思维，只是锁住的是一个 Node，而不是 JDK7 中的 Segment，而锁住 Node 之前的操作是无锁的并且也是线程平安的，建设在之前提到的原子操作上。
get() 办法
get 办法无需加锁，因为其中波及到的共享变量都应用 volatile 润饰，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 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 判断 node 节点第一个元素是不是要找的，如果是间接返回
if ((eh = e.hash) == h) {if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// // hash 小于 0, 阐明是非凡节点（TreeBin 或 ForwardingNode）调用 find
else if (eh < 0)
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;
}Hashtable 和 ConcurrentHashMap 的区别
ConcurrentHashMap 和 Hashtable 的区别次要体现在实现线程平安的形式上不同。
- 底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采纳 分段的数组 + 链表 实现，JDK1.8 采纳的数据结构和 HashMap1.8 的构造相似， 数组 + 链表 / 红黑二叉树 。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构相似都是采纳 数组 + 链表 的模式，数组是 HashMap 的主体，链表则是次要为了解决哈希抵触而存在的；
-
实现线程平安的形式（重要）：
- 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了宰割分段 (Segment)，每一把锁只锁容器其中一部分数据，多线程拜访容器里不同数据段的数据，就不会存在锁竞争，进步并发访问率。（默认调配 16 个 Segment，比 Hashtable 效率进步 16 倍。） 到了 JDK1.8 的时候曾经摒弃了 Segment 的概念，而是间接用 Node 数组 + 链表 / 红黑树的数据结构来实现，并发管制应用 synchronized 和 CAS 来操作。（JDK1.6 当前 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程平安的 HashMap，尽管在 JDK1.8 中还能看到 Segment 的数据结构，然而曾经简化了属性，只是为了兼容旧版本；
- Hashtable(同一把锁)：应用 synchronized 来保障线程平安，效率十分低下。当一个线程拜访同步办法时，其余线程也拜访同步办法，可能会进入阻塞或轮询状态，如应用 put 增加元素，另一个线程不能应用 put 增加元素，也不能应用 get，竞争越强烈效率越低。
Java 疾速失败（fail-fast）和平安失败（fail-safe）区别
疾速失败（fail—fast）
在用迭代器遍历一个汇合对象时，如果遍历过程中对汇合对象的内容进行了批改（减少、删除、批改），则会抛出 ConcurrentModificationException。
原理：迭代器在遍历时间接拜访汇合中的内容，并且在遍历过程中应用一个 modCount 变量。汇合在被遍历期间如果内容发生变化，就会扭转 modCount 的值。每当迭代器应用 hashNext()/next() 遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出异样，终止遍历。
留神：这里异样的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果汇合发生变化时批改 modCount 值刚好又设置为了 expectedmodCount 值，则异样不会抛出。因而，不能依赖于这个异样是否抛出而进行并发操作的编程，这个异样只倡议用于检测并发批改的 bug。
场景：java.util 包下的汇合类都是疾速失败的，不能在多线程下产生并发批改（迭代过程中被批改）。
平安失败（fail—safe）
采纳平安失败机制的汇合容器，在遍历时不是间接在汇合内容上拜访的，而是先复制原有汇合内容，在拷贝的汇合上进行遍历。
原理：因为迭代时是对原汇合的拷贝进行遍历，所以在遍历过程中对原汇合所作的批改并不能被迭代器检测到，所以不会触发 Concurrent Modification Exception。
毛病：基于拷贝内容的长处是防止了 Concurrent Modification Exception，但同样地，迭代器并不能拜访到批改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的汇合拷贝，在遍历期间原汇合产生的批改迭代器是不晓得的。
场景：java.util.concurrent 包下的容器都是平安失败，能够在多线程下并发应用，并发批改。
疾速失败和平安失败是对迭代器而言的。
疾速失败：当在迭代一个汇合的时候，如果有另外一个线程在批改这个汇合，就会抛出 ConcurrentModification 异样，java.util 下都是疾速失败。
平安失败：在迭代时候会在汇合二层做一个拷贝，所以在批改汇合下层元素不会影响上层。在 java.util.concurrent 下都是平安失败
如何防止fail-fast？
- 在单线程的遍历过程中，如果要进行 remove 操作，能够调用迭代器 ListIterator 的 remove 办法而不是汇合类的 remove 办法。看看 ArrayList 中迭代器的 remove 办法的源码，该办法不能指定元素删除，只能 remove 以后遍历元素。
public void remove() {if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = ArrayList.this.modCount; //
} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();
}
}-
应用并发包 (
java.util.concurrent) 中的类来代替 ArrayList 和 hashMap- CopyOnWriterArrayList 代替 ArrayList
- ConcurrentHashMap 代替 HashMap
Iterator 和 Enumeration 区别
在 Java 汇合中，咱们通常都通过“Iterator(迭代器)”或“Enumeration(枚举类)”去遍历汇合。
public interface Enumeration<E> {boolean hasMoreElements();
E nextElement();}public interface Iterator<E> {boolean hasNext();
E next();
void remove();}- 函数接口不同 ，Enumeration 只有 2 个函数接口。通过 Enumeration，咱们只能读取汇合的数据，而不能对数据进行批改。Iterator只有 3 个函数接口。Iterator 除了能读取汇合的数据之外，也能数据进行删除操作。
- Iterator 反对 fail-fast 机制，而 Enumeration 不反对 。Enumeration 是 JDK 1.0 增加的接口。应用到它的函数包含 Vector、Hashtable 等类，这些类都是 JDK 1.0 中退出的，Enumeration 存在的目标就是为它们提供遍历接口。Enumeration 自身并没有反对同步，而在 Vector、Hashtable 实现 Enumeration 时，增加了同步。
而 Iterator 是 JDK 1.2 才增加的接口，它也是为了 HashMap、ArrayList 等汇合提供遍历接口。Iterator 是反对 fail-fast 机制的：当多个线程对同一个汇合的内容进行操作时，就可能会产生 fail-fast 事件
Comparable 和 Comparator 接口有何区别？
Java 中对汇合对象或者数组对象排序，有两种实现形式：
-
对象实现 Comparable 接口
-
Comparable 在
java.lang包下，是一个接口，外部只有一个办法compareTo()public interface Comparable<T> {public int compareTo(T o); } - Comparable 能够让实现它的类的对象进行比拟，具体的比拟规定是依照 compareTo 办法中的规定进行。这种程序称为 天然程序。
- 实现了 Comparable 接口的 List 或则数组能够应用
Collections.sort()或者Arrays.sort()办法进行排序
-
-
定义比拟器，实现 Comparator 接口
-
Comparator 在
java.util包下，也是一个接口，JDK 1.8 以前只有两个办法：public interface Comparator<T> {public int compare(T lhs, T rhs); public boolean equals(Object object); }
-
comparable 相当于外部比拟器。comparator 相当于内部比拟器
区别：
- Comparator 位于
java.util包下，而 Comparable 位于java.lang包下 - Comparable 接口的实现是在类的外部（如 String、Integer 曾经实现了 Comparable 接口，本人就能够实现比拟大小操作），Comparator 接口的实现是在类的内部（能够了解为一个是自已实现比拟，一个是内部程序实现比拟）
-
实现 Comparable 接口要重写 compareTo 办法, 在 compareTo 办法外面实现比拟。一个曾经实现 Comparable 的类的对象或数据，能够通过 Collections.sort(list) 或者 Arrays.sort(arr)实现排序。通过 Collections.sort(list,Collections.reverseOrder()) 对 list 进行倒序排列。
-
实现 Comparator 须要重写 compare 办法
HashSet
HashSet 是用来存储没有反复元素的汇合类，并且它是无序的。HashSet 外部实现是基于 HashMap，实现了 Set 接口。
从 HahSet 提供的结构器能够看出，除了最初一个 HashSet 的构造方法外，其余所有外部就是去创立一个 HashMap。没有其余的操作。而最初一个构造方法不是 public 的，所以不对外公开。
HashSet 如何查看反复
HashSet 的底层其实就是 HashMap，只不过咱们 HashSet 是实现了 Set 接口并且把数据作为 K 值，而 V 值始终应用一个雷同的虚值来保留，HashMap 的 K 值自身就不容许反复，并且在 HashMap 中如果 K/V 雷同时，会用新的 V 笼罩掉旧的 V，而后返回旧的 V。
Iterater 和 ListIterator 之间有什么区别？
- 咱们能够应用 Iterator 来遍历 Set 和 List 汇合，而 ListIterator 只能遍历 List
- ListIterator 有 add 办法，能够向 List 中增加对象，而 Iterator 不能
- ListIterator 和 Iterator 都有 hasNext()和 next()办法，能够实现程序向后遍历，然而 ListIterator 有 hasPrevious()和 previous()办法，能够实现逆向（程序向前）遍历。Iterator 不能够
- ListIterator 能够定位以后索引的地位，nextIndex()和 previousIndex()能够实现。Iterator 没有此性能
- 都可实现删除操作，然而 ListIterator 能够实现对象的批改，set()办法能够实现。Iterator 仅能遍历，不能批改
<img src=”https://static01.imgkr.com/temp/ef920406f7274d06a9b203b6b03e3171.png” style=”zoom:50%;” />
参考与感激
所有内容都是基于源码浏览和各种大佬之前总结的常识整顿而来，输出并输入，奥利给。
https://www.javatpoint.com/java-arraylist
https://www.runoob.com/java/java-collections.html
https://www.javazhiyin.com/21717.html
https://yuqirong.me/2018/01/31/LinkedList 外部原理解析 /
https://youzhixueyuan.com/the-underlying-structure-and-princi…
《HashMap 源码详细分析》http://www.tianxiaobo.com/2018/01/18/HashMap- 源码详细分析 -JDK1-8/
《ConcurrentHashMap1.7 源码剖析》https://www.cnblogs.com/chengxiao/p/6842045.html
http://www.justdojava.com/2019/12/18/java-collection-15.1/
本文由 mdnice 多平台公布
