数据结构和算法（5）

一、哈希表

哈希表（hash table）也叫作散列表，这种数据结构提供了键（Key）和值（Value）的映射关系。只要给出一个Key，就可以高校查找到它所匹配的Value，时间复杂度接近于O（1）。

二、哈希函数

哈希表在本质上是一个数组，可以通过某种方式，把Key和数组下标进行转换。这个方式就叫作哈希函数。

在Python中，哈希表对应的集合叫作字典（dict）。下面以Python为例，来看看哈希函数是如何实现的。

在Python及大多数面向对象的语言中，每一个对象都有属于自己的hash值，这个hash值是区分不同对象的重要标识。无论对象自身的类型是什么，它们的hash值都是一个整型变量。

既然都是整型变量，想要转化成数组的下标也就不难实现了。最简单的转化方式是什么呢？是按照数组长度进行取模运算。

index = hash(key) % size

实际上，Python中的哈希函数并没有直接采用取模运算，而是利用了位运算的方式来优化性能。不过在这里我们可以姑且把它简单理解成取模操作。

通过哈希函数，可以把字符串或其他类型的Key，转化成数组的下标index。

如给出一个长度为8的数组，则当key=001121时，

index = hash (“001121”) % size =1420036703 % 8 = 7

而当key=“this”时，

index = hash (“this”) % size = 3559070 % 8 = 6

三、哈希表的读写操作

1.写操作（put）

写操作就是在哈希表中插入新的键值对（也被称为Entry）。

如调用 dict[“002931”]=“王五”，意思是插入一组Key为002931、Value为王五的键值对。

具体该怎么做呢？

第1步，通过哈希函数，把Key转化成数组下标5。

第2步，如果数组下标5对应的位置没有元素，就把这个Entry填充到数组下标5的位置。

但是，由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可能是相同的。例如，002936这个Key对应的数组下标是2；002947这个Key对应的数组下标也是2。

这种情况，就叫作哈希冲突。

解决哈希冲突的方法主要有两种：一种是开放寻址法，一种是链表法。

开放寻址法就是当一个Key通过哈希函数获得对应的数组下标已被占用时，我们可以不断寻找下一个位置，直到是空当位置。

链表法就是哈希表数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个 Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入对应的链表中即可。

 2.读操作（get）

读操作就是通过给定的Key，在哈希表中查找对应的Value。

例如调用 dict[“002936”]，意思是查找Key为002936的Entry在哈希表中所对应的值。

具体该怎么做呢？下面以链表法为例来讲一下。

第1步，通过哈希函数，把Key转化成数组下标2。

第2步，找到数组下标2所对应的元素，如果这个元素的Key是002936，那么就找到了；如果这个Key不是002936也没关系，由于数组的 每个元素都与一个链表对应，我们可以顺着链表慢慢往下找，看看能否找到与Key相匹配的节点。

在上图中，首先查到的节点Entry6的Key是002947，和待查找的Key002936不符。接着定位到链表的下一个节点Entry1，发现Entry1的Key002936正是我们要寻找的，所以返回Entry1的Value即可。

四、总结

?　数组

数组是由有限个相同类型的变量所组成的有序集合，它的物理存储方式是顺序存储，访问方式是随机访问。利用下标查找数组元素的 时间复杂度是O（1），中间插入、删除数组元素的时间复杂度是O（n）。

?　链表

链表是一种链式数据结构，由若干节点组成，每个节点包含指向下一节点的指针。链表的物理存储方式是随机存储，访问方式是顺序 访问。查找链表节点的时间复杂度是O（n），中间插入、删除节点的时间复杂度是O（1）。

?　栈

栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。栈包含入栈和出栈操作，遵循先入后出的原则（FILO）。

?　队列

队列也是一种线性逻辑结构，可以用数组实现，也可以用链表实现。队列包含入队和出队操作，遵循先入先出的原则（FIFO）。

?　哈希表

哈希表也叫散列表，是存储Key-Value映射的集合。对于某一个Key，哈希表可以在接近O（1）的时间内进行读写操作。哈希表通过哈 希函数实现Key和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突。