iCMS

Java源码解读(一)——HashMap

好喜欢专业转载优质博客文章的地方哦~

HashMap作为常用的一种数据结构,阅读源码去了解其底层的实现是十分有必要的。在这里也分享自己阅读源码遇到的困难以及自己的思考。

HashMap的源码介绍已经有许许多多的博客,这里只记录了一些我看源码过程中的疑问,一些基础知识不再讲解。

一:Hash值的来源和使用

1 public V put(K key,V value) {

2 return putVal(hash(key),key,value,false,true);

3 }

4

5 static final int hash(Object key) {

6 int h;

7 // <<< 无符号右移

8 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

9 }

这里是put()方法,里面有一个调用hash(key)就是得到hash值:

如果key为null,则返回0。否则则返回 key的(h = key.hashCode()) ^ (h >>> 16)(hashCode 异或 hashCode无符号右移16位),既二次散列,这么做的原因是为了尽可能的分散到桶(数组)各个位置,避免数据扎堆放在一个桶里面。提高HashMap运算效率。其中HashCode()是本地方法,不同的jvm会有不同的结果。

例 hashcode : 0001 1000 0001 0001 1111 0001 0110 0000 ^ 0000 0000 0000 00000001 1000 0001 0001

相当于hashCode()的高16位异或低16位。这样就相当于32位数据都参与到了Hash运算。这样使得hash更加散列,尽可能的桶寻址更分散。

这里有专门的传送门http://blog.csdn.net/anxpp/article/details/51234835。

其实按照我的理解,无符号

得到了key的hash值,又是如何运用的哪?下面的代码不需要看那么多,如果有闲心可以看一看~

在putVal()方法中第9行代码,if ((p = tab[i = (n - 1) & hash]) == null),通过(n-1 & hash)与运算得到下标位置,这就是根据hash值得到了桶(数组)的位置。

&操作同时也保证了不会数组越界,(n-1)是桶(数组)界限。

Hash算法本质上就是三步:取key的hashCode值、高位运算、取模运算

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 //table 是否为空,初始化或者加倍表的大小。

5 if ((tab = table) == null || (n = tab.length) == 0)

6 n = (tab = resize()).length;

7 //i = (n - 1) & hash,计算出来下标,这个下标为空,说明没有被占用,直接newNode.

8 //没有发生Hash碰撞

9 if ((p = tab[i = (n - 1) & hash]) == null)

10 tab[i] = newNode(hash,null);

11 else {

12 Node<K,V> e; K k;

13 //判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,相同 e = p;

14 if (p.hash == hash &&

15 ((k = p.key) == key || (key != null && key.equals(k))))

16 e = p;

17 //判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对

18 else if (p instanceof TreeNode)

19 e = ((TreeNode<K,V>)p).putTreeVal(this,tab,hash,value);

20 else {// 该链为链表

21 //遍历table[i],判断链表长度是否大于TREEIFY_THRESHOLD(默认值为8),

22 //大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

23 for (int binCount = 0; ; ++binCount) {

24 //进入链表

25 if ((e = p.next) == null) {

26 p.next = newNode(hash,null);

27 //是否转为红黑树

28 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

29 treeifyBin(tab,hash);

30 break;

31 }

32 if (e.hash == hash &&

33 ((k = e.key) == key || (key != null && key.equals(k))))

34 break;

35 p = e;//进入下一个节点

36 }

37 }

38 if (e != null) { // existing mapping for key

39 V oldValue = e.value;

40 if (!onlyIfAbsent || oldValue == null)

41 e.value = value;

42 afterNodeAccess(e);

43 return oldValue;

44 }

45 }

46 ++modCount;

47 //长度是否超过当前允许的最大值,重新设置大小

48 if (++size > threshold)

49 resize();

50 afterNodeInsertion(evict);

51 return null;

52 }

如果对hashCode感兴趣的话,可以开这个门https://www.cnblogs.com/dolphin0520/p/3681042.html

二 HashMap的扩容resize()

看代码就是一个循序渐进的过程。

我们知道桶(数组)的下标是根据(n-1)&hash得到的,当HashMap扩容后(n-1)就会发生变化啊,这样不就会扩容后寻不到下标了吗?

没错,这是一个很简单的问题,但是我看的时候没有看全就回家了,在地铁上想了一路怎么解决,然后猜测是扩容后会重新把所有数据在计算一遍。回到家后,我就去看代码对这个想法进行验证。

确实如此,所以我觉得扩容真心费劲。这里贴一下resize()方法。比较长~

从第30行就开始处理数据,使其根据新的容量(n-1)重新分配下标。当然,分配也不是漫无目的的:

在第56,57行代码中中:

Node<K,V> loHead = null,loTail = null;//没有改变索引位置的记录loHead【链表】,loTail 当前链表的尾节点

Node<K,V> hiHead = null,hiTail = null;//改变索引位置的记录hiHead【链表】,hiTail 当前链表的尾节点


一个原来数据重新分配后,只有两个位置可以去~

原封不动的还在原来下标 newTab[j]

换新的下标,但是位置是固定的 newTab[j + oldCap]

这是什么原因导致的那?


我们知道,HashMap的桶(数组)扩容是扩容为原来的两倍 (newCap = oldCap << 1)。也就是说,原来的(n-1)是1111,现在成了1 1111 ,而key的hash是不会变的。

两者再次进行&运算,要么,多一个高位1。要么不变。例如:


Java源码解读(一)——HashMap

每次扩容都会将全部元素计算一遍,所以扩容的开销还是很大的。一篇传送门,如果不是很懂,可以看这里~http://blog.csdn.net/bnmb888/article/details/771644851 final Node<K,V>[] resize() {2 Node<K,V>[] oldTab = table;3 int oldCap = (oldTab == null) ? 0 : oldTab.length;//得到原数组(哈希桶)长度4 int oldThr = threshold;//原来所能容纳的key-value对极限,阈值。5 int newCap,newThr = 0;//新的长度,新的阈值。6 if (oldCap > 0) {7 if (oldCap >= MAXIMUM_CAPACITY) {//超过了hashMap最大(哈希桶)容量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 左移一位14 }15 else if (oldThr > 0) // initial capacity was placed in threshold 哈希桶长度为0,且初始化HashMap时设置了长度16 newCap = oldThr;17 else { // zero initial threshold signifies using defaults18 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) {32 Node<K,V> e;33 if ((e = oldTab[j]) != null) {34 oldTab[j] = null;35 if (e.next == null)36 newTab[e.hash & (newCap - 1)] = e;37 else if (e instanceof TreeNode)38 ((TreeNode<K,V>)e).split(this,newTab,j,oldCap);39 else { // preserve order(保持次序)40 //原来的hash值新增的那个bit是1还是0,是0的话索引没变,是1的话索引变成“原索引+oldCap”,即newTab[j + oldCap]41 /**42 * 示例1:43 e.hash=10 0000 101044 oldCap=16-1 0000 1111


newCap=32-1 0001 111145 &old=0 0000 1010 比较高位的第一位


&new=0 0000 101046 结论:元素位置在扩容后数组中的位置没有发生改变 放入 loHead4748 示例2:49 e.hash=17 0001 000150 oldCap=16-1 0000 1111


newCap=32-1 0001 111151 &old =0 0000 0001 比较高位的第一位


&new =1 0001 000152 结论:元素位置在扩容后数组中的位置发生了改变,新的下标位置是[原下标位置+原数组长度] 放入 hiHead53 *54 */55 Node<K,loTail = null;//没有改变索引位置的记录loHead【链表】,loTail 当前链表的尾节点56 Node<K,hiTail = null;//改变索引位置的记录hiHead【链表】,hiTail 当前链表的尾节点57 Node<K,V> next;58 do {59 next = e.next;60 // 索引还是原索引61 if ((e.hash & oldCap) == 0) {//如:oldCap 是 16,即二进制 1 0000 ,(1111),相与,可以判断e.hash的高位是否是0。为0则进入if语句62 if (loTail == null)//loHead链表首位为null63 loHead = e;//链表首位放入e64 else65 loTail.next = e;//依次放入节点,保持次序。66 loTail = e;//记录当前节点位置67 }68 //索引改为 【原索引+oldCap】69 else {70 if (hiTail == null)71 hiHead = e;72 else73 hiTail.next = e;74 hiTail = e;75 }76 } while ((e = next) != null);77 //原索引位置放入整个loHead链表78 if (loTail != null) {79 loTail.next = null;80 newTab[j] = loHead;81 }82 //原索引+oldCap位置放入整个hiHead链表83 if (hiTail != null) {84 hiTail.next = null;85 newTab[j + oldCap] = hiHead;86 }87 }88 }89 }90 }91 return newTab;92 }三HashMap的红黑树操作JDK1.8以后,当HashMap的链表过长时(TREEIFY_THRESHOLD = 8;),会将链表转化为红黑树。在putVal()方法中有介绍。当链表(UNTREEIFY_THRESHOLD = 6)会将其拆分,但是仅仅是在resize()的时候会有这一步操作,remove并不会。38行:((TreeNode<K,oldCap)该方法描述为:调整树结构,树太小拆分掉。 仅从调整大小的时候调用;这个方法是寻找树节点finalTreeNode<K,V>getTreeNode(inth,Objectk){//当前节点的父节点是否为null,不为null,寻找根结点(root()),为null,当前即为根结点return((parent!=null)?root():this).find(h,k,null);}1 final TreeNode<K,V> find(int h,Object k,Class<?> kc) {2 //p是调用这个方法的对象3 //getTreeNode(int h,Object k),p是root对象4 TreeNode<K,V> p = this;5 do {6 int ph,dir; K pk;7 TreeNode<K,V> pl = p.left,pr = p.right,q;8 //hash值,对于任何给定的object,hash值是相同的9 if ((ph = p.hash) > h) //当前节点hash值大于寻找的哈希值,寻找左孩子10 p = pl;11 else if (ph < h)//当前节点hash值小于寻找的哈希值,寻找右孩子12 p = pr;13 else if ((pk = p.key) == k || (k != null && k.equals(pk)))//hash值相同,key值相同,返回该节点p14 return p;15 else if (pl == null)//key值不同,左孩子为null(红黑树的叶子节点),p改为右孩子。红黑树中,为null说明已经到达叶子节点,所以转向pr16 p = pr;17 else if (pr == null)//key值不同,右孩子为null(红黑树的叶子节点),p改为左孩子。18 p = pl;19 else if ((kc != null || //自定义的比较(实现comparable接口的类20 (kc = comparableClassFor(k)) != null) && //Object k(map的key)是否实现了comparable接口,是的话返回该实现类21 (dir = compareComparables(kc,pk)) != 0) //在kc类中 调用k.compareTo(pk),自定义方法,根据返回值决定去左孩子还是右孩子22 p = (dir < 0) ? pl : pr;23 else if ((q = pr.find(h,kc)) != null)//hash值相同,key值不同且左孩子右孩子都存在,递归find右孩子24 return q;25 else //hash值相同,key值不同且左孩子右孩子都存在,右孩子没有找到,find左孩子26 p = pl;27 } while (p != null);//是否到叶子节点,红黑树叶子节点均为null28 return null;29 }更多的HashMap知识,以后有空会继续更新。Java源码所写的注释,上传到了GitHub。会持续更新注释内容。https://github.com/coldwindYBMC/Java_sourcehttps://i.cnblogs.com/EditPosts.aspx?postid=8214358
0

上一篇:

:下一篇

精彩评论

暂无评论...
验证码 换一张
取 消

热门标签