哈希表

英文: Hash table.

1. 通过哈希函数将任何类型的键值转换为固定长度的整数: 键值能作为数组的索引.
2. 通过模运算将结果限制在特定范围内: 数组可以具有任意大小, 避免内存浪费.
3. 数组元素的类型为链表节点的指针: 当哈希碰撞发生时, 若链表中不存在具有相同键值的节点, 将元素插入链表的头部.

优点

综上所述, 可以看出哈希表具有以下几个优点:

• 比数组更快地插入和删除操作.
• 比链表更快地查找操作.

缺点

当元素数量变大而数组大小不变时, 查询操作的时间复杂度将逐渐接近链表. 因此在元素数量与数组大小达到一定比例时需要拓展数组大小.

• 拓展速度缓慢: 拓展后需要将旧哈希表的数据全部插入新的哈希表.

优化

• 引入装载因子. 当使用率达到一定值时自动扩容. 提高查找效率.

较低的装载因子可以提高查找效率, 但提高空间占用; 较高的装载因子可以减少空间占用, 但降低查找效率. 建议的默认值为 0.75.

• 提高求桶索引的效率. 初始容积必须为 \(2^n\), 并且容积二倍增长. 以确保容积始终为 \(2^n\). 该条件下, 便可以使用按位与运算符 (&) 而不是求模运算符 (%) 求桶索引, 提高了执行效率:

index = std::hash<K>{}(key) & (capacity() - 1);

实现

结合了动态数组和单向链表两种数据结构. GitHub Gist

评论