哈希 订阅
Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 展开全文
Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
信息
外文名
Hash
音    译
哈希
特    点
很难找到逆向规律
释    义
把任意长度的输入通过散列算法变换成固定长度的输出
中文名
散列、杂凑
属    性
压缩映射
Hash简介
Hash算法可以将一个数据转换为一个标志,这个标志和源数据的每一个字节都有十分紧密的关系。Hash算法还具有一个特点,就是很难找到逆向规律。Hash算法是一个广义的算法,也可以认为是一种思想,使用Hash算法可以提高存储空间的利用率,可以提高数据的查询效率,也可以做数字签名来保障数据传递的安全性。所以Hash算法被广泛地应用在互联网应用中。 [1]  Hash算法也被称为散列算法,Hash算法虽然被称为算法,但实际上它更像是一种思想。Hash算法没有一个固定的公式,只要符合散列思想的算法都可以被称为是Hash算法。 [2] 
收起全文
精华内容
参与话题
问答
  • 来吧!一文彻底搞定哈希表!

    万次阅读 多人点赞 2019-12-02 10:21:13
    哈希表是个啥? 小白: 庆哥,什么是哈希表?这个哈希好熟悉,记得好像有HashMap和HashTable之类的吧,这是一样的嘛????? 庆哥: 这个哈希确实经常见????,足以说明它是个使用非常频繁的玩意儿,而且像你说的...

    哈希表是个啥?

    小白: 庆哥,什么是哈希表?这个哈希好熟悉,记得好像有HashMap和HashTable之类的吧,这是一样的嘛?😊

    庆哥: 这个哈希确实经常见😂,足以说明它是个使用非常频繁的玩意儿,而且像你说的HashMap和HashTable之类的与哈希这个词肯定是有关系的,那哈希是个啥玩意啊,这个咱们还是得先来搞明白啥是个哈希表。😎

    我们看看百科解释吧:

    散列表Hash table,也叫哈希表),是根据(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表

    怎么样?看到这个,你知道哈希表是什么了嘛?

    小白: 我之前是对哈希表一窍不通啊,不过看了这个百科的解释,我知道如下这些关于哈希表的简单知识点:

    1、哈希表其实也叫散列表,两个是一个玩意,英文是Hash Table

    2、哈希表是一个数据结构

    这两个概念是比较清晰的,至于其他的说什么映射函数叫做散列函数,存放记录的数组叫做散列表这个就有点模糊了,尤其说存放记录的数组称为散列表,那意思是哈希表是个数组?🤣

    庆哥: 首先你说的很清晰的两点说的是很准确的,哈希表也叫做散列表,这只不过是叫法而已,英文单词是Hash table,看到这个英文单词基本上就能猜到,哈希表其实就是直接根绝英文单词音译过来的,至此你应该知道了啥是哈希了吧,对于另外一点,那就很重要了,那就是哈希表其实是一种数据结构。

    要知道数据结构有很多中,每一种都有各自的特点,那么哈希表既然也是一种数据结构,那它有什么特点呢?按照百科的解释,我们大致能知道:可以根据一个key值来直接访问数据,因此查找速度快

    对了,你知道最基本的几个数据结构中,哪个的查询效率是最高的嘛?

    小白: 据我所知,应该是数组吧,我们可以直接使用数组下标来访问数据,因此查询效率是很高滴😁

    庆哥: 对,非常对,哈希表其实本质上就是一个数组 。

    小白: 那为啥还叫哈希表呢?🤣,哈希表肯定有啥特别的吧,为啥本质上是一个数组呢?

    哈希表本质是数组?

    庆哥: 必须滴啊,哈希表本质上是个数组,只能说它的底层实现是用到了数组,简单点说,在数组的这个基础上再捯饬捯饬,加工加工,变得更加有特色了,然后人家就自立门户,叫哈希表😂

    小白: 这是咋个回事啊🤣

    庆哥: 为什么说哈希表的本质是个数组呢?那就得看看,哈希表是怎么来实现的了,一般来说啊,实现哈希表我们可以采用两种方法:

    1、数组+链表

    2、数组+二叉树

    简单点就有这么两种方式,其实说白了,无论哪个都是必须有数组啊,都是再数组的基础上取搞其他的,而且比如第一种数组+链表的形式,本质上是出现哈希冲突的一种解决办法,使用链表存放,所以综合起来叫做数组+链表的方式来实现一个哈希表,另外数组中一般就是存放的单一的数据,而哈希表中存放的是一个键值对,这是个区别吧!

    小白: 停!!!有点迷糊🤣,什么哈希冲突,什么玩意儿啊😂

    庆哥: 🤪,好吧好吧,我说的有点着急了😂,你就记住,哈希表在本质上就是个数组就ok了。

    小白: 可是我还是像知道为啥啊?🤣

    庆哥: 别着急啊,咱慢慢来讲,另外在百科上有这么一个例子,可以帮助你更好的理解哈希表是个啥,它是这样说的:

    在这里插入图片描述

    怎么样?看的懂嘛?

    小白: 反正是有点模糊,这其中提到的函数关系啊,关键字啊,散列函数还有什么函数法则的有点迷迷糊糊的🤣

    哈希表的几个概念

    啥是散列函数

    庆哥: 确实,这都是哈希表中很重要的几个概念,那咱就先搞懂这几个概念吧,我用大白话给你说说这个例子。😎

    比如说,我现在给你个电话本,上面记录的有姓名和对应的手机号,我想让你帮我找王二的手机号是多少,那么你会怎么做呢?

    小白: 这样啊,那我就挨个找王二呗?😀

    庆哥: 确实可以,那么你有没有想过,如果这个王二是在最后几页,那你去岂不是前面几页都白找了,有没有更快的方式呢?

    小白: 也是哦,那这样的话,是不是可以按照人名给分个类,比如按照首字母来排序,就abcd那样的顺序,这样根据王二我就知道去找w这些,这样不久快很多了😁

    庆哥: 的确,我们可以按照人名的首字母去弄一个表格,比如像这样:

    你看,假如现在我让你去帮我找王二的手机号,你一下子就能找到,不用再挨个的去查找了,这效率就高的多了,那么现在重点来了,人家本来叫王二,你为啥用一个w来标记人家呢?让你找王二为啥你不直接找王二而是去找w呢?

    小白: 这个?😅,用w可以更快速的去定位到王二啊😂

    庆哥: 说的很对,我们取姓名的首字母作为一个标志,就可以很快的找到以这个字母开头的人名了,那么王二也就能更快的被我们找到,我们也不用再费力气去找什么张二和李二的,因为人家的名字首字母都不是w。

    小白: 那必须啊,这个方法好吧😁

    庆哥: 对对对,你说到点子上了,那就是方法二字,这里我们就是采用一种方法,什么方法呢?那就是取姓名的首字母做一个排序,那么这是不是就是通过一些特定的方法去得到一个特定的值,比如这里取人名的首字母,那么如果是放到数学中,是不是就是类似一个函数似的,给你一个值,经过某些加工得到另外一个值,就像这里的给你个人名,经过些许加工我们拿到首字母,那么这个函数或者是这个方法在哈希表中就叫做散列函数,其中规定的一些操作就叫做函数法则,这下你知道什么是散列函数了吧😎

    小白: 嗯呢,这下真的是很清楚了,说白了,不就是给我一个值,经过捯饬一下,变成另外一个值吗?花个图的话就是这个样子:

    哈哈,是不是这样?😂

    庆哥: 简单来说就是这样滴😎,咋样,这下知道什么是散列函数了吧?

    关键值key是啥?

    小白: 这下知道了,很清楚😎,那这个关键字key是个啥玩意?

    庆哥: 这个也好理解啊,就像你画的这个图,1是怎么得出来得,是不是根据未加工之前得101得出来得,这个加工过程其实就是个散列函数,而丢给它的这个101就是这个关键值啊,为啥叫它关键值嘞,那是因为我们要对它做加工才能得出我们想要的1啊,你说它关不关键😂

    小白: 哦哦,原来是这样啊,这下就明白啦!对了,我现在有这样的一个理解,你看看对不对啊,那就是哈希表就是通过将关键值也就是key通过一个散列函数加工处理之后得到一个值,这个值就是数据存放的位置,我们就可以根据这个值快速的找到我们想要的数据,是不是这样啊?😂

    庆哥: 说的很正确😎,那你现在对之前那个百科的例子懂了嘛?

    小白: 嗯呢,这下懂了😀

    庆哥: 嗯呢,那就好,其实吧,上面的那中情况并不好,为啥嘞?你想啊,王二在那个位置,如果再来个王三呢?人家的首字母也是w啊,这咋办,位置被王二占了,那王三咋办?这就是哈希冲突啊,撞衫啦🤣

    小白: 阿西吧,又是哈希冲突,它到底似乎个啥玩意啊😂

    庆哥: 不着急,咱们继续来探究哈希表。

    再探哈希表

    庆哥: 我们在之前已经知道了哈希表的本质其实是个数组,数组有啥特点啊?

    小白: 数组嘛,那就是下表从0开始啊,连续的,直接通过下标访问,比如下面这样:

    有一个数组a,我们可以直接通过a[1]的形式来访问到数值7,所以查询效率很高。

    庆哥: 完全正确,那么哈希表本质上是个数组,那它跟这个类似吗?我们来再深入探究一下,首先看个图:

    这张图可是信息量很大啊,你看出来个啥了嘛?

    小白: 这个?我看到了哈希函数,这是啥?它跟散列函数有啥区别啊?还有Entry是个什么鬼😂,还有键值对🤣,蒙圈啊😥

    哈希函数

    庆哥: 别蒙圈啊,我来仔细跟你说说,其实这个哈希函数就是我们之前说的散列函数,为啥嘞?这就跟哈希表也叫做散列表一样啊,你叫作散列表的时候有个散列函数,那你叫哈希表的时候,也得有个哈希函数啊,这样才公平嘛😀,咋样,知道了吧?

    小白: 我去,原来是这么回事啊🤣,那键值对跟Entry嘞?

    键值对和Entry

    庆哥: 这个可是值得好好说道说道,我们知道哈希表本质上是个数组,难道就跟数组的基本使用那样,存个数值,然后通过下表读取之类的嘛?当然不是啦,对于哈希表,它经常存放的是一些键值对的数据,啥是键值对啊,就是我们经常说的key-value啊,简单点说就是一个值对应另外一个值,比如a对应b,那么a就是key,b是value,哈希表存放的就是这样的键值对,在哈希表中是通过哈希函数将一个值映射到另外一个值的,所以在哈希表中,a映射到b,a就叫做键值,而b呢?就叫做a的哈希值,也就是hash值。

    咋样,这块明白了嘛?

    小白: 嗯嗯,明白的,庆哥继续!😎

    庆哥: 那好,我们继续,键值对说的简单点就是有一个key和一个value对应着,比如这张图里的学生信息:

    学生的学号和姓名就是一个键值对啊,根据这个学号就能找到这个学生的姓名,那啥是Entry嘞,我们都知道键值对,在很多语言中也许都有键值对,说白了就是个大众脸啊,咋弄,在咱jdk中可不能那么俗气,不能再叫键值对了,叫啥嘞,那就叫Entry吧😂

    咋样,知道啥是键值对和Entry了吧!

    小白: 必须滴啊,讲的那么生动😁,这张图感觉远不止如此啊,庆哥继续啊😜

    哈希表如何存数据

    庆哥: 好滴,那咱们就继续,来说说哈希表是如何存放数据的,记得看上面的图啊,我们按照这个图来说,我们已经知道了哈希表本质是个数组,所以这里有个数组,长度是8,现在我们要做的是把这个学生信息存放到哈希表中,也就是这个数组中去,那我们需要考虑怎么去存放呢?

    这里的学号是个key,我们之前也知道了,哈希表就是根据key值来通过哈希函数计算得到一个值,这个值就是用来确定这个Entry要存放在哈希表中的位置的,实际上这个值就是一个下标值,来确定放在数组的哪个位置上。

    比如这里的学号是101011,那么经过哈希函数的计算之后得到了1,这个1就是告诉我们应该把这个Entry放到哪个位置,这个1就是数组的确切位置的下标,也就是需要放在数组中下表为1的位置,如图中所示。

    我们之前已经介绍过什么是Entry了,所以这里你要知道,数组中1的位置存放的是一个Entry,它不是一个简单的单个数值,而是一个键值对,也就是存放了key和value,key就是学号101011,value就是张三,我们经过哈希函数计算得出的1只是为了确定这个Entry该放在哪个位置而已。

    现在我们就成功把这个Entry放到了哈希表中了,怎么样,这块听懂了嘛?

    小白: 嗯嗯,听懂了,不过看到这里我产生了一个疑问,那就是这个哈希函数,是不是有一个特定的加工过程,比如可以经过某种计算把101011转换成1,那么有没有可能其他的学号经过哈希函数的计算也得出1呢?那这个时候是不是就撞衫啦😂

    哈希冲突

    庆哥: 的确,你分析得很正确,我们再来看下面这张图:

    你说的这种情况就像图中展示的那样,学号为102011的李四,他的学号经过哈希函数的计算也得出了1,那么也要放到数组中为1的位置,可是这个位置之前已经被张三占了啊,这怎么办?这种情况就是哈希冲突或者也叫哈希碰撞。

    既然出现了这情况,不能不管李四啊,总得给他找个位置啊,怎么找呢?

    小白: 我猜肯定有什么方法可以给李四找位置🤣

    处理哈希冲突

    庆哥: 那必须滴啊😄,有什么方法呢?其实关于哈希冲突的解决办法有好几种嘞,但是我这里只介绍两种主要的方法,一个是开放寻址法,一个是拉链法。

    那什么是开放寻址法呢?我们继续来看图:

    我觉得看图就足以说明问题了,这里所说的开放寻址法其实简单来说就是,既然位置被占了,那就另外再找个位置不就得了,怎么找其他的位置呢?这里其实也有很多的实现,我们说个最基本的就是既然当前位置被占用了,我们就看看该位置的后一个位置是否可用,也就是1的位置被占用了,我们就看看2的位置,如果没有被占用,那就放到这里呗,当然,也有可能2的位置也被占用了,那咱就继续往下找,看看3的位置,一次类推,直到找到空位置。

    对了,Java中的ThreadLocal就是利用了开放寻址法。

    小白: 啥是ThreadLocal啊😂

    庆哥: 咋滴,你不知道啊,没事,给你一篇文章,看了包装你再也不学ThreadLocal了,因为看完这篇,你就再也忘不掉啦,链接直达,走起:再也不学ThreadLocal了,看这一篇就忘不掉了!(万字总结)

    小白: 嗯嗯,我会好好看看的。那什么是拉链法啊?

    庆哥: 拉链法也是比较常用的,像之前你说的HashMap就是使用了这种方法,那这个方法是怎么个回事呢?我们继续来看图:

    之前说的开放寻址法采用的方式是在数组上另外找个新位置,而拉链法则不同,还是在该位置,可是,该位置被占用了咋整,总不能打一架,谁赢是谁的吧😂,当然不是这样,这里采用的是链表,什么意思呢?就像图中所示,现在张三和李四都要放在1找个位置上,但是张三先来的,已经占了这个位置,待在了这个位置上了,那李四呢?解决办法就是链表,这时候这个1的位置存放的不单单是之前的那个Entry了,此时的Entry还额外的保存了一个next指针,这个指针指向数组外的另外一个位置,将李四安排在这里,然后张三那个Entry中的next指针就指向李四的这个位置,也就是保存的这个位置的内存地址,如果还有冲突,那就把又冲突的那个Entry放在一个新位置上,然后李四的Entry中的next指向它,这样就形成了一个链表。

    好啦,这就是拉链法,咋样,明白不😎

    小白: 信息量不少啊,好在庆哥讲的比较清楚,明白啦😀

    庆哥: 明白了就好,那我问你一个问题啊,针对开放寻址和拉链法,你有没有觉得会产生什么问题呢?

    小白: 嗯嗯,我还真有问题,首先是这个拉链法啊,如果冲突的很多,那这个增加的链表岂不是很长,这样也不咋好吧😂

    庆哥: 的确,如果冲突过多的话,这块的链表会变得比较长,怎么处理呢?这里举个例子吧,拿java集合类中的HashMap来说吧,如果这里的链表长度大于等于8的话,链表就会转换成树结构,当然如果长度小于等于6的话,就会还原链表。以此来解决链表过长导致的性能问题。

    小白: 为啥是小于等于6啊,咋不是7嘞😂

    庆哥: 这样设计是因为中间有个7作为一个差值,来避免频繁的进行树和链表的转换,因为转换频繁也是影响性能的啊。

    小白: 嗯嗯,这个知道了,关于开放寻址也有个疑问,那就是如果一直找不到空的位置咋整啊?🤣

    庆哥: 这个不会的,为啥嘞?你这样想,是因为你考虑了一个前提,那就是位置已经被占光了,没有空位置了,但是实际情况是位置不会被占光的,因为有一定量的位置被占了的时候就会发生扩容。

    小白: 阿西吧,还有扩容,那这个扩容是咋回事呢?

    哈希表的扩容

    庆哥: 其实这里不仅仅是因为你说的那种情况才会扩容,还有一个很重要的原因就是当哈希表被占的位置比较多的时候,出现哈希冲突的概率也就变高了,所以很有必要进行扩容。

    那么这个扩容是怎么扩的呢?这里一般会有一个增长因子的概念,也叫作负载因子,简单点说就是已经被占的位置与总位置的一个百分比,比如一共十个位置,现在已经占了七个位置,就触发了扩容机制,因为它的增长因子是0.7,也就是达到了总位置的百分之七十就需要扩容。

    还拿HashMap来说,当它当前的容量占总容量的百分之七十五的时候就需要扩容了。

    而且这个扩容也不是简单的把数组扩大,而是新创建一个数组是原来的2倍,然后把原数组的所有Entry都重新Hash一遍放到新的数组。

    小白: 这个重新Hash一遍是啥意思啊?

    庆哥: 因为数组扩大了,所以一般哈希函数也会有变化,这里的Hash也就是把之前的数据通过新的哈希函数计算出新的位置来存放。

    小白: 嗯嗯,原来是这么回事啊,懂了,对了,那哈希表的数据读取怎么操作的啊?

    哈希表如何读取数据

    庆哥: 要知道这个读取操作,我们还来看这个图:

    比如我们现在要通过学号102011来查找学生的姓名,怎么操作呢?我们首先通过学号利用哈希函数得出位置1,然后我们就去位置1拿数据啊,拿到这个Entry之后我们得看看这个Entry的key是不是我们的学号102011,一看是101011,什么鬼,一边去,这不是我们要的key啊,然后根据这个Entry的next知道下一给位置,在比较key,好成功找到李四。

    小白: 哦哦,原来是这么回事啊,那对于开放寻址那种是不是也是这个思路,先确定到这个位置,然后再看这个位置上的key是不是我们要的,如过不是那就看看下一个位置的。

    庆哥: 可以的,完全正确,好了现在我们对哈希表的讲解已经差不多了,那么你觉得对于哈希表而言,什么是核心呢?

    哈希函数是核心

    小白: 我觉得应该是哈希函数吧,经过上面的讲解,我觉得,如果一个哈希函数设计的足够好的话,就会减少哈希冲突的概率,如果设计的不好,那就会经常撞衫😂,那就很影响性能了,比如刚开始我们举的那个例子,拿姓名的首字母来确定位置,这个哈希函数的设计就不咋滴,比如王二,王三,王四什么的,这都会冲突啊😂

    庆哥: 的确,在哈希表中,哈希函数的设计很重要,一个好的哈希函数可以极大的提升性能,而且如果你的哈希函数设计的比较简单粗陋,那很容易被那些不怀好意的人捣乱,比如知道了你哈希函数的规则,故意制造容易冲突的key值,那就有意思了,你的哈希表就会一直撞啊,一直撞啊😂

    小白: 哈哈😂,那设计哈希函数有什么方法吗?

    庆哥: 必须有啊,比如有直接定址法,数字分析法,折叠法,随机数法和除留余数法等等,要不要继续讲啊😀

    小白: 我去🤣,还是不要了吧,消化不了啊,这次先到这吧,谢谢庆哥😘

    感谢阅读

    大学的时候选择了自学Java,工作了发现吃了计算机基础不好的亏,学历不行这是没办法的事,只能后天弥补,于是在编码之外开启了自己的逆袭之路,不断的学习Java核心知识,深入的研习计算机基础知识,所有心得全部书写成文,整理成有目录的PDF,持续原创,PDF在公众号持续更新,如果你也不甘平庸,那就与我一起在编码之外,不断成长吧!

    其实这里不仅有技术,更有那些技术之外的东西,比如,如何做一个精致的程序员,而不是“屌丝”,程序员本身就是高贵的一种存在啊,难道不是吗?

    非常欢迎你的加入,未来的日子,编码之外,有你有我,一起做一个人不傻,钱很多,活得久的快乐的程序员吧!

    回复关键字“PDF”,获取技术文章合集,已整理好,带有目录,欢迎一起交流技术!

    另外回复“庆哥”,看庆哥给你准备的惊喜大礼包,只给首次关注的你哦!

    任何问题,可以加庆哥微信:H653836923,另外,我有个交流群,我会***不定期在群里分享学习资源,不定时福利***,感兴趣的可以说下我邀请你!

    对了,如果你是个Java小白的话,也可以加我微信,我相信你在学习的过程中一定遇到不少问题,或许我可以帮助你,毕竟我也是过来人了!

    在这里插入图片描述

    感谢各位大大的阅读🥰

    展开全文
  • 哈希

    2018-09-25 21:07:23
    哈希的概念 哈希是一种搜索结构,不过哈希搜索不同于顺序搜索和二叉搜索的是:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储方式,通过某种函数(hashFunc)使元素的存储位置与它的关键码...

    哈希的概念

    哈希是一种搜索结构,不过哈希搜索不同于顺序搜索和二叉搜索的是:可以不经过任何比较,一次直接从表中得到要搜索的元素。
    如果构造一种存储方式,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。

    哈希的搜索效率可高达O(1)。

    常见的哈希函数

    • 直接定制法
      取关键字的某个线性函数为散列地址:Hash(Key) = A * Key + B
      优点:简单、均匀
      缺点:需要事先知道关键字的分布情况
      适合查找比较小且连续的情况
    • 除留余数法
      设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的的质数p作为除数,按照哈希函数:Hash(Key) = Key % p(p<=m),将关键码转换成哈希地址

    例:
    在这里插入图片描述
    如果按照上述哈希方式,向集合中插入元素56,会出现什么问题?

    哈希冲突

    哈希冲突就是不同的关键字计算出了相同的哈希地址,这种现象也称为哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

    解决哈希冲突最常见的方法是:闭散列和开散列
    今天先来看看闭散列
    闭散列:也叫开放地址法,当发生哈希冲突时,如果哈希表未被填满,说明哈希表中必然还有空位置,那么可以把Key存放到表中“下一个”空位中去。

    如何寻找下一个空余位置

    • 线性探测
      当发生哈希冲突时,从冲突的位置开始,依次继续向后探测,直到找到空位置为止。
      例:
      在这里插入图片描述
    • 二次探测
      发生哈希冲突时,二次探查法在表中寻找“下一个”空位置的公式为:Hi = H0 + 2*i +1(i = 1,2,3…),H0是通过关键码Key计算得到的位置,Hi是Key实际的存储位置。
      例:
      在这里插入图片描述

    已经清楚了解决哈希冲突的一些方法,现在就来看看具体的代码如何实现
    哈希表中的位置可以分为三种状态:存在,空,删除,为什么要引入删除状态呢?因为因为删除一个元素后,我们把这个位置的状态置为DELEE,规定这种状态和存在是一样的,不能再在这个位置插入新的元素了,为什么不直接置为空是因为,如果置为空,认为这个位置是没有元素的,那刚刚发生哈希冲突的元素就找不到了。

    例:
    在这里插入图片描述

    【插入】

    1. 使用哈希函数找到待插入元素在哈希表中的位置
    2. 如果该位置中没有元素(是空/删除状态)则直接插入新元素;如果该位置中有元素且和待插入元素相同,则不用插入;如果该位置中有元素但不是待插入元素,则发生哈希冲突,使用线性探测/二次探测找到下一个空位置,插入新元素。
      具体代码:
      HashTable.h //头文件
    #ifndef __HASHTABLE_H__
    #define __HASHTABLE_H__
    
    #include<stdio.h>
    #include<assert.h>
    
    #define MAX_SIZE 10
    
    typedef int HTDataType;
    typedef enum{EMPTY,EXIST,DELETE}State;
    typedef struct HTElem
    {
    	HTDataType _data;
    	State _state;
    }HTElem;
    
    typedef struct HashTable
    {
    	HTElem _ht[MAX_SIZE];
    	int _size;//哈希表中有效元素的个数
    }HT;
    
    void InitHashTable(HT* pHT);
    int InsertHashTable(HT* pHT, HTDataType data);
    int DeleteHashTable(HT* pHT, HTDataType data);
    int FindHashTable(HT* pHT, HTDataType data);
    int EmptyHashTable(HT* pHT);
    int SizeHashTable(HT* pHT);
    int HashFun(HTDataType data);
    
    #endif //__HASHTABLE_H__
    

    HashTable.c //源文件

    #define _CRT_SECURE_NO_WARNINGS 1
    
    #include"HashTable.h"
    
    void InitHashTable(HT* pHT)
    {
    	assert(pHT);
    	int i = 0;
    	for (i = 0; i < MAX_SIZE; i++)
    	{
    		pHT->_ht[i]._state = EMPTY;
    	}
    	pHT->_size = 0;
    }
    
    int InsertHashTable(HT* pHT, HTDataType data)
    {
    	int i = 0;
    	assert(pHT);
    	//防止数据堆积
    	if (pHT->_size * 10 / MAX_SIZE > 7)
    		return 0;
    
    	//1.计算哈希地址
    	int hashAddr = HashFun(data);
    	//2.找存储位置
    	while (EMPTY != pHT->_ht[hashAddr]._state)
    	{
    		if (pHT->_ht[hashAddr]._state == EXIST && data == pHT->_ht[hashAddr]._data)
    			return 0;
    
    		else
    		{
    			线性探测
    			//hashAddr++;
    			越界==超过MAX_SIZE
    			//if (hashAddr == MAX_SIZE)
    			//	hashAddr = 0;
    
    			//二次探测
    			i++;
    			hashAddr = hashAddr + 2 * i + 1;
    			if (hashAddr>MAX_SIZE)
    				hashAddr %= MAX_SIZE;  //这次越界了就不能置0了,万一i很大了,2*i就大于MAX_SIZE了,永远都不能进入哈希表中了,但取模又回到原来的位置了
    		}
    	}
    	//3.插入元素
    	pHT->_ht[hashAddr]._data = data;
    	pHT->_ht[hashAddr]._state = EXIST;
    	pHT->_size++;
    }
    
    int FindHashTable(HT* pHT, HTDataType data)
    {
    	int i = 0;
    	assert(pHT);
    	int hashAddr = HashFun(data);
    	while (EMPTY != pHT->_ht[hashAddr]._state)
    	{
    		if (pHT->_ht[hashAddr]._state == EXIST && data == pHT->_ht[hashAddr]._data)
    			return hashAddr;
    		/* //线性探测
    		hashAddr++;
    		if (hashAddr == MAX_SIZE)
    			hashAddr = 0;*/
    		//二次探测
    		i++;
    		hashAddr = hashAddr + 2 * i + 1;
    		if (hashAddr>MAX_SIZE)
    			hashAddr %= MAX_SIZE;
    	}
    	return -1;
    }
    
    int DeleteHashTable(HT* pHT, HTDataType data)
    {
    	assert(pHT);
    	int ret = FindHashTable(pHT, data);
    	if (-1 != ret)//找到data了
    	{
    		pHT->_ht[ret]._state = DELETE;
    		pHT->_size -= 1;
    		return 1;
    	}
    	return 0;
    }
    
    int EmptyHashTable(HT* pHT)
    {
    	if (pHT == NULL)
    		return 0;
    	return 0 == pHT->_size;
    }
    
    int SizeHashTable(HT* pHT)
    {
    	if (NULL == pHT)
    		return 0;
    	return pHT->_size;
    }
    
    int HashFun(HTDataType data)//求哈希地址
    {
    	return data % MAX_SIZE;
    }
    

    test.c //测试文件

    #define _CRT_SECURE_NO_WARNINGS 1
    
    #include"HashTable.h"
    
    int main()
    {
    	HT pHT;
    	InitHashTable(&pHT);
    	InsertHashTable(&pHT, 23);
    	InsertHashTable(&pHT, 33);
    	InsertHashTable(&pHT, 44);
    	InsertHashTable(&pHT, 43);
    	InsertHashTable(&pHT, 54);
    	InsertHashTable(&pHT, 3);
    	DeleteHashTable(&pHT, 33);
    	int ret = FindHashTable(&pHT, 33);
    	if (-1 != ret)
    	{
    		printf("该数在哈希表中\n");
    	}
    	else
    	{
    		printf("该数不在哈希表中\n");
    
    	}
    
    	InsertHashTable(&pHT, 33);
    
    	return 0;
    }
    
    展开全文
  • 数据结构之哈希

    万次阅读 2019-05-26 17:40:18
    哈希表的相关学习: 哈希表散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数...
    哈希表的相关学习:

    哈希表

    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

    哈希函数

    哈希表是时间与空间之间的平衡,因此哈希函数的设计很重要。所以哈希函数应该尽量减少Hash冲突。也就是说“键”通过哈希函数得到的“索引”分布越均匀越好。

    整形

    对于小范围的整数比如-100~100,我们完全可以对整数直接使用把它映射到0~200之间,而对于身份证这种的大整数,通常我们采用的是取模,比如大整数的后四位相当于mod 10000,这里有一个小问题,如果我们选择的数字如果不好的话,就有可能可能导致数据映射分布不均匀,因此我们最好寻找一个素数.

    如果选择一个合适的素数呢,这里有一个选择:

    图片来源:https://planetmath.org/goodhashtableprimes

    浮点型

    在计算机中都是32位或者64位的二进制表表示,只不过计算j级解析成了浮点数

    字符串

    字符串我们需要把它也转成整型处理

    我们对上面的方法进行优化一下,这就涉及到数学方面的知识了

    对于字符串来说,计算出来的大整形如果特别大的话可能会出现内存溢出,因此我们可以对取模的过程分别挪到式子里面.

    对于整个字符串来说我们可以写程序也是十分容易地写出来他的处理函数

    1
    2
    3
    int hash = 0;
    for (int i = 0; i < s.length; i++) {
    hash = (hash * B + s.charAt(i)) % M;

    案例

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    public class Student {

    int grade;
    int cls;
    String firstName;
    String lastName;

    Student(int grade, int cls, String firstName, String lastName){
    this.grade = grade;
    this.cls = cls;
    this.firstName = firstName;
    this.lastName = lastName;
    }

    @Override
    public int hashCode(){

    int B = 31;
    int hash = 0;
    hash = hash * B + ((Integer)grade).hashCode();
    hash = hash * B + ((Integer)cls).hashCode();
    hash = hash * B + firstName.toLowerCase().hashCode();
    hash = hash * B + lastName.toLowerCase().hashCode();
    return hash;
    }

    //重写
    @Override
    public boolean equals(Object o){

    if(this == o)
    return true;

    if(o == null)
    return false;

    if(getClass() != o.getClass())
    return false;

    Student another = (Student)o;
    return this.grade == another.grade &&
    this.cls == another.cls &&
    this.firstName.toLowerCase().equals(another.firstName.toLowerCase()) &&
    this.lastName.toLowerCase().equals(another.lastName.toLowerCase());
    }

    @Override
    public String toString() {
    return "Student{" +
    "grade=" + grade +
    ", cls=" + cls +
    ", firstName='" + firstName + '\'' +
    ", lastName='" + lastName + '\'' +
    '}';
    }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    import java.util.HashSet;
    import java.util.HashMap;

    public class Main {

    public static void main(String[] args) {

    int a = 42;
    System.out.println(((Integer)a).hashCode());

    int b = -42;
    System.out.println(((Integer)b).hashCode());

    double c = 3.1415926;
    System.out.println(((Double)c).hashCode());

    String d = "imooc";
    System.out.println(d.hashCode());

    System.out.println(Integer.MAX_VALUE + 1);
    System.out.println();

    Student student = new Student(3, 2, "penghui", "Han");
    System.out.println(student.hashCode());

    HashSet<Student> set = new HashSet<>();
    set.add(student);
    for (Student s : set) {
    System.out.println(s.toString());

    }

    HashMap<Student, Integer> scores = new HashMap<>();
    scores.put(student, 100);
    System.out.println(scores.toString());

    Student student2 = new Student(3, 2, "Penghui", "han");
    System.out.println(student2.hashCode());
    System.out.println(student.equals(student2));
    }
    }

    我们可以看到在实际的运行过程中对于整数的负数来说,依旧存在整数类型int中,对于浮点数和字符串来说都有都i是按照上面的方法.来进行计算。对于hashCode值相同我们并没有办法取判断是否属于一个对象,因此在equals和hashCode相同鼓的时候我们才能够说这个两个对象是相同的。

    哈希冲突处理

    链地址法

    哈希表本质就是一个数组,

    对于哈希表我们只需要让他求出K1然后在模于M,当然这个大M是一个素数。对于负数来说,可以直接用绝对值来解决负数的问题。

    当然我们有时候看别人的代码或者源码的时候会看到

    用16进制法表示的整型,先和一个16进制表示的0x7fffffff的结果我们在对M取模,这个表示的是用二进制表示的话是31个1,整型有32位,最高位是符号位,32位和31位相与,这样做是吧最高位的32位,模成了0,符号位的问题我们就解决了。因此如果我们记录的k1的值为4,那么我们就可可以把k1存储到地址4这个位置中去。

    如果k2的索引位置为1,那么假设k3的位置也为1,那么我们就产生了hash冲突,如何解决呢?

    这里我们可以采用链表的方式,对于整个哈希表我们开M个空间,由于会出现hash冲突,我们可以把它做成链表,这种方法也叫separate chaining,当然我们已可以存红黑树,或者TreeMap。

    本质上来说,HashMap就是一个TreeMap数组,HashSet就是一个TreeSet数组。对于Java8来说,Java8之前每一个位置对应的是一个链表,Java8开始之后,当哈希冲突达到了一定的程度,每一个位置从链表转化为红黑树,这个阈值为8;

    代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    import java.util.LinkedList;
    import java.util.List;

    public class HashTable<T>{
    public HashTable() {
    this(DEFAULT_TABLE_SIZE);
    }
    public HashTable(int size) {
    theLists=new LinkedList[nextPrime(size)];
    for(int i=0;i<theLists.length;i++) {
    theLists[i]=new LinkedList<>();//初始化链表数组
    }
    }

    /*
    * 哈希表插入元素
    * */
    public void insert(T x) {
    List<T> whichList=theLists[myhash(x)];
    /*
    * 如果当前哈希地址的链表不含有元素,则链表中添加该元素
    * */
    if(!whichList.contains(x)) {
    whichList.add(x);
    if(++currentSize>theLists.length)//如果表长度不够,则扩容
    rehash();
    }
    }
    public void remove(T x) {
    List<T> whichList=theLists[myhash(x)];
    if(whichList.contains(x)) {
    whichList.remove(x);
    currentSize--;
    }
    }
    public boolean contains(T x) {
    List<T> whilchList=theLists[myhash(x)];
    return whilchList.contains(x);
    }
    public void makeEmpty() {
    for(int i=0;i<theLists.length;i++)
    theLists[i].clear();
    currentSize=0;
    }

    private static final int DEFAULT_TABLE_SIZE=101;

    private List<T> [] theLists;
    private int currentSize;

    /*
    * 哈希表扩容,表长度为下一个素数
    * */
    private void rehash() {
    List<T>[] oldLists=theLists;
    theLists=new List[nextPrime(2*theLists.length)];
    for(int j=0;j<theLists.length;j++)
    theLists[j]=new LinkedList<>();

    currentSize=0;
    /*
    * 更新哈希表
    * */
    for(List<T> list:oldLists)
    for(T item:list)
    insert(item);
    }
    /*
    * myhash()方法获得哈希表的地址
    * */
    private int myhash(T x) {
    int hashVal=x.hashCode();//hashCode()方法返回该对象的哈希码值
    hashVal%=theLists.length;//对哈希表长度取余数
    if(hashVal<0)
    hashVal+=theLists.length;
    return hashVal;
    }
    //下一个素数
    private static int nextPrime(int n) {
    if( n % 2 == 0 )
    n++;

    for( ; !isPrime( n ); n += 2 )
    ;

    return n;
    }
    //判断是否是素数
    private static boolean isPrime(int n) {
    if( n == 2 || n == 3 )
    return true;

    if( n == 1 || n % 2 == 0 )
    return false;

    for( int i = 3; i * i <= n; i += 2 )
    if( n % i == 0 )
    return false;

    return true;
    }
    }

    开放地址法

    这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述:
    H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ( k ≤ m – 1))
    其中: H ( key ) 为关键字 key 的直接哈希地址, m 为哈希表的长度, di 为每次再探测时的地址增量。
    采用这种方法时,首先计算出元素的直接哈希地址 H ( key ) ,如果该存储单元已被其他元素占用,则继续查看地址为 H ( key ) + d 2 的存储单元,如此重复直至找到某个存储单元为空时,将关键字为 key 的数据元素存放到该单元。
    增量 d 可以有不同的取法,并根据其取法有不同的称呼:
    ( 1 ) d i = 1 , 2 , 3 , …… 线性探测再散列;
    ( 2 ) d i = 1^2 ,- 1^2 , 2^2 ,- 2^2 , k^2, -k^2…… 二次探测再散列;
    ( 3 ) d i = 伪随机序列 伪随机再散列;

    例1设有哈希函数 H ( key ) = key mod 7 ,哈希表的地址空间为 0 ~ 6 ,对关键字序列( 32 , 13 , 49 , 55 , 22 , 38 , 21 )按线性探测再散列和二次探测再散列的方法分别构造哈希表。
    解:
    ( 1 )线性探测再散列:
    32 % 7 = 4 ; 13 % 7 = 6 ; 49 % 7 = 0 ;
    55 % 7 = 6 发生冲突,下一个存储地址( 6 + 1 )% 7 = 0 ,仍然发生冲突,再下一个存储地址:( 6 + 2 )% 7 = 1 未发生冲突,可以存入。
    22 % 7 = 1 发生冲突,下一个存储地址是:( 1 + 1 )% 7 = 2 未发生冲突;
    38 % 7 = 3 ;
    21 % 7 = 0 发生冲突,按照上面方法继续探测直至空间 5 ,不发生冲突,所得到的哈希表对应存储位置:
    下标: 0 1 2 3 4 5 6

    49 55 22 38 32 21 13

    当然还有其他的方法比如再哈希法,Coalesced Hashing法(综合了Seperate Chainging 和 Open Addressiing)等。

    代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    class DataItem { //数据                             
    private int iData; // data item (key)

    public DataItem(int ii) {
    iData = ii;
    }
    public int getKey(){
    return iData;
    }

    }

    class HashTable{//数组实现的哈希表,开放地址法之线性探测
    private DataItem[] hashArray; //存放数据的数组
    private int arraySize;
    private DataItem nonItem; //用作删除标志

    public HashTable(int size) {//构造函数
    arraySize = size;
    hashArray = new DataItem[arraySize];
    nonItem = new DataItem(-1); // deleted item key is -1
    }

    public void displayTable(){//显示哈希表
    System.out.print("Table: ");
    for(int j=0; j<arraySize; j++)
    {
    if(hashArray[j] != null)
    System.out.print(hashArray[j].getKey() + " ");
    else
    System.out.print("** ");
    }
    System.out.println("");
    }

    //哈希函数
    public int hashFunc(int key)
    {
    return key % arraySize;
    }


    //在哈希表中插入数据
    public void insert(DataItem item){
    int key = item.getKey(); // 获取数据的键值
    int hashVal = hashFunc(key); // 计算其哈希值

    while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1){
    ++hashVal; // 插入位置被占,线性探测下一位置
    hashVal %= arraySize; // 不让超过数组的大小
    }
    hashArray[hashVal] = item; // 找到空位后插入
    }

    //在哈希表中删除
    public DataItem delete(int key) {
    int hashVal = hashFunc(key); // 计算其哈希值

    while(hashArray[hashVal] != null){
    if(hashArray[hashVal].getKey() == key){
    DataItem temp = hashArray[hashVal]; // 记录已删除的数据
    hashArray[hashVal] = nonItem; // 删除它
    return temp;
    }
    ++hashVal; // 到下一单元找
    hashVal %= arraySize;
    }
    return null; // 没有找到要删除的数据
    }

    //在哈希表中查找
    public DataItem find(int key) {
    int hashVal = hashFunc(key); //哈希这个键

    while(hashArray[hashVal] != null) { // 直到空的单元
    if(hashArray[hashVal].getKey() == key)
    return hashArray[hashVal]; // 找到
    ++hashVal; // 去下一单元找
    hashVal %= arraySize; // 不让超过数组的大小
    }
    return null; // 没有找到
    }

    }

    参考资料

    https://www.cnblogs.com/vincentme/p/7920237.html

    https://blog.csdn.net/w_fenghui/article/details/2010387

    https://128kj.iteye.com/blog/1744810

    展开全文
  • 到底什么是哈希Hash?

    万次阅读 多人点赞 2018-03-13 20:21:00
    定义Hash一般翻译为散列,还有音译为哈希,本文我们统称为哈希(这么叫好听,哈希=散列),通过百度以及谷歌都没有直接找到Hash的定义,而是找到了一些相关的概念,哈希算法,哈希函数,哈希表等概念。我所理解的...

    但凡是从事过计算机行业的人,多多少少都会听说过这个概念,但是又对其很模糊,那么到底什么是Hash呢?

    定义

    Hash一般翻译为散列,还有音译为哈希,本文我们统称为哈希(这么叫好听,哈希=散列),通过百度以及谷歌都没有直接找到Hash的定义,而是找到了一些相关的概念,哈希算法,哈希函数,哈希表等概念。

    我所理解的哈希是指一个过程,这个过程就是把任意长度的输入,通过哈希算法,变换成固定长度的输出,所输出的称为哈希值。这种变换是一种压缩映射,也即哈希值所占的空间一般来说远小于输入值的空间,不同的输入可能会哈希出相同的输出(概率很小)。

    哈希函数、算法

    哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入,在计算上是不可能的,所以数据的哈希值可以检验数据的完整性。一般用于快速查找和加密算法 ---《数据结构与算法分析》

    哈希表

    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表

    特点

    • 如果两个哈希值是不相同的(根据同一函数),那么这两个散列值的原始输入一定是不相同的。
    • 如果两个哈希值相同,两个输入值很可能(极大概率)是相同的,但也可能不同,这种情况称为“哈希碰撞”
    • 抗篡改能力:对于一个数据块,哪怕只改动其一个比特位,其hash值的改动也会非常大。
    • 它是一种单向函数是“非对称”的,即它是一个从明文到密文的不可逆的映射,只有加密过程,没有解密过程。

    部分引自:https://gist.github.com/arrayadd

    展开全文
  • Hash详解

    万次阅读 多人点赞 2018-07-23 10:00:22
    Hash(哈希) Hash :散列,通过关于键值(key)的函数,将数据映射到内存存储中一个位置来访问。这个过程叫做Hash,这个映射函数称做散列函数,存放记录的数组称做散列表(Hash Table),又叫哈希表。JAVA函数hashCode()...
  • 哈希简介

    2018-08-16 23:19:50
    用于数据结构时,主要是为了提高查询的效率,这就对速度比较重视,对抗碰撞不太看中,只要保证hash均匀分布就可以。 在密码学中,hash算法的作用主要是用于消息...也有直接译作哈希表,也叫Hash表, Hash表是一...
  • 哈希

    千次阅读 2018-07-30 17:22:28
    一、什么是哈希哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。 哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来...
  • 哈希图最早介绍

    千次阅读 2018-06-02 15:38:11
    这篇文章写于2016年7月29日,有点老但是很有参考价值 正如很多人在这里所知道的,我对共识机制的兴趣遍布全球。在毕马威的研究报告中,我共同撰写了“共识:价值互联网的不变协议”,讨论了许多共识机制。...
  • 哈希表(散列表)原理详解

    万次阅读 多人点赞 2016-06-03 15:23:19
    哈希表(散列表)原理详解
  • 常见的hash算法及其原理

    万次阅读 多人点赞 2018-07-30 15:47:13
    Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间...
  • 数据结构-哈希表(哈希集合)

    千次阅读 2019-05-12 17:06:05
    哈希表 部分内容来源于博主@SnailMann 前提 在实际编程中,我们常常面临着两个问题:存储和查询,这两个过程的效率往往制约着整个程序的效率,而我们常见的存储数据的数据结构比如线性表,树,图等,数据在结构中的...
  • 哈希函数

    万次阅读 多人点赞 2018-03-01 08:12:14
    什么是 HashHash(哈希),又称“散列”。散列(hash)英文原意是“混杂”、“拼凑”、“重新表述”的意思。在某种程度上,散列是与排序相反的一种操作,排序是将集合中的元素按照某种方式比如字典顺序排列在一起,...
  • Redis底层详解(一) 哈希表和字典

    万次阅读 多人点赞 2018-06-28 17:27:37
    一、哈希表概述  首先简单介绍几个概念:哈希表(散列表)、映射、冲突、链地址、哈希函数。  哈希表(Hash table)的初衷是为了将数据映射到数组中的某个位置,这样就能够通过数组下标访问该数据,提高数据的...
  • 数据结构 Hash表(哈希表

    万次阅读 多人点赞 2018-05-20 01:23:34
    要想知道什么是哈希表,那得先了解哈希函数 哈希函数 对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树,它们的查找都是先从根节点进行查找,从节点取出数据或索引与查找值进行比较。那么,有没有一种...
  • Java 8 中的哈希表

    万次阅读 2020-04-04 13:17:51
    HashMap 是基于 HashTable 的一种数据结构,在普通哈希表的基础上,它支持多线程操作以及空的 key 和 value。 在 HashMap 中定义了几个常量: static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka....
  • 哈希表的原理和使用(C++代码)

    万次阅读 多人点赞 2018-08-12 22:48:32
    概念 散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系f,是的每个关键字key对应一个存储位置f(key)...采用散列技术将记录存储在一块连续的存储空间中,这块连续空间称为散列表或哈希表(Hash-Tab...
  • 哈希表的创建

    万次阅读 多人点赞 2015-10-06 22:28:56
    在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和表中唯一的存储位置相对应,称这个对应关系f为哈希(散列)函数,根据这个思想建立的表为哈希表。  若key1≠key2, 而f(key1)=f(key2), 则...
  • 哈希表、Java中HashMap

    万次阅读 多人点赞 2016-08-05 01:24:46
    哈希表(Hash Table)是一种数据结构; 哈希函数,是支撑哈希表的一类函数; Map是映射、地图的意思,在Java中Map表示一种把K映射到V的数据类型; HashMap是Java中用哈希数据结构实现的Map; 一、Hash算法...
  • 哈希表设计

    2008-08-20 16:05:26
    1.1 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 zhuangshuangshuang). 1.3 假设待填入哈希表的人名...
  • 重温数据结构:哈希 哈希函数 哈希表

    万次阅读 多人点赞 2016-10-27 00:49:30
    在学习 HashMap 前,我们先来温习下 Hash(哈希) 的概念。 什么是 HashHash(哈希),又称“散列”。散列(hash)英文原意是“混杂”、“拼凑”、“重新表述”的意思。在某种程度上,散列是与排序相反的一种操作,...

空空如也

1 2 3 4 5 ... 20
收藏数 435,495
精华内容 174,198
关键字:

哈希