<section id=”nice” data-tool=”mdnice 编辑器 ” data-website=”https://www.mdnice.com” style=”padding: 0 10px; word-spacing: 0px; word-wrap: break-word; text-align: left; font-family: Optima-Regular, Optima, PingFangSC-light, PingFangTC-light, ‘PingFang SC’, Cambria, Cochin, Georgia, Times, ‘Times New Roman’, serif; line-height: 1.6; letter-spacing: .034em; color: rgb(63, 63, 63); font-size: 16px; word-break: all;”><h2 data-tool=”mdnice 编辑器 ” style=”padding: 0px; font-weight: bold; color: black; font-size: 22px; display: block; text-align: center; background-image: url(https://my-wechat.mdnice.com/koala-2.png); background-position: center center; background-repeat: no-repeat; background-attachment: initial; background-origin: initial; background-clip: initial; background-size: 50px; margin-top: 1em; margin-bottom: 10px;”><span class=”prefix” style=”display: none;”></span><span class=”content” style=”text-align: center; display: inline-block; height: 38px; line-height: 42px; color: #48b378; background-position: left center; background-repeat: no-repeat; background-attachment: initial; background-origin: initial; background-clip: initial; background-size: 63px; margin-top: 38px; font-size: 18px; margin-bottom: 10px;”> 前言 </span><span class=”suffix”></span></h2>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 大家好，本篇文章是《齐姐说数据结构》系列的第三篇，更多数据结构和算法的文章曾经整顿在我的 Github 上了：https://github.com/xiaoqi6666…</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>HashMap 是无论在工作还是面试中都十分常见常考的数据结构。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 比方 Leetcode 第一题 Two Sum 的某种变种的最优解就是须要用到 HashMap 的，高频考题 LRU Cache 是须要用到 LinkedHashMap 的。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>HashMap 用起来很简略，底层实现也不简单，先来看几道常见的面试题吧。置信大家多多少少都能答复上来一点，不分明的中央就仔细阅读本文啦～这篇文章带你深挖到 HashMap 的老祖宗，保障吊打面试官 </p>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<ul style=”margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: disc;”>
<li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”>== 和 equals() 的区别？</section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 为什么重写 equals() 就必须要重写 hashCode()？</section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”>Hashtable, HashSet 和 HashMap 的区别和分割 </section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 解决 hash 抵触有哪些办法？Java 中用的哪一种？为什么？另一种办法你在工作中用过吗？在什么状况下用得多？</section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 徒手实现一个 HashMap 吧 </section></li></ul>
</blockquote>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 本文分以下章节：</p>
<ul data-tool=”mdnice 编辑器 ” style=”margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: disc;”>
<li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”>Set 和 Map 家族简介 </section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”>HashMap 实现原理 </section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 哈希抵触详解 </section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”>HashMap 基本操作 </section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 习题 Two Sum</section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 习题 LRU</section></li></ul>
<h2 data-tool=”mdnice 编辑器 ” style=”padding: 0px; font-weight: bold; color: black; font-size: 22px; display: block; text-align: center; background-image: url(https://my-wechat.mdnice.com/koala-2.png); background-position: center center; background-repeat: no-repeat; background-attachment: initial; background-origin: initial; background-clip: initial; background-size: 50px; margin-top: 1em; margin-bottom: 10px;”><span class=”prefix” style=”display: none;”></span><span class=”content” style=”text-align: center; display: inline-block; height: 38px; line-height: 42px; color: #48b378; background-position: left center; background-repeat: no-repeat; background-attachment: initial; background-origin: initial; background-clip: initial; background-size: 63px; margin-top: 38px; font-size: 18px; margin-bottom: 10px;”>Set 家族 </span><span class=”suffix”></span></h2>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 在讲 Map 之前，咱们先来看看 Set。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 汇合的概念咱们初中数学就学过了，就是外面不能有反复元素，这里也是一样。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>Set 在 Java 中是一个接口，能够看到它是 java.util 包中的一个汇合框架类，具体的实现类有很多：</p>
<figure data-tool=”mdnice 编辑器 ” style=”margin: 0; margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;”><img src=”https://tva1.sinaimg.cn/large/007S8ZIlgy1giqpz9036wj314u0gemzf.jpg” alt style=”display: block; margin: 0 auto; max-width: 100%; border-radius: 4px; margin-bottom: 25px;”></figure>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 其中比拟罕用的有三种：</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>HashSet: 采纳 Hashmap 的 key 来贮存元素，次要特点是无序的，基本操作都是 O(1) 的工夫复杂度，很快。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>LinkedHashSet: 这个是一个 HashSet + LinkedList 的构造，特点就是既领有了 O(1) 的工夫复杂度，又可能保留插入的程序。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>TreeSet: 采纳红黑树结构，特点是能够有序，能够用天然排序或者自定义比拟器来排序；毛病就是查问速度没有 HashSet 快。</p>
<h2 data-tool=”mdnice 编辑器 ” style=”padding: 0px; font-weight: bold; color: black; font-size: 22px; display: block; text-align: center; background-image: url(https://my-wechat.mdnice.com/koala-2.png); background-position: center center; background-repeat: no-repeat; background-attachment: initial; background-origin: initial; background-clip: initial; background-size: 50px; margin-top: 1em; margin-bottom: 10px;”><span class=”prefix” style=”display: none;”></span><span class=”content” style=”text-align: center; display: inline-block; height: 38px; line-height: 42px; color: #48b378; background-position: left center; background-repeat: no-repeat; background-attachment: initial; background-origin: initial; background-clip: initial; background-size: 63px; margin-top: 38px; font-size: 18px; margin-bottom: 10px;”>Map 家族 </span><span class=”suffix”></span></h2>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>Map 是一个键值对 (Key – Value pairs)，其中 key 是不能够反复的，毕竟 set 中的 key 要存在这外面。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 那么与 Set 绝对应的，Map 也有这三个实现类：</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>HashMap: 与 HashSet 对应，也是无序的，O(1)。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>LinkedHashMap: 这是一个「HashMap + 双向链表」的构造，落脚点是 HashMap，所以既领有 HashMap 的所有个性还能有程序。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>TreeMap: 是有序的，实质是用二叉搜寻树来实现的。</p>
<h2 data-tool=”mdnice 编辑器 ” style=”padding: 0px; font-weight: bold; color: black; font-size: 22px; display: block; text-align: center; background-image: url(https://my-wechat.mdnice.com/koala-2.png); background-position: center center; background-repeat: no-repeat; background-attachment: initial; background-origin: initial; background-clip: initial; background-size: 50px; margin-top: 1em; margin-bottom: 10px;”><span class=”prefix” style=”display: none;”></span><span class=”content” style=”text-align: center; display: inline-block; height: 38px; line-height: 42px; color: #48b378; background-position: left center; background-repeat: no-repeat; background-attachment: initial; background-origin: initial; background-clip: initial; background-size: 63px; margin-top: 38px; font-size: 18px; margin-bottom: 10px;”>HashMap 实现原理 </span><span class=”suffix”></span></h2>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 对于 HashMap 中的每个 key，首先通过 hash function 计算出一个 hash 值，这个 hash 值就代表了在 buckets 里的编号，而 buckets 实际上是用数组来实现的，所以把这个数值模上数组的长度失去它在数组的 index，就这样把它放在了数组里。</p>
<figure data-tool=”mdnice 编辑器 ” style=”margin: 0; margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;”><img src=”https://tva1.sinaimg.cn/large/007S8ZIlgy1giqq1ge5qfj30hi0cswet.jpg” alt style=”display: block; margin: 0 auto; max-width: 100%; border-radius: 4px; margin-bottom: 25px;”></figure>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 那么这里有几个问题：</p>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<p style=”padding-bottom: 8px; padding-top: 1em; margin: 0px; line-height: 26px; padding: 0px; font-size: 15px; color: rgb(89,89,89);”> 如果不同的元素算出了雷同的哈希值，那么该怎么寄存呢？</p>
</blockquote>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 答：这就是 哈希碰撞 ，即多个 key 对应了同一个桶。</p>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<p style=”padding-bottom: 8px; padding-top: 1em; margin: 0px; line-height: 26px; padding: 0px; font-size: 15px; color: rgb(89,89,89);”>HashMap 中是如何保障元素的唯一性的呢？即雷同的元素会不会算出不同的哈希值呢？</p>
</blockquote>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 答：通过 hashCode() 和 equals() 办法来保障元素的唯一性。</p>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<p style=”padding-bottom: 8px; padding-top: 1em; margin: 0px; line-height: 26px; padding: 0px; font-size: 15px; color: rgb(89,89,89);”> 如果 pairs 太多，buckets 太少怎么破？</p>
</blockquote>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 答：Rehasing. 也就是碰撞太多的时候，会把数组扩容至两倍（默认）。所以这样尽管 hash 值没有变，然而因为数组的长度变了，所以算进去的 index 就变了，就会被调配到不同的地位上了，就不必挤在一起了，小伙伴们咱们江湖再见～</p>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<p style=”padding-bottom: 8px; padding-top: 1em; margin: 0px; line-height: 26px; padding: 0px; font-size: 15px; color: rgb(89,89,89);”> 那什么时候会 rehashing 呢？也就是怎么掂量桶里是不是足够 拥挤 要扩容了呢？</p>
</blockquote>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 答：load factor. 即用 pair 的数量除以 buckets 的数量，也就是 均匀每个桶里装几对。Java 中默认值是 0.75f，如果超过了这个值就会 rehashing.</p>
<h3 data-tool=”mdnice 编辑器 ” style=”margin-bottom: 15px; padding: 0px; font-weight: bold; color: black; font-size: 20px; margin-top: 1.2em;”><span style=”background-image: url(https://my-wechat.mdnice.com/koala-3.png); background-size: 100% 100%; background-repeat: no-repeat; display: inline-block; width: 16px; height: 15px; line-height: 15px; margin-bottom: -1px;”></span><span class=”prefix” style=”display: none;”></span><span class=”content” style=”font-size: 17px; font-weight: bold; display: inline-block; margin-left: 8px; color: #48b378;”> 对于 hashCode() 和 equals()</span><span class=”suffix” style=”display: none;”></span></h3>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 如果 key 的 hashCode() 值雷同，那么有可能是要产生 hash collision 了，也有可能是真的遇到了另一个本人。那么如何判断呢？持续用 equals() 来比拟。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 也就是说，</p>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<p style=”padding-bottom: 8px; padding-top: 1em; margin: 0px; line-height: 26px; padding: 0px; font-size: 15px; color: rgb(89,89,89);”>hashCode() 决定了 key 放在这个桶里的编号，也就是在数组里的 index；</p>
</blockquote>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<p style=”padding-bottom: 8px; padding-top: 1em; margin: 0px; line-height: 26px; padding: 0px; font-size: 15px; color: rgb(89,89,89);”>equals() 是用来比拟两个 object 是否雷同的。</p>
</blockquote>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 那么该如何答复这道 <span style=”color:black;font-weight:bold;”> 经典面试题 </span>：</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”><span style=”color:blue;font-weight:bold;”> 为什么重写 equals() 办法，肯定要重写 hashCode() 呢？</span></p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 答：首先咱们有一个假如：任何两个 object 的 hashCode 都是不同的。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 那么在这个条件下，有两个 object 是相等的，那如果不重写 hashCode()，算进去的哈希值都不一样，就会去到不同的 buckets 了，就迷失在茫茫人海中了，再也无奈相认，就和 equals() 条件矛盾了，证毕。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 撒花～～????????????</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 接下来咱们再对这两个办法一探到底：</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 其实 hashCode() 和 equals() 办法都是在 Object class 这个老祖宗里定义的，Object 是所有 Java 中的 class 的鼻祖，默认都是有的，甩不掉的。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 那既然是白给的，咱们先来看看大礼包里有什么，谷歌 Object 的 Oracle 文档：</p>
<figure data-tool=”mdnice 编辑器 ” style=”margin: 0; margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;”><img src=”https://tva1.sinaimg.cn/large/007S8ZIlgy1giqq1tg1pfj31s60tc10j.jpg” alt style=”display: block; margin: 0 auto; max-width: 100%; border-radius: 4px; margin-bottom: 25px;”></figure>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 所以这些办法都是能够间接拿来用的呢～</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 回到 hashCode() 和 equals()，那么如果这个新的 class 里没有重写 (override) 这两个办法，就是默认继承 Object class 里的定义了。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 那咱们点进去来看看 equals() 是怎么定义的：</p>
<figure data-tool=”mdnice 编辑器 ” style=”margin: 0; margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;”><img src=”https://tva1.sinaimg.cn/large/007S8ZIlgy1giqq27js14j32i20nkzs4.jpg” alt style=”display: block; margin: 0 auto; max-width: 100%; border-radius: 4px; margin-bottom: 25px;”></figure>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 记笔记：</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>equals() 办法就是比拟这两个 references 是否指向了同一个 object.</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 嗯？？？你在逗我吗？？那岂不是和 == 一样了？？</p>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<p style=”padding-bottom: 8px; padding-top: 1em; margin: 0px; line-height: 26px; padding: 0px; font-size: 15px; color: rgb(89,89,89);”> 补充：
咱们罕用的比拟大小的符号之 ==
如果是 primitive type，那么 == 就是比拟数值的大小；
如果是 reference type，那么就比拟的是这两个 reference 是否指向了同一个 object。</p>
</blockquote>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<p style=”padding-bottom: 8px; padding-top: 1em; margin: 0px; line-height: 26px; padding: 0px; font-size: 15px; color: rgb(89,89,89);”> 再补充：
Java 的数据类型能够分为两种：
Primitive type 有且仅有 8 种：byte, short, int, long, float, double, char, boolean.
其余都是 Reference type.
所以尽管 Java 宣称“Everything is object”，然而还是有非 object 数据类型的存在的。</p>
</blockquote>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 我不信，我要去源码里看看它是怎么实现的。</p>
<figure data-tool=”mdnice 编辑器 ” style=”margin: 0; margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;”><img src=”https://tva1.sinaimg.cn/large/007S8ZIlgy1giqq2j26rqj30fr0orq6c.jpg” alt style=”display: block; margin: 0 auto; max-width: 100%; border-radius: 4px; margin-bottom: 25px;”></figure>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”></p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 哈，还真是的，绕了这么半天，equals() 就是用 == 来实现的！</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 那为什么还弄出来这么个办法呢？</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”><span style=”color:blue;font-weight:bold;”> 答：为了让你 override～</span></p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 比方一般来说咱们比拟字符串就是想比拟这两个字符串的内容的，那么：</p>
<pre class=”custom” data-tool=”mdnice 编辑器 ” style=”margin-top: 10px; margin-bottom: 10px; border-radius: 5px; box-shadow: rgba(0, 0, 0, 0.55) 0px 2px 10px;”><span style=”display: block; background: url(https://my-wechat.mdnice.com/point.png); height: 30px; width: 100%; background-size: 40px; background-repeat: no-repeat; background-color: #fff; margin-bottom: -7px; border-radius: 5px; background-position: 10px 10px;”></span>str1 =“tianxiaoqi”;
str2 = <span class="hljs-keyword" style="color: #aa0d91; line-height: 26px;">new</span> String(“tianxiaoqi”);
str1 == str2; <span class="hljs-comment" style="color: #007400; line-height: 26px;">// return false</span>
str1.equals(str2); <span class="hljs-comment" style="color: #007400; line-height: 26px;">// return true </span>
</pre>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 因为 String 里是重写了 equals() 办法的：</p>
<figure data-tool=”mdnice 编辑器 ” style=”margin: 0; margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;”><img src=”https://tva1.sinaimg.cn/large/007S8ZIlgy1giqq37zor0j30gk0ilabv.jpg” alt style=”display: block; margin: 0 auto; max-width: 100%; border-radius: 4px; margin-bottom: 25px;”></figure>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 老祖宗留给你就是让你本人用的，如果你不必，那人家也提供了默认的办法，也是够意思了。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 好了，咱们再去看 hashCode() 的介绍：</p>
<figure data-tool=”mdnice 编辑器 ” style=”margin: 0; margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;”><img src=”https://tva1.sinaimg.cn/large/007S8ZIlgy1giqq3ostfoj32i40k245r.jpg” alt style=”display: block; margin: 0 auto; max-width: 100%; border-radius: 4px; margin-bottom: 25px;”></figure>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 那至于 hashCode() 返回的到底是什么，和本文关联不太大，有趣味的同学能够看参考 <span class=”footnote-word” style=”font-weight: bold; color: rgb(90, 185, 131);”> 这篇文章 </span>[1]，论断就是：</p>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<p style=”padding-bottom: 8px; padding-top: 1em; margin: 0px; line-height: 26px; padding: 0px; font-size: 15px; color: rgb(89,89,89);”> 返回的并不一定是对象的（虚构）内存地址，具体取决于运行时库和 JVM 的具体实现。</p>
</blockquote>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 但无论是怎么实现的，都须要遵循文档上的约定，也就是对不同的 object 会返回 惟一的哈希值 。</p>
<h3 data-tool=”mdnice 编辑器 ” style=”margin-bottom: 15px; padding: 0px; font-weight: bold; color: black; font-size: 20px; margin-top: 1.2em;”><span style=”background-image: url(https://my-wechat.mdnice.com/koala-3.png); background-size: 100% 100%; background-repeat: no-repeat; display: inline-block; width: 16px; height: 15px; line-height: 15px; margin-bottom: -1px;”></span><span class=”prefix” style=”display: none;”></span><span class=”content” style=”font-size: 17px; font-weight: bold; display: inline-block; margin-left: 8px; color: #48b378;”> 哈希抵触详解 </span><span class=”suffix” style=”display: none;”></span></h3>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 一般来说哈希抵触有两大类 <span class=”footnote-word” style=”font-weight: bold; color: rgb(90, 185, 131);”> 解决形式 </span>[2]</p>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<ol style=”margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: decimal;”>
<li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”>Separate chaining</section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”>Open addressing</section></li></ol>
</blockquote>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>Java 中采纳的是第一种 Separate chaining，即在产生碰撞的那个桶前面再加一条“链”来存储，那么这个“链”应用的具体是什么数据结构，不同的版本稍有不同：</p>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<p style=”padding-bottom: 8px; padding-top: 1em; margin: 0px; line-height: 26px; padding: 0px; font-size: 15px; color: rgb(89,89,89);”> 在 JDK1.6 和 1.7 中，是用 链表 存储的，这样如果碰撞很多的话，就变成了在链表上的查找，worst case 就是 O(n)；</p>
</blockquote>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<p style=”padding-bottom: 8px; padding-top: 1em; margin: 0px; line-height: 26px; padding: 0px; font-size: 15px; color: rgb(89,89,89);”> 在 JDK 1.8 进行了优化，当链表长度较大时（超过 8），会采纳 红黑树 来存储，这样大大提高了查找效率。</p>
</blockquote>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>（话说，这个还真的喜爱考，曾经在屡次面试中被问过了，还有面试官问为什么是超过“8”才用红黑树????）</p>
<figure data-tool=”mdnice 编辑器 ” style=”margin: 0; margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;”><img src=”https://tva1.sinaimg.cn/large/007S8ZIlgy1giqq4abk69j30rs0dwaaz.jpg” alt style=”display: block; margin: 0 auto; max-width: 100%; border-radius: 4px; margin-bottom: 25px;”></figure>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 第二种办法 open addressing 也是十分重要的思维，因为在实在的分布式系统里，有很多中央会用到 hash 的思维但又不适宜用 seprate chaining。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 这种办法是程序查找，如果这个桶里曾经被占了，那就依照“某种形式 ”持续找下一个没有被占的桶，直到找到第一个的。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”><img src=”https://tva1.sinaimg.cn/large/007S8ZIlgy1giqq4rnqohj30l40ict9w.jpg” alt style=”display: block; margin: 0 auto; max-width: 100%; border-radius: 4px; margin-bottom: 25px;”> 空的 </p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 如图所示，John Smith 和 Sandra Dee 产生了哈希抵触，都被计算到 152 号桶，于是 Sandra 就去了下一个空位 – 153 号桶，当然也会对之后的 key 产生影响：Ted Baker 计算结果本应是放在 153 号的，但鉴于曾经被 Sandra 占了，就只能再去下一个空位了，所以到了 154 号。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 这种形式叫做 Linear probing 线性探查，就像上图所示，一个个的顺着找下一个空位。当然还有其余的形式，比方去找平方数，或者 Double hashing.</p>
<h2 data-tool=”mdnice 编辑器 ” style=”padding: 0px; font-weight: bold; color: black; font-size: 22px; display: block; text-align: center; background-image: url(https://my-wechat.mdnice.com/koala-2.png); background-position: center center; background-repeat: no-repeat; background-attachment: initial; background-origin: initial; background-clip: initial; background-size: 50px; margin-top: 1em; margin-bottom: 10px;”><span class=”prefix” style=”display: none;”></span><span class=”content” style=”text-align: center; display: inline-block; height: 38px; line-height: 42px; color: #48b378; background-position: left center; background-repeat: no-repeat; background-attachment: initial; background-origin: initial; background-clip: initial; background-size: 63px; margin-top: 38px; font-size: 18px; margin-bottom: 10px;”>HashMap 基本操作 </span><span class=”suffix”></span></h2>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 每种数据结构的基本操作都无外乎 <span style=”color:orangered;font-weight:bold;”> 增删改查 </span> 这四种，具体到 HashMap 来说，</p>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<ul style=”margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: disc;”>
<li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 增：put(K key, V value)</section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 删：remove(Object key)</section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 改：还是用的 put(K key, V value)</section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 查：get(Object key) / containsKey(Object key)</section></li></ul>
</blockquote>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 仔细的同学可能发现了，为什么有些 key 的类型是 Object，有些是 K 呢？这还不是因为 equals()…</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 这是因为，在 get/remove 的时候，不肯定是用的同一个 object。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 还记得那个 str1 和 str2 都是田小齐的例子吗？那比方我先 put(str1, value)，而后用 get(str2) 的时候，也是想要到 tianxiaoqi 对应的 value 呀！不能因为我换了身衣服就不认得我了呀！所以在 get/remove 的时候并没有很限度 key 的类型，不便另一个本人相认。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 其实这些 API 的操作流程大同小异，咱们以最简单的 put(K key, V value) 来讲：</p>
<ol data-tool=”mdnice 编辑器 ” style=”margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: decimal;”>
<li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 首先要拿到 array 中要放的地位的 index</section></li></ol>
<ul data-tool=”mdnice 编辑器 ” style=”margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: disc;”>
<li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 怎么找 index 呢，这里咱们能够独自用 getIndex() method 来做这件事；</section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 具体怎么做，就是通过 hash function 算进去的值，模上数组的长度；</section></li></ul>
<ol start=”2″ data-tool=”mdnice 编辑器 ” style=”margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: decimal;”>
<li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 那拿到了这个地位的 Node，咱们开始 traverse 这个 LinkedList，这就是在链表上的操作了，</section></li></ol>
<ul data-tool=”mdnice 编辑器 ” style=”margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: disc;”>
<li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 如果找的到，就更新一下 value；</section></li><li><section style=”margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;”> 如果没找到，就把它放在链表上，能够放头上，也能够放尾上，个别我喜爱放头上，因为新退出的元素用到的概率总是大一些，但并不影响工夫复杂度。</section></li></ul>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 代码如下：</p>
<pre class=”custom” data-tool=”mdnice 编辑器 ” style=”margin-top: 10px; margin-bottom: 10px; border-radius: 5px; box-shadow: rgba(0, 0, 0, 0.55) 0px 2px 10px;”><span style=”display: block; background: url(https://my-wechat.mdnice.com/point.png); height: 30px; width: 100%; background-size: 40px; background-repeat: no-repeat; background-color: #fff; margin-bottom: -7px; border-radius: 5px; background-position: 10px 10px;”></span> <span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #aa0d91; line-height: 26px;">public</span> V <span class="hljs-title" style="color: #1c00cf; line-height: 26px;">put</span><span class="hljs-params" style="color: #5c2699; line-height: 26px;">(K key, V value)</span> </span>{</pre>
<span class="hljs-keyword" style="color: #aa0d91; line-height: 26px;">int</span> index = getIndex(key);
Node<K, V> node = array[index];
Node<K, V> head = node;
<span class="hljs-keyword" style="color: #aa0d91; line-height: 26px;">while</span> (node != <span class="hljs-keyword" style="color: #aa0d91; line-height: 26px;">null</span>) {
<span class="hljs-comment" style="color: #007400; line-height: 26px;">// 原来有这个 key，仅更新值 </span>
<span class="hljs-keyword" style="color: #aa0d91; line-height: 26px;">if</span> (checkEquals(key, node)) {
V preValue = node.value;
node.value = value;
<span class="hljs-keyword" style="color: #aa0d91; line-height: 26px;">return</span> preValue;
}
node = node.next;
}
<span class="hljs-comment" style="color: #007400; line-height: 26px;">// 原来没有这个 key，新加这个 node</span>
Node<K, V> newNode = <span class="hljs-keyword" style="color: #aa0d91; line-height: 26px;">new</span> Node(key, value);
newNode.next = head;
array[index] = newNode;
<span class="hljs-keyword" style="color: #aa0d91; line-height: 26px;">return</span> <span class="hljs-keyword" style="color: #aa0d91; line-height: 26px;">null</span>;
}
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 至于更多的细节比方加一些 rehashing 啊，load factor 啊，大家能够参考源码。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 读完源码大家能够做做 Leetcode 706 题练手，so easy~</p>
<h3 data-tool=”mdnice 编辑器 ” style=”margin-bottom: 15px; padding: 0px; font-weight: bold; color: black; font-size: 20px; margin-top: 1.2em;”><span style=”background-image: url(https://my-wechat.mdnice.com/koala-3.png); background-size: 100% 100%; background-repeat: no-repeat; display: inline-block; width: 16px; height: 15px; line-height: 15px; margin-bottom: -1px;”></span><span class=”prefix” style=”display: none;”></span><span class=”content” style=”font-size: 17px; font-weight: bold; display: inline-block; margin-left: 8px; color: #48b378;”> 与 Hashtable 的区别 </span><span class=”suffix” style=”display: none;”></span></h3>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 这是一个年龄裸露贴，HashMap 与 Hashtable 的关系，就像 ArrayList 与 Vector，以及 StringBuilder 与 StringBuffer。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>Hashtable 是晚期 JDK 提供的接口，HashMap 是新版的；
它们之间最显著的区别，就是 Hashtable 是线程平安的，HashMap 并非线程平安。</p>
<blockquote data-tool=”mdnice 编辑器 ” style=”font-size: 0.9em; overflow: auto; overflow-scrolling: touch; background: rgba(0, 0, 0, 0.05); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; padding: 15px 20px; line-height: 27px; background-color: #FBF9FD; border-left: 3px solid #35b378; display: block;”>
<p style=”padding-bottom: 8px; padding-top: 1em; margin: 0px; line-height: 26px; padding: 0px; font-size: 15px; color: rgb(89,89,89);”> 这是因为 Java 5.0 之后容许数据结构不思考线程平安的问题，因为理论工作中咱们发现没有必要在数据结构的层面上上锁，加锁和放锁在零碎中是有开销的，外部锁有时候会成为程序的瓶颈。</p>
</blockquote>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 所以 HashMap, ArrayList, StringBuilder 不再思考线程平安的问题，性能晋升了很多，当然，线程平安问题也就转移给咱们程序员了。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 另外一个区别就是：HashMap 容许 key 中有 null 值，Hashtable 是不容许的。这样的益处就是能够给一个默认值。</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 在算法面试中，无关 HashMap 的算法题也很常见，比方有名的 Top K 问题，还有 LRU Cache 问题，这两道题都是十分高频的考题，之后也会讲到，还请大家持续关注我吧！</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”> 如果你喜爱这篇文章，记得给我点赞留言哦～你们的反对和认可，就是我创作的最大能源，咱们下篇文章见！</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>我是小齐，纽约程序媛，终生学习者，每天晚上 9 点，云自习室里不见不散！</p>
<p data-tool=”mdnice 编辑器 ” style=”font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;”>更多干货文章见我的 Github: https://github.com/xiaoqi6666…</p>
<h3 class=”footnotes-sep” data-tool=”mdnice 编辑器 ” style=”margin-bottom: 15px; padding: 0px; font-weight: bold; color: black; font-size: 20px; margin-top: 1.2em;”><span style=”background-repeat: no-repeat; line-height: 15px; margin-bottom: -1px; background-image: none; background-size: none; display: block; width: auto; height: auto;”> 参考资料 </span></h3>
<section class=”footnotes” data-tool=”mdnice 编辑器 ” style=”padding-top: 8px;”>
<span id=”fn1″ class=”footnote-item” style=”display: flex;”><span class=”footnote-num” style=”display: inline; width: 10%; background: none; font-size: 80%; opacity: 0.6; line-height: 26px; font-family: ptima-Regular, Optima, PingFangSC-light, PingFangTC-light, ‘PingFang SC’, Cambria, Cochin, Georgia, Times, ‘Times New Roman’, serif; color: rgb(90, 185, 131);”>[1] </span><p style=”padding-bottom: 8px; padding-top: 1em; display: inline; font-size: 14px; width: 90%; padding: 0px; margin: 0; line-height: 26px; word-break: break-all; width: calc(100%-50); color: rgb(90, 185, 131); font-weight: bold;”>hashCode()参考文章: https://blog.csdn.net/xusiwei…</p>
</span>
<span id=”fn2″ class=”footnote-item” style=”display: flex;”><span class=”footnote-num” style=”display: inline; width: 10%; background: none; font-size: 80%; opacity: 0.6; line-height: 26px; font-family: ptima-Regular, Optima, PingFangSC-light, PingFangTC-light, ‘PingFang SC’, Cambria, Cochin, Georgia, Times, ‘Times New Roman’, serif; color: rgb(90, 185, 131);”>[2] </span><p style=”padding-bottom: 8px; padding-top: 1em; display: inline; font-size: 14px; width: 90%; padding: 0px; margin: 0; line-height: 26px; word-break: break-all; width: calc(100%-50); color: rgb(90, 185, 131); font-weight: bold;”> 哈希抵触 wiki: https://en.wikipedia.org/wiki…</p>
</span>
</section>
</section>