Question

简单易懂数据结构之哈希表

Answer 1

Hash表被称作哈希表，也叫做散列表。哈希表是一种比较特殊的数据结构，它遵循函数映射的思想，以Key: Value的方式存储数据。哈希表最大的特点是可以快速定位到要查找的数据，查询的时间复杂度接近O(1).

假如我们有一组数据,某位工程师每年的收入情况

如果我们用普通的链表来存储这些数据，当我们查询2019年的收入情况时，需要从链表的初始节点开始对整张链表进行遍历，直到找到2019，然后取出对应的数据。这种查找的时间复制度是O(n)，即使当我们顺序存储使用二分查找时，时间复杂度也是O(logn)。如果我们可以知道年份，也就是key值，可以直接取出对应的收入数据，时间复杂度就是O(1)，而如果将数据存储在哈希表中，我们就可以实现这种查找。
哈希表的原理并不复杂，简而言之就是根据Key来计算出存储位置，然后将数据放入该空间，查询时同样根据Key计算出存储位置后直接将相应的值取出。

根据Key来计算存储位置的计算规则我们称之为哈希函数，还是用这个例子，我们取一个最简单的哈希函数H(x) = x。

在上面的这个例子中，虽然我们实现了一个简单的哈希表，但是可以很明显的看出，其中有大量的空间被浪费，长度为2020的数组我们只用到了4个空间，下面我们对这个哈希表进行改良。
通过观察需要存储的数据，我们选择一个新的哈希函数H(x) = x - 2000

在这个例子中，可以看到空间的浪费比优化前大幅减小。从中可以看出，根据数据特点选定合适的表大小和哈希函数是哈希表这种数据结构实现的关键。

下面介绍几种通用的哈希函数

哈希表还要解决的一个问题就是冲突，当选择了一个哈希函数之后，有可能不同的数据会计算出相同的key,比如H(x) = x % 5 这种算法，6 和 11 都会计算出1,此时就会产生冲突。如果不解决冲突，哈希表就无法构建出来。解决冲突的办法有以下几种：

哈希表解决了快速查询的需求，但如果设计不当会造成相当但空间浪费，需要根据实际情况进行设计。