【.com速译】为什么这么重要？首先?哈希映射、关联数组或字典数据结构如何在表中工作？?什么时候适合使用哈希表来存储项目？?如何处理哈希表中的“冲突”？轻松查找：假设我们想要存储一个用户列表，以便我们以后可以通过他们的名字查找他们。我们可以简单的把用户存储在一个数组中，等到后面需要找人的时候，遍历所有的数据就可以找到目标用户。当我们只有3个用户时，我们可以通过简单的方式轻松找到他们。但是，如果我们有成千上万的用户，这个过程将会非常缓慢。因此，通过使用哈希表，可以更好地完成查询。正是因为哈希表是以键值对的方式存储的，所以查找数据的速度要比循环遍历数组快很多。创建哈希表使用哈希表，首先需要为每个用户提供一个唯一的值——键（索引），该键将用于存储该项目以供以后检索。假设每个用户都有一个唯一的名称并将其用作主键。在实际应用中，比如用ID作为主键。哈希表的工作原理是将键值对存储在桶（Bucket）中。Hashtable由多个Bucket组成，每个Bucket存储所有具有相同HashKey的(Key,Value)，如图：例如我们将使用4个桶(Bucket)。当一个用户被添加到哈希表中时，我们通过它的索引来决定将其存储在哪个桶中，当需要再次检索用户时，可以直接跳转到正确的桶（Bucket）中寻找目标，速度更快而不是顺序搜索。存储表在表中存储第一个用户“Ada”。首先，决定存储在哪个桶中。这意味着我们需要在关键字所在的位置存储一个字符串（'Ada'），代入后是否可以得到包含该关键字的表中记录的地址它进入功能。这样做的过程就是我们的哈希表，函数就是哈希函数。在这个例子中，我们将创建一个简单的哈希函数。为用户名中的每个字母分配一个数字；A=0，B=1，C=2等等。最后把所有的值加在一起，结果就是哈希值，也就是哈希值，位置就是哈希地址。对于“Ada”，这个数字是3-所以我们可以将Ada存储在桶3中：当稍后需要检索“Ada”时，可以对她的名字执行相同的哈希函数。这将告诉我们在3号桶中寻找她，而无需遍历数组。然后存储下一个用户“Grace”：“Grace”的哈希值为29，但是我们没有29的桶！仅使用其哈希值存储数组将意味着我们将需要很多Buckets。相反，我们需要一种方法将哈希值(29)转换为桶号（从0到3）。一种常见的做法是将哈希值除以桶数，并将余数作为桶数。两个数相除后得到的余数称为模数。“Grace”的哈希值是29，我们有4个桶。29除以4的余数为1，所以Grace存储在1号桶中。这个操作可以写成29%4=1，或者29mod4=1。这样计算桶时，哈希表看起来是这样的：Collisions一个好的哈希函数不仅具有优越的性能，而且可以更均匀地分布存储在底层数组中的值，减少碰撞。实际上，输入的key（定义域）被映射到一个很小的空间，所以冲突在所难免，能做的就是降低Hash冲突的概率。然后存储“Tim：现在，我们有两个用户需要存储在桶3中：有两种方法可以解决这个问题：我们可以使用一种算法不断选择新的桶，直到找到一个空桶，然后存储哈希地址在那里。在每个桶中只有一个底层数组的方法称为开放寻址。或者，在每个桶中存储一组哈希地址而不是只有一个哈希地址。当我们使用这种方法发现冲突时，我们只需将在同一个桶中碰撞键值对。当我们稍后需要检索该数组时，我们仍然可以直接跳转到正确的桶。但是，这次桶可能包含多个数组。在这种情况下，我们将检查每个array依次在bucket中寻找我们想要的array，这个叫做commonoverflowarea，通常用于hashtables的实现，这也是一个好的hashfunction对性能至关重要的原因之一。函数不均匀分配项目，so它们最终集中在可用的几个桶中。在最坏的情况下，如果所有东西都在同一个桶中，可能会遍历每一项来找到我们需要的东西。这就是为什么我们使用哈希表来避免麻烦的原因！【翻译、合作站点转载请注明原文译者及出处均为.com】
