哈希冲突如何处理？

Question

我最近了解了一些有关散列值的知识，因此也听说了有关散列冲突的问题。
因此，我想知道：一个人该如何处理？

例如，Swift的Dictonary键使用哈希值。我假设它通过哈希查找其值。那么Swift如何Dictionary存储恰好具有相同哈希值的不同键的值呢？

Answer 1

从根本上讲，有两种主要的方式来处理哈希冲突：分别的链接（将具有冲突哈希码的项目存储在单独的数据结构中）和开放式寻址（当冲突的数据存储在使用某种算法选择的另一个可用存储桶中时）。

两种策略都有许多子策略，如Wikipedia所述。毫无疑问，特定实现所使用的确切策略是特定于实现的，因此作者可以随时更改它以获得更有效的效果，而不会破坏用户的假设。

至此，找出Swift如何处理冲突的唯一方法就是反汇编库（也就是说，除非您为Apple工作，并且可以访问源代码）。好奇的人对这样做NSDictionary，并确定它使用线性探测（开放寻址技术的最简单变体）。