本文主要内容：

hash的意思是散列，如果音译的话就是哈希。
不过，今天讲的是hash的一部分：hash table，即哈希表。
这两个有什么区别？

• 哈希可以认为是一种方法，可以认为是一种思想：将存储的值和存储的位置建立出一种对应的关系。
• 哈希表是哈希的一种具体应用，是一种支持插入、查找、删除等字典操作的数据结构。

在AVL和红黑树中，查找的效率被提升至了$O(lo{g}_{2}N)$，而哈希表更进一步，将平均查找效率提升到$O(1)$。虽然在特定的情况下，哈希表的最坏时间复杂度为$O(N)$，但在实际中哈希表的查找性能是很好的。

哈希表是普通数组的推广。
普通数组一般采用直接寻址，即将key直接作为数组下标。问题是如果key可能的取值范围过大，而存入的元素又过少，就会产生大量的空间浪费。
哈希表则用一个哈希函数，将key和下标建立了对应的关系。但如果不同的key在哈希函数处理后进了同一个下标，这就造成了哈希冲突。

哈希冲突的解决方式有很多，最主要有的两种：开放寻址法、链表法。