java - 在 Java 中获取哈希表中的键的索引

Question

我正在编写一个 Dictionary 类的实现。我目前正在编写添加方法

(public V add (K key, V value))

算法:

if the table is too full
    rehash
grab the index based on the key
probe with the index and key to resolve collisions
if the table at the index is null, or has been removed
    increment the number of entries
    increment the number of locations used
    set the table at that index to a new tableentry
else
    grab the value currently at that index
    set the value at the index to the new value
return the old value

我不知道如何根据提供的键获取索引。我也不知道如何引用哈希表中的特定索引。

谢谢

Answer 1

假设您出于任何原因从头开始重新实现字典/哈希表(如果您不是，并且使用哈希表 - 那么您引用的算法完全不合适).

实现数组支持的哈希表的经典方法是计算键的哈希值，然后将值放入该键的数组索引中，以数组大小为模(在以任何方式考虑冲突之后)。

因此，“根据键获取索引”将是 index = hash(key) % backing_array_length;。