什么是哈希表
哈希表（hash table）也叫作散列表，是存储Key-Value映射的集合。对于某一个Key，散列表可以在接近O(1)的时间内进行读写操作。散列表通过哈希函数实现 Key和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突。散列表这种数据结构提供了键（Key）和值（Value） 的映射关系。只要给出一个Key，就可以高效查找到它所匹配的Value，时间复杂度接近于O(1) 。
什么是哈希函数？
本质上哈希表其实也是数组，数组只能根据下标，像a[0]、a[1]、 a[2]、a[3]、a[4]这样来访问，而散列表的Key则是以字符串类型为 主的。需要一个“中转站”，通过某种方式，把Key和数组下标进行转换。这个中转站就叫作哈希函数。
哈希函数的实现
在不同的语言中，哈希函数的实现方式是不一样的。以Java的常用集合HashMap为例。 在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
哈希表中的读写操作
写操作
- 第1步，通过哈希函数，把Key转化成数组下标5。
- 第2步，如果数组下标5对应的位置没有元素，就把这个Entry填充到数 组下标5的位置
读操作
什么是哈希冲突
在散列表写操作时，由于数组的长度是有限的，当插入的Entry越来越多时，不同的 Key通过哈希函数获得的下标有可能是相同的。例如002936这个Key对应的数组下标是2；002947这个Key对应的数组下标也是2。这种情况，就叫作哈希冲突
解决哈希冲突的方法
开放寻址法，
开放寻址法的原理很简单，当一个Key通过哈希函数获得对应的数组下 标已被占用时，我们可以“另谋高就”，寻找下一个空档位置。
链表法。
Java的集合类HashMap当中。 HashMap数组的每一个元素不仅是一个Entry对象，还是一个链表的头节 点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的 Entry映射到与之冲突的数组位置时，需要插入到对应的链表中
链表法比较重要，所以讲讲链表法实现步骤如下
- 第1步，通过哈希函数，把Key转化成数组下标2。
- 第2步，找到数组下标2所对应的元素，如果这个元素的Key是002936， 那么就找到了；如果这个Key不是002936也没关系，由于数组的每个元素都与一个链表对应，可以顺着链表慢慢往下找，看看能否找到与 Key相匹配的节点。
注意：关于HashMap的实现，JDK 8和以前的版本有着很大的 不同。当多个Entry被Hash到同一个数组下标位置时，为了提升插入和查找的效率，HashMap会把Entry的链表转化为红黑树这种数据结构。由于散列表的具体实现代码比较复杂，所以有兴趣自己去看看源码吧嘿嘿。
哈希算法
Hash算法是一个广义的算法，也可以认为是一种思想，使用Hash算法可以提高存储空间的利用率，可以提高数据的查询效率，也可以做数字签名来保障数据传递的安全性。所以Hash算法被广泛地应用在互联网应用中。
