网站设计 原型图,网站的维护和建设,外贸网站,网站建设与维护是什么意思HashMap 是日常开发中#xff0c;用的最多的集合类之一#xff0c;也是面试中经常被问到的 Java 类之一。同时#xff0c;HashMap 在实现方式上面又有十分典型的范例。不管是从哪一方面来看#xff0c;学习 HashMap 都可以说是有利无害的。分析 HashMap 的源码的文章在网上… HashMap 是日常开发中用的最多的集合类之一也是面试中经常被问到的 Java 类之一。同时HashMap 在实现方式上面又有十分典型的范例。不管是从哪一方面来看学习 HashMap 都可以说是有利无害的。分析 HashMap 的源码的文章在网上面已经数不胜数了本文另辟蹊径来分析 HashMap 的设计思想。底层数据结构说到 HashMap 的数据库我们需要从两个 JDK 版本来分析JDK7 和 JDK8。JDK7 版本的 HashMap 的数据结构为数组 链表。而 JDK8 版本的 HashMap 的数据结构为数组 链表 红黑树。可以看到 7 和 8 中 HashMap 的底层数据结构最主要的区别就是 Java8 多了红黑树。为何是数组加链表上文中说到了 不管是 7 或者8 底层数据结构都是 数组 链表但这又是为什么呢数组是一个链式数据结构。put时通过特定的哈希算法将key映射成数组下标这样子就可以将数据保存在对应的槽中这个槽在 HashMap 中被称为 Entry。在 get 时候通过相同的哈希函数将 key 进行哈希运算可以得到对应的下标就可以快速找到该 key 对应的 value。这时候 get 的时间复杂度还是 O(1)。但哈希算法就避免不了有哈希冲突不同的值通过哈希运算之后可能得到同一个值。在散列表的相关概念中介绍了几种解决哈希冲突的方案而HashMap就是使用的链表法。在发生了哈希冲突之后我们在Entry中形成一个单链表。但是这里还存在了一个问题如果链表过长检索起来的效率同样也会很低。于是在 Java8 中通过链表转红黑树来解决这个问题。为何要加上红黑树为什么要链表转红黑树我们需要从数据结构来解析。如果从一个无序单链表中检索数据我们只能从头到尾一个一个检索一旦数据量很大的情况下检索的效率就很低(O(n))。这时我们想到了红黑树从目前的情况来看红黑树能很好地解决这个问题(时间复杂度度为O(logn))。我们先来看看红黑树的定义红黑树是每个节点都带有颜色属性的二叉查找树颜色为红色或黑色。在二叉查找树强制一般要求以外对于任何有效的红黑树我们增加了如下的额外要求节点是红色或黑色。根是黑色。所有叶子都是黑色(叶子是NIL节点)。每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。红黑树要是红黑树首先得是二叉查找树二叉查找树(英语Binary Search Tree)也称为二叉搜索树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree)是指一棵空树或者具有下列性质的二叉树若任意节点的左子树不空则左子树上所有节点的值均小于它的根节点的值若任意节点的右子树不空则右子树上所有节点的值均大于或等于它的根节点的值任意节点的左、右子树也分别为二叉查找树简单总结一下红黑树的左节点要比父节点小右节点要比父节点大。如果要检索一个数字可以将时间复杂度从 O(n) 降低到 O(logn)。当然了添加了红黑树的数据结构之后代码实现要比 只用数组 链表要复杂了好几倍。看代码的时候简直是不能再痛苦了。什么时候转成红黑树有什么转成链表在源码中有这么一个字段static final int TREEIFY_THRESHOLD 8;见字知义这个字段的意思链表转红黑树的阈值也就是 8。同样的还有这么一个字段static final int UNTREEIFY_THRESHOLD 6;它意思是红黑树转链表的阈值。这里还需要再注意一个字段static final int MIN_TREEIFY_CAPACITY 64。这个字段意思是链表转红黑树的最小数组大小也就是说只有在 **链表长度大于8且数组长度大于64的时候链表才会转成红黑树。**但在本节这不是重点也就不多做阐述大家只需要知道这肯定是为了性能就是了。为什么是 8 呢在源码的注释中也有解释英文翻译过来就是下面的意思。链表查询的时间复杂度是 O (n)红黑树的查询复杂度是 O (log n)。在链表数据不多的时候使用链表进行遍历也比较快只有当链表数据比较多的时候才会转化成红黑树但红黑树需要的占用空间是链表的 2 倍考虑到转化时间和空间损耗所以我们需要定义出转化的边界值。在考虑设计 8 这个值的时候我们参考了泊松分布概率函数由泊松分布中得出结论链表各个长度的命中概率为* 0: 0.60653066* 1: 0.30326533* 2: 0.07581633* 3: 0.01263606* 4: 0.00157952* 5: 0.00015795* 6: 0.00001316* 7: 0.00000094* 8: 0.00000006意思是当链表的长度是 8 的时候出现的概率是 0.00000006不到千万分之一所以说正常情况下链表的长度不可能到达 8 而一旦到达 8 时肯定是 hash 算法出了问题所以在这种情况下为了让 HashMap 仍然有较高的查询性能所以让链表转化成红黑树我们正常写代码使用 HashMap 时几乎不会碰到链表转化成红黑树的情况毕竟概念只有千万分之一。为什么两个阈值不一样的大家想想如果一样的在链表达到8 的时候会转成红黑树但红黑树转链表的阈值也是8这时候就会出现循环转换。扩容的条件对比 HashMap 在 7 和 8 中初始化我发现两个版本的初始化做的事情并不一样。在 Java 7 中HashMap 初始化的时候会有个默认容量 (16)。但在 Java8 中HashMap 初始化的时候默认容量为0只有在第一次 put 的时候才会扩容到 16。在 HashMap 源码中有一个字段定义 static final float DEFAULT_LOAD_FACTOR 0.75f;。这个字段的意思是当HashMap 的长度 HashMap 当前容量 * 0.75的时候就会发生扩容。关于为什么负载因子是0.75我们可以在源码注释找到一定的答案。load factor大致意思就是说负载因子是0.75的时候空间利用率比较高而且避免了相当多的Hash冲突使得底层的链表或者是红黑树的高度比较低提升了空间效率。最后我们要知道HashMap的扩容是变成原先容量的 2 倍。Hash函数我们来看看 Java 8 的 hash 函数。 static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这里的大概意思就是先计算出 key 的 hashCode h。然后计算计算 h ^ (h 16)。无符号右移16位。这么做的好处是使大多数场景下算出来的 hash 值比较分散。一般来说hash 值算出来之后要计算当前 key 在数组中的索引下标位置时可以采用取模的方式就是索引下标位置 hash 值 % 数组大小这样做的好处就是可以保证计算出来的索引下标值可以均匀的分布在数组的各个索引位置上但取模操作对于处理器的计算是比较慢的数学上有个公式当 b 是 2 的幂次方时a % b a (b-1)所以此处索引位置的计算公式我们可以更换为(n-1) hash。此问题可以延伸出三个小问题为什么不用 key % 数组大小而是需要用 key 的 hash 值 % 数组大小。如果 key 是数字直接用 key % 数组大小是完全没有问题的但我们的 key 还有可能是字符串是复杂对象这时候用 字符串或复杂对象 % 数组大小是不行的所以需要先计算出 key 的 hash 值。计算 hash 值时为什么需要右移 16 位hash 算法是 h ^ (h 16)为了使计算出的 hash 值更分散所以选择先将 h 无符号右移 16 位然后再于 h 异或时就能达到 h 的高 16 位和低 16 位都能参与计算减少了碰撞的可能性。为什么把取模操作换成了 操作key.hashCode() 算出来的 hash 值还不是数组的索引下标为了随机的计算出索引的下表位置我们还会用 hash 值和数组大小进行取模这样子计算出来的索引下标比较均匀分布。取模操作处理器计算比较慢处理器对 操作就比较擅长换成了 操作是有数学上证明的支撑为了提高了处理器处理的速度。hash 冲突时怎么办hash 冲突指的是 key 值的 hashcode 计算相同但 key 值不同的情况。如果桶中元素原本只有一个或已经是链表了新增元素直接追加到链表尾部如果桶中元素已经是链表并且链表个数大于等于 8 时此时有两种情况如果此时数组大小小于 64数组再次扩容链表不会转化成红黑树;如果数组大小大于 64 时链表就会转化成红黑树。这里不仅仅判断链表个数大于等于 8还判断了数组大小数组容量小于 64 没有立即转化的原因猜测主要是因为红黑树占用的空间比链表大很多转化也比较耗时所以数组容量小的情况下冲突严重我们可以先尝试扩容看看能否通过扩容来解决冲突的问题。
