哈希表链地址法/线性探测法无法存储重复键的原因及Java Hashtable相关实现疑问

嘿，我来帮你理清这两个核心问题——你其实是混淆了键重复和哈希冲突这两个完全不同的概念啦：

一、为什么相同键的put操作不会用链地址法存储多个值？ #

首先要明确：Java里的Hashtable（以及所有实现Map接口的类，比如HashMap）的核心规则是键的唯一性——每个键在Map中只能对应一个值。当你用同一个键重复put时，新的值会直接覆盖旧的值，这和哈希冲突的处理机制完全无关！

你提到的链地址法（或线性探测法），是用来处理哈希冲突的：也就是当不同的键计算出了相同的哈希值，导致它们要存到哈希表的同一个桶里时，才会用这些方法来解决冲突（链地址法是把同一个桶里的元素连成链表，线性探测是找下一个空的桶）。

回到你的代码：

Hashtable<Character, Integer> map = new Hashtable<>();
map.put('h', 0); // 键'h'对应值0
map.put('h', 1); // 同一个键'h'，直接覆盖旧值，现在对应值1
System.out.println(map.remove('h')); // 移除的是最后存储的1
System.out.println(map.get('h')); // 键已经被移除，所以返回null

这里根本没触发哈希冲突，因为两次用的是同一个键，哈希值完全一样，Map直接执行覆盖逻辑，不会把两个值都存起来。而且Java的Hashtable是实现了冲突处理的（用的是链地址法），只是这种场景下轮不到冲突处理机制工作。

二、线性探测法的哈希表如何根据键找值？ #

线性探测法是开放地址法的一种，查找逻辑大概是这样的：

• 第一步：计算目标键的哈希值，然后通过哈希函数映射到哈希表的初始索引位置index。
• 第二步：检查index位置的元素：
  • 如果该位置为空，说明目标键不存在，返回空或抛出异常。
  • 如果该位置的键和目标键完全相等，直接返回对应的值。
  • 如果该位置的键和目标键不相等（发生了哈希冲突，不同键哈希到了同一位置），就按照线性顺序依次检查下一个位置（比如index+1，如果到了表尾就循环到表头）。
  • 重复这个检查过程，直到找到匹配的键，或者遇到空位置（说明键不存在）。

举个简单的逻辑伪代码：

function get(key):
    hash = calculateHash(key)
    index = hash % tableSize
    while table[index] is not null:
        if table[index].key == key:
            return table[index].value
        index = (index + 1) % tableSize
    return null

总结一下：键重复是Map的语义规则（键唯一，覆盖旧值），哈希冲突是不同键哈希到同一位置的存储问题，二者完全是两回事～

内容的提问来源于stack exchange，提问作者JakeDrone