如果哈希表使用单独的链接，为什么重复的键是不可能的？

Question

所以我对这个有点困惑。如果 Hashtables 使用单独的链接（或线性探测），为什么以下不会打印出两个值？

         Hashtable<Character, Integer> map = new Hashtable<>();
         map.put('h', 0);
         map.put('h', 1);
         System.out.println(map.remove('h')); // outputs 1
         System.out.println(map.get('h')); // outputs null

我试图理解为什么在给定 2 个相同的键的情况下，哈希表不会使用单独的链接来存储这两个值。我是不是理解错了，或者 Java 只是没有在他们的哈希表 class 中实现冲突处理？

另一个可能联系在一起的问题是，在给定键的情况下，使用线性探测的哈希表如何知道我们要查找的值是哪个？

提前致谢！

Answer 1

I'm trying to understand why, given 2 identical keys, the hashtable won't use separate chaining in order to store both values.

Map 的规范（即 javadoc）说 每个键只存储一个 值。这就是 HashTable 和 HashMap 实现所做的。

当然，单独的链接不会阻止某人使用属性实现散列 table。 put(key, value) 在散列 table 上具有单独链接的伪代码大致如下：

计算密钥的哈希值。
根据散列值计算散列链数组中的索引。（计算是 index = hash % array.length 或类似的东西。）
在计算索引的哈希链中搜索与键匹配的条目。
如果您在链上找到密钥条目，请更新条目中的值。
如果您没有找到该条目，请创建一个条目并将其添加到链中。

如果您对同一个键重复该操作，您将计算出相同的哈希值，搜索相同的链，并找到相同的条目。然后您更新它，并且该密钥仍然只有一个条目......按照规范的要求。

总之，上述算法满足Map.putAPI要求没有问题

Answer 2

我认为您误解了散列 table 的工作原理。假设我正在寻找 ID 为 227828 的人。假设我有 1000 个这样的人。我可以搜索所有 1000 个并最终找到该 ID 及其所属的人。

但如果将它们的 ID 用作散列中的键 table，那就更容易了。使用 id 作为键，假设哈希函数 returns 0 表示偶数 id，1 表示奇数 id。然后我所要做的就是找到包含偶数 ID 的框。理想情况下，我只需搜索 500 个条目即可找到密钥 - 即 ID，以及 return 与之关联的值。

但是散列函数更复杂，并且有很多这样的盒子或桶。并且可以识别适当的盒子或桶，然后搜索适当的密钥。然后 return 它的关联值。

如果哈希表使用单独的链接，为什么重复的键是不可能的？

If Hashtables use separate chaining, why are duplicate keys not possible?

java

hashtable

data-structures