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

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

我试图理解为什么，给定2个相同的键，哈希表不会使用单独的链接来存储两个值。我是否理解得有些不正确，或者Java只是没有在他们的哈希表类中实现冲突处理?

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

提前感谢!

Answer 1

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

Map的规范(即javadoc)说只有一个值为每个键存储。这就是HashTable和HashMap的实现。

当然，单独的链接并不能阻止某人实现具有该属性的哈希表。put(key, value)在单独链的哈希表中的伪代码大致如下:

1. 计算key的哈希值
2. 根据哈希值在哈希链数组中计算索引。(计算是index = hash % array.length或类似的东西)
3. 在计算索引处搜索哈希链，查找与键匹配的条目。
4. 如果你在链上找到了键的条目，更新条目中的值。
5. 如果没有找到条目，创建一个条目并将其添加到链中。

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

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

Answer 2

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

但如果它们的id在哈希表中用作键，则更容易。使用id作为键，假设哈希函数为偶数id返回0，为奇数id返回1。然后我要做的就是找到包含偶数id的盒子。理想情况下，我只需要搜索500个条目来找到键-即id，并返回与之相关的值。

但是哈希函数更复杂，有很多这样的盒子或桶。并且可以识别相应的框或桶，然后搜索合适的键。然后返回它的关联值。