data-structures 哈希表java - 哈希表如何工作?




哈希表python 哈希表冲突 (13)

对于所有寻找编程说法的人来说,这是它的工作原理。 高级哈希表的内部实现对于存储分配/释放和搜索有许多复杂和优化,但顶层思路将非常相似。

(void) addValue : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   if (bucket) 
   {
       //do nothing, just overwrite
   }
   else   //create bucket
   {
      create_extra_space_for_bucket();
   }
   put_value_into_bucket(bucket,value);
}

(bool) exists : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   return bucket;
}

where calculate_bucket_from_val() is the hashing function where all the uniqueness magic must happen.

The rule of thumb is: For a given value to be inserted, bucket must be UNIQUE & DERIVABLE FROM THE VALUE that it is supposed to STORE.

Bucket is any space where the values are stored - for here I have kept it int as an array index, but it maybe a memory location as well.

我正在寻找一个哈希表如何工作的解释 - 对于像我这样的傻瓜来说,简单英语!

例如,我知道它需要关键字,计算散列(我正在寻找一个解释如何),然后执行某种模数来确定它存储在数组中的位置,但这是我的知识停止的地方。

任何人都可以澄清这个过程吗?

编辑:我没有具体询问如何计算哈希码,而是总体了解哈希表的工作原理。


如何计算散列通常不依赖于散列表,而是依赖于添加到它的项目。 在.net和Java之类的框架/基类库中,每个对象都有一个GetHashCode()(或类似的)方法返回这个对象的哈希码。 理想的哈希码算法和确切的实现取决于对象中表示的数据。


这是我理解的方式:

下面是一个例子:将整个表格视为一系列桶。 假设你有一个字母数字散列码的实现,并且每个字母的字母都有一个存储桶。 该实现将哈希码以特定字母开头的每个项目放入相应的桶中。

假设您有200个对象,但其中只有15个哈希代码以字母“B”开头。 散列表只需要查找并搜索'B'桶中的15个对象,而不是全部200个对象。

就计算哈希码而言,没有什么不可思议的。 目标是让不同的对象返回不同的代码,并让相同的对象返回相同的代码。 你可以编写一个总是返回与所有实例的哈希码相同的整数的类,但是你基本上会破坏哈希表的有用性,因为它只会成为一个巨大的桶。


很多答案,但没有一个是非常直观的 ,哈希表可以在可视化时轻松“点击”。

哈希表通常以链表的数组形式实现。 如果我们想象一张存储人名的表格,那么在插入一些内容后,它可能会按照如下所示放置在内存中,其中()包含文本的哈希值。

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

几点:

  • 每个数组元素(索引[0][1] ...)被称为一个 ,并启动一个 - 可能为空链接的值列表
  • 每个值(例如,带有散列42 "fred" )从桶[hash % number_of_buckets]例如42 % 10 == [2] ; %是模数运算符 - 除以存储区数量的余数
  • 多数据值可能在同一个桶中发生冲突和链接,这通常是因为它们的哈希值在模数运算后发生冲突(例如42 % 10 == [2]9282 % 10 == [2] ),但偶尔会因为散列值是相同的(例如,上面的散列42所示的"fred""jane"
    • 大多数散列表处理冲突 - 性能略有下降,但没有功能混淆 - 通过比较被查找或插入的密钥的全部值(此处为文本)与散列处理中的链接列表中已存在的每个密钥

如果表大小增长,如上实现的哈希表往往会调整自己的大小(即创建一个更大的数组桶),在那里创建新的/更新的链接列表 - 从删除旧数组),以保持元素与桶的比率因子 )在0.5到1.0的范围内。 使用负载因子1和密码强度哈希函数,36.8%的桶倾向于空,另外36.8%有一个元素,18.4%两个元素,6.1%三个元素,1.5%四个元素,.3%五个等。 - 无论表中有多少元素,列表长度平均为 2.0个元素,这就是为什么查找/插入/擦除是O(1)个常量时间操作的原因。

(注意:并非所有的哈希表都使用链表,但大多数通用目标都使用封闭哈希(又名开放寻址),特别是支持擦除操作时,具有不易稳定的性能特性,并具有容易碰撞的键/散列函数)。

关于散列函数的几句话

通用的,最坏情况的碰撞最小化散列函数的工作是随机地将密钥散布在散列表桶中,同时始终为相同的密钥生成相同的散列函数。 理想情况下,即使在密钥中的任何位置改变一位,也可以随机翻转得到的散列值中的大约一半位。

这通常是数学计算过于复杂,我不能苟同。 我会提到一种易于理解的方式 - 不是最具可扩展性或缓存友好的,但内在优雅的(例如使用一次性密码加密!) - 因为我认为它有助于推动上述所需的品质。 假设你正在哈希64位double s--你可以创建8个包含256个随机数的表,然后使用double内存表示的每个8位/ 1字节片索引到一个不同的表中,将你的随机数抬头。 通过这种方法,很容易看出,在double结果中的任何位置发生变化都会导致在其中一个表中查找到不同的随机数,并且完全不相关的最终值。

尽管如此,许多库的哈希函数通过不变的整数来传递整数,在最糟糕的情况下这是非常容易碰撞的,但是希望在整数密钥相当普遍的情况下,这些整数密钥往往会增加,他们会映射到连续的桶中,比随机哈希离开的36.8%更空,从而与随机映射相比具有更少的碰撞和更长的碰撞元素的链接列表。 节省生成强大散列所花费的时间也非常棒。 当密钥不能很好地增加时,希望它们会足够随机,它们不需要强大的哈希函数来将它们的位置完全随机化到桶中。

那么,这是比哈希表解释更有趣,更重要,但希望它可以帮助某人....


你拿一堆东西和一个数组。

对于每一件事,你都为它构成一个索引,称为哈希。 散列的重要之处在于它“散布”很多; 你不希望两个类似的东西具有相似的散列。

你把你的东西放在哈希表示的位置。 不止一件事情可以结束于给定的散列,因此您可以将其存储在数组或其他适当的东西中,我们通常称之为存储桶。

当你在散列中查找事物时,你会经历相同的步骤,计算散列值,然后查看该位置存储桶中的内容,并检查它是否是你要查找的内容。

当你的哈希工作正常,并且你的数组足够大时,在数组中的任何特定索引处最多只会有几件事情,所以你不必非常注意。

对于奖励积分,应该这样做,即当你的哈希表被访问时,它将发现的东西(如果有的话)移动到桶的开始处,所以下一次是检查的第一件事情。


简短而甜美:

散列表包装了一个数组,我们称它为internalArray 。 项目以这种方式插入到数组中:

let insert key value =
    internalArray[hash(key) % internalArray.Length] <- (key, value)
    //oversimplified for educational purposes

有时候两个键会散列到数组中的同一个索引,并且你想保留这两个值。 我喜欢将这两个值存储在同一个索引中,通过使internalArray成为链表的数组来简化代码:

let insert key value =
    internalArray[hash(key) % internalArray.Length].AddLast(key, value)

所以,如果我想从我的哈希表中检索一个项目,我可以写:

let get key =
    let linkedList = internalArray[hash(key) % internalArray.Length]
    for (testKey, value) in linkedList
        if (testKey = key) then return value
    return null

删除操作就像写简单一样。 正如你所看到的,插入,查找和从我们的链表中删除几乎是O(1)。

当我们的内部阵列变得太满时,可能容量大约为85%,我们可以调整内部阵列的大小,并将旧阵列中的所有项目移动到新阵列中。


到目前为止所有的答案都很好,可以从哈希表的不同方面着手。 这是一个简单的例子,可能会有所帮助。 比方说,我们想存储一些小写字母字符串的项目作为一个键。

正如西蒙解释的那样,哈希函数用于从大空间映射到小空间。 对于我们的例子来说,一个简单而朴实的哈希函数实现可以将字符串的第一个字母和映射到一个整数,所以“alligator”的哈希码为0,“bee”的哈希码为1,“斑马“将是25等。

接下来我们有一个26个桶的阵列(可以是Java中的ArrayLists),并且我们把这个项目放在与我们的密钥的哈希码匹配的桶中。 如果我们有多个项目具有以相同字母开头的密钥,则它们将具有相同的散列码,因此所有散列码都会进入桶中,因此必须在存储桶中进行线性搜索找到一个特定的项目。

在我们的例子中,如果我们只有几十个项目,并且键盘跨越字母表,那么它将工作得很好。 但是,如果我们有一百万个项目或者所有的键都以'a'或'b'开头,那么我们的哈希表就不是理想的。 为了获得更好的性能,我们需要一个不同的散列函数和/或更多的存储桶。


事实证明,这是一个相当深的理论领域,但基本轮廓很简单。

从本质上讲,散列函数只是一个从一个空间(例如任意长度的字符串)获取事物的函数,并将它们映射到一个对索引有用的空间(比如无符号整数)。

如果你只有一小部分空间需要散列,你可能会将这些东西解释为整数,而你完成了(例如4字节的字符串)

不过,通常情况下,你有更大的空间。 如果你允许的东西作为键的空间大于你用来索引的东西的空间(你的uint32或其他东西),那么你不可能为每个东西赋一个唯一的值。 当两个或两个以上的东西哈希到相同的结果,你必须以适当的方式处理冗余(这通常被称为碰撞,你如何处理或不取决于你是什么使用散列)。

这意味着你希望它不太可能有相同的结果,并且你可能也真的希望散列函数更快。

平衡这两个属性(和其他一些属性)让很多人忙碌起来!

在实践中,您通常应该能够找到已知适用于您的应用程序并使用它的功能。

现在让这个工作成为一个哈希表:想象一下,你并不关心内存使用情况。 然后,只要您的索引集(例如,所有uint32)都可以创建一个数组。 当你添加一些东西到表中时,你将它散列为键,并查看该索引处的数组。 如果那里什么都没有,你就把价值放在那里。 如果那里已经有东西,你可以将这个新条目添加到该地址的一个列表中,以及足够的信息(你的原始密钥或聪明的东西),以找到哪个条目实际上属于哪个键。

因此,当你走了很长一段时间,你的散列表(数组)中的每个条目都是空的,或者包含一个条目或一个条目列表。 检索是一种简单的索引到数组中,并返回值,或走值的列表并返回正确的值。

当然在实践中你通常不能这样做,这会浪费太多的记忆。 所以你根据一个稀疏数组来做一切事情(其中唯一的条目是你实际使用的条目,其他条目都隐式为空)。

有很多方案和技巧可以使这项工作更好,但这是基础知识。


这是另一种看待它的方法。

我假设你理解数组A的概念。这是支持索引操作的东西,在这里你可以一步到达第I个元素A [I],不管A有多大。

因此,举个例子,如果你想存储关于所有恰好有不同年龄段的人的信息,一个简单的方法是创建一个足够大的数组,并将每个人的年龄作为数组的索引。 Thay的方式,你可以一步到达任何人的信息。

但是,当然可能有不止一个年龄相同的人,所以在每个条目中放入的数组都是具有该年龄段的所有人的列表。 所以你可以在一个步骤中加入一个人的信息,并在该列表中添加一些搜索(称为“桶”)。 只有当人数众多,水桶变大时,它才会变慢。 然后你需要一个更大的阵列,并用其他方式获得更多关于这个人的识别信息,比如他们姓氏的前几个字母,而不是使用年龄。

这是基本的想法。 可以使用产生良好价值分布的人的任何功能,而不是使用年龄。 这是散列函数。 就像你可以把人名的ASCII表示的每一个三位一样,按照某种顺序进行编码。 重要的是,你不想让太多的人散列到同一个桶中,因为速度取决于桶很小。


散列表完全适用于实际计算遵循随机访问机器模型的事实,即在O(1)时间或恒定时间内可访问存储器中任何地址的值。

因此,如果我有一个全键(我可以在应用程序中使用的所有可能的键的集合,例如学生的卷号,如果它是4位数,那么这个宇宙是一组数字,从1到9999)和一个方法将它们映射到一个有限的数量的大小我可以在我的系统中分配内存,理论上我的哈希表已准备就绪。

通常,在应用程序中,密钥的Universe的大小要比我想要添加到散列表的元素的数量大很多(我不想浪费1GB的内存来散列,例如10000或100000的整数值,因为它们是32在二进制reprsentaion长)。 所以,我们使用这个哈希。 这是一种混合式的“数学”操作,它将我的大型宇宙映射到一小组我能够容纳的记忆中。 在实际情况中,散列表的空间常常与(每个元素的元素数*大小)具有相同的“order”(big-O),所以我们不会浪费太多内存。

现在,映射到一个小集合的大集合映射必须是多对一的。 所以,不同的键将被分配到相同的空间(??不公平)。 有几种方法可以解决这个问题,我只知道其中两个受欢迎的方法:

  • 使用要分配给该值的空间作为链接列表的引用。 此链接列表将存储一个或多个值,它们位于同一个槽中,位于多个到一个映射中。 链接列表还包含帮助搜索的人的密钥。 就像同一间公寓里的很多人一样,当送货员来时,他走进房间,专门为那个人问道。
  • 在一个数组中使用双散列函数,每次给出相同的值序列而不是单个值。 当我去存储一个值时,我会看到所需的内存位置是空闲的还是被占用的。 如果它是免费的,我可以在那里存储我的价值,如果它被占用了,我会从序列中获得下一个值,等等,直到我找到一个免费的位置,然后在那里存储我的价值。 当搜索或检索值时,我回到序列给定的相同路径上,并且在每个位置询问vaue,直到找到它或搜索数组中的所有可能位置。

CLRS算法简介提供了有关该主题的非常好的见解。


你们非常接近解释这一点,但错过了一些事情。 散列表只是一个数组。 阵列本身将包含每个插槽中的内容。 最低限度,您将在此插槽中存储散列值或值本身。 除此之外,还可以存储已在此插槽上发生碰撞的链接/链接值列表,或者可以使用开放寻址方法。 您还可以存储一个指针或指针,指向您想要从此插槽中检索的其他数据。

值得注意的是,散列值本身通常不会指示放置值的位置。 例如,散列值可能是一个负整数值。 显然,负数不能指向数组的位置。 另外,散列值往往会比可用的插槽大很多倍。 因此,哈希表本身需要执行另一个计算来确定值应该进入哪个时隙。 这是通过模数运算来完成的,例如:

uint slotIndex = hashValue % hashTableSize;

该值是该值将要进入的时隙。 在开放寻址中,如果插槽已经填充了另一个散列值和/或其他数据,则将再次运行模数运算以查找下一个插槽:

slotIndex = (remainder + 1) % hashTableSize;

我想可能还有其他更先进的确定槽位索引的方法,但这是我见过的常见方法......会对任何性能更好的其他方法感兴趣。

使用模数方法,如果您有一个表格大小为1000,那么介于1和1000之间的任何散列值将进入相应的插槽。 任何负值和大于1000的任何值都可能会碰撞槽值。 发生这种情况的可能性取决于你的散列方法,以及你添加到散列表中的总项数。 一般来说,最好的做法是制作散列表的大小,使得添加到其中的值的总数仅等于其大小的约70%。 如果你的散列函数在分布上做的很好,你通常会遇到很少或没有桶/槽冲突,并且它对于查找和写操作都会非常快速地执行。 如果事先不知道要添加的值的总数,则可以使用任何方法进行良好的猜测,然后在添加到元素的元素数量达到容量的70%时调整您的哈希表的大小。

我希望这有助于。

PS - 在C#中, GetHashCode()方法很慢,在我测试过的很多条件下会导致实际值冲突。 为了一些真正的乐趣,建立你自己的散列函数并尝试使它永远不会碰撞你正在散列的特定数据,运行速度比GetHashCode快,并且分布相当均匀。 我已经使用long来代替int大小的hashcode值,并且它在散列表中有3个32位的散列值,它们在0个冲突的情况下运行得非常好。 不幸的是,我不能分享代码,因为它属于我的雇主......但是我可以揭示某些数据域可能存在这种情况。 当你可以做到这一点时,散列表非常快。 :)


它比这更简单。

散列表只不过是一个包含键/值对的向量的数组(通常是sparse )。 此数组的最大大小通常小于存储在散列表中的数据类型的可能值集合中的项目数。

散列算法用于根据将存储在数组中的项目的值生成该数组中的索引。

这就是存储数组中键/值对的向量的地方。因为数组中的索引值集合通常小于该类型可能具有的所有可能值的数量,所以有可能您的哈希值算法将为两个单独的密钥生成相同的值。 一个好的散列算法会尽可能地避免这种情况(这就是为什么它会被降级到这种类型的原因,因为它具有一般散列算法不可能知道的特定信息),但这是不可能的。

正因为如此,你可以有多个密钥来生成相同的哈希码。 当发生这种情况时,向量中的项目将被迭代,并直接比较向量中的键和正在查找的键。 如果找到了,很好,并且与该关键字相关联的值被返回,否则没有返回。


以下是我如何使用它:

final MessageDigest messageDigest = MessageDigest.getInstance("MD5");
messageDigest.reset();
messageDigest.update(string.getBytes(Charset.forName("UTF8")));
final byte[] resultByte = messageDigest.digest();
final String result = new String(Hex.encodeHex(resultByte));

其中Hex是: Apache Commons项目中的 org.apache.commons.codec.binary.Hex





data-structures hash hashtable modulo