55

我对哈希表的基本概念感到很困惑。如果我要编写一个哈希，我什至会如何开始？哈希表和普通数组有什么区别？

基本上，如果有人回答了这个问题，我想我的所有问题都会得到回答：如果我有 100 个随机生成的数字（作为键），我将如何实现哈希表，为什么这比数组更有利？

伪代码或 Java 将被视为一种学习工具......

4

11 回答 11

70

到目前为止的答案有助于定义哈希表并解释一些理论，但我认为一个示例可以帮助您更好地了解它们。

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

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

为什么要使用哈希表？

哈希表可以提供一种非常有效的方式来搜索大量数据中的项目，尤其是在其他情况下不易搜索的数据。（这里的“Large”是指巨大的，意思是执行顺序搜索需要很长时间）。

如果我要编写一个哈希，我什至会如何开始？

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

示例： 一家大型购物中心保留了顾客汽车和停车位置的数据库，以帮助购物者记住他们的停车地点。数据库存储make、color、license plate和parking location。在离开商店时，购物者通过输入其品牌和颜色来找到他的汽车。该数据库返回一个（相对较短的）车牌和停车位列表。快速扫描定位购物者的汽车。

您可以使用 SQL 查询来实现这一点：

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

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

另一方面，想象一个哈希规则：

将make和color中所有字母的ASCII码相加，除以100，余数作为hash值。

此规则会将每个项目转换为 0 到 99 之间的数字，本质上将数据分类到 100 个桶中。每次客户需要定位汽车时，您都可以对品牌和颜色进行哈希运算，从 100个存储桶中找出包含该信息的存储桶。您立即将搜索量减少了 100 倍！

现在将示例扩展到大量数据，例如一个包含数百万个条目的数据库，根据数十个标准进行搜索。一个“好的”散列函数将以最小化任何额外搜索的方式将数据分配到存储桶中，从而节省大量时间。

于 2008-11-12T02:57:43.403 回答
46

首先，您必须了解哈希函数是什么。哈希函数是一个函数，它接受一个键（例如，任意长度的字符串）并返回一个尽可能唯一的数字。相同的键必须始终返回相同的散列。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;
}
于 2008-11-12T02:36:23.243 回答
17

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

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.

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

于 2008-11-12T01:30:02.270 回答
8

“我对哈希表查找密钥的方式以及密钥的生成方式更感兴趣。”

  1. 散列将关键对象转换为数字。这称为“散列”——它对对象进行散列。请参阅散列函数。例如，对字符串的字节求和是一种标准的散列技术。您计算总和模 2 32以将散列保持在可管理的大小。哈希总是给出相同的答案。这是O (1)。

  2. 该数字在哈希表中为您提供了一个“插槽”。给定一个任意键对象，哈希值计算一个哈希值。然后哈希值会为您提供表中的插槽。通常mod( hash, table size ). 这也是O (1)。

这是一般的解决方案。两个数值计算，你已经从任意对象作为键到任意对象作为值。很少有事情可以这么快。

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

  1. 如果它是 4 字节的“原始”对象，则该对象的本机值是一个数字。

  2. 对象的地址是4个字节，那么对象的地址可以作为哈希值。

  3. 一个简单的散列函数（MD5、SHA1 等等）累积对象的字节以创建一个 4 字节的数字。高级哈希不是简单的字节总和，简单的总和并不能充分反映所有原始输入位。

哈希表中的槽是 mod( number, size of table )。

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

探测算法不是O (1)。如果桌子足够大，那么碰撞的几率就会很低，探测也无关紧要。如果表太小，则会发生冲突并进行探测。到那时，就需要“调整和调整”来平衡探测和表大小以优化性能。通常我们只是把桌子变大。

请参阅哈希表。

于 2008-11-12T02:35:43.603 回答
6

我还没有看到特别指出的东西：

在数组上使用哈希表的重点是性能。

遍历数组通常需要从 O(1) 到 O(x) 的任何时间，其中 x 是数组中的项目数。但是，找到您的项目的时间会非常多变，特别是如果我们谈论的是数组中的数十万个项目。

一个适当加权的哈希表通常具有几乎恒定的访问时间，略高于 O(1)，无论哈希表中有多少项。

于 2008-11-12T02:47:03.707 回答
4

您不希望对 100 个随机生成的数字使用哈希表。

考虑哈希表的一个好方法是考虑值对。让我们以学生为例，假设每个人都有一个学生证号码。在您的程序中，您存储有关学生的信息（姓名、电话号码、账单等）。您希望仅使用基本信息（例如姓名或学生 ID）来查找有关学生的所有信息。

假设您有 10,000 名学生。如果您将它们全部存储在一个数组中，那么您必须遍历整个数组，将每个条目的学生 ID 与您要查找的学生 ID 进行比较。

相反，如果您将他们的学生 ID 号“散列”（见下文）到数组中的某个位置，那么您只需搜索学生的编号具有相同的散列即可。找到你想要的东西的工作要少得多。

在此示例中，假设学生 ID 只是 6 位数字。我们的哈希函数只能使用数字的后 3 位作为“哈希键”。因此 232145 被散列到数组位置 145。所以你只需要一个包含 999 个元素的数组（每个元素都是一个学生列表）。

这对你来说应该是一个好的开始。当然，您应该阅读教科书或维基百科以获取此类信息。但我假设你已经这样做了，并且厌倦了阅读。

于 2008-11-12T01:30:23.690 回答
3

简而言之，这是哈希表的工作原理。

想象一下，你有一个图书馆，里面装满了书。如果您要将书籍存储在一个阵列中，您会将每本书放在书架上的一个位置，然后当有人要求您找一本书时，您会浏览所有书架 - 非常慢。如果有人说“book #12345”，你可以很容易地找到它。

假设您说，如果书名以“A”开头，则位于第 1 行。如果第二个字母为“B”，则位于第 1 行，第 2 架。如果第三个字母为“C”，则进入第 1 行、第 2 架子、第 3 架子……以此类推，直到您确定书的位置。然后，根据书名，您可以确切地知道它应该在哪里。

现在，我描述的简单的“散列”算法存在一些问题——一些书架会超载，而另一些书架会空着，一些书会被分配到同一个插槽..所以真正的散列函数是经过精心构造的尽量避免此类问题。

但这是基本思想。

于 2008-11-12T02:38:27.297 回答
0

我将回答关于哈希表和数组之间区别的那部分......但由于我以前从未实现过任何导入的哈希算法，我将把它留给更有知识的人:)

数组只是对象的有序列表。对象本身并不重要......重要的是，如果您想按插入顺序列出对象，它始终是相同的（意味着第一个元素的索引始终为 0）。

至于哈希表，它是按键索引的，而不是顺序...我认为对哈希算法的基本搜索会给您比我更多的洞察力...维基百科有一个非常不错的...确定“桶" 用于快速检索用作键的任意对象的键。

至于优点：如果插入顺序很重要，则需要数组或某种有序列表。如果通过任意键（由各种散列函数作为键）进行快速查找很重要，那么散列表是有意义的。

于 2008-11-12T01:31:53.920 回答
0

[这是对上面me.yahoo.com/a的评论的回复]

这取决于您的哈希函数。假设您的哈希函数根据单词的长度对单词进行哈希处理，chris 的键为 5。同样，yahoo 的键也为 5。现在，两个值（chris 和 yahoo）都将低于 5（即在由 5 键入的“桶”中）。这样，您不必使数组等于数据的大小。

于 2008-11-12T01:47:24.933 回答
0

我相信，这个问题现在已经得到了非常清楚的回答，而且有很多不同的方式。

我只想添加另一个观点（这也可能使新读者感到困惑）

在最抽象的层次上，数组只是连续的内存块。给定单个元素的起始地址 ( startAddress)、大小 ( sizeOfElement) 和 ，index元素的地址计算如下：

elementAddress = startAddress + sizeOfElement * index

这里要注意的有趣的事情是，可以将数组抽象/视为具有indexas 键的哈希表，并将上述函数作为哈希函数计算O(1)中值的位置

于 2010-05-24T12:46:24.603 回答
0

哈希表是一种为快速查找而创建的数据结构。

当条目数非常小时，哈希表无效。

参考

一些例子：

    import java.util.Collection;
    import java.util.Enumeration;
    import java.util.Hashtable;
    import java.util.Set;

    public class HashtableDemo {

    public static void main(String args[]) {

// Creating Hashtable for example

     Hashtable companies = new Hashtable();


// Java Hashtable example to put object into Hashtable
// put(key, value) is used to insert object into map

     companies.put("Google", "United States");
     companies.put("Nokia", "Finland");
     companies.put("Sony", "Japan");


// Java Hashtable example to get Object from Hashtable
// get(key) method is used to retrieve Objects from Hashtable

     companies.get("Google");


// Hashtable containsKey Example
// Use containsKey(Object) method to check if an Object exits as key in
// hashtable

     System.out.println("Does hashtable contains Google as key: "+companies.containsKey("Google"));


// Hashtable containsValue Example
// just like containsKey(), containsValue returns true if hashtable
// contains specified object as value

      System.out.println("Does hashtable contains Japan as value: "+companies.containsValue("Japan"));


// Hashtable enumeration Example
// hashtabl.elements() return enumeration of all hashtable values

      Enumeration enumeration = companies.elements();

      while (enumeration.hasMoreElements()) {
      System.out.println("hashtable values: "+enumeration.nextElement());
      }


// How to check if Hashtable is empty in Java
// use isEmpty method of hashtable to check emptiness of hashtable in
// Java

       System.out.println("Is companies hashtable empty: "+companies.isEmpty());


// How to find size of Hashtable in Java
// use hashtable.size() method to find size of hashtable in Java

      System.out.println("Size of hashtable in Java: " + companies.size());


// How to get all values form hashtable in Java
// you can use keySet() method to get a Set of all the keys of hashtable
// in Java

      Set hashtableKeys = companies.keySet();


// you can also get enumeration of all keys by using method keys()

      Enumeration hashtableKeysEnum = companies.keys();


// How to get all keys from hashtable in Java
// There are two ways to get all values form hashtalbe first by using
// Enumeration and second getting values ad Collection

      Enumeration hashtableValuesEnum = companies.elements();


      Collection hashtableValues = companies.values();


// Hashtable clear example
// by using clear() we can reuse an existing hashtable, it clears all
// mappings.

       companies.clear();
      }
     }

输出：

Does hashtable contains Google as key: true

Does hashtable contains Japan as value: true

hashtable values: Finland

hashtable values: United States

hashtable values: Japan

Is companies hashtable empty: false

Size of hashtable in Java: 3
于 2013-08-24T10:27:49.240 回答