如何实现一个简单的哈希表(例如,只使用数组)

Question

可能重复:
哈希表的基本原理？

我试图用简单的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

这将为您提供0到255之间的桶ID.

请记住,存储桶可能包含多个项目,因此您不能仅将存储桶ID用作数组索引.每个存储桶都需要是一个可能包含多个项目的结构(例如链表或其他哈希表).