第一部分：HashMap
1.HashMap介绍
- JDK7：底层实现【数组+链表（头插法）】
- JDK8: 底层实现【数组+链表（尾插法）\红黑树】
- JDK7版本在多线程resize时会发生死循环
- JDK8优化：红黑树的引入避免链表过长查找耗时（链表最坏O(n)、红黑树O(logn)）、扩容优化。
- 转红黑树的判断**：链表长度大于8，先判断数组容量是否超过64，是，直接转红黑树；否则，先扩容。**
-
1.1HashMap允许空键空值么
HashMap最多只允许一个键为Null(多条会覆盖)，但允许多个值为Null
1.2影响HashMap性能的重要参数
初始容量：
创建哈希表(数组)时桶的数量，默认为 16，创建时为空数组,``在添加第一个元素时进行初始化容量
负载因子：哈希表在其容量自动增加之前可以达到多满的一种尺度，默认为 0.752.HashMap的存储结构
底层存储数据的数组是一个哈希桶数组，明显它是一个Node的数组。链表也是基于Node结点完成。
static class Node<K,V> implements Map.Entry<K,V> {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;}}
红黑树结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // needed to unlink next upon deletionboolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}}
3.功能实现
本文主要从根据key获取哈希桶数组索引位置、put方法的详细执行、扩容过程三个具有代表性的点进行记录
3.1 key获取Hash索引位置
计算hash索引的源代码如下:
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高16位与低16位参与异或运算static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = key.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
3.2 put方法
3.3 扩容机制
JDK8则因为巧妙的设计，性能有了大大的提升：由于数组的容量是以2的幂次方扩容的，那么一个Entity在扩容时，新的位置要么在原位置，要么在原长度+原位置的位置。原因如下图：
数组长度变为原来的2倍，表现在二进制上就是多了一个高位参与数组下标确定。此时，一个元素通过hash转换坐标的方法计算后，恰好出现一个现象：最高位是0则坐标不变，最高位是1则坐标变为“10000+原坐标”，即“原长度+原坐标”。如下图：
JDK8中的扩容，索引下标位置要么不变，要么是原来的下表+原来数组的容量。
4.为什么HashMap的底层数组长度为何总是2的n次方【经典面试题】
第一：当length为2的N次方的时候，h & (length-1) = h % length
第二：当length为2的N次方的时候，数据分布均匀，减少hash冲突
此时我们基于第一个原因进行分析，此时hash策略为h & (length-1)。
我们来举例当length为奇数、偶数时的情况：
从上面的图表中我们可以看到，当 length 为15时总共发生了8次碰撞，同时发现空间浪费非常大，因为在 1、3、5、7、9、11、13、15 这八处没有存放数据。
这是因为hash值在与14（即 1110）进行&运算时，得到的结果最后一位永远都是0，那么最后一位为1的位置即 0001、0011、0101、0111、1001、1011、1101、1111位置处是不可能存储数据的。这样，空间的减少会导致碰撞几率的进一步增加，从而就会导致查询速度慢。
而当length为16时，length – 1 = 15， 即 1111，那么，在进行低位&运算时，值总是与原来hash值相同，而进行高位运算时，其值等于其低位值。所以，当 length=2^n 时，不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询速度也较快。
如果上面这句话大家还看不明白的话，可以多试一些数，就可以发现规律。当length为奇数时，length-1为偶数，而偶数二进制的最后一位永远为0，那么与其进行 & 运算，得到的二进制数最后一位永远为0，那么结果一定是偶数，那么就会导致下标为奇数的桶永远不会放置数据，这就不符合我们均匀放置，减少冲突的要求了。
第三：数组扩容以后，所有元素的下标的索引位置要么在原来的位置，要么在【原来索引+原来数组容量】处。
5.HashMap和Hashtable的比较
- HashMap允许键或值为null的键存在，HashTable不允许键或值为null。
第二部分：ConcurrentHashMap
1.JDK7版本
1.1 底层数据结构
数组+链表实现。
如图所示，是由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表**
Segment 是 ConcurrentHashMap 的一个内部类，主要的组成如下：
static final class Segment<K,V> extends ReentrantLock implements Serializable {private static final long serialVersionUID = 2249069246763182397L;// 和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶transient volatile HashEntry<K,V>[] table;transient int count;// 记得快速失败（fail—fast）么？transient int modCount;// 大小transient int threshold;// 负载因子final float loadFactor;}
HashEntry跟HashMap差不多的，但是不同点是，他使用volatile去修饰了他的数据Value还有下一个节点next。
1.2 并发度高的原因
ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。
每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。就是说如果容量大小是16他的并发度就是16，可以同时允许16个线程操作16个Segment而且还是线程安全的。
- put方法
首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。
- 尝试自旋获取锁。
- 如果重试的次数达到了
MAX_SCAN_RETRIES则改为阻塞锁获取，保证能获取成功。
- get方法
只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。
由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。
2.JDK8版本
2.1 底层数据结构
- 加锁机制：1.8抛弃segment分段锁，而采用了
CAS + synchronized来保证并发安全性。 -
2.2 安全原因分析
put方法
final V putVal(K key, V value, boolean onlyIfAbsent) {if (key == null || value == null) throw new NullPointerException();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();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}else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);else {V oldVal = null;synchronized (f) {if (tabAt(tab, i) == f) {if (fh >= 0) {binCount = 1;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;}
1.如果key或者value为null，则抛出空指针异常，和HashMap不同的是HashMap单线程是允许为Null；
if (key == null || value == null) throw new NullPointerException();
2.for的死循环，为了实现CAS的无锁化更新，如果table为null或者table的长度为0，则初始化table，调用initTable()方法（第一次put数据，调用默认参数实现，其中重要的sizeCtl参数）。//计算索引的第一步，传入键值的hash值int hash = spread(key.hashCode());int binCount = 0; //保存当前节点的长度for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh; K fk; V fv;if (tab == null || (n = tab.length) == 0)tab = initTable(); //初始化Hash表...}
3.确定元素在Hash表的索引
通过hash算法可以将元素分散到哈希桶中。在ConcurrentHashMap中通过如下方法确定数组索引：
第一步：static final int spread(int h) {return (h ^ (h >>> 16)) & HASH_BITS;}
第二步：
(length-1) & (h ^ (h >>> 16)) & HASH_BITS);
4.通过tableAt()方法找到位置tab[i]的Node,当Node为null时为没有hash冲突的话，使用casTabAt()方法CAS操作将元素插入到Hash表中，ConcurrentHashmap使用CAS无锁化操作，这样在高并发hash冲突低的情况下，性能良好。else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//利用CAS操作将元素插入到Hash表中if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))break; // no lock when adding to empty bin(插入null的节点，无需加锁)}
5.当f不为null时，说明发生了hash冲突，当f.hash == MOVED==-1 时，说明
ConcurrentHashmap正在发生resize操作,使用helpTransfer()方法帮助正在进行resize操作。else if ((fh = f.hash) == MOVED) //f.hash == -1//hash为-1 说明是一个forwarding nodes节点，表明正在扩容tab = helpTransfer(tab, f);
6.以上情况都不满足的时，使用
synchronized同步块上锁当前节点Node,并判断有没有线程对数组进行了修改，如果没有则进行：- 遍历该链表并统计该链表长度
binCount，查找是否有和key相同的节点，如果有则将查找到节点的val值替换为新的value值，并返回旧的value值，否则根据key，value，hash创建新Node并将其放在链表的尾部 - 如果
Node f是TreeBin的类型，则使用红黑树的方式进行插入。然后则退出synchronized(f)锁住的代码块
7.执行完//当前节点加锁synchronized (f) {//判断下有没有线程对数组进行了修改if (tabAt(tab, i) == f) {//如果hash值是大于等于0的说明是链表if (fh >= 0) {binCount = 1;for (Node<K,V> e = f;; ++binCount) {K ek;//插入的元素键值的hash值有节点中元素的hash值相同，替换当前元素的值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);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;}}else if (f instanceof ReservationNode)throw new IllegalStateException("Recursive update");}}
synchronized(f)同步代码块之后会先检查binCount,如果大于等于TREEIFY_THRESHOLD = 8则进行treeifyBin操作尝试将该链表转换为红黑树。
执行了一个if (binCount != 0) {//如果节点长度大于8,转化为树if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal != null)return oldVal;break;}
addCount方法,主要用于统计数量以及决定是否需要扩容.addCount(1L, binCount);
get方法
public V get(Object key) {Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;// 计算hashcodeint h = spread(key.hashCode());//在桶上直接返回if ((tab = table) != null && (n = tab.length) > 0 &&(e = tabAt(tab, (n - 1) & h)) != null) {//如果是红黑树就按照树的方式遍历if ((eh = e.hash) == h) {if ((ek = e.key) == key || (ek != null && key.equals(ek)))return e.val;}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;}
1.根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
2.如果是红黑树那就按照树的方式获取值。
3.就不满足那就按照链表的方式遍历获取值。其它
CopyOnWriteArrayList
https://www.nowcoder.com/discuss/232479
红黑树
若有收获，就点个赞吧
0 人点赞
