HashMap结构分析

水深无声 2022-10-09 00:46 161阅读 0赞

本篇文章是网上多篇文章的精华的总结，结合自己看源代码的一些感悟，其中线程安全性和性能测试部分并未做实践测试，直接是“拿来”网上的博客的。

**哈希表概述**

哈希表本质上一个数组，数组中每一个元素称为一个箱子（Bin），箱子中存放的是键值对**Entry<K,V>**链表，因而也称之为链表散列。

我们可以用图来形象地说明这个结构：

![f0f4b94aecb68c5b695521c6a0f04e10.png][]

哈希表是如何工作的？

**存储**

**Step1：**根据哈希函数来计算HashCode值h，其中键值对**Entry<K,V>**的K来计算时需要的参数。

**Step2：**根据HashCode，来计算存放在哈希表（长度为n）中的位置（箱子的位置），一种计算方法是取余：h%n。

**Step3：**如果该箱子中已经存在键值对数据，则使用开放寻址法或拉链法解决冲突。

**获取**

**Step1：**根据key值计算HashCode的值h。

**Step2：**假设箱子的个数为 n，那么这个键值对应该放在第 (h % n) 个箱子中。

**Step3：**如果这个箱子里有多个键值对，同时假设箱子里的多个值是采用链表的方式存储，则需要遍历这个链表，复杂度为O(n)。

**扩容**

哈希表还有 一个重要的属性：负载因子，它是衡量哈希表的空/满程度，一定程度上也能体现查询的效率。其计算公式为：

> **负载因子 = 总键值对数 / 箱子数量**

负载因子越大，意味着哈希表越满，越容易导致冲突（更大的概念找到同一个箱子上），因而查询效率也就更低。因而，一般来说，当负载因子大于某个常数（可能是1，也可能是其他值，Java8的HashMap的负载因子为0.75）时，哈希表就会自动扩容。

哈希表在扩容的时候，一般都会选择扩大2的倍数，同时将原来的哈希表的数据迁移到新的哈希表中，这样即使key的哈希值不变，对箱子的取余结果（假设我们用这种方法来计算HashCode）也会不同，因此所有的箱子和元素的存放位置都有可能发生变化，这个过程也称为重哈希（rehash）。

哈表的扩容并不能有效解决负载因子过大的问题，因为在前面的取HashCode的方法中，假设所有key的HashCode值都一样，那么即使扩容以后他们在哈希表中的位置也不会变，实际存放在箱子中的链表长度也不变，因此也就不能提高哈希表的查询速度。

因而，哈希表存在以下两个问题：

1、在扩容的时候，重哈希的成本比较大

2、如果Hash函数设计地不合理（如上面举例说明的取余），会导致哈希表中极端情况下变成线性表，性能极低。

我们下面来看看Java8中是如何处理这两个问题的。

以上这部分内容多参考自：**[深入理解哈希表][Link 1]** ，图片来自于**[HashMap的图示][HashMap]**

**Java8中的HashMap**

在说明这个问题之前，我们来看下HashMap在Java8中在类图关系，如下所示：

![9416bc6ba9a731d9a02067fd0c94ce42.png][]

Java8中通过如下几种方式来解决上面的两个问题：

**一、让元素分布地更合理**

（下面这部分不知道是哪位大神写的，原文照抄吧）

学过概率论的读者也许知道，理想状态下哈希表的每个箱子中，元素的数量遵守泊松分布：

![7b75a2beb9523723db33d12b28f167c6.png][]

当**负载因子为 0.75** 时，上述公式中 λ 约等于 0.5，因此箱子中元素个数和概率的关系如下：

这就是为什么我们将0.75设为负载因子，同时针对箱子中链表长度超过8以后要做另外的优化（一来是优化的概念较小，二来是优化过后的效率提升明显）。所以，一般情况下负载因子不建议修改；同时如果在数量为8的链表的概率较大，则几乎可以认为是哈希函数设计有问题导致的。

**二、通过红黑树让查询更有效率（O(n)—>O(Log(n))）**

第一点已经说明，当箱子中的链表元素超过8个时，会将这个链表转为红黑树，红黑树的查找效率为O(log(n))。红黑树的示图如下：

![da6a49bc59fe0b24b1fdc9d7a55521e5.png][]

**三、让扩容时重哈希(rehash)的成本变得更小**

在Java7中，重哈希是要重新计算Hash值的，而在Java8中，通过高位运算的巧妙设计，避免了这种计算。下面我们举例说明：

我们要在初始大小为**2**的HashMap中存储3、5、7这3个值，Hash函数为取余法。

**Step1：**在开始的时候，3、5、7经过Hash过后 3%2=1、5%2=1、7%2=1，因而3、5、7存储在同一个箱子的链表中（**地址为1**）。

**Step2：**现在扩容了，扩容后的大小为2\*2=4，现在经过Hash后3%4=3、5%4=1、7%4=3，因而3与7一起放在箱子的链表中（**地址为3**），5单独存放在一个箱子里（**地址为1**）。

整个过程如下图所示：

![3a46694a52cbc67f635b262a4e9ddd90.png][]

我们注意到，在扩容后3和7的位置变化了，由1—>3**（=1+2）**

**      **再进行扩容，由4容为8，那么经过Hash后，3%8=3、5%8=5、7%8=7，分别存放于3、5**（=1+4）**、7**（=3+4）**这几个位置中。

我们发现，扩容后的元素要么在原位置，要么在原位置再移动2次幂的位置，整个过程只需要使用一个**位运算符<<**就可以了（在源码的resize方法中可以找到）。

我们用计算机的地址来展示这个过程：

![2eb012dc241d388f10378474c416e9b2.png][]

n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

![ce5e207238b2f8050fd1e457982f42b2.png][]

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

![5c5f4068e14ec7b27e5f7d315e260f19.png][]

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。

以上这部分中的图示和位移讲解的内容参考自：[**深入分析hashmap**][hashmap]

另外：

**四：我们可以通过适当地初始化大小来控制扩容的次数：**既然扩容是不可避免的，我们就尽可能少地让它发生，要实际编程的时候，应该根据业务合理地设置初始大小的值。

此外，Java8中HashMap还提供了另外一些参数来控制HashMap的性能，如下所示：

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

/**
         * 默认的初始化大小(必须为2的幂)
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /**
         * 最大的存储数量(默认的数量,可以在构造函数中指定)
         * 必须为2的幂同时小于2的30次方
         */
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /**
         * 默认的负载因子,可以在构建函数中指定
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        /**
         * HashMap由链表转为红黑树存储的阀值
         * 1.8提供的新特性
         */
        static final int TREEIFY_THRESHOLD = 8;
    
        /**
         * HashMap由红黑树转为链表存储的阀值
         */
        static final int UNTREEIFY_THRESHOLD = 6;
    
        /**
         * HashMap的箱子中的链表转为红黑树之前还有一个判断:
         * 只在所有箱子(键值对)的数量大于64才会发生转换
         * 这样是为了避免在哈希表建立初期,多个键值对恰好被放入了同一个链表而导致不必要的转化
         */
        static final int MIN_TREEIFY_CAPACITY = 64;

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

**源码中的关键方法**

** 方法一、hash方法**

1 static final int hash(Object key) {
    2         int h;
    3         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//这里其实就要求大家来重写HashCode方法
    4     }

** 方法二、putVal方法**

下面是putVal方法的执行过程图示：

![254a73e0fd145a77c87cc735d0eec806.png][]

![961ddebeb323a10fe0623af514929fc1.png][]

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

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      // 步骤①：tab为空则创建
     5      if ((tab = table) == null || (n = tab.length) == 0)
     6          n = (tab = resize()).length;
     7      // 步骤②：计算index，并对null做处理
     8      if ((p = tab[i = (n - 1) & hash]) == null)
     9          tab[i] = newNode(hash, key, value, null);
    10      else {
    11          Node<K,V> e; K k;
    12          // 步骤③：节点key存在，直接覆盖value
    13          if (p.hash == hash &&
    14              ((k = p.key) == key || (key != null && key.equals(k))))
    15              e = p;
    16          // 步骤④：判断该链为红黑树
    17          else if (p instanceof TreeNode)
    18              e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    19         // 步骤⑤：该链为链表
    20          else {
    21              for (int binCount = 0; ; ++binCount) {
    22                  if ((e = p.next) == null) {
    23                      p.next = newNode(hash, key,value,null);
    24                         //链表长度大于8转换为红黑树进行处理
    25                      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
    26                          treeifyBin(tab, hash);
    27                      break;
    28                  }
    29                     // key已经存在直接覆盖value
    30                  if (e.hash == hash &&
    31                      ((k = e.key) == key || (key != null && key.equals(k))))
    32                             break;
    33                  p = e;
    34              }
    35          }
    36         
    37          if (e != null) { // existing mapping for key
    38              V oldValue = e.value;
    39              if (!onlyIfAbsent || oldValue == null)
    40                  e.value = value;
    41              afterNodeAccess(e);
    42              return oldValue;
    43          }
    44      }
    45      ++modCount;
    46      // 步骤⑥：超过最大容量 就扩容
    47      if (++size > threshold)
    48          resize();
    49      afterNodeInsertion(evict);
    50      return null;
    51  }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

**      **这个 getNode() 方法就是根据哈希表元素个数与哈希值求模（`使用的公式是 (n - 1) &hash`）得到 key 所在的桶的头结点，如果头节点恰好是红黑树节点，就调用红黑树节点的 getTreeNode() 方法，否则就遍历链表节点。

** 方法三、节点查找方法getNode**

![961ddebeb323a10fe0623af514929fc1.png][]

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

1 final Node<K,V> getNode(int hash, Object key) {
     2     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
     3     if ((tab = table) != null && (n = tab.length) > 0 &&
     4         (first = tab[(n - 1) & hash]) != null) {
     5        if (first.hash == hash && // always check first node
     6             ((k = first.key) == key || (key != null && key.equals(k))))
     7             return first;
     8         if ((e = first.next) != null) {
     9             if (first instanceof TreeNode)
    10                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    11             do {
    12                if (e.hash == hash &&
    13                     ((k = e.key) == key || (key != null && key.equals(k))))
    14                     return e;
    15             } while ((e = e.next) != null);
    16         }
    17     }
    18     return null;
    19 }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

** **

**方法四、红黑树生成方法**

![961ddebeb323a10fe0623af514929fc1.png][]

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

1 //将桶内所有的 链表节点 替换成 红黑树节点
     2 
     3 final void treeifyBin(Node<K,V>[] tab, int hash) {
     4 
     5     int n, index; Node<K,V> e;
     6 
     7     //如果当前哈希表为空，或者哈希表中元素的个数小于 进行树形化的阈值(默认为 64)，就去新建/扩容
     8 
     9    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    10 
    11         resize();
    12 
    13     else if ((e = tab[index = (n - 1) & hash]) != null) {
    14 
    15         //如果哈希表中的元素个数超过了 树形化阈值，进行树形化
    16 
    17         // e 是哈希表中指定位置桶里的链表节点，从第一个开始
    18 
    19         TreeNode<K,V> hd = null, tl = null; //红黑树的头、尾节点
    20 
    21         do {
    22 
    23             //新建一个树形节点，内容和当前链表节点 e 一致
    24 
    25             TreeNode<K,V> p = replacementTreeNode(e, null);
    26 
    27             if (tl == null) //确定树头节点
    28 
    29                 hd = p;
    30 
    31            else {
    32 
    33                p.prev = tl;
    34 
    35                 tl.next = p;
    36 
    37             }
    38 
    39             tl = p;
    40 
    41         } while ((e = e.next) != null); 
    42 
    43         //让桶的第一个元素指向新建的红黑树头结点，以后这个桶里的元素就是红黑树而不是链表了
    44 
    45         if ((tab[index] = hd) != null)
    46 
    47             hd.treeify(tab);
    48 
    49     }
    50 
    51  }
    52 
    53     TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    54 
    55     return new TreeNode<>(p.hash, p.key, p.value, next);
    56 
    57  }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

**方法五、红黑树节点查找方法**

![961ddebeb323a10fe0623af514929fc1.png][]

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

1 final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
     2             TreeNode<K,V> p = this;
     3             do {
     4                 int ph, dir; K pk;
     5                 TreeNode<K,V> pl = p.left, pr = p.right, q;
     6                 if ((ph = p.hash) > h)
     7                     p = pl;
     8                 else if (ph < h)
     9                     p = pr;
    10                 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
    11                     return p;
    12                 else if (pl == null)
    13                     p = pr;
    14                 else if (pr == null)
    15                     p = pl;
    16                 else if ((kc != null ||
    17                           (kc = comparableClassFor(k)) != null) &&
    18                          (dir = compareComparables(kc, k, pk)) != 0)
    19                     p = (dir < 0) ? pl : pr;
    20                 else if ((q = pr.find(h, k, kc)) != null)
    21                     return q;
    22                 else
    23                     p = pl;
    24             } while (p != null);
    25             return null;
    26         }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

**方法六、扩容方法**

![961ddebeb323a10fe0623af514929fc1.png][]

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

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         // 超过最大值就不再扩充了，就只好随你碰撞去吧
     8         if (oldCap >= MAXIMUM_CAPACITY) {
     9             threshold = Integer.MAX_VALUE;
    10             return oldTab;
    11         }
    12         // 没超过最大值，就扩充为原来的2倍
    13         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
    14                  oldCap >= DEFAULT_INITIAL_CAPACITY)
    15             newThr = oldThr << 1; // double threshold
    16     }
    17     else if (oldThr > 0) // initial capacity was placed in threshold
    18         newCap = oldThr;
    19     else {               // zero initial threshold signifies using defaults
    20         newCap = DEFAULT_INITIAL_CAPACITY;
    21         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    22     }
    23     // 计算新的resize上限
    24     if (newThr == 0) {
    25 
    26         float ft = (float)newCap * loadFactor;
    27         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
    28                   (int)ft : Integer.MAX_VALUE);
    29     }
    30     threshold = newThr;
    31     @SuppressWarnings({"rawtypes","unchecked"})
    32         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    33     table = newTab;
    34     if (oldTab != null) {
    35         // 把每个bucket都移动到新的buckets中
    36         for (int j = 0; j < oldCap; ++j) {
    37             Node<K,V> e;
    38             if ((e = oldTab[j]) != null) {
    39                 oldTab[j] = null;
    40                 if (e.next == null)
    41                     newTab[e.hash & (newCap - 1)] = e;
    42                 else if (e instanceof TreeNode)
    43                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    44                 else { // preserve order
    45                     Node<K,V> loHead = null, loTail = null;
    46                     Node<K,V> hiHead = null, hiTail = null;
    47                     Node<K,V> next;
    48                     do {
    49                         next = e.next;
    50                         // 原索引
    51                         if ((e.hash & oldCap) == 0) {
    52                             if (loTail == null)
    53                                 loHead = e;
    54                             else
    55                                 loTail.next = e;
    56                             loTail = e;
    57                         }
    58                         // 原索引+oldCap
    59                         else {
    60                             if (hiTail == null)
    61                                 hiHead = e;
    62                             else
    63                                 hiTail.next = e;
    64                             hiTail = e;
    65                         }
    66                     } while ((e = next) != null);
    67                     // 原索引放到bucket里
    68                     if (loTail != null) {
    69                         loTail.next = null;
    70                         newTab[j] = loHead;
    71                     }
    72                     // 原索引+oldCap放到bucket里
    73                     if (hiTail != null) {
    74                         hiTail.next = null;
    75                         newTab[j + oldCap] = hiHead;
    76                     }
    77                 }
    78             }
    79         }
    80     }
    81     return newTab;
    82 }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

**方法七、扩容后的元素转移方法**

![961ddebeb323a10fe0623af514929fc1.png][]

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

1  void transfer(Entry[] newTable) {
     2      Entry[] src = table;                   //src引用了旧的Entry数组
     3      int newCapacity = newTable.length;
     4      for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
     5          Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
     6          if (e != null) {
     7              src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
     8              do {
     9                  Entry<K,V> next = e.next;
    10                  int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
    11                  e.next = newTable[i]; //标记[1]
    12                  newTable[i] = e;      //将元素放在数组上
    13                  e = next;             //访问下一个Entry链上的元素
    14              } while (e != null);
    15          }
    16      }
    17 17 }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

**线程安全性**

在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap。那么为什么说HashMap是线程不安全的，下面举例子说明在并发的多线程使用场景中使用HashMap可能造成死循环。代码例子如下(便于理解，仍然使用JDK1.7的环境)：

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

1 public class HashMapInfiniteLoop {  
     2  
     3     private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);  
     4     public static void main(String[] args) {  
     5         map.put(5， "C");  
     6  
     7         new Thread("Thread1") {  
     8             public void run() {  
     9                 map.put(7, "B");  
    10                 System.out.println(map);  
    11             };  
    12         }.start();  
    13         new Thread("Thread2") {  
    14             public void run() {  
    15                 map.put(3, "A);  
    16                 System.out.println(map);  
    17             };  
    18         }.start();        
    19     }  
    20 }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

其中，map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2\*0.75=1，也就是说当put第二个key的时候，map就需要进行resize。

通过设置断点让线程1和线程2同时debug到transfer方法(3.3小节代码块)的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行；然后放开线程2的的断点，让线程2进行resize。结果如下图：

![9fc4ce15283991646b5025c020112279.png][]

注意，Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。

线程一被调度回来执行，先是执行 newTalbe\[i\] = e， 然后是e = next，导致了e指向了key(7)，而下一次循环的next = e.next导致了next指向了key(3)。

![2495b4bfaf5eb0716fe19e9109fced1d.png][]

e.next = newTable\[i\] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。

![25510219f7a5ef59a00607e049dce9ec.png][]

于是，当我们用线程一调用map.get(11)时，悲剧就出现了——Infinite Loop。

**性能表现：JDK1.8 vs JDK1.7**

HashMap中，如果key经过hash算法得出的数组索引位置全部不相同，即Hash算法非常好，那样的话，getKey方法的时间复杂度就是O(1)，如果Hash算法技术的结果碰撞非常多，假如Hash算极其差，所有的Hash算法结果得出的索引位置一样，那样所有的键值对都集中到一个桶中，或者在一个链表中，或者在一个红黑树中，时间复杂度分别为O(n)和O(lgn)。 鉴于JDK1.8做了多方面的优化，总体性能优于JDK1.7，下面我们从两个方面用例子证明这一点。

## Hash较均匀的情况 ##

为了便于测试，我们先写一个类Key，如下：

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

1 class Key implements Comparable<Key> {
     2  
     3     private final int value;
     4  
     5     Key(int value) {
     6         this.value = value;
     7     }
     8  
     9     @Override
    10     public int compareTo(Key o) {
    11         return Integer.compare(this.value, o.value);
    12     }
    13  
    14     @Override
    15     public boolean equals(Object o) {
    16         if (this == o) return true;
    17         if (o == null || getClass() != o.getClass())
    18             return false;
    19         Key key = (Key) o;
    20         return value == key.value;
    21     }
    22  
    23     @Override
    24     public int hashCode() {
    25         return value;
    26     }
    27 }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

这个类复写了equals方法，并且提供了相当好的hashCode函数，任何一个值的hashCode都不会相同，因为直接使用value当做hashcode。为了避免频繁的GC，我将不变的Key实例缓存了起来，而不是一遍一遍的创建它们。代码如下：

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

1 public class Keys {
     2  
     3     public static final int MAX_KEY = 10_000_000;
     4     private static final Key[] KEYS_CACHE = new Key[MAX_KEY];
     5  
     6     static {
     7         for (int i = 0; i < MAX_KEY; ++i) {
     8             KEYS_CACHE[i] = new Key(i);
     9         }
    10     }
    11  
    12     public static Key of(int value) {
    13         return KEYS_CACHE[value];
    14     }
    15 }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

现在开始我们的试验，测试需要做的仅仅是，创建不同size的HashMap（1、10、100、……10000000），屏蔽了扩容的情况，代码如下：

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

1 static void test(int mapSize) {
     2  
     3        HashMap<Key, Integer> map = new HashMap<Key,Integer>(mapSize);
     4        for (int i = 0; i < mapSize; ++i) {
     5            map.put(Keys.of(i), i);
     6        }
     7  
     8        long beginTime = System.nanoTime(); //获取纳秒
     9        for (int i = 0; i < mapSize; i++) {
    10            map.get(Keys.of(i));
    11        }
    12        long endTime = System.nanoTime();
    13        System.out.println(endTime - beginTime);
    14    }
    15  
    16    public static void main(String[] args) {
    17        for(int i=10;i<= 1000 0000;i*= 10){
    18            test(i);
    19        }
    20    }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

在测试中会查找不同的值，然后度量花费的时间，为了计算getKey的平均时间，我们遍历所有的get方法，计算总的时间，除以key的数量，计算一个平均值，主要用来比较，绝对值可能会受很多环境因素的影响。结果如下：

![64ccbaa667d6ba06f25a93f78d29c128.png][]

通过观测测试结果可知，JDK1.8的性能要高于JDK1.7 15%以上，在某些size的区域上，甚至高于100%。由于Hash算法较均匀，JDK1.8引入的红黑树效果不明显，下面我们看看Hash不均匀的的情况。

## Hash极不均匀的情况 ##

假设我们又一个非常差的Key，它们所有的实例都返回相同的hashCode值。这是使用HashMap最坏的情况。代码修改如下：

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

1 class Key implements Comparable<Key> {
    2  
    3     //...
    4  
    5     @Override
    6     public int hashCode() {
    7         return 1;
    8     }
    9 }

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png]

仍然执行main方法，得出的结果如下表所示：

![aa0140375324d1443a9f52bd1023062d.png][]

从表中结果中可知，随着size的变大，JDK1.7的花费时间是增长的趋势，而JDK1.8是明显的降低趋势，并且呈现对数增长稳定。当一个链表太长的时候，HashMap会动态的将它替换成一个红黑树，这话的话会将时间复杂度从O(n)降为O(logn)。hash算法均匀和不均匀所花费的时间明显也不相同，这两种情况的相对比较，可以说明一个好的hash算法的重要性。

**小结**

1.有两个字典，分别存有 100 条数据和 10000 条数据，如果用一个不存在的 key 去查找数据，在哪个字典中速度更快？

完整的答案是:在 Redis 中，得益于自动扩容和默认哈希函数，两者查找速度一样快。在 Java 和 Objective-C 中，如果哈希函数不合理，返回值过于集中，会导致大字典更慢。Java 由于存在链表和红黑树互换机制，搜索时间呈对数级增长，而非线性增长。在理想的哈希函数下，无论字典多大，搜索速度都是一样快。

2. 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。

3. 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。

4. HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。

5. JDK1.8引入红黑树大程度优化了HashMap的性能。

[f0f4b94aecb68c5b695521c6a0f04e10.png]: /images/20221005/b2df3a60f7bd4919ae50222097c0a212.png
[Link 1]: https://www.cnblogs.com/gotodsp/p/6534699.html
[HashMap]: http://blog.csdn.net/wenyiqingnianiii/article/details/52204136
[9416bc6ba9a731d9a02067fd0c94ce42.png]: /images/20221005/896df94c9f304fe98967e01fc65387fd.png
[7b75a2beb9523723db33d12b28f167c6.png]: /images/20221005/4ab752b0a138421d8d83819b8ef6da23.png
[da6a49bc59fe0b24b1fdc9d7a55521e5.png]: /images/20221005/cf62e87d7643420d99fef2c6082e0eb8.png
[3a46694a52cbc67f635b262a4e9ddd90.png]: /images/20221005/6ac4418f17db402b8339349bf07ee73f.png
[2eb012dc241d388f10378474c416e9b2.png]: /images/20221005/75ee769ac18f4b6d945a78954656cede.png
[ce5e207238b2f8050fd1e457982f42b2.png]: /images/20221005/2842aa45a0fd447797b99f7567099942.png
[5c5f4068e14ec7b27e5f7d315e260f19.png]: /images/20221005/301cc868aa2a40b094ea45a8f1e4e740.png
[hashmap]: http://blog.csdn.net/lianhuazy167/article/details/66967698
[48304ba5e6f9fe08f3fa1abda7d326ab.png]: /images/20221005/f23539108ad54bda84e91f1fe8b24a7e.png
[254a73e0fd145a77c87cc735d0eec806.png]: /images/20221005/229fe67f50e8465d8f6f22934bd13d08.png
[961ddebeb323a10fe0623af514929fc1.png]: /images/20221005/40cef983f53b48b1b3f43e2799ca8088.png
[9fc4ce15283991646b5025c020112279.png]: /images/20221005/0dd39d995afa4783bffeaaea05406538.png
[2495b4bfaf5eb0716fe19e9109fced1d.png]: /images/20221005/aac9e898095e4f0b9c6409d522daf146.png
[25510219f7a5ef59a00607e049dce9ec.png]: /images/20221005/5c20db753d3b40469aa3241dae36ed12.png
[64ccbaa667d6ba06f25a93f78d29c128.png]: /images/20221005/68d95cf5746541d4a52a3a0c0b65ed92.png
[aa0140375324d1443a9f52bd1023062d.png]: /images/20221005/f4eda84046ef45adbbd24b1a5fd77333.png