https://stackoverflow.com/questions/282712
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我对哈希表的基本概念感到很困惑。如果我要编写哈希代码，我怎么会开始？ Hash表和普通数组之间有什么区别？
基本上如果有人回答了这个问题，我认为我的所有问题都会得到解答： 如果我有100个随机生成的数字（作为键），我将如何实现哈希表？为什么这对数组有利？
Psuedo-code或Java将被视为一种学习工具......
解决方案
到目前为止，答案有助于定义哈希表并解释一些理论，但我认为一个例子可以帮助你对他们有更好的感受。
哈希表和普通数组有什么区别？
哈希表和数组都是允许您存储和检索数据的结构。两者都允许您指定索引并检索与其关联的值。正如Daniel Spiewak指出的那样，差异在于数组的索引是顺序，而散列表的索引是基于与它们相关联的数据的值。
为什么我会使用哈希表？
哈希表可以提供一种非常有效的方法来搜索大量数据中的项目，尤其是那些无法轻易搜索的数据。 （“大”在这里意味着 ginormous ，从某种意义上说需要很长时间才能执行顺序搜索。）
如果我要编写哈希代码，我甚至可以开始？
没问题。最简单的方法是发明一个可以对数据执行的任意数学运算，它返回一个数字 N （通常是一个整数）。然后使用该数字作为“桶”数组的索引。并将数据存储在存储桶＃ N 中。诀窍在于选择一种操作，该操作倾向于将值放在不同的存储桶中，以便您以后轻松找到它们。
示例：大型购物中心会保留其顾客的汽车和停车位置的数据库，以帮助购物者记住他们停放的位置。数据库存储 make ， color ，牌照和停车位置。在离开商店时，购物者通过输入其品牌和颜色来找到他的汽车。数据库返回（相对较短的）车牌和停车位列表。快速扫描找到购物者的车。
您可以使用SQL查询实现此目的：
SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"
如果数据存储在一个基本上只是一个列表的数组中，您可以想象通过扫描数组中的所有匹配条目来实现查询。
另一方面，设想一个哈希规则：
添加make和color中所有字母的ASCII字符代码除以100，并使用余数作为哈希值。
此规则会将每个项目转换为0到99之间的数字，基本上将数据排序到100个存储桶中。每次客户需要找到汽车时，您都可以对品牌和颜色进行散列，以找到包含该信息的100个 one 桶。您立即将搜索量减少了100倍！
现在将示例扩展为大量数据，比如根据数十个条件搜索数百万条目的数据库。一个“好”的哈希函数将以最小化任何额外搜索的方式将数据分发到存储桶中，从而节省大量时间。
其他提示
首先，您必须了解哈希函数是什么。 哈希函数是一个获取密钥的函数（例如，一串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;
}
哈希表是关联。这与数组有很大的不同，数组只是线性数据结构。使用数组，您可以执行以下操作：
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 。
我认为这可能会回答你的大部分问题。哈希表的实现是一个相当有趣的主题，一个哪个维基百科可以很好地解决。
“我对Hash Tables查找密钥的方式以及密钥的生成方式更感兴趣。”
-
哈希将密钥对象转换为数字。这被称为“散列”。 - 它从对象中产生哈希。请参阅哈希函数。例如，对字符串的字节求和是标准散列技术。您计算模2＆sup> 32 的总和，以使散列保持可管理的大小。哈希总是给出相同的答案。这是 O （1）。
-
该号码为您提供了“广告位”。在HashTable中。给定任意密钥对象，哈希值计算哈希值。哈希值然后为您提供表中的插槽。通常是
mod（哈希，表大小）。这也是 O （1）， -
如果它是“原始”的话。对象的4个字节，那么对象的原生值就是一个数字。
-
对象的地址是4个字节，然后对象的地址可以用作哈希值。
-
一个简单的哈希函数（MD5，SHA1，无论如何）累积字节创建4字节数字的对象。高级哈希值不是简单的字节总和，简单的和不足以反映所有原始输入位。
这是一般解决方案。两个数值计算，你已经从任意对象作为任意对象的键作为值。很少有东西可以快。
从对象到哈希值的转换以这些常见方式之一发生。
哈希表中的槽是mod（数量，表的大小）。
如果该插槽具有所需的值，则表示您已完成。如果这不是所需的值，则需要查看其他位置。有几种流行的探测算法可以在表格中查找空闲点。线性是对下一个免费点的简单搜索。 Quadratic是一种寻找空闲时隙的非线性跳跃。随机数生成器（带有固定种子）可用于生成一系列探针，这些探针将均匀但任意地传播数据。
探测算法不是 O （1）。如果表格足够大，碰撞的几率很低，探测无关紧要。如果表太小，则会发生冲突并发生探测。此时，它变成了“调整和调整”的问题。平衡探测和表格大小以优化性能。通常我们只是把桌子做得更大。
请参阅哈希表。
我没有特别注意到的东西：
在数组上使用哈希表的关键是性能。
遍历数组通常需要从O（1）到O（x）的任何位置，其中x是数组中的项数。但是，找到你的项目的时间将非常变量，特别是如果我们在谈论数组中的数十万个项目。
正确加权的哈希表通常具有几乎超过O（1）的常量访问时间，无论哈希表中有多少项。
您不希望对100个随机生成的数字使用哈希表。
考虑哈希表的一个好方法是考虑价值对。让我们使用学生，并说每个人都有一个学生证号码。在您的程序中，您可以存储学生的信息（姓名，电话号码，账单等）。您只想使用基本信息（例如姓名或学生ID）找到有关学生的所有信息。
假设您有10,000名学生。如果将它们全部存储在数组中，则必须遍历整个数组，将每个条目的学生ID与您要查找的学生ID进行比较。
相反，如果您“哈希” （见下文）他们的学生证号码到阵列中的一个位置，那么你只需要搜索学生的号码具有相同的哈希值。找到你想要的东西要少得多。
在这个例子中，假设学生ID只是6位数字。我们的散列函数可以仅使用数字的底部3位作为“散列键”。因此232145被散列到数组位置145.那么你只需要一个999元素的数组（每个元素都是学生列表）。
这对你来说应该是一个好的开始。当然，您应该阅读教科书或维基百科来获取此类信息。但我认为你已经这样做了，并且厌倦了阅读。
简而言之，就是哈希表的工作原理。
想象一下，你有一个满是书的图书馆。如果你要将书籍存放在一个阵列中，你可以将每本书放在书架上的某个位置，然后当有人要求你找一本书时，你会看到所有书架 - 非常慢。如果有人说“预订＃12345”，你可以很容易地找到它。
让我们说，如果书名以'A'开头，则在第1行。如果第二个字母是'B'，则在第1行，第2行。如果第三个字母是'C '，它在第1排，第2排，第3层......等等，直到您确定书的位置。然后，根据书的标题，你可以准确地知道它应该在哪里。
现在，在简化的“散列”中存在一些问题。我描述的算法 - 一些架子将被重载而另一些架空，一些书将被分配到同一个槽..所以真正的哈希函数被精心构造以试图避免这样的问题。
但这是基本的想法。
我将回答有关哈希表和数组之间差异的部分...但由于我以前从未实现任何导入的哈希算法，我会将其留给更有见识的人：）
数组只是一个有序的对象列表。对象本身并不重要......重要的是，如果要按插入顺序列出对象，它总是相同的（意味着第一个元素总是的索引为0）。
至于哈希表，它是由键索引的，而不是顺序...我认为哈希算法的基本搜索会给你提供比我更多的洞察力...维基百科有一个非常体面的...确定“桶”密钥用于快速检索用作密钥的任意对象。
关于优点：如果插入顺序很重要，则需要一个数组或某种有序列表。如果通过任意键快速查找（由各种哈希函数键入）很重要，那么哈希表是有意义的。
[这是me.yahoo.com/a上述评论的回复]
这取决于你的哈希函数。让我们假设您的哈希函数按照单词的长度哈希一个单词，克里斯的键将是5.同样，雅虎的键也将是5.现在，两个值（克里斯和雅虎）将低于5（即在一个'桶'键入5）。这样，您就不必使数组等于数据大小。
我相信，这个问题现在已经以很多不同的方式得到了很清楚的回答。
我只想添加另一个视角（也可能会让新读者感到困惑）
在抽象程度最低的情况下，数组只是连续的内存块。给定单个元素的起始地址（ startAddress ），size（ sizeOfElement ）和 index ，元素的地址计算如下： / p>
elementAddress = startAddress + sizeOfElement * index
这里需要注意的有趣的事情是，数组可以抽象/查看为哈希表， index 作为键，上面的函数作为哈希函数计算中值的位置O（1）
哈希表是为快速查找而创建的数据结构。
当条目数非常小时，哈希表无效。
一些例子：
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
