上面 HashSet 和 HashMap 都使用了 散列表来做数据的检索，那么什么是散列表 ，这个又有什么优点呢 ？
散列表也叫作哈希表（hash table），这种数据结构提供了键（Key）和值（Value）的映射关系。只要给出一个Key，就可以高效查找到它所匹配的Value，时间复杂度接近于O(1)。
是不是想到了 Map ？
散列表是如何根据Key来快速找到它所匹配的 Value 呢 ？
在目前所学的数据结构中，数组的查询效率是最高的。散列表本质就是一个数组。不同的是数组的下标是数字，但是散列表的下标是字符串。这就需要设计一个中转站，通过某种方式，把Key和数组下标进行转换。这个中转站就叫作哈希函数。
在不同的语言中，哈希函数的实现是不一样的。我们以Java的HashMap为例，来看看哈希函数的实现。
在Java及大多数面向对象的语言中，每一个对象都有属于自己的hashcode，这个hashcode是区分不同对象的重要标识。无论对象自身的类型是什么，它们的hashcode都是一个整型变量。
既然都是整型变量，想要转化成数组的下标也就不难实现了。最简单的转化方式是什么呢？是按照数组长度进行取模运算
<
index = HashCode (Key) % Array.length
其实JDK中的哈希函数为了提升效率，使用的是位运算。我们就假设使用的是模运算
通过哈希函数，我们可以把字符串或其他类型的Key，转化成数组的下标index。如给出一个长度为8的数组，则当
key=001121时
index = HashCode ("001121") % Array.length = 1420036703 % 8 = 7
而当key=this时，
index = HashCode ("this") % Array.length = 3559070 % 8 = 6
散列表的读写操作
写操作就是在散列表中插入新的键值对（在JDK中叫作Entry）。如调用hashMap.put("002931", "王五")，意思是插入一组Key为002931、Value为王五的键值对。具体该怎么做呢？
通过哈希函数，把Key转化成数组下标5。
-
如果数组下标5对应的位置没有元素，就把这个Entry填充到数组下标5的位置
篇.png
由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可能是相同的。例如002936这个Key对应的数组下标是2；002947这个Key对应的数组下标也是2。
图片.png
这种情况，就叫作哈希冲突
解决哈希冲突的方法主要有两种，一种是开放寻址法，一种是链表法
- 开放寻址法的原理很简单，当一个Key通过哈希函数获得对应的数组下标已被占用时，我们可以“另谋高就”，寻找下一个空档位置
-
HashMap数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可
图片1.png
读操作（get）
读操作就是通过给定的Key，在散列表中查找对应的Value。例如调用 hashMap.get("002936")，意思是查找Key为002936的Entry在散列表中所对应的值
- 通过哈希函数，把Key转化成数组下标2。
- 找到数组下标2所对应的元素，如果这个元素的Key是002936，那么就找到了；如果这个Key不是002936也没关系，由于数组的每个元素都与一个链表对应，我们可以顺着链表慢慢往下找，看看能否找到与Key相匹配的节点。
