除了碰撞检测和在哈希表中抛出LinkedList之外，哈希表还可以实现哪些其他方式?碰撞检测是实现高效哈希表的唯一方法吗?
最终，有限大小的哈希表将会有碰撞，至少任何一般编程的碰撞。如果您的键是类型string，那么哈希表具有无限个可能的键，但是对于哈希表，您只有有限数量的桶。所以基本上肯定会有碰撞。如果你要实现一个忽略碰撞的哈希表，那么你就会得到一个非常奇怪的、不确定的数据结构，它似乎是随机删除元素的。
现在，后端使用的数据结构不必是链表。你可以把它实现成红黑树从碰撞中得到log(n)的性能。你应该看看关于哈希表的5个误区，以及关于HashMaps vs Maps的Stack Overflow问题。
现在，如果你知道你的键类型，假设键是一个2字符长的字符串，那么只有有限数量的可能的键，然后你可以继续创建一个"哈希"函数，将键转换为相对小整数，你可以创建一个查找表，保证没有冲突。
重要的是要注意，一个实现良好的哈希表不会受到碰撞的影响。世界上有比计算机每5天遍历链表中的三个节点更大的问题，比如世界饥饿(甚至如何实现一个有效的哈希函数)。
除了碰撞检测和在哈希表中抛出LinkedList之外，哈希表还可以实现哪些其他方式?
其他方式包括:
-
从元素碰撞的节点链接另一个容器类型，例如平衡二叉树或向量/数组
-
GCC的哈希表支撑
std::unordered_X使用一个单链值列表和一个连续的桶容器迭代器数组;它有一些很好的特性，包括最优的迭代速度，无论当前的load_factor() -
使用开放寻址/封闭哈希，当插入/查找/擦除在它已经哈希到的桶中找到另一个键时，使用某种算法找到另一个桶来查找(以此类推，直到找到键，可以插入的已删除元素或未使用的桶);这种"探测"有许多选择，最简单的是尝试下一个桶的方法，另一种是二次1、4、9、16……
-
完美散列函数(下)
碰撞检测是实现高效哈希表的唯一方法吗?
- 有时有可能找到一个完美的哈希函数不会有冲突，但这通常只适用于非常有限的输入集，无论是由于输入的性质(例如，活着的人的出生月份和年份只有一千个可能的值)，还是因为在编译时已知的数量很少(例如，编译器的一组200个关键字)。