浅入浅出 1.7和1.8的 HashMap _生活百科

前言HashMap 是我们最最最常用的东西了，它就是我们在大学中学习数据结构的时候，学到的哈希表这种数据结构。面试中，HashMap 的问题也是常客，现在卷到必须答出来了，是必须会的知识。
我在学习 HashMap 的过程中，也遇到了不少问题，从概念到使用，整个过程都大大小小有些疑惑，然而我这些疑惑是因为我在某个知识环节上出了问题，导致不能理解，当我看了网上各种关于 HashMap 的有关博客以及 HashMap 的源码后，大致是理解了，但是我又不确定我是否是真的理解了，决定把 HashMap 的基本必须会的知识全部梳理下来，势必得搞定它！

从最开始只是会使用它的 API 进行数据的存?。骄龆ㄒ愣ㄒ苫蟆⒏愣牡撞阍恚?

本篇文章，将从 0 浅入，从什么是哈希表讲起，然后再说 Java 是怎样实现哈希表的。整个梳理过程，将通过源码这个第一手的资料进行梳理分析，吸收知识、解决疑问，一步一步进行梳理，如果你是对 HashMap 懵懵懂懂的同学，那么欢迎跟着我的节奏一起来梳理！
阅读完本篇文章，你将收获：

认识哈希表、哈希冲突、冲突解决方法...
明白 Java 中哈希表是怎样实现的...
table 数组的意思、哈希桶的意思、Entry 的意思、Node 的意思...
1.7 的 HashMap 源码分析流程...
明白为什么已经有了 hashCode() 方法了，为什么还需要 hash() 方法
整个 put、get、扩容的过程...
1.8 的 HashMap 与 1.7 的不同的地方...
1.8 的扩容和 1.7 的扩容不一样的地方...

总之，我相信屏幕前的你读完肯定是有收获的，当然，最大的收获目前是我自己哈哈哈。
全文1万2000多字，欢迎慢慢食用！由于本人水平有限，文中肯定还有许多不足之处，欢迎大家指出！
学习 HashMap 之前，我们需要知道什么？我们知道 HashMap 就是 Java 中对哈希表这种数据结构的实现，倘若你不知道什么是哈希表，那么自然学习 HashMap 就会有大大的困难，倘若你知道哈希表，但仅仅是懵懵懂懂，有个简单了解，那自然困难会降低许多。
所以，在学习 HashMap 之前，我们自然需要先知道什么是哈希表，当然还需要知道链表，不过本篇文章仅对哈希表作出说明。下面将开始讲讲哈希表这种抽象的数据结构，之所以说抽象，是因为下面只说哈希表应该具备的功能，但是不会给出具体实现，比如说我们可以简单地使用数组来实现哈希表，是吧，但是 Java 中的哈希表的实现就不是单单一个数组就实现了的。
好了，废话少说，开搞！

文章插图
什么是哈希表？哈希表（Hash Table，也有另一个称呼：散列表）。
哈希表是一种可以通过键（Key）直接访问存储在某个位置上的值（Value）的数据结构。
Hash 被翻译成「哈希」、「散列」。Key 被翻译成「键」、「关键字」
哈希表可以用来干嘛？很简单，和我们以前学习的数据结构一样，可以用来存储数据。
这不是废话嘛？确实是废话。
好吧，那么都可以存储数据，为什么还会出现哈希表？直接用以前的顺序表、链表、栈、队列，这些数据结构来存储不行吗？这个问题问得好，确实，反正都是存储，为什么还要哈希表？
要回答这个问题，就得说说为什么要有数据结构了，之所以需要数据结构，有一个目的就是：更有效地进行数据的存储，不同的数据结构有不同的特性，顺序表可以通过下标快速的查找出数据、链表可以不需要占用一整片连续的存储空间进行存储等等。哈希表也是一样。
哈希表如何存储数据？哈希表存储数据，给定一个 Key，存储一个 Value 。这里就需要用到一个哈希函数（散列函数）。
以数学中的「函数」来理解，就是有一个函数是这样的 $f(x) = y$ ，一个 $x$ 通过函数 $f$ 映射成值 $y$。
那么哈希函数也可以这样理解：$hash(key) = address$
即键通过哈希函数映射成了一个地址，这个地址可以是数组下标、内存地址等。
所以呢，存储就是，通过哈希函数，把 Key 映射到某个地址，然后将 Value 存储到这个地址上。
那么存储后如何获取，如何查找到这个 Value 呢？还是一样，通过哈希函数获得 Key 映射的地址，然后从这个地址取出 Value。理想的情况下，在哈希表中查找数据，查找的时间复杂度是 $O(1)$。