[关闭]
@zero1036 2017-04-06T08:01:05.000000Z 字数 6475 阅读 1355

HashMap源码分析

Java-Base

HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的。

HashCode与Hash

HashCode：计算机散列码
Hash：通过散列码计算获得的散列值

Hash() --获取对象散列码

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

计算table位置索引

  1. int n = (tab = resize()).length;
  2. Node<K,V> p  = tab[i = (n - 1) & hash];

HashMap的数据结构及HashCode相等的情况带来的问题是，如何将具有不相同HashCode的Key对象，均匀地分布在数组中，同时将相同HashCode的Key，组合成链表。

Hashtable采用的策略是除法散列法，而HashMap则通过效率更高更巧妙hash & (length-1) 方法，同样实现了均匀的散列。如下例子，

巧妙之处在于以下3点：

1、由于table的长度length=2的整数次幂，确保了length为奇数，奇数的二进制最后一位尾数必为1，所以hash最后一位无论是1或是0，与运算结果都会产生1或0的结果。反之，如果Length为偶数，尾数是0，与运算结果只可能是0。导致所有位置索引的计算值都只能是偶数，浪费一半空间。

2、 通过与运算索引，一次运算效率更高，而且保证取样数据小于table长度，例如，长度为16（10000），length - 1 = 15（1111）；所有与15参与运算的Hash，实际运算都只有后4位，必然不会产生大于15的值

10001101 & 1111 = 1101
10000101 & 1111 = 101

  1. private static void test() {
  2.     int num = 156546;
  3.     int target = 0;
  5.     printInfo(target = 15 & (num + 1));//二进制：11；十进制3
  6.     printInfo(target = 15 & (num + 2));//二进制：100；十进制4
  7.     printInfo(target = 15 & (num + 3));//二进制：101；十进制5
  8.     printInfo(target = 15 & (num + 4));//二进制：110；十进制6
  9.     printInfo(target = 15 & (num + 5));//二进制：111；十进制7
  10.     printInfo(target = 15 & (num + 6));//二进制：1000；十进制8
  11.     printInfo(target = 15 & (num + 7));//二进制：1001；十进制9
  12.     printInfo(target = 15 & (num + 8));//二进制：1010；十进制10
  13. }

put()--插入目标对象

  2. public V put(K key, V value) {
  3.     return putVal(hash(key), key, value, false, true);
  4. }
  6. //Map接口put()方法的具体实现
  7. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  8.                boolean evict) {
  9.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  10.     if ((tab = table) == null || (n = tab.length) == 0)
  11.         n = (tab = resize()).length;
  12.     //table索引位置无节点，创建新节点
  13.     if ((p = tab[i = (n - 1) & hash]) == null)
  14.         tab[i] = newNode(hash, key, value, null);
  15.      //反之，有节点
  16.     else {
  17.         Node<K,V> e; K k;
  18.         //验证首节点（链表）相等即直接赋值
  19.         if (p.hash == hash &&
  20.             ((k = p.key) == key || (key != null && key.equals(k))))
  21.             e = p;
  22.         //验证首节点为树节点（红黑树）即执行树节点添加方法putTreeVal()。后续会有分析
  23.         else if (p instanceof TreeNode)
  24.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  26.         //TREEIFY_THRESHOLD : 链表转换红黑树的阈值，默认为8，当链表深度大于8时，treeifyBin()转换
  27.         else {
  28.             for (int binCount = 0; ; ++binCount) {
  29.                 if ((e = p.next) == null) {
  30.                     p.next = newNode(hash, key, value, null);
  31.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  32.                         treeifyBin(tab, hash);
  33.                     break;
  34.                 }
  36.                 //当链表包含相同的Key，则更新节点
  37.                 if (e.hash == hash &&
  38.                     ((k = e.key) == key || (key != null && key.equals(k))))
  39.                     break;
  40.                 p = e;
  41.             }
  42.         }
  43.         if (e != null) { // existing mapping for key
  44.             V oldValue = e.value;
  45.             if (!onlyIfAbsent || oldValue == null)
  46.                 e.value = value;
  47.             afterNodeAccess(e);
  48.             return oldValue;
  49.         }
  50.     }
  51.     ++modCount;
  52.     //重要：当HashMap的容量大于数组table的阈值时，对数组进行扩容，参考resize()说明。
  53.     if (++size > threshold)
  54.         resize();
  55.     afterNodeInsertion(evict);
  56.     return null;
  57. }

get()--获取目标对象

  1. public V get(Object key) {
  2.     Node<k,v> e;
  3.     return (e = getNode(hash(key), key)) == null ? null : e.value;
  4. }
  6. //Map接口get()方法的具体实现
  7. final Node<K,V> getNode(int hash, Object key) {
  8.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  10.     //通过hash值计算table位置索引（以上有分析 ），获得table上对应位置的首个链表Node
  11.     if ((tab = table) != null && (n = tab.length) > 0 &&
  12.         (first = tab[(n - 1) & hash]) != null) { 
  13.         //大牛注释：always check first node，首个Node直接验证hash，在数据量较少情况下提高性能
  14.         //hash相等，且key，bingo，找对目标Node
  15.         if (first.hash == hash && // always check first node
  16.             ((k = first.key) == key || (key != null && key.equals(k))))
  17.             return first;
  19.         //遍历链表，直至找到链表最后一个Node节点
  20.         if ((e = first.next) != null) {
  21.             if (first instanceof TreeNode)
  22.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  23.             do {
  24.                 if (e.hash == hash &&
  25.                     ((k = e.key) == key || (key != null && key.equals(k))))
  26.                     return e;
  27.             } while ((e = e.next) != null);
  28.         }
  29.     }
  30.     return null;
  31. }

1、判断是否目标节点的代码是：要求节点的hash值一致，这一点毫无疑问；通过==或equal()方法两次判断相等的原因，原因是不是所有数据类型都能通过==判断相等；例如string，new String("abc")与"abc"分别指向不同内存区域的数据，是不相等的。而equals()方法是将参数，强转成string，再转换为char[]，然后迭代，逐个char进行比较，因此是两个string的值之间的比较

  1. if (e.hash == hash &&
  2.     ((k = e.key) == key || (key != null && key.equals(k))))
  3. {}

2、遍历链表，加载链表首部节点永远优先于尾部节点。

resize()--数组扩容

  1. final Node<K,V>[] resize() {
  2.     Node<K,V>[] oldTab = table;
  3.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  4.     //oldThr：旧数组实际容量 = 长度 * 扩展因子0.75
  5.     int oldThr = threshold;
  6.     int newCap, newThr = 0;
  7.     //oldCap：旧数组长度
  8.     if (oldCap > 0) {
  9.         if (oldCap >= MAXIMUM_CAPACITY) {
  10.             threshold = Integer.MAX_VALUE;
  11.             return oldTab;
  12.         }
  13.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
  14.             newThr = oldThr << 1; // 实际容量扩充一倍
  15.     }
  16.     else if (oldThr > 0) // initial capacity was placed in threshold
  17.         newCap = oldThr;
  18.     else {               // zero initial threshold signifies using defaults
  19.         newCap = DEFAULT_INITIAL_CAPACITY;
  20.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  21.     }
  22.     //数组实际容量为0时，初始化：newThr = 长度 * 扩展因子0.75
  23.     if (newThr == 0) {
  24.         float ft = (float)newCap * loadFactor;
  25.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  26.                     (int)ft : Integer.MAX_VALUE);
  27.     }
  28.     threshold = newThr;
  29.     @SuppressWarnings({"rawtypes","unchecked"})
  30.         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  31.     table = newTab;
  32.     if (oldTab != null) {
  33.         for (int j = 0; j < oldCap; ++j) {
  34.             Node<K,V> e;
  35.             if ((e = oldTab[j]) != null) {
  36.                 oldTab[j] = null;
  37.                 if (e.next == null)
  38.                     newTab[e.hash & (newCap - 1)] = e;
  39.                 else if (e instanceof TreeNode)
  40.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  41.                 else { // preserve order
  42.                     Node<K,V> loHead = null, loTail = null;
  43.                     Node<K,V> hiHead = null, hiTail = null;
  44.                     Node<K,V> next;
  45.                     do {
  46.                         next = e.next;
  47.                         if ((e.hash & oldCap) == 0) {
  48.                             if (loTail == null)
  49.                                 loHead = e;
  50.                             else
  51.                                 loTail.next = e;
  52.                             loTail = e;
  53.                         }
  54.                         else {
  55.                             if (hiTail == null)
  56.                                 hiHead = e;
  57.                             else
  58.                                 hiTail.next = e;
  59.                             hiTail = e;
  60.                         }
  61.                     } while ((e = next) != null);
  62.                     if (loTail != null) {
  63.                         loTail.next = null;
  64.                         newTab[j] = loHead;
  65.                     }
  66.                     if (hiTail != null) {
  67.                         hiTail.next = null;
  68.                         newTab[j + oldCap] = hiHead;
  69.                     }
  70.                 }
  71.             }
  72.         }
  73.     }
  74.     return newTab;
  75. }

1、扩容的时机：resize()方法在putVal()方法中调用，每次往HashMap中添加新的对象（注意是size是整个HashMap的大小，非数组长度，亦非链表或红黑树的深度），HashMap的数据量大于扩容阈值threshold时，对table进行扩容。默认情况，扩容阈值：threshold = 12 = 16(table长度阈值) * 0.75(扩充因子)，

  1. if (++size > threshold)
  2.     resize();

2、扩容的本质：计算新的容量值，创建新数组，重新计算原数组的各个链表（红黑树）的新位置，拷贝至新数组。

  1. Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

3、扩容阈值threshold：HashMap的数据量大于扩容此值时，对table进行扩容；
填充因子loadFactor：threshold = table.length * loadFactor;
例如默认情况：table默认长度为16，loadFactor默认为0.75，因此，threshold = 16 * 0.75 = table.length * loadFactor 12。根据第1点，即table有16个位置，本个HashMap最多也能容纳12个对象，超出则需要扩容table。

当12个对象Hash位置全部不同时，达到该loadFactor下最佳空间利用率：
【a】【b】【c】【d】【e】【f】【g】【h】【i】【j】【k】【l】【】【】【】【】
反之：
【a-b】【c-d-e】【f-g-h-i】【j】【k-l】【】【】【】【】【】【】【】【】【】【】【】

当loadFactor填充因子越大，table填满程度越高：假设以下例子全部达到最佳空间利用率
1：【a】【b】【c】【d】【e】【f】【g】【h】【i】【j】【k】【l】【m】【o】【p】【q】
0.75：【a】【b】【c】【d】【e】【f】【g】【h】【i】【j】【k】【l】【 】【 】【 】【 】

4、扩容方式：table长度与扩容阈值分别增大一倍，其结果必须为2的幂。

  1. newCap = oldCap << 1;
  2. newThr = oldThr << 1;

5、空间与性能的平衡：其实是空间利用率与冲突机会的平衡。

假设loadFactor为1，空间利用率100%，16个位置摆放的16个对象，通过算法(16 - 1) & hash获得的下标范围必然是[0, 15]，若loadFactor为0.75，通过(31 - 1) & hash计算，16个对象的下标范围则是[0, 31]。相比于有31个位置可以摆放，只有16个位置的冲突机会必然更大。

然而，冲突机会越大，意味着查询插入时要遍历单个位置上链表的可能越高，性能越低。
结论：loadFactor越大，空间利用率越高；越小，则查询性能越高；

如果机器内存足够，并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机器内存紧张，并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它，让它取默认值0.75就好
了。

实现最少使用cache

待

参考博文：

位运算博文：http://blog.csdn.net/is_zhoufeng/article/details/8112199

hashMap源码分析：http://www.cnblogs.com/ITtangtang/p/3948406.html

hash()计算原理分析：http://blog.csdn.net/huzhigenlaohu/article/details/51802457

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注