哈希表的基本原理是利用数组索引的时间复杂度为O(1)，即元素地址为 base + sizeof(item) * N。要放进哈希表的物品可以是任何类型，我们只需要对这个物品的特征进行“扫描”，得到一个整数，就可以把它放到这个整数对应的数组“格子”。下次当我们需要查找这个物品时，我们一定是已经掌握了它的特征。要根据特征找到它，只需要用相同的方式“扫描”特征，就能再次得到相同的整数，截下来只需要按照O(1)的时间复杂度去数组的格子中拿取物品即可。“扫描”算法有个特别的名字：哈希函数。以上就是哈希表最简化且不严谨的描述了。

如果你仔细思考，会发现存在一些细节问题。其中，最重要的是，如果哈希函数得出的整数答案是不重复的，而它又可以给世界上所有的物品都完成扫描，数组的容量就必须是无限的。更糟糕的是，任何物品的扫描结果都可以是非常巨大的整数，数组的基本原理决定了它必须实际分配和占据全部的空间才可以开始工作。这意味着你需要一台无穷大内存空间的计算机才能完成任务，这显然是不合理的。

如此一来，哈希函数的结果必须是可重复的。这样就会出现多个物品挤在同一个格子里，而在一个混乱的格子里找东西，其时间复杂度又会落入O(n),只不过这次的n只是这个格子里的物品数量。如果物品总数为n，一共有k个格子，假设所有物品随机但均匀地分配到哈希表中，则时间复杂度会从原本的O(n)降低到O(n / k)。当n和k的在相似的数量级时，我们可以将其称为O(1)。当我们实际使用时，需要在合理范围内尽可能地提供更大的哈希表，以提升性能。

最常见的哈希表实现方式是一个链表数组，即数组的每个元素都是一个链表指针。数组的每个元素，代表前面所说的“格子”，术语上一般叫做slot(插槽)或者bucket(篮子)。多个物品要挤在同一个地方，物品还要随时可以实现CRUD操作，链表几乎就是唯一的选择。

哈希函数的代码实现：最常见的哈希函数，将特征key视为一个整数，然后对它除以数组的尺寸，得到的余数(模运算)就是答案。实际上，哈希函数用任何能将特征固定地转换为数组尺寸范围内整数的算法，这里唯一的强制要求是每次答案都必须是相同的，即幂等性。很显然，掷骰子算法很难作为哈希函数。这里的隐藏要求是，我们希望在物品的分布空间内，哈希函数可以均匀地将物品分配到格子中。不均衡的分配将会导致哈希表的性能降低。极端情况下，如果所有物品都挤在同一个格子里，哈希表就丧失了作用。当物品在空间中分布是均匀的，模运算显然是非常好的哈希函数。当物品在空间中的分布不是均匀的，我们就需要借助对物品的先验知识，让其转换到均匀分布的空间，这个转换函数就是合适的哈希函数。

在链表方面，我们可以根据实际应用场景，选择使用单向链表或是双向链表，还可以根据新旧数据的关系，选择在链表的头部或者尾部插入新元素。一般情况下，这对哈希表的性能影响不大，如非必要默认设置即可。