首页 文章

哈希表如何工作?

提问于
浏览
451

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

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

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

Edit: 我没有具体询问哈希码是如何计算的,而是关于哈希表如何工作的一般概述 .

14 回答

  • 64

    这是另一种看待它的方式 .

    我假设你理解了数组A的概念 . 这是支持索引操作的东西,你可以在一步中找到Ith元素A [I],无论A有多大 .

    因此,例如,如果您想要存储有关一群人的信息,这些人都碰巧有不同的年龄,一个简单的方法就是拥有一个足够大的数组,并使用每个人的年龄作为数组的索引 . Thay方式,您可以一步访问任何人的信息 .

    但是当然可能有不止一个人具有相同的年龄,所以你在每个条目中放入数组的是所有具有该年龄的人的列表 . 因此,您可以一步到达一个人的信息,再加上该列表中的一点点搜索(称为“桶”) . 如果有这么多人让水桶变大,它只会减慢速度 . 然后你需要一个更大的数组,以及其他一些方法来获得更多关于这个人的识别信息,比如姓氏的前几个字母,而不是使用年龄 .

    这是基本的想法 . 可以使用产生良好 Value 分布的人的任何功能,而不是使用年龄 . 这是哈希函数 . 就像你可以采取人名的ASCII表示的每三位一样,按某种顺序加扰 . 重要的是,您不希望太多人哈希到同一个桶,因为速度取决于剩余的小桶 .

  • 0

    你拿了很多东西和一个数组 .

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

    你把你的东西放在哈希指示的位置的数组中 . 在给定的散列中,不止一件事可以结束,所以你将这些东西存储在数组或其他合适的东西中,我们通常将其称为存储桶 .

    当您在哈希中查找内容时,您将执行相同的步骤,计算哈希值,然后查看该位置的桶中的内容并检查它是否是您要查找的内容 .

    当您的散列运行良好并且您的数组足够大时,阵列中的任何特定索引最多只会有一些内容,因此您不必非常关注 .

    对于奖励积分,请将其设置为当访问哈希表时,它会将找到的东西(如果有的话)移动到桶的开头,因此下次检查时首先检查它 .

  • 24

    用法和Lingo:

    • Hash tables 用于快速存储和检索数据(或记录) .

    • 使用 hash keys 将记录存储在 buckets

    • Hash keys 是通过将哈希算法应用于记录中包含的选定值来计算的 . 此选择的值必须是所有记录的公共值 .

    • 每个 bucket 可以有多个记录,这些记录按特定顺序组织 .

    真实世界的例子:

    Hash & Co. ,成立于1803年,缺乏任何计算机技术,总共有300个文件柜,以保存其约30,000个客户的详细信息(记录) . 每个文件夹都清楚地标识了0到299的唯一编号 .

    当时的备案员必须快速获取并存储工作人员的客户记录 . 工作人员已经决定使用散列方法来存储和检索他们的记录会更有效率 .

    要提交客户记录,归档职员将使用写在该文件夹上的唯一客户端编号 . 使用此客户编号,他们将调整 hash key 乘以300以识别其所包含的文件柜 . 当他们打开文件柜时,他们会发现它包含许多按客户编号排序的文件夹 . 在确定正确的位置后,他们只需将其放入 .

    要检索客户记录,归档文员将在一张纸上给出一个客户编号 . 使用这个唯一的客户端编号,他们会将其调制为300( hash key ),以确定哪个文件柜具有客户端文件夹 . 当他们打开文件柜时,他们会发现它包含许多按客户编号排序的文件夹 . 通过搜索记录,他们可以快速找到客户端文件夹并检索它 .

    在我们的现实世界中,我们的 bucketsfiling cabinets 而我们的 recordsfile folders .


    要记住的一件重要事情是计算机(及其算法)处理数字比字符串好 . 因此,使用索引访问大型数组比按顺序访问要快得多 .

    As Simon has mentioned 我认为 very important 是散列部分是变换一个大空间(任意长度,通常是字符串等)并将其映射到一个小空间(已知大小,通常是数字)进行索引 . 这个非常重要,要记住!

    因此,在上面的示例中,30,000个可能的客户端映射到较小的空间 .


    其中的主要思想是将整个数据集划分为多个段,以加快实际搜索速度,这通常很耗时 . 在上面的示例中,300个文件柜中的每一个(统计上)将包含大约100条记录 . 通过100条记录搜索(无论顺序)比处理30,000条记录要快得多 .

    您可能已经注意到有些人已经这样做了 . 但是,在大多数情况下,它们不是设计散列方法来生成散列键,而是简单地使用姓氏的第一个字母 . 因此,如果您有26个文件柜,每个文件柜都包含从A到Z的字母,理论上您只需要对数据进行细分并增强文件归档和检索过程 .

    希望这可以帮助,

    Jeach!

  • 2

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

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

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

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

    • 使用要分配给值的空间作为对链接列表的引用 . 此链接列表将存储一个或多个值,这些值将位于多对一映射中的相同插槽中 . 链表还包含帮助搜索人员的密钥 . 这就像在同一个公寓里的很多人,当一个送货员来的时候,他去了房间并专门询问那个人 .

    • 在数组中使用双哈希函数,每次都给出相同的值序列而不是单个值 . 当我去存储一个值时,我会看到所需的内存位置是空闲还是占用 . 如果's free, I can store my value there, if it'被占用,我从序列中取下一个值,依此类推,直到我找到一个空闲位置并将值存储在那里 . 当搜索或返回值时,我返回到序列给出的相同路径,并且在每个位置询问vaue是否存在,直到我找到它或搜索阵列中的所有可能位置 .

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

  • 2

    短而甜蜜:

    哈希表包装了一个数组,我们称之为 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) .

    当我们的internalArray太满,可能大约85%的容量时,我们可以调整内部数组的大小,并将旧数组中的所有项目移动到新数组中 .

  • 12

    到目前为止,所有的答案都很好,并且可以了解哈希表如何工作的不同方面 . 这是一个可能有用的简单示例 . 让我们说我们想要存储一些带有小写字母字符串的项目作为键 .

    正如simon所解释的那样,哈希函数用于从大空间映射到小空间 . 对于我们的示例,哈希函数的简单,天真的实现可以取字符串的第一个字母,并将其映射到整数,因此“alligator”的哈希码为0,“bee”的哈希码为1,“斑马“将是25等

    接下来我们有一个包含26个桶的数组(可能是Java中的ArrayLists),我们将该项放在与哈希相匹配的存储桶中我们的密码 . 如果我们有多个项目的密钥以相同的字母开头,那么它们将具有相同的哈希码,因此所有哈希代码都会在桶中进行,因此必须在桶中进行线性搜索找到一个特定的项目 .

    在我们的例子中,如果我们只有几十个带有跨越字母表的键的项目,那么它将非常有效 . 但是,如果我们有一百万个项目或所有键都以“a”或“b”开头,那么我们的哈希表就不太理想了 . 为了获得更好的性能,我们需要一个不同的散列函数和/或更多的桶 .

  • 34

    它甚至更简单 .

    哈希表只不过是一个包含键/值对的数组(通常是sparse) . 此数组的最大大小通常小于存储在哈希表中的数据类型的可能值集中的项数 .

    哈希算法用于根据将存储在数组中的项的值生成该数组的索引 .

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

    因此,您可以使用多个密钥生成相同的哈希代码 . 当发生这种情况时,迭代向量中的项目,并在向量中的键和正在查找的键之间进行直接比较 . 如果找到,则返回了很好的值,并返回与键关联的值,否则返回任何内容 .

  • 8

    这是外行人的说法 .

    让我们假设您想要在图书馆中填写书籍,而不仅仅是将它们填入其中,但您希望能够在需要时再次轻松找到它们 .

    所以,你决定如果想要阅读一本书的人知道书的 Headers 和引导的确切 Headers ,那么就应该采取这一切 . 有了头衔,这个人在图书管理员的帮助下,应该能够轻松快速地找到这本书 .

    那么,你怎么能这样做?好吧,显然你可以保留一些列表,你可以放置每本书,但是你遇到的问题与搜索图书馆有关,你需要搜索列表 . 当然,列表会更小,更容易搜索,但您仍然不希望从库(或列表)的一端顺序搜索到另一端 .

    你想要的东西,凭书的 Headers ,可以立刻给你正确的位置,所以你要做的只是漫步到正确的架子,拿起书 .

    但是怎么做呢?好吧,当你填满图书馆并填写图书馆时需要做一些预见 .

    您可以设计一个聪明的小方法,而不是仅仅开始从一端到另一端填充库 . 你拿这本书的 Headers ,通过一个小型计算机程序运行它,该计算机程序在该架子上吐出一个货架编号和一个插槽号 . 这是你放书的地方 .

    这个程序的美妙之处在于,当一个人回来阅读这本书时,你再次通过该程序提供 Headers ,并获得与你最初给出的相同的货架编号和插槽号,这是这本书的位置 .

    正如其他人已经提到的那样,该程序被称为散列算法或散列计算,并且通常通过将数据馈入其中(在这种情况下为书的 Headers )并从中计算数字来工作 .

    为简单起见,我们假设它只是将每个字母和符号转换为数字并将它们全部加起来 . 实际上,它比这复杂得多,但是现在就让它留在那里 .

    这种算法的优点在于,如果你一次又一次地向它输入相同的输入,它每次都会继续吐出相同的数字 .

    好吧,这基本上就是哈希表的工作原理 .

    技术内容如下 .

    首先,这个号码的大小 . 通常,这种散列算法的输出位于某个大数字的范围内,通常远大于表中的空间 . 例如,假设我们在图书馆中只有一百万册书籍 . 哈希计算的输出可以在0到10亿的范围内,这要高得多 .

    那么我们该怎么办?我们使用一种称为模数计算的东西,它基本上说如果你计算到你想要的数字(即10亿个数字),但想要保持在一个更小的范围内,每次你达到那个较小范围的极限时,你就开始回到0,但是你必须跟踪你来到的大序列中的距离 .

    假设哈希算法的输出在0的范围内到20,你从特定的 Headers 获得值17 . 如果图书馆的大小只有7本书,你可以算上1,2,3,4,5,6,当你到7时,你会从0开始 . 因为我们需要计算17次,我们有1, 2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,最终数为3 .

    当然,模数计算不是这样做的,它是用除法和余数完成的 . 将17除以7的余数为3(在14处,7次为2次,17次为14次,17次与之间的差值为3次) .

    因此,您将该书放在3号插槽中 .

    这导致了下一个问题 . 碰撞 . 由于该算法无法将书籍空间分开以便它们完全填充库(或者如果你愿意的话就填充哈希表),因此它总是会计算出之前使用过的数字 . 在图书馆的意义上,当你到书架上并想要放入一本书的插槽编号时,那里已经有了一本书 .

    存在各种冲突处理方法,包括将数据运行到另一个计算中以获得表中的另一个点(double hashing),或者只是找到一个与您给出的空间接近的空间(即,在前一本书的旁边,假设插槽是也可称为linear probing) . 这意味着当你稍后试图找到这本书时你会有一些需要做的事情,但它仍然比仅仅从图书馆的一端开始更好 .

    最后,在某些时候,您可能希望将更多书籍放入库中,而不是库允许的 . 换句话说,您需要构建一个更大的库 . 由于库中的确切位置是使用库的精确和当前大小计算的,因此如果您调整库的大小,您可能最终必须找到所有书籍的新位置,因为计算完成后才能找到它们的位置已经改变 .

    我希望这个解释比桶和函数更加脚踏实地:)

  • 10

    很多答案,但没有一个是非常直观的,哈希表在可视化时很容易"click" .

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

    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] ...)被称为 bucket ,并启动一个 - 可能是空的 - 链接值列表(在此示例中也称为元素 - 人名)

    • 每个值(例如带有散列 42"fred" )从存储桶 [hash % number_of_buckets] 链接,例如 42 % 10 == [2] ; % 是模数运算符 - 除以桶的数量时的余数

    • 多个数据值可以在同一个桶中进行链接,最常见的原因是它们的哈希值在模数运算后发生冲突(例如 42 % 10 == [2]9282 % 10 == [2] ),但偶尔因为哈希值相同(例如 "fred" 和_186036都显示)哈希 42 以上)

    • 大多数哈希表处理冲突 - 性能略有降低但没有功能混淆 - 通过将正在搜索或插入的密钥的完整值(此处为文本)与散列到桶中的链表中的每个密钥进行比较

    如果表大小增加,上面实现的哈希表倾向于调整自身大小(即创建更大的桶数组,从那里创建新的/更新的链表,删除旧数组)以保持元素与桶的比率(也称为负载)因素)在0.5到1.0范围内的某个地方 . 使用加载因子1和加密强度散列函数,36.8%的桶将倾向于空,另外36.8%的桶具有一个元素,18.4%的两个元素,6.1%的三个元素,1.5%的四个元素,0.3%的五个等等 . - 无论表中有多少元素(即是否有100个元素和100个桶,或1亿个元素和1亿个桶),列表长度平均为2.0个元素,这就是为什么我们说查找/插入/擦除是O( 1)恒定时间操作 .

    (注意:并非所有哈希表都使用链表,但大多数通用表都使用,因为封闭散列(也称为开放寻址) - 特别是支持擦除操作 - 具有较少稳定的性能属性,具有易于碰撞的键/散列函数) .

    关于哈希函数的几句话

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

    这通常是精心编排的,数学太复杂,我不能理解 . 我将提到一种易于理解的方式 - 不是最具扩展性或缓存友好性但本质上优雅(如使用一次性密码加密!) - 因为我认为它有助于将上述所需的品质带回家 . 假设您正在散列64位 double s - 您可以创建8个表,每个256个随机数(即 size_t random[8][256] ),然后使用 double 's memory representation to index into a different table, XORing the random numbers you look up. With this approach, it'的每个8位/ 1字节切片很容易看出, double 中的任何位置都会发生变化,导致在其中一个表中查找不同的随机数,以及完全不相关的最终值 .

    尽管如此,许多库的散列函数都会通过整数传递整数,这在最坏的情况下极易发生冲突,但希望在相当常见的整数键往往递增的情况下,它们会映射到连续的桶中,从而减少比36.8%的随机散列叶空,因此与随机映射相比,碰撞元素的冲突更少,链接列表的链接列表更少 . 保存生成强哈希所需的时间也很棒 . 当键没有很好地增加时,希望它们是随机的,它们不需要强大的哈希函数来完全随机化它们放置到桶中 .

    嗯,这比散列表解释更有趣,更重,但希望它有助于某人....

  • 17

    这就是我的理解:

    这是一个例子:将整个表格描绘成一系列桶 . 假设您有一个带字母数字哈希码的实现,并且每个字母表都有一个桶 . 此实现将其哈希码以特定字母开头的每个项目放在相应的存储桶中 .

    假设您有200个对象,但其中只有15个具有以字母“B”开头的哈希码 . 哈希表只需要查找并搜索“B”桶中的15个对象,而不是所有200个对象 .

    就计算哈希码而言,没有任何神奇之处 . 目标只是让不同的对象返回不同的代码,并使相同的对象返回相同的代码 . 您可以编写一个总是返回与所有实例的哈希代码相同的整数的类,但是您实际上会破坏哈希表的有用性,因为它只会成为一个巨大的桶 .

  • 2

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

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

    uint slotIndex = hashValue % hashTableSize;
    

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

    slotIndex = (remainder + 1) % hashTableSize;
    

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

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

    我希望这有帮助 .

    PS - 在C#中, GetHashCode() 方法非常慢并且在很多条件下导致实际值冲突我使用long而不是int size hashcode值来完成此操作并且's worked quite well on up to 32 million entires hashvalues in the hashtable with 0 collisions. Unfortunately I can' t共享代码,因为它属于我的雇主...但我可以透露某些数据域是可能的 . 当你可以实现这一点时,哈希表非常快 . :)

  • 92

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

    (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() 是哈希函数必须发生所有唯一性魔法 .

    经验法则是: For a given value to be inserted, bucket must be UNIQUE & DERIVABLE FROM THE VALUE that it is supposed to STORE.

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

  • 2

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

  • 868

    事实证明这是一个非常深刻的理论领域,但基本的轮廓很简单 .

    本质上,哈希函数只是一个从一个空间(比如任意长度的字符串)获取东西并将它们映射到一个对索引有用的空间(比如说无符号整数)的函数 .

    如果你只有很小的空间来散列,那么你可能只需要将这些东西解释为整数,然后你就完成了(例如4字节字符串)

    但通常情况下,你有更大的空间 . 如果你允许作为键的东西的空间大于你用来索引的东西的空间(你的uint32或其他什么),那么你不可能为每个东西都有一个唯一的值 . 当两个或多个东西散列到相同的结果时,你将必须以适当的方式处理冗余(这通常被称为冲突,你如何处理它或不依赖于你是什么使用哈希) .

    这意味着您希望它不太可能具有相同的结果,并且您可能也非常希望哈希函数快速 .

    balancer 这两个属性(以及其他一些属性)让很多人忙碌起来!

    在实践中,您通常应该能够找到一个已知适合您的应用程序并使用它的函数 .

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

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

    当然,在实践中你通常不能这样做,它浪费了太多的内存 . 因此,您可以基于稀疏数组执行所有操作(其中唯一的条目是您实际使用的条目,其他所有条目都隐式为null) .

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

相关问题