「Java」HashMap底层实现、加载因子、容量值及死循环

HashMap 简介

10年积累的成都做网站、成都网站设计经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先做网站设计后付款的网站建设流程，更有南谯免费网站建设让你可以放心的选择与我们合作。

HashMap是一个基于哈希表实现的无序的key-value容器，它键和值允许设置为 null，同时它是线程不安全的。

HashMap 底层实现

  •  在jdk 1.7中HashMap是以数组+链表的实现的
  •  在jdk1.8开始引入红黑树，HashMap底层变成了数组+链表+红黑树实现

红黑树简介

红黑树是一种特殊的平衡二叉树，它有如下的特征：

  •  节点是红色或黑色
  •  根节点是黑色的
  •  所有叶子都是黑色。（叶子是NULL节点）
  •  每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）
  •  从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

所以红黑树的时间复杂度为: O(lgn)。

jdk1.8：数组+链表+红黑树

HashMap的底层首先是一个数组，元素存放的数组索引值就是由该元素的哈希值（key-value中key的哈希值）确定的，这就可能产生一种特殊情况——不同的key哈希值相同。

在这样的情况下，于是引入链表，如果key的哈希值相同，在数组的该索引中存放一个链表，这个链表就包含了所有key的哈希值相同的value值，这就解决了哈希冲突的问题。

但是如果发生大量哈希值相同的特殊情况，导致链表很长，就会严重影响HashMap的性能，因为链表的查询效率需要遍历所有节点。于是在jdk1.8引入了红黑树，当链表的长度大于8，且HashMap的容量大于64的时候，就会将链表转化为红黑树。

 
 
 
 
    
  
  
  
  
  1. // jdk1.8 
    2. 
  
  
  
  
  2. // HashMap#putVal 
    3. 
  
  
  
  
  3. // binCount 是该链表的长度计数器，当链表长度大于等于8时，执行树化方法 
    4. 
  
  
  
  
  4. // TREEIFY_THRESHOLD = 8 
    5. 
  
  
  
  
  5. if (binCount >= TREEIFY_THRESHOLD - 1) 
    6. 
  
  
  
  
  6.     treeifyBin(tab, hash); 
    7. 
  
  
  
  
  7. // HashMap#treeifyBin     
    8. 
  
  
  
  
  8. final void treeifyBin(Node[] tab, int hash) { 
    9. 
  
  
  
  
  9.     int n, index; Node e; 
    10. 
  
  
  
  
  10.     // MIN_TREEIFY_CAPACITY=64 
    11. 
  
  
  
  
  11.     // 若 HashMap 的大小小于64，仅扩容，不树化 
    12. 
  
  
  
  
  12.     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 
    13. 
  
  
  
  
  13.         resize(); 
    14. 
  
  
  
  
  14.     else if ((e = tab[index = (n - 1) & hash]) != null) { 
    15. 
  
  
  
  
  15.         TreeNode hd = null, tl = null; 
    16. 
  
  
  
  
  16.         do {
    17. 
  
  
  
  
  17.              TreeNode p = replacementTreeNode(e, null); 
    18. 
  
  
  
  
  18.             if (tl == null) 
    19. 
  
  
  
  
  19.                 hd = p;
    20. 
  
  
  
  
  20.              else { 
    21. 
  
  
  
  
  21.                 p.prev = tl;
    22. 
  
  
  
  
  22.                  tl.next = p; 
    23. 
  
  
  
  
  23.             } 
    24. 
  
  
  
  
  24.             tl = p; 
    25. 
  
  
  
  
  25.         } while ((ee = e.next) != null); 
    26. 
  
  
  
  
  26.         if ((tab[index] = hd) != null) 
    27. 
  
  
  
  
  27.             hd.treeify(tab); 
    28. 
  
  
  
  
  28.     } 
    29. 
  
  
  
  
  29. }
    30.

加载因子为什么是0.75

所谓的加载因子，也叫扩容因子或者负载因子，它是用来进行扩容判断的。

假设加载因子是0.5，HashMap初始化容量是16，当HashMap中有16 * 0.5=8个元素时，HashMap就会进行扩容操作。

而HashMap中加载因子为0.75，是考虑到了性能和容量的平衡。

由加载因子的定义，可以知道它的取值范围是(0, 1]。

  •  如果加载因子过小，那么扩容门槛低，扩容频繁，这虽然能使元素存储得更稀疏，有效避免了哈希冲突发生，同时操作性能较高，但是会占用更多的空间。
  •  如果加载因子过大，那么扩容门槛高，扩容不频繁，虽然占用的空间降低了，但是这会导致元素存储密集，发生哈希冲突的概率大大提高，从而导致存储元素的数据结构更加复杂（用于解决哈希冲突），最终导致操作性能降低。
  •  还有一个因素是为了提升扩容效率。因为HashMap的容量（size属性，构造函数中的initialCapacity变量）有一个要求：它一定是2的幂。所以加载因子选择了0.75就可以保证它与容量的乘积为整数。
 
 
 
 
    
  
  
  
  
  1. // 构造函数 
    2. 
  
  
  
  
  2. public HashMap(int initialCapacity, float loadFactor) { 
    3. 
  
  
  
  
  3.     // …… 
    4. 
  
  
  
  
  4.     this.loadFactor = loadFactor;// 加载因子 
    5. 
  
  
  
  
  5.     this.threshold = tableSizeFor(initialCapacity); 
    6. 
  
  
  
  
  6. } 
    7. 
  
  
  
  
  7. /** 
    8. 
  
  
  
  
  8.  * Returns a power of two size for the given target capacity.返回2的幂 
    9. 
  
  
  
  
  9.  * MAXIMUM_CAPACITY = 1 << 30 
    10. 
  
  
  
  
  10.  */ 
    11. 
  
  
  
  
  11. static final int tableSizeFor(int cap) { 
    12. 
  
  
  
  
  12.     int n = cap - 1; 
    13. 
  
  
  
  
  13.     n |= n >>> 1; 
    14. 
  
  
  
  
  14.     n |= n >>> 2;
    15. 
  
  
  
  
  15.     n |= n >>> 4; 
    16. 
  
  
  
  
  16.     n |= n >>> 8; 
    17. 
  
  
  
  
  17.     n |= n >>> 16; 
    18. 
  
  
  
  
  18.     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 
    19. 
  
  
  
  
  19. }
    20.

HashMap 的容量为什么是2的 n 次幂

HashMap的默认初始容量是16，而每次扩容是扩容为原来的2倍。这里的16和2倍就保证了HashMap的容量是2的n次幂，那么这样设计的原因是什么呢？

原因一：与运算高效

与运算&，基于二进制数值，同时为1结果为1，否则就是0。如1&1=1,1&0=0,0&0=0。使用与运算的原因就是对于计算机来说，与运算十分高效。

原因二：有利于元素充分散列，减少 Hash 碰撞

在给HashMap添加元素的putVal函数中，有这样一段代码：

 
 
 
 
    
  
  
  
  
  1. // n为容量，hash为该元素的hash值 
    2. 
  
  
  
  
  2. if ((p = tab[i = (n - 1) & hash]) == null) 
    3. 
  
  
  
  
  3.     tab[i] = newNode(hash, key, value, null);
    4.

它会在添加元素时，通过i = (n - 1) & hash计算该元素在HashMap中的位置。

当 HashMap 的容量为 2 的 n 次幂时，他的二进制值是100000……（n个0），所以n-1的值就是011111……（n个1），这样的话(n - 1) & hash的值才能够充分散列。

举个例子，假设容量为16，现在有哈希值为1111，1110，1011，1001四种将被添加，它们与n-1(15的二进制=01111)的哈希值分别为1111、1110、1110、1011，都不相同。

而假设容量不为2的n次幂，假设为10，那么它与上述四个哈希值进行与运算的结果分别是：0101、0100、0001、0001。

可以看到后两个值发生了碰撞，从中可以看出，非2的n次幂会加大哈希碰撞的概率。所以 HashMap 的容量设置为2的n次幂有利于元素的充分散列。

参考：HashMap初始容量为什么是2的n次幂及扩容为什么是2倍的形式

HashMap 是如何导致死循环的

HashMap会导致死循环是在jdk1.7中，由于扩容时的操作是使用头插法，在多线程的环境下可能产生循环链表，由此导致了死循环。在jdk1.8中改为使用尾插法，避免了该死循环的情况。

网站名称：「Java」HashMap底层实现、加载因子、容量值及死循环
文章URL：http://www.csdahua.cn/qtweb/news36/90786.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

面包屑导航知识

同城分类信息

微信小程序开发　　 　品牌网站建设公司　　 　成都网站建设　　 　成都服务器托管　　 　成都网站设计　　 　橡塑保温板　　 　微信小程序开发　　 　虚拟主机　　 　微信服务号订阅号开发　　 　网络营销推广　　 　四川胜锦安防　　 　成都机柜租用　　 　成都枢纽中心　　 　广元双南建站　　 　成都网站建设　　 　快照排名　　 　成都免费做网站　　 　自适应网页设计　　 　成都网站维护　　 　营销型网站建设