Hashtable与HashMap中的哈希函数？

Question

我知道Hashtable和HashMap之间的区别.但是,这两个类似乎都在使用哈希函数来完成工作.Hashtable中使用的哈希函数和HashMap中使用的哈希函数之间有区别吗？

特别是,他们使用的散列算法有区别吗？在这两个类中使用哈希的公式是什么？

换句话说,计算索引(哈希值)的方式是不同的？

Answer 1

特别是,他们使用的散列算法有区别吗？在这两个类中使用哈希的公式是什么？

将对象用作哈希表键时使用的主哈希函数是对象的hashCode()方法.实现一个像样的哈希函数是关键类.

的Hashtable和HashMap类带钥匙的哈希码值,并将其转换为索引在主哈希表阵列的链.但是,在Hashtable和之间发生这种情况的方式存在差异HashMap.

• 对于Hashtable(Java 8),代码是这样的:

   hash = key.hashCode();
   index = (hash & 0x7FFFFFFF) % tab.length;
  

• 对于HashMap(Java 8),代码是(有效地):

   // (I have restructured the code for ease of comparison.)
   int h;
   hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   index = (tab.length - 1) & hash;
  

如您所见,HashMap正在加扰密钥的哈希码函数返回的哈希码值.这在源代码中解释如下:

[此方法]计算key.hashCode()并将更高位的散列扩展(XOR)降低.因为该表使用2次幂掩蔽,所以仅在当前掩码之上的位中变化的散列组将始终发生冲突.(在已知的例子中是一组Float键,在小表中保存连续的整数.)因此我们应用一个向下传播高位比特影响的变换.速度,效用和比特扩展质量之间存在权衡.因为许多常见的哈希集合已经合理分布(因此不会受益于传播),并且因为我们使用树来处理容器中的大量冲突,所以我们只是以最便宜的方式对一些移位的位进行异或,以减少系统损失,以及由于表格边界而包含最高位的影响,否则这些位将永远不会用于索引计算.

笔记:

1. 在&与%不同的是,因为在Hashtable散列数组大小是一个素数,但在HashMap(爪哇8)的大小为2的幂.

2. 在Java 8中HashMap,如果密钥类实现,则实现将把长哈希链转换为二叉树Comparable.

3. HashMap处理null密钥,但Hashtable没有.

但是,HashMap如果您的密钥类具有设计糟糕/实现的hashCode()方法......或者如果有人故意设计哈希冲突,那么所有这些额外的复杂性才会发挥作用.

换句话说,如果你的关键类设计得很好,那么差异就不重要了.