我对哈希表的基本概念感到很困惑。如果我要编写一个哈希,我该如何开始?哈希表和普通数组有什么区别?
如果有人回答这个问题,我认为我所有的问题都会得到解答: 如果我有100个随机生成的数字(作为键),我该如何实现一个哈希表?为什么哈希表比数组更优?
伪代码或Java将作为学习工具受到赞赏...
我对哈希表的基本概念感到很困惑。如果我要编写一个哈希,我该如何开始?哈希表和普通数组有什么区别?
如果有人回答这个问题,我认为我所有的问题都会得到解答: 如果我有100个随机生成的数字(作为键),我该如何实现一个哈希表?为什么哈希表比数组更优?
伪代码或Java将作为学习工具受到赞赏...
到目前为止,答案已经帮助定义了哈希表并解释了一些理论,但我认为一个示例可能会帮助您更好地理解它们。
哈希表和普通数组之间有什么区别?
哈希表和数组都是允许您存储和检索数据的结构。两者都允许您指定一个索引并检索与之关联的值。如Daniel Spiewak所指出的那样,区别在于数组的索引是连续的,而哈希表的索引基于与其关联的数据的值。
我为什么要使用哈希表?
哈希表可以提供一种非常有效的方法来搜索大量数据中的项目,特别是其他情况下难以进行搜索的数据。(在这里,“大”意味着巨大的,也就是说,对于执行顺序搜索需要很长时间的数据)。
如果我要编写哈希,我该如何开始?
没问题。最简单的方法是发明一个可以对数据执行的任意数学操作,返回一个数字N
(通常是整数)。然后使用该数字作为索引进入一个“桶”数组中,并将数据存储在桶#N
中。关键是选择一种操作,使值以一种易于稍后找到它们的方式放置在不同的桶中。
例子:一个大商场保存其顾客的汽车和停车位置的数据库,以帮助购物者记住他们停车的地方。数据库存储make
,color
,license plate
和parking location
。离开商店时,购物者通过输入其汽车的品牌和颜色找到了车辆。数据库返回一个(相对较短的)许可证号码和停车位列表。快速扫描即可定位购物者的汽车。
您可以使用一个SQL查询来实现这个:
SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"
如果数据存储在数组中,它本质上就是一个列表,您可以想像通过扫描所有匹配条目的数组来实现查询。
另一方面,想象一下哈希规则:
添加制造商和颜色中所有字母的ASCII字符代码,除以100,并使用余数作为哈希值。
此规则将每个项目转换为0到99之间的数字,从而将数据排序到100个桶中。 每次客户需要查找汽车时,您可以将制造商和颜色哈希化,以找到包含信息的100个桶之一。 您已经将搜索减少了100倍!
现在将这个例子扩展到大量数据,例如基于十多个条件搜索的数百万条目的数据库。 一个“好”的哈希函数将以最小化任何额外搜索的方式将数据分发到桶中,从而节省大量时间。
首先,你需要了解哈希函数是什么。 哈希函数是一种接受键(例如,任意长度的字符串)并返回尽可能唯一的数字的函数。相同的键必须始终返回相同的哈希值。在Java中,一个非常简单的字符串哈希函数可能如下所示:
public int stringHash(String s) {
int h = s.length();
for(char c : s.toCharArray()) {
h ^= c;
}
return h;
}
你可以在http://www.azillionmonkeys.com/qed/hash.html学习一个好的哈希函数。现在,哈希表使用该哈希值将值放置到一个数组中。以下是简单的Java方法:public void put(String key, Object val) {
int hash = stringHash(s) % array.length;
if(array[hash] == null) {
array[hash] = new LinkedList<Entry<String, Object> >();
}
for(Entry e : array[hash]) {
if(e.key.equals(key)){
e.value = val;
return;
}
}
array[hash].add(new Entry<String, Object>(key, val));
}
(该映射强制唯一键。并非所有映射都是如此。)
两个不同的键可能哈希到相同的值,或者两个不同的哈希映射到相同的数组索引。存在许多处理这种情况的技术。最简单的方法是为每个数组索引使用链表(或二叉树)。如果哈希函数足够好,您将永远不需要进行线性搜索。
现在来查找一个键:
public Object get(String key) {
int hash = stringHash(key) % array.length;
if(array[hash] != null) {
for(Entry e : array[hash]) {
if(e.key.equals(key))
return e.value;
}
}
return null;
}
哈希表是一种关联数组。这与数组的线性数据结构有很大的区别。使用数组,您可能会执行以下操作:
int[] arr = ...
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i] + 1);
}
注意通过指定确切的内存偏移量 (i
) 从数组中获取元素。这与哈希表不同,哈希表允许您存储键 / 值对,并根据键检索值:
Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);
通过上述表格,我们可以进行如下调用:
int n = table.get("Chris");
请放心,n
的值将被设为 18
。
我认为这可能会回答你大部分的问题。哈希表的实现是一个相当有趣的主题,其中维基百科在此方面处理得还算不错。(链接)
"我更关心哈希表如何查找键和生成键的方式."
哈希将一个键对象转换为数字。这被称为“哈希”——它使对象成为哈希。请参见哈希函数。例如,对于字符串,求和字节是一种标准的哈希技术。计算模2 32的余数以保持哈希到可管理的大小。哈希总是给出相同的答案。这是O(1)。
数字为您提供哈希表中的“插槽”。给定任意键对象,哈希值计算出哈希值。然后,哈希值为您提供了表中的插槽。通常是mod(hash,table size)
。这也是O(1)。
这是一般的解决方案。两个数字计算,您就可以从任意对象作为键转换为任意对象作为值。很少有什么东西能像这样快。
从对象到哈希值的转换以以下其中一种常见方式进行。
如果这是一个四字节的“原始”对象,那么该对象的本机值就是一个数字。
对象的地址是4个字节,因此对象的地址可以用作哈希值。
一个简单的哈希函数(例如MD5、SHA1等)会累加对象的字节以创建一个4字节的数字。高级哈希不是字节的简单总和,简单总和不能充分反映所有原始输入位。
哈希表中的插槽是mod(数值,表大小)。
如果插槽有所需的值,您已经完成了任务。如果不是所需值,您需要查找其他位置。有几种流行的探测算法可用于查找表中的空闲位置。线性搜索是查找下一个空闲位置的简单方法。二次探查是一种非线性跳跃,寻找空闲插槽。可以使用固定种子的随机数生成器来生成一系列探测,以平均但任意地传播数据。
探测算法不是O(1)。如果表足够大,碰撞的几率很低,探测就不重要了。如果表太小,就会发生碰撞和探测。此时,需要进行“调整和微调”,以平衡探测和表大小,以优化性能。通常我们只需扩大表格。有一点我还没有看到特别指出的:
使用哈希表而不是数组的重点是性能。
遍历数组通常需要从O(1)到O(x)的时间,其中x是数组中的项目数。但是查找项目的时间将非常变量,特别是如果我们谈论的是数组中数十万个项目。
一个正确加权的哈希表通常具有几乎恒定的访问时间,略高于O(1),无论哈希表中有多少项目。
我相信这个问题已经被清晰地回答了很多次。
我只想添加另一个角度(可能会让新读者感到困惑)
在最低抽象级别上,数组只是一块连续的内存块。给定起始地址(startAddress
)、大小(sizeOfElement
)和单个元素的索引(index
),元素的地址计算如下:
elementAddress = startAddress + sizeOfElement * index
我来回答一下哈希表和数组之间的区别,但由于我以前从未实现过任何重要的哈希算法,所以我会把这个问题留给更有经验的人 :)
数组只是一个对象的有序列表。对象本身并不重要...重要的是,如果您想按插入顺序列出对象,则始终相同(这意味着第一个元素始终具有索引0)。
至于哈希表,它是由键索引的,而不是按顺序排列的...我认为对哈希算法进行基本搜索将为您提供比我更多的见解...维基百科有一个非常不错的算法...它确定了“桶”,使得用作键的任意对象可以快速检索。
至于优点:如果插入顺序很重要,则需要数组或某种有序列表。如果快速查找任意键(由各种哈希函数键入)很重要,则哈希表是有意义的。
[这是对我在me.yahoo.com/a上发表评论的回复]
这取决于您的哈希函数。假设您的哈希函数按照单词的长度哈希一个单词,那么chris的键将为5。同样,yahoo的键也将为5。现在,这两个值(chris和yahoo)都将进入5(即由5键控的“桶”中)。这样,您就不需要创建与您的数据大小相等的数组。