如何实现一个简单的哈希表（例如只使用阵列。）

Question

可能重复：
The fundamentals of Hash tables?

我想可能实现一个简单的哈希表用简单的Java数组。但第一我需要以某种方式有一个关联数组或排序？简单的哈希表实现如何看起来像？它应该还是可以做的添加/删除/获得O(1)

Answer 1

哈希表基本上采用的输入键，用一个函数来哈希它找到存储分区ID，然后使用该存储分区ID存储或检索与该密钥关联的数据。

换句话说，对于你的情况，你只需要在你的数据上提供一个哈希函数，它会给你一个你的数组索引的桶ID。

也许最简单的（也是最幼稚的）会将你的密钥的所有字符排在一起，然后做一个模数运算以使它达到想要的范围。例如，假设你有一个包含结构：

• 名称
• 地址
• 电话
• 各种其他细节

如下您可以生成一个散列：

set hashval to zero 
for each character in Name: 
    hashval = hashval xor character 
hashval = hashval mod 256 

这会给你一个赌注的桶ID包括0和255。

请记住，存储桶可能包含多个项目，因此您不能仅将存储桶ID用作数组索引。每个桶将需要是一个包含可能的多个项目（例如链表或甚至另一个散列表）的结构。

Answer 2

阅读数据结构和算法，或任何教科书只是Wikipedia "Hash Table" entry

Answer 3

与JDK一起封装的实现对自我学习来说非常好（尽管我承认绝不是简单的）。有一个look at it here。