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

Question

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

         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

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

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

提前谢谢！

Answer 1

我认为你误解了哈希表的工作原理。想象一下，我在找一个id为227828的人。假设我有1000个这样的人。我可以搜索所有1000个，最终找到那个ID和它所属的人。

但是如果他们的id被用作哈希表中的键，那就更容易了。使用id作为键，假设哈希函数对偶数id返回0，对奇数id返回1。然后我所要做的就是找到包含偶数id的框。理想情况下，我只需要搜索500个条目就能找到键——即id，并返回与之相关的值。

但是散列函数更复杂，有很多这样的盒子或桶。可以识别出合适的盒子或桶，然后搜索合适的钥匙。然后返回其关联值。

Answer 2

我试图理解为什么给定两个相同的键，哈希表不会使用单独的链接来存储这两个值。

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

当然，单独的链接不会阻止某人使用该属性实现哈希表。put（key，value）在具有单独链接的哈希表上的伪代码大致如下：

1. 计算密钥的哈希值

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

简而言之，上述算法在满足映射方面没有问题。提出API要求。