哈希冲突如何处理？ [英] How are hash collisions handled?

问题描述

我最近学到了一些关于哈希值的信息，因此也听说过哈希冲突的问题。

因此，我想知道如何处理这些错误？

例如Swift的 Dictonary 使用带键的哈希值。我假设它通过哈希来查找它的值。那么Swift的字典如何存储不同键的值，那就是有相同的哈希？

解决方案

从根本上说，当具有相互冲突的哈希码的项目存储在单独的数据结构中时，有两种主要的处理哈希冲突的方法 - 单独链接，并且打开寻址

这两种策略都有许多子策略，维基百科。特定实现使用的确切策略并不出人意料地是实现特定的，因此作者可以随时更改它，使其更有效，而不会破坏用户的假设。

这一点，了解Swift如何处理冲突的唯一方法是拆卸库（即，除非您使用Apple，并且可以访问源代码）。 好奇的人做了 NSDictionary ，并确定它使用 线性探测 ，开放式寻址技术的最简单的变体。

I've recently learned a little bit about hash values, and therefore also heard of about the problem of hash collisions.
I therefore wondered: How does one deal with those?

E.g. Swift's Dictonary uses hash values with its keys. I assume that it looks up its values via the hash. So how would Swift's Dictionary then store values for different keys, that happen to have the same hash?

解决方案

Fundamentally, there are two major ways of handling hash collisions - separate chaining, when items with colliding hash codes are stored in a separate data structure, and open addressing, when colliding data is stored in another available bucket that was selected using some algorithm.

Both strategies have numerous sub-strategies, described in Wikipedia. The exact strategy used by a particular implementation is, not surprisingly, implementation-specific, so the authors can change it at any time for something more efficient without breaking the assumptions of their users.

A this point, the only way to find out how Swift handles collisions would be disassembling the library (that is, unless you work for Apple, and have access to the source code). Curious people did that to NSDictionary, and determined that it uses linear probing, the simplest variation of the open addressing technique.

这篇关于哈希冲突如何处理？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！