概述
java8对java7中hashmap的实现进行了一部分修改，最大的修改在于利用了红黑树，jdk7使用数组+链表实现hashmap，jdk8使用数组+链表+红黑树实现hashmap，之所以jdk8要引入红黑树，因为jdk7的单向链表可以无限延伸，时间复杂度取决于链表的长度，为O(n)，为了降低这部分开销，jdk8中，当单向链表中元素达到8个的时候，会将链表转换为红黑树，这些位置的查找的时间复杂度降低为O(logN)
java7使用Entry描述hashmap中的每个数据节点，java8在没生成红黑树的时候，使用node来描述链表元素，当转换红黑树的时候，使用treenode描述链表元素
哈希表
哈希表，又称散列表，是一种数据结构，一个哈希表包含一个数组，通过特殊的key来访问数组中元素，哈希表主要思想是通过一个哈希函数，在key映射的位置去寻找存放值的地方
如下图字典：寻找安存放的位置，通过hash函数f(安)计算出an，从而放在第二位，哈希冲突：f(按)=an，追加在安后面，哈希冲突无法避免
哈希表的特性决定了哈希表具有较高性能，大多数查找或插入元素时间复杂度都为O(1)，时间主要花在计算hash值上，如果使用的hash函数不够好，会导致大量hash值映射在同一个地址上，这样哈希表就会退化成链表，时间复杂度变O(n)，效率低下
jdk8版本hashmap结构
jdk8版本hashmap源码
基本属性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 用于扩容，不会说到16才扩容，没到16的时候就会，这个阈值就是加载因子乘以容量，即12的时候就会扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 变成红黑树的阈值=8
static final int TREEIFY_THRESHOLD = 8;
transient Node<K,V>[] table;
put(K key, V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
//此处为了降低哈希冲突的几率，在这里不直接返回hashCode而是分下面几步
//1 获取key的HashCode
//2 将获取到的hashCode向右移16位
//3 移动结果和原来的key的hashCode异或运算 (相同的异或为0，不相同异或为1)
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
元素在数组中存放的位置是由下面的i=(n-1)&hash决定的，这行代码摘自putVal()，n为当前数组的大小，i为当前元素存放的索引
测试代码
HashMap map=new HashMap(1)
带参数初始化
tableSizeFor结果为1，this.threshold扩容阈值初始化为1，然后执行下面代码map.put("key1",111)，发现tab是null，开始准备调用扩容方法初始化table
扩容的时候，oldCap=0，oldThr=1，newCap=newThr初始值为0，在经过else if完后，newCap=1，在经过if(newThr==0)后，newThr=（int）ft，而ft=0.75，取int后未0，即newThr新的扩容阈值为0，只要table中元素超过0，就重新调用本方法，然后初始化table，初始化完后返回到putVal方法
在putVal方法中，首先将要放入的key1元素放入进去
然后到最下边，开始判断是否需要扩容，putVal放入一个元素后size=1，超过扩容阈值0，开始扩容
然后resize部分代码上边部分如下，oldCap=1,oldThr=0,newCap在下面的1中变成2，newThr经过计算2*0.75=1.5变成1，然后完成新的table的初始化，准备开始迁移
putVal
下面为变换红黑树的条件判断以及判断是否有节点的key跟待插入的key相同的逻辑
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 创建变量引用
Node<K,V>[] tab; Node<K,V> p; int n, i;
//先用局部变量拷贝一份成员变量，然后对局部变量判断，另一个局部变量也对刚刚被赋值的局部变量判断
if ((tab = table) == null || (n = tab.length) == 0)
// 数组没初始化就进行初始化
n = (tab = resize()).length;
// 寻址算法算出应该放的位置没有元素
if ((p = tab[i = (n - 1) & hash]) == null)
// 直接创建元素节点放入
tab[i] = newNode(hash, key, value, null);
else {
// e指针保存如果之前该key已经有值了的旧值，k保存旧值的key
Node<K,V> e; K k;
// 如果要插入的位置的哈希跟要插入的key的hash结果相同并且【 key相同或者key不为空，但是key和那个位置的key equals】
// 注意：***下面是if elseif else 三个分支！！！
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) {
// 认为是同一个key的插入，则用局部变量e取出这个旧的节点
e = p;
} else if (p instanceof TreeNode) // 如果寻址算法算出的位置上的该节点是红黑树节点
// 用局部变量e取出这个旧的红黑树节点
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 数组上的寻址算法算出的位置上该节点的key和要写入的key不同，走了上面两个if以后，这里必定是链表节点
for (int binCount = 0; ; ++binCount) {
// 用e记录节点p的下一个元素，如果不存在
if ((e = p.next) == null) {
// 直接将新元素插入作为p元素的后继节点
p.next = newNode(hash, key, value, null);
// binCount=0的时候，有2个节点，p节点和新插入的节点
// binCount=7的时候，有9个节点，p节点+p后面的原本节点+新插入的节点
// binCount与新插入的节点无关系！！！ 原来链表上有8个节点，现在先插入以后再判断转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 转化为红黑树
treeifyBin(tab, hash);
break;
}
// 说明p节点后面还有节点，e是p下一个节点，如果e就是要插入的key的相同的key值，跳出
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 继续进行循环，将p的下一个节点e作为新的p，e指向更下一个节点
p = e;
}
}
// 如果e是null，说明没有找到相同key的节点 e是exists
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 如果允许覆盖或者旧值为null （hashmap是允许key，value都可以是null的）
if (!onlyIfAbsent || oldValue == null)
// 将新的值赋值给那个节点
e.value = value;
afterNodeAccess(e); // hashmap自身并未实现该方法细节，子类实现
return oldValue; // 将之前的同key的节点的旧value返回
}
}
++modCount;
// 如果新加入元素以后的值大于扩容阈值
if (++size > threshold)
// 进行扩容
resize();
afterNodeInsertion(evict); // hashmap自身并未实现该方法细节，子类实现
return null;
}
resize
扩容过程主要完成了map的初始化以及容量到达阈值的时候创建新的数组，并将旧数组数据迁移
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 后面判断都是用局部变量去判断的
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 旧的扩容阈值
int oldThr = threshold;
// 声明新的数组容量和新的扩容阈值
int newCap, newThr = 0;
// 如果老的容量>0
if (oldCap > 0) {
// 如果老的数组容量已经达到了最大容量了
if (oldCap >= MAXIMUM_CAPACITY) {
// 扩容阈值修改为2^32
threshold = Integer.MAX_VALUE;
// 不进行扩容直接返回老的容量
return oldTab;
}
// 否则，判断将老的数组容量放大2倍以后如果没超过最大容量且老的容量大于等于初始的默认的初始容量16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 符合条件则将新的阈值变为老阈值的2倍
newThr = oldThr << 1; // double threshold
// 这里必要条件：老的容量小于最大容量2的30次幂
// 这里选择条件：扩容2倍后大于等于最大容量 或者老的数组容量小于默认的容量16（如5，适配后变成8小于16），newThr这时候仍然为0
}
// 必要条件：oldCap=0
// 可能有两种情况，一种是oldThreshold=0（不带初始容量初始化），一种是大于0（带初始容量初始化）
else if (oldThr > 0) // initial capacity was placed in threshold
// 即带初始容量参数初始化（new HashMap(initCapacity)）。oldThr在tableSizeFor被赋值，直接将他赋值给新的*容量*。oldThr只是用来配置参数，那时候还没有实例化数组，这里才真正实例化，要用到上面的参数。这时候newCap=oldThr，newThr=0(代码头部初始化的)
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 说明为不带参数初始化（new HashMap()）
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 上面主要是为了堆newCap和newThr赋值，如果newThr没有值说明走了if中的else if的else 或者 走了外围的else if(oldThr>0)
/*
即可能存在 ：新扩容后的容量大于最大容量 或者
老的容量小于默认初始容量16（最有可能）
或者 oldThr>0
*/
// newCap已经在if的elseif分支赋值了
if (newThr == 0) {
// 假设老的容量为8，加载因子是0.75，则ft=6，newCap=1，则ft=0.75
float ft = (float)newCap * loadFactor;
// 如果新的容量小于最大容量并且新计算的float类型的扩容阈值ft小于 float类型的最大容量，则新的扩容阈值为该int类型的扩容阈值
/**
带参数初始化容量1，则首先执行完：newCap=1，newThr=0，然后回到putValue方法，放入要添加的元素以后发现大于扩容阈值，开始扩容
*/
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指向新的table的内存地址，但是临时变量oldTable还是指向了旧的数组的内存地址
table = newTab;
// 如果为初始化这里已经结束
if (oldTab != null) {
// 这里说明老的数组存在，则遍历
for (int j = 0; j < oldCap; ++j) {
// 游走指针，记录每个被遍历的元素
Node<K,V> e;
// 如果旧数组第一个元素存在
if ((e = oldTab[j]) != null) {
// 将旧数组第一个位置置空
oldTab[j] = null;
// 如果旧数组第一个元素所在的链表没有后面的元素了
if (e.next == null)
// 将记录的这个旧数组第一个元素使用 寻址算法，再计算一次他的位置，只能是原位置或者加上oldCapacity
newTab[e.hash & (newCap - 1)] = e;
// 如果旧数组第一个元素所在链表后面有元素，并且是红黑树节点
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 说明为链表节点，开始遍历第j个元素的链表节点
// 声明低链表头尾指针
Node<K,V> loHead = null, loTail = null;
// 声明高链表头尾指针
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 节点哈希值 和 旧的数组容量 与的结果 只能是0和旧的容量，从0开始一部分，从oldCap一部分， 又从0开始一部分
// 需要将此链表拆成两个链表，放到新的数组中，并且保留原来的先后顺序
// loHead、loTail 对应一条链表，hiHead、hiTail 对应另一条链表
// 低位链表
if ((e.hash & oldCap) == 0) {
// 如果低位链表此时没有尾结点
if (loTail == null)
// 将当前节点设置为低位链表的头结点
loHead = e;
else
// 将低位链表之前的尾结点的next指针指向当前节点
loTail.next = e;
// 将当前节点设置为低位链表的尾结点
loTail = e;
}
// 高位链表，与的结果是旧的数组cap，操作同上，就是完成一个高位链表的初始化
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 某个节点上的高位链表和低位链表初始化完以后，将低位链表的头部放到新链表的j角标位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 将高位链表的头部放到新链表的j+旧的数组容量的寻址位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
面试题
1. 为什么定义hashmap初始值是16是2的n次幂，扩容的时候新数组大小要是2的n次幂
核心：寻址算法
i是数组下标，n是数组长度，hash是要插入的entry的key的hash值
i =(n-1)&hash
2的次幂-1永远得到的结果的二进制位最后面都是1，如
2-1
0000 0000 0000 0001
4-1
0000 0000 0000 0011
8-1
0000 0000 0000 0111
16-1
0000 0000 0000 1111
32-1
0000 0000 0001 1111
我们接下来按照如果数组长度是2的次幂和不是2的次幂来做寻址算法比较，假如我们又4个entry等待插入，entry的key的hash计算结果分别为：
9 0000 0000 0001 1001
10 0000 0000 0001 1010
11 0000 0000 0001 1011
12 0000 0000 0001 1100
- 如果长度是2的次幂，如默认的数组长度16，n-1=16-1=15 = 0000 0000 0000 1111
- 如果长度不是2的次幂，如长度为10，n-1=9=0000 0000 0001 1001
可以发现如果数组的长度不使用2的n次幂的话，经过寻址算法，得到的结果会出现很多重复，增加了哈希碰撞的几率。因此HashMap的初始容量是2的n次幂。
下面我们看为什么扩容也需要是2的幂次数，满足2的幂就是相当于每次扩容都是翻倍
假设现在扩容为长度32，n-1=31=0000 0000 0001 1111则寻址算法结果为
可以看到，扩容时在重新计算下标位置时，只有两种情况，一种是下标不变，另一种是下标变为：原下标位置+扩容前容量，而上图很明显就是在扩容器的与的二进制结果的第一位加了1，等于是在原有的结果基础上加了2的4次幂即扩容前的容量16.这样扩容后节点移动相对较少，可以提高性能
总结：
HashMap计算添加元素的位置时，使用的位运算，这是特别高效的运算；另外，HashMap的初始容量是2的n次幂，扩容也是2倍的形式进行扩容，是因为容量是2的n次幂，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞，避免形成链表的结构，使得查询效率降低！
2. hashmap初始化的时候可以指定数组长度，那是怎么保证输入的值是2的n次幂
主要是通过如下代码完成对输入数组长度转化为2的n次幂
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
这一系列的无符号右移操作和按位或运算返回的什么结果，我们可以通过一个测试来说明
public static void main(String[] args) throws Exception {
HashMap map = new HashMap();
Method tableSizeFor = map.getClass().getDeclaredMethod("tableSizeFor", int.class);
tableSizeFor.setAccessible(true);
List<Integer> list = Lists.newArrayList(3,4,15,16,17,31,32,33);
list.forEach(e-> {
try {
System.out.println(tableSizeFor.invoke(map,e));
} catch (IllegalAccessException | InvocationTargetException e1) {
e1.printStackTrace();
}
});
}
打印结果如下：
可以看出是用距离传入的数组正向长度最近的2次幂来替换该长度
3. 什么时候扩容以及加载因子为什么是0.75
/**
* The next size value at which to resize (capacity * load factor).
*
int threshold;
threshold是扩容阈值，达到threshold就扩容，值为数组长度 x 加载因子
至于加载因子为什么是0.75是因为：在理想情况下，使用随机哈希码，在加载因子为0.75的情况下，节点出现在频率在Hash桶（表）中遵循参数平均为0.5的泊松分布
4. 讲述一下java8的hashmap的扩容过程
根据我们在第一道面试题中的结论 验证了 hashmap扩容方法的注释
当超过限制的时候会resize，然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。
我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的第一个bit位。看那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：
这个设计非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了
5. 讲述一下hashmap中用到的链表头插法与尾插法
jdk1.7插入元素到单链表中采用头插法，jdk1.8采用的是尾插法。
jdk1.7 插入链表的头部,有一种看法是新插入的数据被查询的概率比较大,插入到头部查询相对比较快. 但是在多线程环境中扩容可能会造成循环链表,导致CPU100%
jdk1.8 改进:采用尾插法,在扩容时不用重新计算hash值,元素索引值的变换是有规律的.
1.7版本的死循环问题
扩容的时候，会遍历原Entry数组，把所有的Entry重新Hash到新数组。为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。
让我们回顾一下Hash公式：
index = HashCode（Key） & （Length - 1）
当原数组长度为8时，Hash运算是和111B做与运算；新数组长度为16，Hash运算是和1111B做与运算。Hash结果显然不同
正常的rehash过程：
假如使用的hash算法就是简单的用key mod 一下也就是数组的长度
最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table[1]这里了
接下来的三个步骤是Hash表 resize成4，然后所有的<key,value> 重新rehash的过程
并发下的rehash
有两个线程，线程A和线程B，线程A在执行完Entry<K,V>next = e.next后被调度挂起，e指向key3，next指向key7
然后线程B开始执行，并且执行完了整个rehash过程
线程A在线程B rehash后，指向了线程B重组后的原链表，然后线程A开始执行
【注意：之所以并发操作有问题，不是在线程内部的newTable上，而是在线程A、B会操作oldTable，造成并发问题，因为线程B对oldTable中元素的指向的改变导致出现问题】
这里有个非常重要的地方，扩容后的newTable是方法参数，是属于线程私有！！！注意
线程A的rehash过程：
- 此时e指向key3，next指向key7，而key7的next因为线程B的rehash仍然指向key3【导致问题核心】，新的table表是线程A的，表中无元素
- 执行e.next=newTable[i]=null，让key3的next指向null，然后让key3成为3位置的头号节点，然后next指针仍然是1步骤中指向key7，然后因为e=next，所以e指向key7
- e指向key7，next指针因为1步骤的原因仍然指向key3，而key3的next是null，key7成为新的头结点，下一步e指向key3
- e指向key3，next指向null，因为e.next=newTable[i]，所以key3的next指向key7，而key7的next一直指向key3，这时候环形链表就构成了。又因为e=next，next=null，所以e指针和next指针均指向null
网友评论