2.4.1 为什么需要散列表
说起学习英语，小灰上学时可没有那么丰富的学习资源和工具。当时有一款很流行的电子词典，小伙伴们遇到不会的单词，只要输入到小小的电子词典里，就可以查出它的中文含义。
当时的英语老师强烈反对使用这样的工具，因为电子词典查出来的中文资料太有限，而传统的纸质词典可以查到单词的多种含义、词性、例句等。
但是，同学们还是倾向于使用电子词典。因为电子词典实在太方便了，只要输入要查的单词，一瞬间就可以得到结果，而不需要像纸质词典那样烦琐地进行人工查找。
在我们的程序世界里，往往也需要在内存中存放这样一个“词典”，方便我们进行高效的查询和统计。
例如开发一个学生管理系统，需要有通过输入学号快速查出对应学生的姓名的功能。这里不必每次都去查询数据库，而可以在内存中建立一个缓存表，这样做可以提高查询效率。
再如我们需要统计一本英文书里某些单词出现的频率，就需要遍历整本书的内容，把这些单词出现的次数记录在内存中。
因为这些需求，一个重要的数据结构诞生了，这个数据结构叫作散列表 。
散列表也叫作哈希表 （hash table），这种数据结构提供了键（Key） 和值（Value） 的映射关系。只要给出一个Key，就可以高效查找到它所匹配的Value，时间复杂度接近于O(1) 。
那么，散列表是如何根据Key来快速找到它所匹配的Value呢？
这就是我下面要讲的散列表的基本原理。
2.4.2 哈希函数
小灰，在咱们之前学过的几个数据结构中，谁的查询效率最高？
当然是数组喽，数组可以根据下标，进行元素的随机访问。
说得没错，散列表在本质上也是一个数组。
可是数组只能根据下标，像a[0]、a[1]、a[2]、a[3]、a[4]这样来访问，而散列表的Key则是以字符串类型为主的。
例如以学生的学号作为Key，输入002123，查询到李四；或者以单词为Key，输入by，查询到数字46……
所以我们需要一个“中转站”，通过某种方式，把Key和数组下标进行转换。这个中转站就叫作哈希函数 。
这个所谓的哈希函数是怎么实现的呢？
在不同的语言中，哈希函数的实现方式是不一样的。这里以Java的常用集合HashMap为例，来看一看哈希函数在Java中的实现。
在Java及大多数面向对象的语言中，每一个对象都有属于自己的hashcode，这个hashcode是区分不同对象的重要标识。无论对象自身的类型是什么，它们的hashcode都是一个整型变量。
既然都是整型变量，想要转化成数组的下标也就不难实现了。最简单的转化方式是什么呢？是按照数组长度进行取模运算。
index = HashCode (Key) % Array.length
实际上，JDK（Java Development Kit，Java语言的软件开发工具包）中的哈希函数并没有直接采用取模运算，而是利用了位运算的方式来优化性能。不过在这里可以姑且简单理解成取模操作。
通过哈希函数，我们可以把字符串或其他类型的Key，转化成数组的下标index。
如给出一个长度为8的数组，则当
key=001121时，
index = HashCode ("001121") % Array.length = 1420036703 % 8 = 7
而当key=this时，
index = HashCode ("this") % Array.length = 3559070 % 8 = 6
2.4.3 散列表的读写操作
有了哈希函数，就可以在散列表中进行读写操作了。
1. 写操作（put）
写操作就是在散列表中插入新的键值对（在JDK中叫作Entry）。
如调用hashMap.put("002931", "王五")，意思是插入一组Key为002931、Value为王五的键值对。
具体该怎么做呢？
第1步，通过哈希函数，把Key转化成数组下标5。
第2步，如果数组下标5对应的位置没有元素，就把这个Entry填充到数组下标5的位置。
但是，由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可能是相同的。例如002936这个Key对应的数组下标是2；002947这个Key对应的数组下标也是2。
这种情况，就叫作哈希冲突 。
哎呀，哈希函数“撞衫”了，这该怎么办呢？
哈希冲突是无法避免的，既然不能避免，我们就要想办法来解决。解决哈希冲突的方法主要有两种，一种是开放寻址法，一种是链表法。
开放寻址法的原理很简单，当一个Key通过哈希函数获得对应的数组下标已被占用时，我们可以“另谋高就”，寻找下一个空档位置。
以上面的情况为例，Entry6通过哈希函数得到下标2，该下标在数组中已经有了其他元素，那么就向后移动1位，看看数组下标3的位置是否有空。
很不巧，下标3也已经被占用，那么就再向后移动1位，看看数组下标4的位置是否有空。
幸运的是，数组下标4的位置还没有被占用，因此把Entry6存入数组下标4的位置。
这就是开放寻址法的基本思路。当然，在遇到哈希冲突时，寻址方式有很多种，并不一定只是简单地寻找当前元素的后一个元素，这里只是举一个简单的示例而已。
在Java中，ThreadLocal所使用的就是开放寻址法。
接下来，重点讲一下解决哈希冲突的另一种方法——链表法。这种方法被应用在了Java的集合类HashMap当中。
HashMap数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可。
2. 读操作（get）
讲完了写操作，我们再来讲一讲读操作。读操作就是通过给定的Key，在散列表中查找对应的Value。
例如调用 hashMap.get("002936")，意思是查找Key为002936的Entry在散列表中所对应的值。
具体该怎么做呢？下面以链表法为例来讲一下。
第1步，通过哈希函数，把Key转化成数组下标2。
第2步，找到数组下标2所对应的元素，如果这个元素的Key是002936，那么就找到了；如果这个Key不是002936也没关系，由于数组的每个元素都与一个链表对应，我们可以顺着链表慢慢往下找，看看能否找到与Key相匹配的节点。
在上图中，首先查到的节点Entry6的Key是002947，和待查找的Key 002936不符。接着定位到链表下一个节点Entry1，发现Entry1的Key 002936正是我们要寻找的，所以返回Entry1的Value即可。
3. 扩容（resize）
在讲解数组时，曾经介绍过数组的扩容。既然散列表是基于数组实现的，那么散列表也要涉及扩容的问题。
首先，什么时候需要进行扩容呢？
当经过多次元素插入，散列表达到一定饱和度时，Key映射位置发生冲突的概率会逐渐提高。这样一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能都有很大影响。
这时，散列表就需要扩展它的长度，也就是进行扩容 。
对于JDK中的散列表实现类HashMap来说，影响其扩容的因素有两个。
Capacity ，即HashMap的当前长度
LoadFactor ，即HashMap的负载因子，默认值为0.75f
衡量HashMap需要进行扩容的条件如下。
HashMap.Size >= Capacity×LoadFactor
散列表的扩容操作，具体做了什么事情呢？
扩容不是简单地把散列表的长度扩大，而是经历了下面两个步骤。
1．扩容 ，创建一个新的Entry空数组，长度是原数组的2倍。
2．重新Hash ，遍历原Entry数组，把所有的Entry重新Hash到新数组中。为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。
经过扩容，原本拥挤的散列表重新变得稀疏，原有的Entry也重新得到了尽可能均匀的分配。
扩容前的HashMap。
扩容后的HashMap。
以上就是散列表各种基本操作的原理。由于HashMap的实现代码相对比较复杂，这里就不直接列出源码了，有兴趣的读者可以在JDK中直接阅读HashMap类的源码。
需要注意的是，关于HashMap的实现，JDK 8和以前的版本有着很大的不同。当多个Entry被Hash到同一个数组下标位置时，为了提升插入和查找的效率，HashMap会把Entry的链表转化为红黑树这种数据结构。建议读者把两个版本的实现都认真地看一看，这会让你受益匪浅。
基本明白了，散列表还真是个神奇的数据结构！
散列表可以说是数组和链表的结合，它在算法中的应用很普遍，是一种非常重要的数据结构，大家一定要认真掌握哦。
这一次就讲到这里，咱们下一章再见。