亲宝软件园·资讯

展开

HashMap 源码赏析 JDK8

超级小小黑 人气:3

一、简介

HashMap源码看过无数遍了,但是总是忘,好记性不如烂笔头。

本文HashMap源码基于JDK8。

文章将全面介绍HashMap的源码及HashMap存在的诸多问题。

开局一张图,先来看看hashmap的结构。

 

 

二、历史版本

再次声明一下本文HashMap源码基于JDK8。不同版本HashMap的变化还是比较大的,在1.8之前,HashMap没有引入红黑树,也就是说HashMap的桶(桶即hashmap数组的一个索引位置)单纯的采取链表存储。这种结构虽然简单,但是当Hash冲突达到一定程度,链表长度过长,会导致时间复杂度无限向O(n)靠近。比如向HashMap中插入如下元素,你会神奇的发现,在HashMap的下表为1的桶中形成了一个链表。

1 map.put(1, 1);
2 map.put(17,17);
3 map.put(33,33);
4 map.put(49,49);
5 map.put(65,65);
6 map.put(81,81);
7 map.put(97,97);
...
16^n + 1

为了解决这种简单的底层存储结构带来的性能问题,引入了红黑树。在一定程度上缓解了链表存储带来的性能问题。引入红黑树之后当桶中链表长度超过8将会树化即转为红黑树(put触发)。当红黑树元素少于6会转为链表(remove触发)。

在这里还有一个很重要的知识点,树化和链表化的阈值不一样?想一个极端情况,假设阈值都是8,一个桶中链表长度为8时,此时继续向该桶中put会进行树化,然后remove又会链表化。如果反复put和remove。每次都会进行极其耗时的数据结构转换。如果是两个阈值,将会形成一个缓冲带,减少这种极端情况发生的概率。

上面这种极端情况也被称之为复杂度震荡。

类似的复杂度震荡问题ArrayList也存在。

 

三、基础知识

3.1,常量和构造方法

 1 // 16 默认初始容量(这个容量不是说map能装多少个元素,而是桶的个数)
 2 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
 3 // 最大容量值
 4 static final int MAXIMUM_CAPACITY = 1 << 30; 
 5 // 默认负载因子
 6 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 7 //树化阈值 一个桶链表长度超过 8 进行树化
 8 static final int TREEIFY_THRESHOLD = 8;
 9 //链表化阈值 一个桶中红黑树元素少于 6 从红黑树变成链表
10 static final int UNTREEIFY_THRESHOLD = 6;
11 //最小树化容量,当容量未达到64,即使链表长度>8,也不会树化,而是进行扩容。
12 static final int MIN_TREEIFY_CAPACITY = 64;
13 //桶数组,bucket. 这个也就是hashmap的底层结构。
14 transient Node<K,V>[] table;
15 //数量,即hashmap中的元素数量
16 transient int size;
17 //hashmap进行扩容的阈值。 (这个表示的元素多少,可不是桶被用了多少哦,比如阈值是16,当有16个元素就进行扩容,而不是说当桶被用了16个)
18 int threshold;
19 //当前负载因子,默认是 DEFAULT_LOAD_FACTOR=0.75
20 final float loadFactor;
21 /************************************三个构造方法***************************************/
22 public HashMap(int initialCapacity, float loadFactor) {//1,初始化容量2,负载因子
23     if (initialCapacity < 0)
24         throw new IllegalArgumentException("Illegal initial capacity: " +
25                                            initialCapacity);
26     if (initialCapacity > MAXIMUM_CAPACITY)// > 不能大于最大容量
27         initialCapacity = MAXIMUM_CAPACITY;
28     if (loadFactor <= 0 || Float.isNaN(loadFactor))
29         throw new IllegalArgumentException("Illegal load factor: " +
30                                            loadFactor);
31     this.loadFactor = loadFactor;
32     this.threshold = tableSizeFor(initialCapacity);//总要保持 初始容量为 2的整数次幂
33 }
34 public HashMap(int initialCapacity) {
35     this(initialCapacity, DEFAULT_LOAD_FACTOR);
36 }
37 public HashMap() {
38     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
39 }

 

3.2、桶的两种数据结构

前面说了,JDK8 HashMap采用的是链表+红黑树。

链表结构

 1 static class Node<K,V> implements Map.Entry<K,V> {
 2     final int hash;
 3     final K key;
 4     V value;
 5     Node<K,V> next;
 6 
 7     Node(int hash, K key, V value, Node<K,V> next) {
 8         this.hash = hash;
 9         this.key = key;
10         this.value = value;
11         this.next = next;
12     }
13 }

 

红黑树结构

 1 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
 2     TreeNode<K,V> parent;  // red-black tree links
 3     TreeNode<K,V> left;
 4     TreeNode<K,V> right;
 5     TreeNode<K,V> prev;    // needed to unlink next upon deletion
 6     boolean red;
 7     TreeNode(int hash, K key, V val, Node<K,V> next) {
 8         super(hash, key, val, next);
 9     }
10 }

 

3.3、hash算法实现

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 

计算桶下标方法

(n - 1) & hash//n表示HashMap的容量。 相当于取模运算。等同于 hash % n。

 

n其实说白了就是HashMap底层数组的长度。(n-1) & hash这个与运算,等同于hash % n。

hash()方法,只是key的hashCode的再散列,使key更加散列。而元素究竟存在哪个桶中。还是 (n - 1) & hash 结果决定的。

综合一下如下,在hashmap中计算桶索引的方法如下所示。

public static int index(Object key, Integer length) {
    int h;
    h = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    return (length - 1) & h;
}

 

假设当前hashmap桶个数即数组长度为16,现在插入一个元素key。

 计算过程如上图所示。得到了桶的索引位置。

在上面计算过程中,只有一步是比较难以理解的。也就是为什么不直接拿 key.hashcode() & (n - 1) ,为什么要用 key.hashcode() ^ (key.hashcode() >>> 16) 为什么要多一步呢?后面问题总结会详细介绍。

 

四、HashMap put过程源码

 1 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 2                boolean evict) {
 3     Node<K,V>[] tab; Node<K,V> p; int n, i;
 4     if ((tab = table) == null || (n = tab.length) == 0)//put1,懒加载,第一次put的时候初始化table(node数组)
 5         n = (tab = resize()).length;//resize中会进行table的初始化即hashmap数组初始化。
 6     if ((p = tab[i = (n - 1) & hash]) == null)//put2,(n - 1) & hash:计算下标。// put3,判空,为空即没hash碰撞。直接放入桶中
 7         tab[i] = newNode(hash, key, value, null);//将数据放入桶中
 8     else {//put4,有hash碰撞
 9         Node<K,V> e; K k;
10         if (p.hash == hash &&
11             ((k = p.key) == key || (key != null && key.equals(k))))//如果key已经存在,覆盖旧值
12             e = p;
13         else if (p instanceof TreeNode)//put4-3:如果是红黑树直接插入
14             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
15         else {//如果桶是链表,存在两种情况,超过阈值转换成红黑树,否则直接在链表后面追加
16             for (int binCount = 0; ; ++binCount) {
17                 if ((e = p.next) == null) {//put4-1:在链表尾部追加
18                     p.next = newNode(hash, key, value, null);
19                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
20                         treeifyBin(tab, hash);//put4-2:链表长度超过8,树化(转化成红黑树)
21                     break;
22                 }
23                 if (e.hash == hash &&
24                     ((k = e.key) == key || (key != null && key.equals(k))))//如果key已经存在,覆盖旧值
25                     break;
26                 p = e;
27             }
28         }
29         if (e != null) { // existing mapping for key //put5:当key已经存在,执行覆盖旧值逻辑。
30             V oldValue = e.value;
31             if (!onlyIfAbsent || oldValue == null)
32                 e.value = value;
33             afterNodeAccess(e);
34             return oldValue;
35         }
36     }
37     ++modCount;
38     if (++size > threshold)//put6,当size > threshold,进行扩容。
39         resize();
40     afterNodeInsertion(evict);
41     return null;
42 }

 

其实上面put的逻辑还算是比较清晰的。(吐槽一下JDK源码,可读性真的不好,可读性真的不如Spring。尤其是JDK中总是在if或者for中对变量进行赋值。可读性真的差。但是逻辑是真的经典)

总结一下put的过程大致分为以下8步。

1,懒汉式,第一次put才初始化table桶数组。(节省内存,时间换空间)
2,计算hash及桶下标。
3,未发生hash碰撞,直接放入桶中。
4,发生碰撞
    4.1、如果是链表,迭代插入到链表尾部。
    4.2、如果链表长度超过8,树化即转换为红黑树。(当数组长度小于64时,进行扩容而不是树化)
    4.3、如果是红黑树,插入到红黑树中。
5,如果在以上过程中发现key已经存在,覆盖旧值。
6,如果size > threshold。进行扩容。

 

以上过程中,当链表长度超过8进行树化,只是执行树化方法 treeifyBin(tab, hash); 。但是在该方法中还有一步判断,也就是当桶数组长度<64。并不会进行树化,而是进行扩容。你想想,假如容量为16,你就插入了9个元素,巧了,都在同一个桶里面,如果这时进行树化,树化本身就是一个耗时的过程。时间复杂度会增加,性能下降,不如直接进行扩容,空间换时间。

看看这个方法

 1 final void treeifyBin(Node<K,V>[] tab, int hash) {
 2     int n, index; Node<K,V> e;
 3     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//如果容量 < 64则直接进行扩容;不转红黑树。(你想想,假如容量为16,你就插入了9个元素,巧了,都在同一个桶里面,如果这时进行树化,时间复杂度会增加,性能下降,不如直接进行扩容,空间换时间)
 4         resize();
 5     else if ((e = tab[index = (n - 1) & hash]) != null) {
 6         TreeNode<K,V> hd = null, tl = null;
 7         do {
 8             TreeNode<K,V> p = replacementTreeNode(e, null);
 9             if (tl == null)
10                 hd = p;
11             else {
12                 p.prev = tl;
13                 tl.next = p;
14             }
15             tl = p;
16         } while ((e = e.next) != null);
17         if ((tab[index] = hd) != null)
18             hd.treeify(tab);
19     }
20 }

在put逻辑中还有最重要的一个过程也就是扩容。

 

五、扩容

5.1、扩容

 1     final Node<K,V>[] resize() {
 2         Node<K,V>[] oldTab = table;
 3         int oldCap = (oldTab == null) ? 0 : oldTab.length;
 4         int oldThr = threshold;
 5         int newCap, newThr = 0;
 6         if (oldCap > 0) {
 7             if (oldCap >= MAXIMUM_CAPACITY) {// 大于最大容量,不进行扩容(桶数量固定)
 8                 threshold = Integer.MAX_VALUE;
 9                 return oldTab;
10             }
11             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
12                      oldCap >= DEFAULT_INITIAL_CAPACITY)//扩容为原来的两倍,<< 位运算
13                 newThr = oldThr << 1; // double threshold threshold不在重新计算,同样直接扩容为原来的两倍
14         }
15         else if (oldThr > 0) // initial capacity was placed in threshold
16             newCap = oldThr;
17         else {               // zero initial threshold signifies using defaults
18             newCap = DEFAULT_INITIAL_CAPACITY;
19             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
20         }
21         if (newThr == 0) {
22             float ft = (float)newCap * loadFactor;
23             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
24                       (int)ft : Integer.MAX_VALUE);
25         }
26         threshold = newThr;
27         @SuppressWarnings({"rawtypes","unchecked"})
28             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建新的桶(原来的两倍)
29         table = newTab;
30         if (oldTab != null) {
31             for (int j = 0; j < oldCap; ++j) {//一共oldCap个桶
32                 Node<K,V> e;
33                 if ((e = oldTab[j]) != null) {//如果第j个桶没元素就不管了
34                     oldTab[j] = null;
35                     if (e.next == null)//只有一个元素,直接移到新的桶中(为什么不先判断是不是TreeNode?很简单,因为TreeNode没有next指针,在此一定为null,也能证明是一个元素。对于大多数没有hash冲突的桶,减少了判断,处处充满着智慧)
36                         newTab[e.hash & (newCap - 1)] = e;//计算桶下标,e.hash & (newCap - 1)是newCap哦
37                     else if (e instanceof TreeNode)
38                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);          
39                     else { // rehash  源码很经典                                      40                         Node<K,V> loHead = null, loTail = null;//下标保持不变的桶     41                         Node<K,V> hiHead = null, hiTail = null;//下标扩容两倍后的桶   42                         Node<K,V> next;                                            43                         do {                                                       44                             next = e.next;                                        
45                             if ((e.hash & oldCap) == 0) {//判断成立,说明该元素不用移动 
46                                 if (loTail == null)//尾空,头插                      47                                     loHead = e;                                   48                                 else//尾不空,尾插                                 49                                     loTail.next = e;                            50                                 loTail = e;                                     51                             }                                                   52                             else {//判断不成立,说明该元素要移位到 (j + oldCap) 位置 53                                 if (hiTail == null)                             54                                     hiHead = e;                                 55                                 else                                           56                                     hiTail.next = e;                          57                                 hiTail = e;                                   
58                             }
59                         } while ((e = next) != null);
60                         if (loTail != null) {
61                             loTail.next = null;
62                             newTab[j] = loHead;
63                         }
64                         if (hiTail != null) {
65                             hiTail.next = null;
66                             newTab[j + oldCap] = hiHead;
67                         }
68                     }
69                 }
70             }
71         }
72         return newTab;
73     }

 从以上源码总计一下扩容的过程:

1,创建一个两倍于原来(oldTab)容量的数组(newTab)。
2,遍历oldTab
    2.1,如果当前桶没有元素直接跳过。
    2.2,如果当前桶只有一个元素,直接移动到newTab中的索引位。(e.hash & (newCap - 1))
    2.3,如果当前桶为红黑树,在split()方法中进行元素的移动。
    2.4,如果当前桶为链表,执行链表的元素移动逻辑。

在以上过程中,我们着重介绍链表的元素移动。也就是上述代码中的39-68行。

首先,我们看其中

1 Node<K,V> loHead = null, loTail = null;//下标保持不变的桶       
2 Node<K,V> hiHead = null, hiTail = null;//下标扩容两倍后的桶

loHead和loTail分别对应经过rehash后下标保持不变的元素形成的链表头和尾。

hiHead和hiTail分别对应经过rehash后下标变为原来(n + oldIndex)后的链表头和尾。

经过上面变量,我们不难发现,桶中的数据只有两个去向。(oldIndex和 n + oldIndex)

接下来我们思考一个问题。为什么经过rehash,一个桶中的元素只有两个去向?

以下过程很烧脑,但是看懂了保证会收获很多。 更会体会到源码之美。

大致画一下图,如下所示。

 

HashMap的容量总是2的n次方(n <= 32)。

假设扩容前桶个数为16。

 看扩容前后的结果。观察扩容前后可以发现,唯一影响索引位的是hash的低第5位。

所以分为两种情况hash低第5位为0或者1。

1 当低第5位为0:newIndex = oldIndex
2 当低第5位为1:newIndex = oldIndex + oldCap

以上过程也就说明了为啥rehash后一个桶中的元素只有两个去向。这个过程我看没有博客介绍过。为什么在这里详细介绍这个呢?因为这个很重要,不懂这个就看不懂以上rehash代码,也很难体会到JDK源码的经典之处。给ConcurrentHashMap rehash时的锁打一个基础。

回到源码第45行。

if ((e.hash & oldCap) == 0)

这个判断成立,则说明该元素在rehash后下标不变,还在原来的索引位置的桶中。为什么?

 我们先看一下 (e.hash & oldCap) 

 看结果,如果判断 if ((e.hash & oldCap) == 0) 成立,也就是说hash的低第5位为0。

在上个问题我们推导桶中元素的两个去向的时候,发现低第5位的两种情况决定了该元素的去向。再观察上面问题推导中的hash的第一种情况当*为0;

 惊不惊喜,意不意外,神奇的发现,当hash低5位为0时,其新索引为依然为oldIndex。OK,你不得不佩服作者的脑子为何如此聪明。当然了这一切巧妙的设计都是建立在hashmap桶的数量总是2的n次方。

回到源码第60-67行。很简单了,将新的两个链表分别放到newTab的oldIndex位置和newIndex位置。正如我们上面推导的那样

1 if (loTail != null) {
2     loTail.next = null;
3     newTab[j] = loHead;//j 即oldIndex
4 }
5 if (hiTail != null) {
6     hiTail.next = null;
7     newTab[j + oldCap] = hiHead; //j + oldCap即newIndex
8 }

以上resize过程就说完了。

留一个问题,以上resize过程性能还能不能进一步优化呢?有兴趣的可以对比ConcurrentHashMap的这个rehash源码。你会神奇的发现JDK8的作者为了性能究竟有多拼。

当然resize过程在并发环境下还是存在一定问题的。接下来继续往下看。

 

5.2、JDK7并发环境扩容问题——循环链表

先看源码

 1  //将当前所有的哈希表数据复制到新的哈希表
 2 void transfer(Entry[] newTable, boolean rehash) {
 3        int newCapacity = newTable.length;
 4        //遍历旧的哈希表
 5        for (Entry<K,V> e : table) {
 6            while(null != e) {
 7                //保存旧的哈希表对应的链表头的下一个结点
 8                Entry<K,V> next = e.next;
 9                if (rehash) {
10                    e.hash = null == e.key ? 0 : hash(e.key);
11                }
12                //因为哈希表的长度变了,需要重新计算索引
13                int i = indexFor(e.hash, newCapacity);
14                //第一次循环的newTable[i]为空,赋值给当前结点的下一个元素,
15                e.next = newTable[i];
16                //将结点赋值到新的哈希表
17                newTable[i] = e;
18                e = next;
19            }
20        }
21 }

JDK7 hashmap采用的是头插法,也就是每put一个元素,总是插入到链表的头部。相对于JDK8尾插法,插入操作时间复杂度更低。

看上面transfer方法。假设扩容前数组长度为2,扩容后即长度为4。过程如下。(以下几张图片来自慕课网课程)

第一步:处理节点5,resize后还在原来位置。

第二步:处理节点9,resize后还在原来位置。头插,node(9).next = node(5);

第三步:处理节点11,resize后在索引位置3处。移动到新桶中。

并发环境下的问题

假设此时有两个线程同时put并同时触发resize操作。

线程1执行到,只改变了旧的链表的链表头,使其指向下一个元素9。此时线程1因为分配的时间片已经用完了。

紧接着线程2完成了整个resize过程。

线程1再次获得时间片,继续执行。解释下图,因为节点本身是在堆区。两个线程栈只是调整链表指针的指向问题。

当线程2执行结束后,table这个变量将不是我们关注的重点,因为table是两个线程的共享变量,线程2已经将table中的变量搬运完了。但是由于线程1停止的时间如上,线程1的工作内存中依然有一个变量next是指向9节点的。明确了这一点继续往下看。

当线程2执行结束。线程1继续执行,newTable[1]位置是指向节点5的。如下图。

如上图线程1的第一次while循环结束后,注意 e = next 这行代码。经过第一次循环后,e指向9。如下图所示。

按理来说此时如果线程1也结束了也没啥事了,但是经过线程2的resize,9节点时指向5节点的,如上图。所以线程1按照代码逻辑来说,依然没有处理完。然后再将5节点插入到newTable中,5节点继续指向9节点,这层循环因为5.next==null,所以循环结束(自己看代码逻辑哦,e是在while之外的,所以这里不会死循环)。如下图所示,循环链表形成。

然后在你下一次进行get的时候,会进入死循环。

最后想一下JDK7会出现死循环的根源在哪里?很重要哦这个问题,根源就在于JDK7用的是头插法,而resize又是从头开始rehash,也就是在老的table中本来是头的,到新table中便成为了尾,改变了节点的指向。

5.3、JDK8的数据丢失问题

上面介绍了JDK7中循环链表的形成,然后想想JDK8中的resize代码,JDK8中的策略是将oldTab中的链表拆分成两个链表然后再将两个链表分别放到newTab中即新的数组中。在JDK8会出现丢失数据的现象(很好理解,在这里就不画图了,感兴

趣的自己画一下),但是不会出现循环链表。丢数据总比形成死循环好吧。。。另外一点JDK8的这种策略也间接的保证了节点间的相对顺序。

好吧,还是说说JDK8的丢数据问题吧。

 1 do {
 2     next = e.next;
 3     if ((e.hash & oldCap) == 0) {//判断成立,说明该元素不用移动
 4         if (loTail == null)//尾空,头插
 5             loHead = e;
 6         else//尾不空,尾插
 7             loTail.next = e;
 8         loTail = e;
 9     }
10     else {//判断不成立,说明该元素要移位到 (j + oldCap) 位置
11         if (hiTail == null)
12             hiHead = e;
13         else
14             hiTail.next = e;
15         hiTail = e;
16     }
17 } while ((e = next) != null);
18 if (loTail != null) {
19     loTail.next = null;
20     newTab[j] = loHead;//j 即oldIndex
21 }
22 if (hiTail != null) {
23     hiTail.next = null;
24     newTab[j + oldCap] = hiHead; //j + oldCap即newIndex
25 }

假设两个线程,根据代码逻辑,线程1执行了4次循环让出时间片,如下图所示。

 此时链表table索引1位置的桶如下所示

 

 如果此时线程2也进行resize。此时线程2看到的oldTab是如上图所示的。很明显,接下来线程1执行完成,并顺利将两个链表放到了newTab中。

此时线程2又获取时间片并继续执行以下操作相当于之前线程1的resize结果被线程2覆盖了。此时就发生了数据的丢失。

 

终于介绍完了扩容过程,不容易啊。

 

六、HashMap get过程源码

 1 public V get(Object key) {
 2     Node<K,V> e;
 3     return (e = getNode(hash(key), key)) == null ? null : e.value;//get1,计算hash
 4 }
 5 final Node<K,V> getNode(int hash, Object key) {
 6     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
 7     if ((tab = table) != null && (n = tab.length) > 0 &&
 8         (first = tab[(n - 1) & hash]) != null) {// get2,(n - 1) & hash 计算下标
 9         if (first.hash == hash && // always check first node //get3-1,首先检查第一个元素(头元素),如果是目标元素,直接返回
10             ((k = first.key) == key || (key != null && key.equals(k))))
11             return first;
12         if ((e = first.next) != null) {
13             if (first instanceof TreeNode)//get3-2,红黑树
14                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
15             do {//get3-3,链表
16                 if (e.hash == hash &&
17                     ((k = e.key) == key || (key != null && key.equals(k))))
18                     return e;
19             } while ((e = e.next) != null);
20         }
21     }
22     return null;
23 }

看完了put的源码,会发现get过程是何其简单,大致过程如下

1,计算hash
2,计算下标
3,获取桶的头节点,如果头结点key等于目标key直接返回。
    3.1,如果是链表,执行链表迭代逻辑,找到目标节点返回。
    3.2,如果是红黑树,执行红黑树迭代逻辑,找到目标节点返回。

关于remove方法,不介绍了,无非就是就是get过程+红黑树到链表的转化过程。不介绍了。

 

七、问题总结

 7.1、为什么hashmap的容量必须是2的n次方。

回顾一下计算下标的方法。即计算key在数组中的索引位。

hash&(n - 1)

 

其中n就是hashmap的容量也就是数组的长度。

 

 

假设n是奇数。则n-1就是偶数。偶数二进制中最后一位一定是0。所以如上图所示, hash&(n - 1) 最终结果二进制中最后一位一定是0,也就意味着结果一定是偶数。这会导致数组中只有偶数位被用了,而奇数位就白白浪费了。无形中浪费了内存,同样也增加了hash碰撞的概率。

其中n是2的n次方保证了(两个n不一样哦,别较真)hash更加散列,节省了内存。

难道不能是偶数吗?为啥偏偏是2的n次方?

2的n次方能保证(n - 1)低位都是1,能使hash低位的特征得以更好的保留,也就是说当hash低位相同时两个元素才能产生hash碰撞。换句话说就是使hash更散列。

呃。。。个人觉得2在程序中是个特殊的数字,通过上文resize中的关于二进制的一堆分析也是建立在容量是2的n次方的基础上的。虽然这个解释有点牵强。如果大家有更好的解释可以在下方留言。

两层含义:

1,从奇偶数来解释。

2,从hash低位的1能使得hash本身的特性更容易得到保护方面来说。(很类似源码中hash方法中 <<< 16的做法)

 

7.2、解决hash冲突的方法

hashmap中解决hash冲突采用的是链地址法,其实就是有冲突了,在数组中将冲突的元素放到链表中。

一般有以下四种解决方案。详情度娘。

1 链地址法
2 开放地址法
3 再哈希法
4 建立公共溢出区

 

 

7.3、HashMap、HashTable、ConcurrentHashMap区别

HashMap是不具备线程安全性的。

HashTable是通过Synchronized关键字修饰每一个方法达到线程安全的。性能很低,不建议使用。

ConcurrentHashMap很经典,Java程序员必精通。下篇文章就介绍ConcurrentHashMap。该类位于J.U.C并发包中,为并发而生。

 

7.4、如何保证HashMap的同步

Map map = Collections.synchronizedMap(new HashMap());其实其就是给HashMap的每一个方法加Synchronized关键字。

性能远不如ConcurrentHashMap。不建议使用。

 

7.5、为什么引入红黑树

这个问题很简单,因为红黑树的时间复杂度表现更好为O(logN),而链表为O(N)。

为什么红黑树这么好还要用链表?

因为大多数情况下hash碰撞导致的单个桶中的元素不会太多,太多也扩容了。只是极端情况下,当链表太长会大大降低HashMap的性能。所以为了应付这种极端情况才引入的红黑树。当桶中元素很少比如小于8,维护一个红黑树是比较耗时的,因为红黑树需要左旋右旋等,也很耗时。在元素很少的情况下的表现不如链表。

一般的HashMap的时间复杂度用平均时间复杂度来分析。除了极端情况链表对HashMap整体时间复杂度的表现影响比较小。

 

7.6、为什么树转链表和链表转树阈值不同

其实上文中已经介绍了,因为复杂度震荡。详情请参考上文。

 

7.7、Capacity的计算

变相问一下这个问题就是当初始化hashMap时initialCapacity参数传的是18,HashMap的容量是什么?是32。

1     static final int tableSizeFor(int cap) {
2         int n = cap - 1;
3         n |= n >>> 1;
4         n |= n >>> 2;
5         n |= n >>> 4;
6         n |= n >>> 8;
7         n |= n >>> 16;
8         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
9     }

 

该方法大意:如果cap不是2的n次方则取大于cap的最小的2的n次方的值。当然这个值不能超过MAXIMUM_CAPACITY 。

(这里对这个方法没怎么看懂,明白的大神们回应在留言区指教。)

 

7.8、为什么默认的负载因子loadFactor = 0.75

 1      * Because TreeNodes are about twice the size of regular nodes, we
 2      * use them only when bins contain enough nodes to warrant use
 3      * (see TREEIFY_THRESHOLD). And when they become too small (due to
 4      * removal or resizing) they are converted back to plain bins.  In
 5      * usages with well-distributed user hashCodes, tree bins are
 6      * rarely used.  Ideally, under random hashCodes, the frequency of
 7      * nodes in bins follows a Poisson distribution
 8      * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 9      * parameter of about 0.5 on average for the default resizing
10      * threshold of 0.75, although with a large variance because of
11      * resizing granularity. Ignoring variance, the expected
12      * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
13      * factorial(k)). The first values are:
14      *
15      * 0:    0.60653066
16      * 1:    0.30326533
17      * 2:    0.07581633
18      * 3:    0.01263606
19      * 4:    0.00157952
20      * 5:    0.00015795
21      * 6:    0.00001316
22      * 7:    0.00000094
23      * 8:    0.00000006
24      * more: less than 1 in ten million

 

源码中有这么一段注释,重点就是  Poisson distribution 泊松分布。

以上是桶中元素个数和出现的概率对照表。

意思就是说当负载因子为0.75的时候,桶中元素个数为8的概率几乎为零。

通过泊松分布来看,0.75是"空间利用率"和"时间复杂度"之间的折衷。关于这个请参考《为什么默认的负载因子是0.75》。

 

7.9、HashMap中为什么用位运算而不是取模运算

主要是位运算在底层计算速度更快。

简单证明一下

1 long s1 = System.nanoTime();
2 System.out.println(2147483640 % 16);//8
3 long e1 = System.nanoTime();
4 long s2 = System.nanoTime();
5 System.out.println(2147483640 & 15);//8
6 long e2 = System.nanoTime();
7 System.out.println("取模时间:" + (e1 - s1));//取模时间:134200
8 System.out.println("与运算时间:" + (e2 - s2));//与运算时间:15800

题外话:还有一个刷leetcode题,二分法计算中心点。总结的经验,用除法会导致部分算法题超时。

1 long s1 = System.nanoTime();
2 System.out.println(1 + (2147483640 - 1) / 2);//1073741820
3 long e1 = System.nanoTime();
4 long s2 = System.nanoTime();
5 System.out.println(1 + (2147483640 - 1) >> 1);//1073741820
6 long e2 = System.nanoTime();
7 System.out.println("除法时间:" + (e1 - s1));//除法时间:20100
8 System.out.println("位运算时间:" + (e2 - s2));//位运算时间:15700

注意:一般二分法用left + (right - left)/2;因为如果用(right+left)/2;right + left容易>Integer.MAX_VALUE;

 

  如有错误的地方还请留言指正。
  原创不易,转载请注明原文地址: https://www.cnblogs.com/hello-shf/p/12168181.html

 

   参考文献:

  https://www.jianshu.com/p/003256ce41ce

  https://www.cnblogs.com/morethink/p/7762168.html

加载全部内容

相关教程
猜你喜欢
用户评论