3

关于 HashTable（以及此类的后续衍生物），有人知道 .net 和 Java 使用什么散列算法吗？

List 和 Dictionary 都是 Hashtable 的直接降级吗？

4

7 回答 7

6

哈希函数没有内置在哈希表中；哈希表调用键对象上的方法来计算哈希。因此，散列函数根据关键对象的类型而有所不同。

在 Java 中，aList不是哈希表（也就是说，它不扩展Map接口）。可以在List内部使用哈希表（稀疏列表，其中列表索引是哈希表的键）实现 a，但这样的实现不是标准 Java 库的一部分。

于 2009-05-21T18:46:04.393 回答
3

我对.NET 一无所知，但我会尝试为Java 发言。

在 Java 中，哈希码最终是给定对象的 hashCode() 函数返回的代码和 HashMap/ConcurrentHashMap 类中的二级哈希函数的组合（有趣的是，两者使用不同的函数）。请注意，Hashtable 和 Dictionary（HashMap 和 AbstractMap 的前身）是过时的类。列表实际上只是“其他东西”。

例如，String 类通过重复将当前代码乘以 31 并添加下一个字符来构造哈希代码。有关更多信息，请参阅我关于字符串散列函数如何工作的文章。数字一般使用“自己”作为哈希码；其他具有字段组合的类（例如 Rectangle）通常使用字符串技术的组合，即乘以一个小的素数并添加，但添加各种字段值。（选择质数意味着您不太可能在某些值和哈希码宽度之间获得“意外交互”，因为它们不会除以任何东西。）

由于哈希表的大小——即它所拥有的“桶”的数量——是2的幂，所以桶号基本上是通过去掉高位直到哈希码在范围内而从哈希码导出的。二级散列函数通过“散布位”来防止所有或大部分随机性都在那些高位中的散列函数，这样一些随机性最终会出现在低位中并且不会被截断。如果没有这种混合，String 哈希码实际上可以很好地工作，但用户创建的哈希码可能不会很好地工作。请注意，如果两个不同的哈希码解析为相同的桶号，Java 的 HashMap 实现使用“链接”技术——即它们在每个桶中创建一个条目的链接列表。它' s 因此对于散列码具有良好的随机性很重要，这样项目就不会聚集到特定范围的桶中。（然而，即使有一个完美的散列函数，你仍然会根据平均定律预计会发生一些链接。）

哈希码的实现不应该是个谜。您可以查看您选择的任何类的 hashCode() 源代码。

于 2009-05-21T20:06:29.580 回答
2

HASHING 算法是用于确定 HashTable 中项目的哈希码的算法。

HASHTABLE 算法（我认为这是这个人所要求的）是 HashTable 用于根据其哈希码组织其元素的算法。

Java 恰好使用链式哈希表算法。

于 2009-05-21T18:56:00.410 回答
2

在自己寻找相同的答案时，我在 .net 的参考源 @ http://referencesource.microsoft.com中找到了这个。

     /*
      Implementation Notes:
      The generic Dictionary was copied from Hashtable's source - any bug 
      fixes here probably need to be made to the generic Dictionary as well.
      This Hashtable uses double hashing.  There are hashsize buckets in the 
      table, and each bucket can contain 0 or 1 element.  We a bit to mark
      whether there's been a collision when we inserted multiple elements
      (ie, an inserted item was hashed at least a second time and we probed 
      this bucket, but it was already in use).  Using the collision bit, we
      can terminate lookups & removes for elements that aren't in the hash
      table more quickly.  We steal the most significant bit from the hash code
      to store the collision bit.

      Our hash function is of the following form:

      h(key, n) = h1(key) + n*h2(key)

      where n is the number of times we've hit a collided bucket and rehashed
      (on this particular lookup).  Here are our hash functions:

      h1(key) = GetHash(key);  // default implementation calls key.GetHashCode();
      h2(key) = 1 + (((h1(key) >> 5) + 1) % (hashsize - 1));

      The h1 can return any number.  h2 must return a number between 1 and
      hashsize - 1 that is relatively prime to hashsize (not a problem if 
      hashsize is prime).  (Knuth's Art of Computer Programming, Vol. 3, p. 528-9)
      If this is true, then we are guaranteed to visit every bucket in exactly
      hashsize probes, since the least common multiple of hashsize and h2(key)
      will be hashsize * h2(key).  (This is the first number where adding h2 to
      h1 mod hashsize will be 0 and we will search the same bucket twice).

      We previously used a different h2(key, n) that was not constant.  That is a 
      horrifically bad idea, unless you can prove that series will never produce
      any identical numbers that overlap when you mod them by hashsize, for all
      subranges from i to i+hashsize, for all i.  It's not worth investigating,
      since there was no clear benefit from using that hash function, and it was
      broken.

      For efficiency reasons, we've implemented this by storing h1 and h2 in a 
      temporary, and setting a variable called seed equal to h1.  We do a probe,
      and if we collided, we simply add h2 to seed each time through the loop.

      A good test for h2() is to subclass Hashtable, provide your own implementation
      of GetHash() that returns a constant, then add many items to the hash table.
      Make sure Count equals the number of items you inserted.

      Note that when we remove an item from the hash table, we set the key
      equal to buckets, if there was a collision in this bucket.  Otherwise
      we'd either wipe out the collision bit, or we'd still have an item in
      the hash table.

       -- 
    */
于 2015-05-04T17:11:19.917 回答
1

任何声称是 HashTable 或 .NET 中类似的东西都不会实现自己的散列算法：它们总是调用对象被散列的GetHashCode()方法。

尽管关于这个方法做什么或应该做什么，有很多困惑，特别是在涉及覆盖基本 Object 实现的用户定义或其他自定义类时。

于 2009-05-21T18:54:35.140 回答
1

对于 .NET，您可以使用 Reflector 查看各种算法。通用和非通用哈希表有不同的，当然每个类都定义了自己的哈希码公式。

于 2009-05-21T18:55:14.530 回答
1

.NETDictionary<T>类使用IEqualityComparer<T>计算键的哈希码并在键之间进行比较以进行哈希查找。IEqualityComparer<T>如果您在构造实例时不提供 an Dictionary<T>（它是构造函数的可选参数），它将为您创建一个默认值，默认情况下使用object.GetHashCodeandobject.Equals方法。

至于标准GetHashCode实现是如何工作的，我不确定它是否已记录在案。对于特定类型，您可以阅读 Reflector 中方法的源代码或尝试检查 Rotor 源代码以查看它是否存在。

于 2009-05-21T20:40:13.943 回答