哈希表的基础知识是什么？

到目前为止，这些答案有助于定义哈希表并解释一些理论，但我认为一个例子可能会帮助你更好地感受它们。

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

哈希表和数组都是允许您存储和检索数据的结构。两者都允许您指定索引并检索与其关联的值。正如 Daniel Spiewak 所指出的，不同之处在于数组的索引是连续的，而哈希表的索引是基于与它们关联的数据的值。

为什么要使用哈希表？

哈希表可以提供一种非常有效的方法来搜索大量数据中的项目，特别是那些不容易搜索的数据。（这里的“大”意味着巨大，从某种意义上说，执行顺序搜索需要很长时间）。

如果我要编写哈希值，我该如何开始？

没关系。最简单的方法是发明一个任意的数学运算，你可以对数据执行，返回一个数字（通常是整数）。然后使用该数字作为“存储桶”数组的索引，并将数据存储在存储桶 #中。诀窍在于选择一种操作，该操作倾向于将值放在不同的存储桶中，以便您以后轻松找到它们。NN

例：一家大型购物中心保留了顾客的汽车和停车地点的数据库，以帮助购物者记住他们的停车地点。数据库存储 、 、 和 。离开商店时，购物者通过输入其品牌和颜色来找到他的汽车。数据库返回一个（相对较短的）车牌和停车位列表。快速扫描可找到购物者的汽车。makecolorlicense plateparking 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;
}