前言
大家好，本篇文章是《齐姐说数据结构》系列的第三篇，更多数据结构和算法的文章已经整理在我的 Github 上了：https://github.com/xiaoqi6666/NYCSDE
HashMap 是无论在工作还是面试中都非常常见常考的数据结构。
比如 Leetcode 第一题 Two Sum 的某种变种的最优解就是需要用到 HashMap 的，高频考题 LRU Cache 是需要用到 LinkedHashMap 的。
HashMap 用起来很简单，底层实现也不复杂，先来看几道常见的面试题吧。相信大家多多少少都能回答上来一点，不清楚的地方就仔细阅读本文啦～这篇文章带你深挖到 HashMap 的老祖宗，保证吊打面试官:smirk:
== 和 equals() 的区别？ 为什么重写 equals() 就必须要重写 hashCode()？ Hashtable, HashSet 和 HashMap 的区别和联系 处理 hash 冲突有哪些方法？Java 中用的哪一种？为什么？另一种方法你在工作中用过吗？在什么情况下用得多？ 徒手实现一个 HashMap 吧
本文分以下章节：
Set 和 Map 家族简介 HashMap 实现原理 哈希冲突详解 HashMap 基本操作 习题 Two Sum 习题 LRU
Set 家族
在讲 Map 之前，我们先来看看 Set。
集合的概念我们初中数学就学过了，就是里面不能有重复元素，这里也是一样。
Set 在 Java 中是一个接口，可以看到它是 java.util 包中的一个集合框架类，具体的实现类有很多：
其中比较常用的有三种：
HashSet: 采用 Hashmap 的 key 来储存元素，主要特点是无序的，基本操作都是 O(1) 的时间复杂度，很快。
LinkedHashSet: 这个是一个 HashSet + LinkedList 的结构，特点就是既拥有了 O(1) 的时间复杂度，又能够保留插入的顺序。
TreeSet: 采用红黑树结构，特点是可以有序，可以用自然排序或者自定义比较器来排序；缺点就是查询速度没有 HashSet 快。
Map 家族
Map 是一个键值对 (Key - Value pairs)，其中 key 是不可以重复的，毕竟 set 中的 key 要存在这里面。
那么与 Set 相对应的，Map 也有这三个实现类：
HashMap: 与 HashSet 对应，也是无序的，O(1)。
LinkedHashMap: 这是一个「HashMap + 双向链表」的结构，落脚点是 HashMap，所以既拥有 HashMap 的所有特性还能有顺序。
TreeMap: 是有序的，本质是用二叉搜索树来实现的。
HashMap 实现原理
对于 HashMap 中的每个 key，首先通过 hash function 计算出一个 hash 值，这个hash值就代表了在 buckets 里的编号，而 buckets 实际上是用数组来实现的，所以把这个数值模上数组的长度得到它在数组的 index，就这样把它放在了数组里。
那么这里有几个问题：
如果不同的元素算出了相同的哈希值，那么该怎么存放呢？
答：这就是哈希碰撞，即多个 key 对应了同一个桶。
HashMap 中是如何保证元素的唯一性的呢？即相同的元素会不会算出不同的哈希值呢？
答：通过 hashCode() 和 equals() 方法来保证元素的唯一性。
如果 pairs 太多，buckets 太少怎么破？
答：Rehasing. 也就是碰撞太多的时候，会把数组扩容至两倍（默认）。所以这样虽然 hash 值没有变，但是因为数组的长度变了，所以算出来的 index 就变了，就会被分配到不同的位置上了，就不用挤在一起了，小伙伴们我们江湖再见～
那什么时候会 rehashing 呢？也就是怎么衡量桶里是不是足够拥挤要扩容了呢？
答：load factor. 即用 pair 的数量除以 buckets 的数量，也就是平均每个桶里装几对。Java 中默认值是 0.75f，如果超过了这个值就会 rehashing.
关于 hashCode() 和 equals()
如果 key 的 hashCode() 值相同，那么有可能是要发生 hash collision 了，也有可能是真的遇到了另一个自己。那么如何判断呢？继续用 equals() 来比较。
也就是说，
hashCode() 决定了 key 放在这个桶里的编号，也就是在数组里的 index；
equals() 是用来比较两个 object 是否相同的。
那么该如何回答这道经典面试题：
为什么重写 equals() 方法，一定要重写 hashCode() 呢？
答：首先我们有一个假设：任何两个 object 的 hashCode 都是不同的。
那么在这个条件下，有两个 object 是相等的，那如果不重写 hashCode()，算出来的哈希值都不一样，就会去到不同的 buckets 了，就迷失在茫茫人海中了，再也无法相认，就和 equals() 条件矛盾了，证毕。
撒花～～
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
