文档章节

哈希表如何工作?

j
 javail
发布于 01/21 19:48
字数 3621
阅读 109
收藏 0

我正在寻找哈希表如何工作的解释 - 用简单的英语表示像我这样的傻瓜!

例如,我知道它需要密钥,计算哈希值(我正在寻找解释如何)然后执行某种模数来计算它存储在存储值的数组中的位置,但这就是我的知识停止的地方。

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

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


#1楼

你们非常接近完全解释这一点,但遗漏了一些事情。 哈希表只是一个数组。 数组本身将在每个插槽中包含一些内容。 您至少会将哈希值或值本身存储在此插槽中。 除此之外,您还可以存储已在此插槽上发生冲突的链接/链接值列表,或者您可以使用开放寻址方法。 您还可以存储指向要从此插槽中检索的其他数据的指针或指针。

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

uint slotIndex = hashValue % hashTableSize;

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

slotIndex = (remainder + 1) % hashTableSize;

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

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

我希望这有帮助。

PS - 在C#中, GetHashCode()方法非常慢,并且在我测试的很多条件下导致实际值冲突。 为了一些真正的乐趣,构建自己的哈希函数并尝试使其永远不会碰撞您正在散列的特定数据,运行速度比GetHashCode快,并且具有相当均匀的分布。 我使用long而不是int size hashcode值完成了这项工作,并且它在哈希表中有多达3200万个哈希值,并且有0次冲突。 不幸的是,我无法共享代码,因为它属于我的雇主...但我可以透露它可能是某些数据域。 当你可以实现这一点时,哈希表非常快。 :)


#2楼

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

散列表通常实现为链接列表的数组。 如果我们想象一个存储人名的表,在几次插入之后它可能会在内存中布局如下,其中()封闭的数字是文本/名称的哈希值。

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

几点:

  • 每个数组条目(indices [0][1] ...)被称为一个 ,并启动一个 - 可能是空的 - 链接列表(在这个例子中也称为元素 - 人名
  • 每个值(例如,带有散列42 "fred" )从bucket [hash % number_of_buckets]链接,例如42 % 10 == [2] ; %模运算符 - 除以桶的数量时的余数
  • 多个数据值可能在同一个桶中发生冲突并从中链接,最常见的原因是它们的哈希值在模运算后发生冲突(例如42 % 10 == [2]9282 % 10 == [2] ),但偶尔会因为哈希值是相同的(例如"fred""jane"都用上面的哈希42显示)
    • 大多数哈希表处理冲突 - 性能略有降低但没有功能混淆 - 通过将正在搜索或插入的值的完整值(此处为文本)与散列到桶中链接列表中已有的每个值进行比较

链表长度与加载因子有关,而与值的数量无关

如果表大小增加,上面实现的哈希表倾向于调整自身大小(即创建更大的桶数组,从那里创建新的/更新的链表,删除旧数组)以保持值与桶的比率(也称为负载)因素 )在0.5到1.0范围内的某个地方。

Hans在下面的注释中给出了其他负载因子的实际公式,但是对于指示值:使用加载因子1和加密强度哈希函数,1 / e(~36.8%)的桶将倾向于为空,另外1 / e (~36.8%)有一个元素,1 /(2e)或~18.4%两个元素,1 /(3!e)约6.1%三元素,1 /(4!e)或~1.5%四元素,1 / (5!e)〜。3%有五个等等。 - 无论表中有多少元素,非空桶的平均链长是~1.58(即是否有100个元素和100个桶,或1亿个元素和1亿个桶),这就是为什么我们说查找/插入/擦除是O (1)常数时间操作。

哈希表如何将键与值相关联

给定如上所述的哈希表实现,我们可以想象创建一个值类型,例如struct Value { string name; int age; }; struct Value { string name; int age; }; ,以及仅查看name字段(忽略年龄)的相等比较和哈希函数,然后发生了一些奇妙的事情:我们可以在表中存储像{"sue", 63}这样的Value记录,然后在没有搜索“sue”的情况下了解她的年龄,找到储值,恢复甚至更新她的年龄
- 生日快乐苏 - 有趣的是不会改变哈希值,因此不需要我们将苏的记录移动到另一个桶。

当我们这样做时,我们使用哈希表作为关联容器map ,并且它存储的值可以被认为是由一个 (名称)和一个或多个其他字段组成 - 仍然被称为 - 容易混淆 - (在我的例子中,只是年龄)。 用作映射的哈希表实现称为哈希映射

这与本答案前面的示例形成对比,我们存储了像“sue”这样的离散值,您可以将其视为自己的密钥:这种用法称为哈希集

还有其他方法可以实现哈希表

并非所有哈希表都使用链接列表(称为单独链接 ),但大多数通用链接列表都是如此,因为主要的替代方案是封闭散列 (也称为开放寻址 - 特别是支持擦除操作 - 具有较少稳定的性能属性,易于发生冲突/哈希函数。


哈希函数的几个字

强烈的哈希......

通用的,最坏情况下的冲突最小化散列函数的工作是有效地随机地在哈希表桶周围喷射密钥,同时总是为相同的密钥生成相同的哈希值。 即使在密钥中任何地方改变一位,理想情况下 - 随机 - 在结果散列值中翻转大约一半的位。

这通常是用数学太精心策划的,这对我来说太复杂了。 我将提到一种易于理解的方式 - 不是最具扩展性或缓存友好性但本质上优雅(如使用一次性密码加密!) - 因为我认为它有助于将上述所需的品质带回家。 假设您正在散列64位double s - 您可以创建8个表,每个256个随机数(下面的代码),然后使用double的内存表示的每个8位/ 1字节切片索引到不同的表,对你查找的随机数进行异或。 通过这种方法,很容易看出在double精度中任何位置改变的位(在二进制数字意义上)导致在其中一个表中查找不同的随机数,以及完全不相关的最终值。

// note caveats above: cache unfriendly (SLOW) but strong hashing...
size_t random[8][256] = { ...random data... };
const char* p = (const char*)&my_double;
size_t hash = random[0][p[0]] ^ random[1][p[1]] ^ ... ^ random[7][p[7]];

弱但快速的哈希......

许多库的散列函数通过未更改的整数传递(称为平凡标识散列函数); 它是上述强烈散列的另一个极端。 在最糟糕的情况下,身份哈希极易发生冲突,但希望是在相当普遍的整数键的情况下,往往会递增(可能有一些间隙),它们会映射到连续的桶中,留下的空白比随机散列更少叶子(我们在前面提到的载荷因子1下约为36.8%),因​​此与随机映射相比,碰撞元素的碰撞更少,链接列表的链接列表更少。 保存生成强哈希所需的时间也很棒,如果按顺序查找密钥,它们将在内存中的存储桶中找到,从而提高缓存命中率。 当键没有很好地增加时,希望它们是随机的,它们不需要强大的哈希函数来完全随机化它们放置到桶中。


#3楼

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

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

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

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

  • 使用要分配给值的空间作为对链接列表的引用。 此链接列表将存储一个或多个值,这些值将在多对一映射中驻留在同一插槽中。 链表还包含帮助搜索人员的密钥。 这就像同一间公寓里的很多人一样,当一个送货员来的时候,他去了房间并专门询问那个人。
  • 在数组中使用双哈希函数,每次都给出相同的值序列而不是单个值。 当我去存储一个值时,我会看到所需的内存位置是空闲还是占用。 如果它是免费的,我可以在那里存储我的值,如果它被占用我从序列中取下一个值,依此类推,直到我找到一个空闲位置并将值存储在那里。 当搜索或检索该值时,我返回到序列给出的相同路径,并且在每个位置询问vaue是否存在,直到我找到它或搜索阵列中的所有可能位置。

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


#4楼

对于所有寻求编程用语的人来说,这是它的工作原理。 高级哈希表的内部实现对存储分配/解除分配和搜索有许多复杂性和优化,但顶级思想将非常相似。

(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;
}

其中calculate_bucket_from_val()是散列函数,其中必须发生所有唯一性魔法。

经验法则是: 对于要插入的给定值,存储桶必须是从它应该存储的值开始的唯一和可衍生的。

Bucket是存储值的任何空间 - 对于这里我将int保存为数组索引,但它也可能是一个内存位置。


#5楼

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

本文转载自:https://vi.sofbug.com/question/344C

j
粉丝 5
博文 1162
码字总数 0
作品 0
深圳
私信 提问
HashMap在并发下可能出现的问题分析

我们都知道,HashMap在并发环境下使用可能出现问题,但是具体表现,以及为什么出现并发问题, 可能并不是所有人都了解,这篇文章记录一下HashMap在多线程环境下可能出现的问题以及如何避免。...

Elivense
2016/12/26
50
0
【译】Swift算法俱乐部-哈希表

本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下...

Andy_Ron
2018/11/15
0
0
Nginx 源码分析:ngx_hash_t(下)

本篇的上篇为 Nginx 源码分析:ngxhasht(上)。 建议先读完上篇再来读下篇。 上篇回顾了hash表的基础概念,分析了中hash表的内存模型及逻辑模型,从而引出了其核型数据结构和,并从设计的角...

_Zhao
2018/08/27
0
0
机器学习时代的哈希算法,将如何更高效地索引数据

  选自blog.bradfieldcs   作者:Tyler Elliot Bettilyon   机器之心编译      哈希算法一直是索引中最为经典的方法,它们能高效地储存与检索数据。但在去年 12 月,Jeff Dean 与 ...

机器之心
2018/05/06
0
0
Redis数据结构——字典

除了用来表示数据库之外,字典也是哈希键的底层实现 typedef struct dictEntry { void *key; //键 union { //值 void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *n......

nao
2016/05/06
128
0

没有更多内容

加载失败,请刷新页面

加载更多

maven插件加载类问题

https://www.cnblogs.com/coder-chi/p/11305498.html

Java搬砖工程师
50分钟前
56
0
(免费)霍兰德职业兴趣测试 在线测试霍兰德职业兴趣

霍兰德职业兴趣测试通过对你的个性进项测试评估,并为你关联到具体的职业。霍兰德职业兴趣量表是由美国著名的心理学教授霍兰德编制,具有广泛的应用和深度的职业兴趣理论。霍兰德职业兴趣量表...

蛤蟆丸子
51分钟前
74
0
在Linux中对pthread_create的未定义引用

我从https://computing.llnl.gov/tutorials/pthreads/在网络上获取了以下演示 #include <pthread.h>#include <stdio.h>#define NUM_THREADS 5void *PrintHello(void *threadid){ ......

javail
51分钟前
90
0
CAS原理分析及ABA问题详解

什么是CAS CAS即Compare And Swap的缩写,翻译成中文就是比较并交换,其作用是让CPU比较内存中某个值是否和预期的值相同,如果相同则将这个值更新为新值,不相同则不做更新,也就是CAS是原子...

Onegoleya
54分钟前
67
0
安卓版微信视频播放全屏处理

问题 在安卓版微信里,video在播放的时候,如果在没有做任何处理的情况下,微信会全屏播放你的视频,会严重影响一些例如直播之类的边看视频边交互的H5应用(注:在iOS里可以通过playsinline...

Jack088
今天
73
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部