哈希表的基础？
我很困惑哈希表的基本概念。 如果我要编码哈希，我甚至会开始？ 哈希表和普通数组有什么区别？
基本上如果有人回答这个问题，我想我的所有问题都会被回答：如果我有100个随机生成的数字（作为键），我将如何实现一个哈希表，为什么这将有利于数组？
伪代码或Java将被赞赏作为一种学习工具…
到目前为止的答案已经帮助定义了散列表并解释了一些理论，但是我认为一个例子可能会帮助你对它们有更好的感觉。
散列表和普通数组有什么区别？
哈希表和数组都是允许您存储和检索数据的结构。 两者都允许您指定索引并检索与其关联的值。 Daniel Spiewak指出，区别在于数组的索引是连续的 ，而哈希表的索引是基于与其相关的数据的值 。
为什么我会使用哈希表？
散列表可以提供一种非常有效的方法来search大量数据中的项目，尤其是不易于search的数据。 （这里的“大”意味着巨大的 ，因为执行顺序search会花费很长时间）。
如果我要编码哈希，我甚至会开始？
没问题。 最简单的方法是发明一个任意的math运算，你可以对数据执行，返回一个数字N （通常是一个整数）。 然后使用该数字作为索引到“桶”数组中，并将数据存储在桶N 。 诀窍在于select一种操作，这种操作倾向于将值放在不同的桶中，以便于以后find它们。
例如：一个大型购物中心保存顾客的汽车和停车位的数据库，以帮助购物者记住他们停放的位置。 数据库存储make ， color ， license plate和parking location 。 在离开商店时，购物者通过input其颜色和颜色来find他的汽车。 数据库返回一个（较短的）车牌和停车位列表。 快速扫描find购物车。
你可以用一个SQL查询来实现这个：
SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"
如果数据存储在一个基本上只是一个列表的数组中，您可以想象通过扫描数组来查找所有匹配的条目来实现查询。
另一方面，设想一个哈希规则：
添加make和color中所有字母的ASCII字符代码，除以100，并使用余数作为散列值。
这个规则将把每个项目转换为0到99之间的一个数字，基本上把数据整理到100个桶中。 每次客户需要定位一辆汽车时，您可以对制造商和颜色进行散列，以查找包含信息的100 个桶。 您立即将search量减less了100倍！
现在把这个例子扩展到大量的数据，比方说一个有数百万个条目的数据库，这个数据库是根据数十个标准进行search的。 一个“好的”散列函数将把数据分配到桶中，以最小化任何额外的search，从而节省大量的时间。
首先，你必须了解什么是散列函数。 哈希函数是一个函数，它需要一个键（例如，一个长度为arbritrary的string）并返回一个尽可能唯一的数字。 相同的键必须总是返回相同的散列。 在java中一个非常简单的string哈希函数可能看起来像
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)); }
（这张地图执行唯一的键，并不是所有的地图都可以。）
两个不同的键可以散列到相同的值，或者两个不同的散列映射到相同的数组索引。 有很多处理这个技术。 最简单的方法是为每个数组索引使用链表（或二叉树）。 如果散列函数足够好，则永远不需要线性search。
现在查找一个关键：
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查找关键字和生成关键字的方式更感兴趣。”
-
哈希将一个关键对象转换为一个数字。 这就是所谓的“哈希” – 它把哈希当作对象。 请参阅散列函数 。 例如，总结string的字节是标准的散列技术。 您计算模2 2 32的总和，以保持散列的可pipe理的大小。 哈希总是给出相同的答案。 这是O （1）。
-
这个数字给你一个HashTable中的“槽”。 给定一个任意的关键对象，散列值计算一个散列值。 散列值然后给你表中的插槽。 通常是
mod( hash, table size )。 这也是O （1）。
这是一般的解决scheme。 两个数字计算，你已经从任意对象作为关键到任意对象作为值。 几件事情可以一样快。
从对象到哈希值的转换发生在这些常见的方式之一。
-
如果它是一个4字节的“原始”对象，那么该对象的本地值是一个数字。
-
对象的地址是4个字节，那么对象的地址可以用作散列值。
-
一个简单的哈希函数 （MD5，SHA1，无论）累积对象的字节来创build一个4字节的数字。 高级哈希不是简单的字节总和，简单的总和并不足以反映所有的原始input位。
哈希表中的槽是mod（数字，表的大小）。
如果该插槽具有所需的值，则表示完成。 如果这不是理想的价值，你需要去别的地方看看。 有几种stream行的探测algorithm在表格中寻找一个空闲点。 线性是一个简单的search下一个自由点。 二次方是一个非线性跳跃寻找一个空闲的插槽。 一个随机数发生器（带有一个固定的种子）可以被用来产生一系列的均匀但是任意地传播数据的探测器。
探测algorithm不是O （1）。 如果桌子足够大，碰撞的可能性很小，探测器也不重要。 如果桌子太小，碰撞就会发生，探测就会发生。 此时，平衡探测和表格大小以优化性能成为“调整和调整”的问题。 通常我们只是让桌子变大一点。
见散列表 。
我没有看到特别指出的东西：
在数组上使用散列表的关键是性能。
遍历数组通常需要从O（1）到O（x）的任何地方，其中x是数组中的项目数。 然而，find你的物品的时间将是非常可变的 ，特别是如果我们正在谈论数以十万计的物品在arrays中。
无论哈希表中有多less项，正确加权的哈希表通常具有刚刚超过O（1）的几乎恒定的访问时间。
你不想使用一个哈希表100个随机生成的数字。
考虑哈希表的一个好方法是考虑值对。 让我们使用学生，并说每个人都有一个学生的身份证号码。 在你的程序中，你存储学生的信息（姓名，电话号码，账单等）。 您只想使用基本信息（例如姓名或学号）查找所有关于学生的信息。
假设你有一万名学生。 如果将它们全部存储在一个数组中，则必须遍历整个数组，将每个条目的学生ID与您正在查找的ID进行比较。
相反，如果您将他们的学生ID号码“散列”（见下文）到数组中的某个位置，那么您只需要search学生的数字是否具有相同的散列值。 更less的工作，find你想要的东西。
在这个例子中，假设学生ID只是6位数字。 我们的散列函数只能使用数字的最后3位作为“散列键”。 因此232145被哈希到数组位置145.那么你只需要一个包含999个元素的数组（每个元素都是学生列表）。
这对你来说应该是一个好的开始。 当然，你应该阅读一个教科书或维基百科这种信息。 但是我认为你已经这样做了，厌倦了阅读。
简而言之，哈希表是如何工作的。
想象一下，你有一个图书馆，充满书籍。 如果你要把书放在一个arrays里，你可以把每本书放在书架上的某个位置，然后当有人让你find一本书的时候，你会翻遍所有的书架 – 很慢。 如果有人说“book＃12345”，你可以很容易地find它。
比方说，如果书名以'A'开始，则它在第一行。如果第二个字母是'B'，则它在第一行，第二行。如果第三个字母是'C'，则它进入第1排，第2排，第3排，等等，直到你确定书的位置。 然后，根据这本书的标题，你可以确切地知道它应该在哪里。
现在，我所描述的简单的“哈希”algorithm中存在一些问题 – 有些书架会被重载，而有些书架则是空的，有些书会被分配到同一个槽中。所以真正的哈希函数被精心构造尽量避免这样的问题。
但这是基本的想法。
我将回答这个部分关于哈希表和数组之间的区别…但是因为我从来没有实现过任何导入哈希algorithm，我会留给那些更知识的人:)
数组只是一个有序的对象列表。 对象本身并不重要，重要的是，如果你想按照插入顺序列出对象，它总是一样的（也就是说第一个元素总是索引为0）。
至于散列表，这是索引的关键，而不是秩序…我认为，散列algorithm的基本search将给你更多的洞察力，比我可以…维基百科有一个非常体面的…确定“桶“密钥进入快速检索作为关键的任意对象。
至于优点：如果插入顺序很重要，则需要一个数组或某种有序列表。 如果通过任意键快速查找（由各种散列函数键入）是重要的，那么散列表是有意义的。
[这是对上面的me.yahoo.com/a发表的评论的回复]
这取决于你的哈希函数。 让我们假设你的散列函数按照你的单词的长度散列了一个单词，chris的密钥将是5.同样，yahoo的密钥也将是5.现在，两个值（chris和yahoo）都会低于5在由5键键入的“桶”中）。 这样你就不必制作一个等于数据大小的数组。
我相信这个问题现在已经有了很清楚的解答。
我只想补充一点（这也可能会使新读者感到困惑）
在最不抽象的层面上，数组只是连续的内存块。 给定起始地址（ startAddress ），size（ sizeOfElement ）和单个元素的index ，元素的地址计算如下：
elementAddress = startAddress + sizeOfElement * index
在这里需要注意的是，数组可以被抽象/视为散列表，其index作为关键字，以及上述函数作为计算O（1）中的值的位置的散列函数，
哈希表是为快速查找而创build的数据结构。
当条目数量非常小时，哈希表无效。
参考
一些例子：
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
