JDK1.7版本中的HashMap

  1. 云栖社区>
  2. 博客>
  3. 正文

JDK1.7版本中的HashMap

技术小牛人 2018-03-10 15:01:15 浏览1139
展开阅读全文

以下讲解基于JDK1.7



16e2d5411abebb9936a0a8ca46147371.png


HashMap底层是一个数组,哈希值相同的元素放在数组中的相同的位置,多个相同哈希值的元素形成一个链表。也就是说,元素的组织形式是单向链表。

下面从put、get、remove这三个方法分析一下源代码,看看HashMap增删查改是怎么做的。

c1457a37a1263785263c4f295139c194.png

52c70c6639570c637115c51fce0b9edc.png

31ae5bd82dd27e186909af6f3e7f0824.png

构造HashMap对象的时候做了初始化,指定默认的初始容量(数组长度)和增长因子

接下来,从put开始分析


4266c06f740f92a3670abe063b774944.png

422ebfef9499513522b028f870209cf4.png

8549e057a56656e2bab37e2f90b13c13.png

从上面三段代码可以看出添加一个元素的基本流程:

(1)HashMap的key值允许为null,而且key为null的元素放在数组中下标为0的位置

(2)根据待插入元素的key值计算出一个哈希值,然后根据这个哈希值和数组的长度计算该元素将要放置的位置(PS:下标)。如果这个位置为空,那么直接插入。否则,遍历该位置上的链表,依次比较他们的key值是否相同,如果相同,则将用新值替换旧值,然后返回就值。

(3)正常插入,将待插入的元素放置在链表的头部,然后将其指向原先的链表头部(即:原先放置在待插入位置的元素)。也就是说,新插入的元素是放在头部的,我觉得这样做的好处可能是根据LRU的原则减少遍历的次数。

4aaa1f8dfd8c2aa5524e77b383f1d413.png

(4)有一种特殊情况是,扩容。

e353474a8dabc72e43738c338e3cda84.png

c22e2dfcf011e6bd26b17492f1fd5cae.png

9a6f0038999803732fd6a601ba1c3dc2.png

扩容就是,将原数组中的每个位置的元素都迁移到新数组中,在迁移到新数组的过程中同样先计算哈希值,然后得出将要放置在新数组中那个位置上。链表的迁移过程相当于将原先的链表倒置,先将头部的元素迁移过去,然后将下一个元素迁移过去,令next元素的next指向新数组位置上的元素,最终呈现出来的效果就是链表倒置。


接下来看get操作

a3ba157a678f086b90172ede47e6ee72.png

7f1b13557cabd806e2451490868996a9.png

get操作比较简单:

(1)根据key算哈希值,进而得出元素可能的位置,然后遍历该位置上的链表,比较key值是否相同,相同则返回,否则返回null


最后是remove


97e8dbac5c28d9a9fe3250c759858b34.png58c351170490d06642ff4e2e6b217824.png


删除也相对比较简单:

(1)删除元素所在位置,遍历链表,比较key值,找到待删除元素以后,如果当前只有一个元素,直接删除,此位置置位NULL,否则将前面元素的next指向后面元素。



HashMap在并发情况下存在的问题(并发就是没法保证顺序)

(1)插入的元素可能被覆盖

75421e9d2f9efb86b0993eacc39674dc.png

假设有两个线程都执行到这里,线程1它的key=A,value=aaa,线程2它的key=B,value=bbb。

假设i=1,那么线程1执行的时候table[1]=new Entry<>(1234, "A", "aaa", null);

等到线程2执行的时候table[1]=new Entry<>(1234, "B", "bbb", null);

于是乎,线程1插入的数据就丢失了(或者说是被覆盖了)

(2)put的时候,链表可能形成环形数据结构,导致如果查找一个不存在的元素时死循环

那么环状是怎么形成的呢?发生在扩容的时候。请看图

fe7de554410a6b5077ada724afc4b907.png


假设有两个元素A和B,它们的关系是A.next=B,B.next=null

大概就是下面这个样子

3848a9c0cc5f7fe380da2d7a1605b807.png

假设有两个线程,线程-1和线程-2,它们在执行插入的时候都发现需要扩容,于是乎都开始扩容。

当然,扩容是在它们自己的内存中进行的。假设线程-1完成对A元素的迁移后准备对B进行迁移并执行到Entry<K,V> next = e.next;时还没执行时线程被挂起了。执行到线程-2先执行完扩容,于是扩容后的指向关系变成了这个样子:B.next=A,A.next=null

c07b8da039ca7de381673f0b09bcba76.png

特别注意,看图上画的好像是元素直接放到数组的某个位置,但我们要知道,其它放的是元素的地址,也就是说元素本身的位置不变,修改的只是指针指向。尽管线程-2构造的新数组对线程-1而言是不可见的,但是不可否认,线程-2在扩容过程中已经将A和B的指向关系修改了,也就是说,此时,B是指向A的,这一点对线程-1而言是可见的。


接下来,线程-1醒来,继续执行

while(null != e) {

    Entry<,> next = e.;
    (rehash) {
        e.= == e.? : hash(e.);
    }
    i = (e., newCapacity);
    e.= newTable[i];
    newTable[i] = e;
    e = next;
}

此时,对照代码应该是这样的

e5d8c692c771bfecb2bde936bee2164a.png

经过这一遍,现在在新数组中的指向关系变成:B-->A-->NULL

紧接着,因为e已经是A了,所以null != e,于是再执行一遍

ecc603045ca1f804f44cce7d805a47a5.png


然后就变成这样了

15c1dd235ec478750eab54e90b07bf39.png

接下来,麻烦来了。

查找C,经过计算C应该与A、B在数组的同一个位置,于是遍历链表

ea09508843b2647c5dccd5874aaebc8c.png

于是,通过A找到B,通过B又找到A,通过A又找到B,通过B又找到A,如此反复,永远都不为null,死循环



终于讲明白了


最后,再提一点,就是hash方法,字符串和非字符串算哈希值的方法是不一样的

cbb2f3f52dcfd68e2d21a2e1327ee8c9.png

参考:

http://blog.csdn.net/zhuqiuhui/article/details/51849692

https://www.cnblogs.com/binyue/p/3726403.html


本文转自   手不要乱摸  51CTO博客,原文链接:http://blog.51cto.com/5880861/1984059

网友评论

登录后评论
0/500
评论
技术小牛人
+ 关注