哈希表的基本原理？

Question

我对Hash表的基本概念很困惑.如果我要编写哈希代码,我怎么会开始？Hash表和普通数组之间有什么区别？

基本上如果有人回答了这个问题,我认为我的所有问题都会得到解答:如果我有100个随机生成的数字(作为键),我将如何实现哈希表？为什么这对数组有利？

Psuedo-code或Java将被视为一种学习工具......

Answer 1

到目前为止,答案有助于定义哈希表并解释一些理论,但我认为一个例子可以帮助您更好地感受它们.

哈希表和普通数组之间有什么区别？

哈希表和数组都是允许您存储和检索数据的结构.两者都允许您指定索引并检索与其关联的值.正如Daniel Spiewak指出的那样,差异在于数组的索引是顺序的,而散列表的索引是基于与它们相关联的数据的值.

为什么我要使用哈希表？

哈希表可以提供一种非常有效的方法来搜索大量数据中的项目,特别是那些无法轻易搜索的数据.("大"在这里意味着巨大的,因为执行顺序搜索需要很长时间).

如果我要编写哈希代码,我怎么会开始？

没问题.最简单的方法是发明一个可以对数据执行的任意数学运算,它返回一个数字N(通常是一个整数).然后使用该数字作为"桶"数组的索引,并将数据存储在桶#中N.诀窍在于选择一种操作,该操作倾向于将值放在不同的存储桶中,以便您以后轻松找到它们.

示例: 大型购物中心保存其顾客的汽车和停车位置的数据库,以帮助购物者记住他们停放的位置.数据库存储make,color,license plate,和parking location.在离开商店时,购物者通过输入其品牌和颜色来找到他的汽车.数据库返回(相对较短的)车牌和停车位列表.快速扫描定位购物者的汽车.

您可以使用SQL查询实现此功能:

SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"

如果数据存储在一个基本上只是一个列表的数组中,您可以想象通过扫描数组中的所有匹配条目来实现查询.

另一方面,想象一个哈希规则:

添加make和color中所有字母的ASCII字符代码除以100,并使用余数作为哈希值.

此规则将每个项目转换为0到99之间的数字,基本上将数据排序为100个桶.每次客户需要定位汽车时,您都可以对品牌和颜色进行散列,以找到包含信息的100个中的一个桶.您立即将搜索量减少了100倍!

现在将示例扩展为大量数据,例如,根据数十个条件搜索具有数百万条目的数据库."良好"的散列函数将以最小化任何其他搜索的方式将数据分发到存储桶中,从而节省大量时间.

Answer 2

首先,您必须了解哈希函数是什么.哈希函数是一个获取密钥(例如,一串arbritrary长度)并返回尽可能唯一的数字的函数.相同的密钥必须始终返回相同的哈希.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;
}

Answer 3

哈希表是关联的.这与数组有很大的不同,数组只是线性数据结构.使用数组,您可能会执行以下操作:

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.

我想这可能会回答你的大部分问题.哈希表的实现是一个相当有趣的主题,维基百科很好地解决了这个问题.

Answer 4

"我对Hash Tables查找密钥以及如何生成密钥的方式更感兴趣."

1. 散列将关键对象转换为数字.这称为"哈希" - 它从对象中产生哈希.请参阅哈希函数.例如,对字符串的字节求和是标准散列技术.您计算总和模2 ³²以将散列保持为可管理的大小.哈希总是给出相同的答案.这是O(1).

2. 该数字为您提供了HashTable中的"插槽".给定任意密钥对象,哈希值计算哈希值.哈希值然后为您提供表中的插槽.通常mod( hash, table size ).这也是O(1).

这是一般解决方案.两个数值计算,你已经从任意对象作为任意对象的键作为值.很少有东西可以快.

从对象到哈希值的转换以这些常见方式之一发生.

1. 如果它是4字节的"原始"对象,则对象的本机值是一个数字.

2. 对象的地址是4个字节,然后对象的地址可以用作哈希值.

3. 一个简单的散列函数(MD5,SHA1,无论如何)累积对象的字节以创建一个4字节的数字.高级哈希值不是简单的字节总和,简单的和不足以反映所有原始输入位.

哈希表中的槽是mod(数量,表的大小).

如果该插槽具有所需的值,那么您就完成了.如果这不是所需的值,则需要查看其他位置.有几种流行的探测算法可以在表中查找空闲点.线性是对下一个免费点的简单搜索.Quadratic是一种寻找空闲时隙的非线性跳跃.随机数发生器(具有固定种子)可用于生成一系列探针,这些探针将均匀但任意地传播数据.

探测算法不是O(1).如果表格足够大,碰撞的几率很低,探测无关紧要.如果表太小,则会发生冲突并发生探测.此时,它将成为"调整和调整"以平衡探测和表大小以优化性能的问题.通常我们只是让桌子更大.

请参阅哈希表.

Answer 5

我没有特别注意到的东西:

在数组上使用哈希表的关键是性能.

迭代数组通常需要从O(1)到O(x)的任何位置,其中x是数组中的项数.然而,为了找到你的项目的时间将是非常变量,expecially如果我们谈论的是几十万的数组中的项目.

无论哈希表中有多少项,正确加权的哈希表通常具有刚好超过O(1)的几乎恒定的访问时间.