哈希表

在哈希表中增删查改的时间复杂度都为 。

哈希表的简单实现

仅用一个数组来实现哈希表。数组中的每个空位称为桶（bucket），每个桶可存储一个键值对。因此，查询操作就是找到 key 对应的桶，并在桶中获取 value 。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有 key ，输出空间是所有桶（数组索引）。哈希函数的计算分为两步：