精华内容
下载资源
问答
  • HASH链表

    千次阅读 2019-04-19 10:18:06
    一,HASH链表与逻辑读 oracle要从高速缓冲区中拿到5号文件1234号块buffer的信息,就需要使用到HASH算法。 Buffer Cache:高速缓冲区中包含多个buffer,每一个buffer就记录一个数据块对应的缓冲信息。 Buffer Header:...

    Oracle内核技术揭密_吕海波  学习笔记

    一,HASH链表与逻辑读

    oracle要从高速缓冲区中拿到5号文件1234号块buffer的信息,就需要使用到HASH算法。
    Buffer Cache:高速缓冲区中包含多个buffer,每一个buffer就记录一个数据块对应的缓冲信息。
    Buffer Header:每一个Buffer Cache都有一个Buffer Header(BH),它用来记录这个高速缓冲区中所有的buffer address(BA),通过BA可以定位到缓冲区中的buffer。
    Buffer Bucket:它里面只记录一系列Buffer Header双向链的链表头信息,oracle通过文件号和块号计算出HASH值,来定位到相应的Bucket,当不同Buffer Header下的buffer计算HASH值发生冲突时就会定位到同一个bucket,这时多个Buffer Header会构成一个双向链,叫cache buffer chain链表(CBC链表),并将链表头信息记录在bucket中。

    Bucket数量由隐藏参数_db_block_hash_buckets决定:

    SQL> SELECT   ksppinm, ksppstvl, ksppdesc FROM   x$ksppi x, x$ksppcv y WHERE   x.indx = y.indx AND  ksppinm = '_db_block_hash_buckets';
    
    KSPPINM                    KSPPSTVL      KSPPDESC
    ----------------------     ---------    -------------------------------------
    _db_block_hash_buckets     262144        Number of database block hash buckets


    搜索buffer步骤如下:
    1,进程根据要访问块的文件号和块号,计算HASH值得到到数字X。
    2,根据HASH值X,定位到相应HASH Bucket,如BucketX。
    3,搜索Bucket后的链表,查找哪个Buffer Header(BH)是目标BH。
    4,找到目标BH后,从中取出Buffer的Buffer Address(BA)。
    5,按BA访问Buffer

    上述为oracle逻辑读的过程,如果搜索Bucket后的BH链表,没有找到包含目标块的BH,就说明目标块不在缓存中,只能物理读了。

    二,catch buffer chain latch 与buffer pin 锁

     SGA是公共内存,因此在访问buffer时是需要锁保护机制的,oracle采用的锁机制是latch和mutex。

    正常情况下一个bucket后面的catch buffer chain就需要一个catch buffer chain latch来保护,但latch也是占用空间的,于是oracle这里是一个CBC  latch负责多个bucket的锁管理。一个latch的大小为192字节:

    SQL> select to_number(b.addr,'xxxxxxxxxxxxxxxxxxxxx')- 
                to_number(a.addr,'xxxxxxxxxxxxxxxxxxxxx')
         from (select rownum rid,addr from v$latch_children where name='cache buffers chains' order by addr) a,
              (select rownum rid,addr from v$latch_children where name='cache buffers chains' order by addr) b 
         where a.rid=b.rid+1 and rownum <=1;
    
    TO_NUMBER(B.ADDR,'XXXXXXXXXXXXXXXXXXXXX')-TO_NUMBER(A.ADDR,'XXXXXXXXXXXXXXXXXXXX
    --------------------------------------------------------------------------------
                                                                                 192

    当我们搜索CBC链表时,需要先获取CBC latch进行锁保护;当找到目标所在BH,访问buffer前要修改buffer pin进行锁保护,修改完buffer pin后就可以释放CBC latch ,后续的buffer访问只需要在buffer pin保护下进行即可;当访问完buffer需要释放buffer pin时,这时又需要CBC latch 来保护。CBC latch的功能就是保护CBC链的访问和buffer pin的修改。

    buffer pin锁有多种模式,常见的为共享模式(S)和独占模式(X)。在没有加锁时buffer pin值为0。

    CBC latch也有共享和独占两种模式,模式的选择取决于以下4个要素:

    1)对象类型(唯一索引,非唯一索引等)

    2)块类型(根块,叶块,表块等)

    3)操作(读,修改)

    4)访问路径

    对于一般的逻辑读,我们在读取buffer信息前都需要修改buffer pin值,这时的CBC latch基本都是独占锁。步骤如下:

     

     

     当我们要访问索引的叶块时,需要频繁的访问它的根块和枝块,但对根块和枝块修改的频繁度又很低,这时没有必要使用独占模式的CBC latch。优化后的步骤如下:

     

     

     

     

     

     可以看到在CBC latch 共享模式中搜索CBC链表和访问buffer,中间没有修改buffer pin,也没有释放CBC latch,这样CBC latch的加载时间比独占模式要长,但它缓解了独占模式下的争用。

    在有唯一索引、唯一索引扫描情况时,根块、枝块、叶块、表块都是使用共享模式的CBC latch。也就是说当唯一索引使用‘where  id = ?’这样的等值条件查询时,就使用共享模式的CBC latch;当使用的是范围查询时,则和非唯一索引一样,只有根块、枝块共享模式的CBC latch,不修改buffer pin,而叶块、表块还是使用独占模式的CBC latch。可以理解为使用索引唯一访问路径时,所有块的访问都是共享模式的CBC latch;另外,rowid方式直接逻辑读表块时是使用独占模式的CBC latch。

    除了唯一索引外,在多数情况下,读或者写表块,都是使用独占模式的CBC latch。

    另外根块和枝块,只要不修改,就使用共享模式的CBC  latch。

     

    展开全文
  • 数据结构 Hash表(哈希表)

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

    参考链接:数据结构(严蔚敏)
    文章发布很久了,具体细节已经不清晰了,不再回复各种问题
    文章整理自严蔚敏公开课视频
    可以参考
    https://www.bilibili.com/video/av22258871/
    如果链接失效 可以自行搜索 数据结构严蔚敏视频
    @2021/07/12

    一、什么是Hash表

    要想知道什么是哈希表,那得先了解哈希函数
    哈希函数

    对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树,它们的查找都是先从根节点进行查找,从节点取出数据或索引与查找值进行比较。那么,有没有一种函数H,根据这个函数和查找关键字key,可以直接确定查找值所在位置,而不需要一个个比较。这样就**“预先知道”**key所在的位置,直接找到数据,提升效率。

    地址index=H(key)
    说白了,hash函数就是根据key计算出应该存储地址的位置,而哈希表是基于哈希函数建立的一种查找表

    二、哈希函数的构造方法

    根据前人经验,统计出如下几种常用hash函数的构造方法:
    直接定制法
    哈希函数为关键字的线性函数如 H(key)=a*key+b
    这种构造方法比较简便,均匀,但是有很大限制,仅限于地址大小=关键字集合的情况
    使用举例:
    假设需要统计中国人口的年龄分布,以10为最小单元。今年是2018年,那么10岁以内的分布在2008-2018,20岁以内的分布在1998-2008……假设2018代表2018-2008直接的数据,那么关键字应该是2018,2008,1998……
    那么可以构造哈希函数H(key)=(2018-key)/10=201-key/10
    那么hash表建立如下

    indexkey年龄人数(假设数据)
    02018 0-10200W
    12008 10-20250W
    21998 20-30253W
    31988 30-40300W
    ……

    数字分析法
    假设关键字集合中的每个关键字key都是由s位数字组成( k 1 , k 2 , … … , k n k_1,k_2,……,k_n k1,k2,,kn),分析key中的全体数据,并从中提取分布均匀的若干位或他们的组合构成全体

    使用举例
    我们知道身份证号是有规律的,现在我们要存储一个班级学生的身份证号码,假设这个班级的学生都出生在同一个地区,同一年,那么他们的身份证的前面数位都是相同的,那么我们可以截取后面不同的几位存储,假设有5位不同,那么就用这五位代表地址。
    H(key)=key%100000
    此种方法通常用于数字位数较长的情况,必须数字存在一定规律,其必须知道数字的分布情况,比如上面的例子,我们事先知道这个班级的学生出生在同一年,同一个地区。
    平方取中法
    如果关键字的每一位都有某些数字重复出现频率很高的现象,可以先求关键字的平方值,通过平方扩大差异,而后取中间数位作为最终存储地址。
    使用举例
    比如key=1234 1234^2=1522756 取227作hash地址
    比如key=4321 4321^2=18671041 取671作hash地址
    这种方法适合事先不知道数据并且数据长度较小的情况
    折叠法
    如果数字的位数很多,可以将数字分割为几个部分,取他们的叠加和作为hash地址
    使用举例
    比如key=123 456 789
    我们可以存储在61524,取末三位,存在524的位置
    该方法适用于数字位数较多且事先不知道数据分布的情况
    除留余数法用的较多
    H(key)=key MOD p (p<=m m为表长)
    很明显,如何选取p是个关键问题。

    使用举例
    比如我们存储3 6 9,那么p就不能取3
    因为 3 MOD 3 == 6 MOD 3 == 9 MOD 3
    p应为不大于m的质数或是不含20以下的质因子的合数,这样可以减少地址的重复(冲突)

    比如key = 7,39,18,24,33,21时取表长m为9 p为7 那么存储如下

    index012345678
    key721(冲突后移)24*39*18(冲突后移)33冲突后移)
    **随机数法** H(key) =Random(key) 取关键字的随机函数值为它的散列地址

    hash函数设计的考虑因素

    1.计算散列地址所需要的时间(即hash函数本身不要太复杂)
    2.关键字的长度
    3.表长
    4.关键字分布是否均匀,是否有规律可循
    5.设计的hash函数在满足以上条件的情况下尽量减少冲突

    三、哈希冲突

    即不同key值产生相同的地址,H(key1)=H(key2)
    比如我们上面说的存储3 6 9,p取3是
    3 MOD 3 == 6 MOD 3 == 9 MOD 3
    此时3 6 9都发生了hash冲突

    哈希冲突的解决方案

    不管hash函数设计的如何巧妙,总会有特殊的key导致hash冲突,特别是对动态查找表来说。
    hash函数解决冲突的方法有以下几个常用的方法
    1.开放定制法
    2.链地址法
    3.公共溢出区法
    建立一个特殊存储空间,专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。
    4.再散列法
    准备若干个hash函数,如果使用第一个hash函数发生了冲突,就使用第二个hash函数,第二个也冲突,使用第三个……
    重点了解一下开放定制法和链地址法

    开放定制法

    首先有一个H(key)的哈希函数
    如果H(key1)=H(keyi)
    那么keyi存储位置 H i = ( H ( k e y ) + d i ) M O D m H_i=(H(key)+d_i)MOD m Hi=(H(key)+di)MODmm为表长
    d i d_i di有三种取法
    1)线性探测再散列
    d i = c ∗ i d_i=c*i di=ci
    2)平方探测再散列
    d i = 1 2 , − 1 2 , 2 2 , − 2 2 d_i=1^2,-1^2,2^2,-2^2 di=12,12,22,22……
    3)随机探测在散列(双探测再散列)
    d i d_i di是一组伪随机数列
    注意
    增量di应该具有以下特点(完备性):产生的Hi(地址)均不相同,且所产生的s(m-1)个Hi能覆盖hash表中的所有地址

    • 平方探测时表长m必须为4j+3的质数(平方探测表长有限制)
    • 随机探测时m和di没有公因子(随机探测di有限制)
      三种开放定址法解决冲突方案的例子

    废话不多说,上例子就明白了
    有一组数据
    19 01 23 14 55 68 11 86 37要存储在表长11的数组中,其中H(key)=key MOD 11
    那么按照上面三种解决冲突的方法,存储过程如下:
    (表格解释:从前向后插入数据,如果插入位置已经占用,发生冲突,冲突的另起一行,计算地址,直到地址可用,后面冲突的继续向下另起一行。最终结果取最上面的数据(因为是最“占座”的数据))
    线性探测再散列
    我们取di=1,即冲突后存储在冲突后一个位置,如果仍然冲突继续向后

    index012345678910
    key551141986
    23冲突23
    68冲突68冲突68
    11冲突11冲突11冲突11冲突11冲突11
    37冲突37冲突37
    最终存储结果55123146811371986
    **平方探测再散列**
    index012345678910
    key55114371986
    23冲突H(23)+1
    H(68)-1冲突68冲突H(68)+1冲突H(68)+4
    11冲突H(11)+1冲突H(11)-1
    最终存储结果55123143768198611
    **随机探测在散列(双探测再散列)** 发生冲突后 H(key)‘=(H(key)+di)MOD m 在该例子中 H(key)=key MOD 11 我们取di=key MOD 10 +1 则有如下结果:
    index012345678910
    key55168141986
    23冲突H(23)+3+1
    11冲突H(11)+1+1冲突H(11)+1+1+1+1
    (H(37)+8)模11冲突37冲突(H(37)+8+8+8)模11(H(37)+8+8)模11冲突
    最终存储结果55168142311371986

    链地址法

    产生hash冲突后在存储数据后面加一个指针,指向后面冲突的数据
    上面的例子,用链地址法则是下面这样:

    这里写图片描述
    四、hash表的查找

    查找过程和造表过程一致,假设采用开放定址法处理冲突,则查找过程为:
    对于给定的key,计算hash地址index = H(key)
    如果数组arr【index】的值为空 则查找不成功
    如果数组arr【index】== key 则查找成功
    否则 使用冲突解决方法求下一个地址,直到arr【index】== key或者 arr【index】==null

    hash表的查找效率

    决定hash表查找的ASL因素:
    1)选用的hash函数
    2)选用的处理冲突的方法
    3)hash表的饱和度,装载因子 α=n/m(n表示实际装载数据长度 m为表长)
    一般情况,假设hash函数是均匀的,则在讨论ASL时可以不考虑它的因素
    hash表的ASL是处理冲突方法和装载因子的函数
    前人已经证明,查找成功时如下结果:

    这里写图片描述
    可以看到无论哪个函数,装载因子越大,平均查找长度越大,那么装载因子α越小越好?也不是,就像100的表长只存一个数据,α是小了,但是空间利用率不高啊,这里就是时间空间的取舍问题了。通常情况下,认为α=0.75是时间空间综合利用效率最高的情况。

    上面的这个表可是特别有用的。假设我现在有10个数据,想使用链地址法解决冲突,并要求平均查找长度<2
    那么有1+α/2 <2
    α<2
    即 n/m<2 (n=10)
    m>10/2
    m>5 即采用链地址法,使得平均查找长度< 2 那么m>5

    之前我的博客讨论过各种树的平均查找长度,他们都是基于存储数据n的函数,而hash表不同,他是基于装载因子的函数,也就是说,当数据n增加时,我可以通过增加表长m,以维持装载因子不变,确保ASL不变。
    那么hash表的构造应该是这样的:

    这里写图片描述
    五、hash表的删除

    首先链地址法是可以直接删除元素的,但是开放定址法是不行的,拿前面的双探测再散列来说,假如我们删除了元素1,将其位置置空,那 23就永远找不到了。正确做法应该是删除之后置入一个原来不存在的数据,比如-1

    展开全文
  • hash是以空间换时间的结构,现在空间越来越大,而且对性能要求越来越高的年代,这绝对是值得的。...hash函数的选择必须慎重,如果不幸所有的元素之间都产生了冲突,那么hash表将退化为链表,其性能会大打折扣,时间...

    hash是以空间换时间的结构,现在空间越来越大,而且对性能要求越来越高的年代,这绝对是值得的。

    hash含义就是散列,就是把我们本来想​查找的一大群结构体数据分散开,更容易查找。一个好的hash函数应该做到对所有元素平均分散排列,尽量避免或者降低他们之间的冲突(Collision)。hash函数的选择必须慎重,如果不幸所有的元素之间都产生了冲突,那么hash表将退化为链表,其性能会大打折扣,时间复杂度迅速降为O(n),绝对不要存在任何侥幸心理,因为那是相当危险的。历史上就出现过利用Linux内核hash函数的漏洞,成功构造出大量使hash表发生碰撞的元素,导致系统被DoS,所以目前内核的大部分hash函数都有一个随机数作为参数进行掺杂,以使其最后的值不能或者是不易被预测。这又对 hash函数提出了第二点安全方面的要求:hash函数最好是单向的,并且要用随机数进行掺杂。提到单向,你也许会想到单向散列函数md4和md5,很不幸地告诉你,他们是不适合的,因为hash函数需要有相当好的性能。

    散列函数: 将字符串等传入我们的散列函数,而散列函数的职责就是给我们返回一个value值,我们通过这个值引做hash表下标去访问我们想要查找的数据;例如这样的函数:

    int Hash(char *key, int TableSize)
    {
         unsigned int HashVal = 0;
         while(*key != '\0')
                 HashVal += *key++;
         return HashVal % TableSize;
    }
    

    这就是一个简单的hash函数,就是把我们传入过来的key(由我们的数据中一个或者多个结构体成员的成员来作为key)来得到一个返回值,这个返回值就是我们的value值。

    一个好的hash​函数就是把我们的说有数据尽可能均匀的分散在我们预设的TableSize大小的hash表中。哈希表的几种方法:

    1、直接定址法:取关键字key的某个线性函数为散列地址,如Hash(key) = key 或 Hash(key) = A*key+B;A,B为常数

    2、除留取余法:关键值除以比散列表长度小的素数所得的余数作为散列地址。Hash(key) = key % p;

    3、平均取中法:先计算构成关键码的标识符的内码的平方,然后按照散列表的大小取中间的若干位作为散列地址。

    4、折叠法:把关键码自左到右分为位数相等的几部分,每一部分的位数应与散列表地址位数相同,只有最后一部分的位数可以短一些。把这些部分的数据叠加起来,就可以得到具有关键码的记录的散列地址。分为移位法和分界法。

    5、随机数法:选择一个随机函数,取关键字的随机函数作为它的哈希地址。

    6、数学分析法:设有N个d位数,每一位可能有r种不同的符号。这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布均匀些,每种符号出现的机会均等;在某些位上分布不均匀,只有某几种符号经常出现。可根据散列表的大小,选取其中各种符号分布均匀的若干位作为散列地址。

    但是无论我们怎么样去选择这个函数,都不可能完全避免不同key值的hash[value]​指向会映射到同一散列地址上。这样就会造成哈希冲突/哈希碰撞。所以我们需要找到处理这种冲突的方法,大概分为这两种:分离链接法和开放定址法。

    分离链接法:其实就是我们说的hash桶的含义了。哈希桶就是盛放不同key链表的容器(即是哈希表),在这里我们可以把每个key的位置看作是一个桶,桶里放了一个链表

    这里写图片描述

    相信大家可以看出来,使用一个数组来存放记录方法的哈希冲突太多,基于载荷因子的束缚,空间利用率不高,在需要节省空间的情况下,我们可以用哈希桶来处理哈希冲突。

    哈希桶是使用一个顺序表来存放具有相同哈希值的key的链表的头节点,利用这个头节点可以找到其它的key。哈希桶就是为了解决哈希冲突的。举个例子,有一组序列为[1,2,3,4,5,6,7,8,9],使用的哈希函数为f(key) = key mod 5,那么依次得到的hasvalue就是[1,2,3,4,0,1,2,3,4],显然在key值为1、6的时候得到的哈希值都为1,如下所示:

    key123456789
    f(key)123401234

    这个时候就产生了冲突了,也就是不同的key通过映射后得到了同样值的hashvalue。而所谓的哈希桶算法其实就是链地址解决冲突的方法,如上面的例子所示,就可以设置桶的个数为5,也就是f(key)集合的个数,而这样的话,hashvalue就可以作为桶的索引,将1,2,3,4,5分别通过f(key)得到1,2,3,4,0,则可将这几个key放入桶1,2,3,4,0的首地址所指的内存中,然后处理值为6的key,得到hashvalue值为1,这个时候需要放入桶1中,但桶1的首地址已经有了元素1,怎么办?那么就可以为每个桶开辟一片内存,内存中存放所有hashvalue相同的key,冲突的key之间用单向链表进行存储,这样就解决了哈希冲突,在查找对应key的时候,只需要通过key索引到对应的桶,然后从桶的首地址对应的节点开始查找,就是链表顺序找到,对比key的值,直到找到对应key的信息,所以,在冲突的时候,特别是冲突率比较高的时候,桶内的链表就会很长,使得查找效率比较低,而在最坏的情况下,所有的key都对应同一个hashvalue,当然这种情况不会出现,这样的哈希函数选取的也没有意义了,假设这种情况出现,那么哈希表就退化成了单链表,其他桶内存浪费,且将查找效率从O(1)直接降到了O(N),所以上面才说,哈希函数的选择也是很关键的。

    下面把完整的一套函数分开讲:

    1、首先是创建我们需要的结构体:

    数据的结构体(也就是我们表中需要存放的数据):

     typedef struct node_s
    {
            int key;    //这个值是我们得到我们的value值的依据,当然也可以能使字符串等,看你的数据类型了;
    
           struct node *next;
    
    }NODE;
    
    hash表的节点:​
    
    typedef struct hash_s
    {
            NODE **list;   //这个就是我们所有的hash桶的首个节点了,我们用它来查找到我们的桶的位置,为什么是**类型呢 ,因为这是地址的地址,例如某个桶 i 的位置*list[i];这样就找到我们的桶了;然后再在桶下面看看有没有我们要查找的NODE节点了
    
    }HASH;
    
    
    

    2、初始化hash表:

    HashTable InitializeTable(int TableSize)
    {
            Hash H;
            int i = 0;
            H = calloc(1, sizeof(HASH));
            if (H ==  NULL)
                    return -1;
    
            H->TableSize = NextPrime();   //就是和TableSize最近的下一个素数;
            H->hlist = calloc(1, sizeof(&NODE) * H->TableSize);
            if (H->hlist == NULL)
                    return -1;
    
            for (i = 0; i < H->TableSize; i ++)     
            {
                    *(H->hlist[i)] = calloc(1, sizeof(NODE));
                    if (*hlist[i] == NULL)
                            return -1;
                    else
                            *(H->hlist[i])->next = NULL;
            }
    }
    
    
    

    3、查找NODE:

    NODE *Find(int key, HASH H)
    {
            NODE *p;
            NODE *list;
    
            list = H->hlist[Hash(key, H->TableSize)];
            p = list->next;
            while(p != NULL && p->key != key)
                    p = p->next;
            return p;
    
    }    //先找到这个桶的头结点list,然后再往后面遍历查找,这时候基本是链表查找操作了;
    
    
    

    4、插入NODE:

    void Insert(int key, HASH H)
    {
            NODE *p;
            NODE *list;
            NODE *tmp;
    
            if (Find(key, H) == NULL)
            {
                    tmp = calloc(1, sizeof(NODE));
                    if (tmp == NULL)
                            return -1;
    
                    list = H->hlist[Hash(key, H->TableSize)];
                    tmp->key = key;
                    tmp->next = list->next;//这里是直接把我们的节点插入到桶的首节点;
                    list->next = tmp;
            }
            return;
    }
    
    
    

    以上基本完成以hash桶​为处理冲突的hash表的实现

    展开全文
  • java中HashMap与Hash表详解

    万次阅读 多人点赞 2018-04-03 09:44:39
    转载至... 哈希算法,是一类算法; 哈希Hash Table)是一种数据结构; 哈希函数,是支撑哈希的一类函数; Map是映射、地图的意思,在Java中Map表示一种把K映...

    转载至https://blog.csdn.net/u010297957/article/details/51974340

    • 哈希算法,是一类算法;

    • 哈希表(Hash Table)是一种数据结构;

    • 哈希函数,是支撑哈希表的一类函数;

    • Map是映射、地图的意思,在Java中Map表示一种把K映射到V的数据类型;

    • HashMap是Java中用哈希数据结构实现的Map




    一、Hash算法

    1. 是什么?

    1. 查词典
      先来看英语翻译:

      hash[hæʃ][hæʃ]
      n. 剁碎的食物;混杂,拼凑;重新表述
      vt. 搞糟,把…弄乱;切碎;推敲
      n. (Hash)人名;(阿拉伯、保、英)哈什;(西)阿什
           
      • 1
      • 2
      • 3
      • 4
      • 5

      我觉得 切碎 最适合,但正式上会被称为“散列 ”。有时候也叫“哈希 ”,据说是因为最早翻译的人以为这是某个叫Hash 的人发明的算法,所以音译了其名字;

      (下面我可能会根据情况混合使用这些词,所以要记得他们是同义词

    2. 所以
      Hash算法 是这样一类算法:

      这类算法接受任意长度的二进制输入值,对输入值做换算(切碎),最终给出固定长度的二进制输出值

      所以注意:Hash算法 不是某个固定的算法,它代表的是一类算法

      以更好理解的方式来说,Hash算法 摘要算法 :也就是说,从不同的输入中,通过一些计算摘取出来一段输出数据,值可以用以区分输入数据

      所以,MD5 可能是最著名的一种Hash算法 了。
      这里写图片描述

    2. 有什么用?

    那么,具体来说Hash/摘要/散列/切碎算法 有哪些用处呢?

    1. 信息安全领域

      Hash算法 可用作加密算法
      文件校验:通过对文件摘要,可以得到文件的“数字指纹”,你下载的任何副本的“数字指纹”只要和官方给出的“数字指纹”一致,那么就可以知道这是未经篡改的。例如著名的MD5

    2. 数据结构领域

      Hash算法 通常还可用作快速查找
      这是今天我想说的部分。根据Hash函数 我们可以实现一种叫做哈希表(Hash Table)的数据结构。这种结构可以实现对数据进行快速的存取。


    接下来我们就来看看Hash算法 的一个重要的应用领域:数据结构 - 哈希表;




    二、哈希表

    1. 什么是哈希表

    首先想一个问题:我们是如何在数据结构中做查找的呢?

    • 线性表、树

      线性表、树 这些结构中,记录 结构 中的相对位置是随机的,和记录的关键字之间不存在确定关系,因此,在结构中查找时需要进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上。在顺序查找时,比较的结果为“=”与“≠”2种可能;在折半查找、二叉排序树查找和B-树查找时,比较的结果为“<”“=”“>”3种可能。查找的效率依赖于查找过程中所进行的比较次数。

    • 哈希表

      理想的情况是希望不经过任何比较,一次存取便能得到所查记录,那就必须在记录的存储位置和它的关键字之间建立一个确定的关系f” role=”presentation”>ff哈希(Hash)函数 ,按这个思想建立的表为哈希表

      (插播:注意“理想情况”这几个字~~ 这会在后文给出解释)

    这是《数据结构(C语言版)》[1]中引出哈希表的一段描述,通俗易懂。所以,我们知道了什么是哈希函数 哈希表

    • 哈希函数

      1. 灵活
        哈希函数是一个映像,因此哈希函数的设定很灵活,只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可。

      2. 冲突
        对不同的关键字可能得到同一哈希地址,即key1&#x2260;key2” role=”presentation”>key1key2key1≠key2 ,这种现象称为冲突(collision);

        冲突只能尽量地少,而不能完全避免。因为,哈希函数是从关键字集合到地址集合的映像。而通常关键字集合比较大,它的元素包括所有可能的关键字,而地址集合的元素仅为哈希表中的地址值。因此,在实现哈希表这种数据结构的时候不仅要设定一个“好”的哈希函数,而且要设定一种处理冲突的方法。

    综上所述,我们可以给出哈希表的定义如下

    根据设定的Hash函数 - H(key)” role=”presentation”>H(key)H(key)和处理冲突的方法,将一组关键字映象 到一个有限的连续的地址集(区间)上,并以关键字在地址集中的作为记录在表中的存储位置,这样的表便称为Hash表

    2. 哈希函数

    上面我们已经引出了并解释了Hash函数 。实际工作中,需要视不同的情况采用不同的Hash函数 ,通常要考虑的因素有:

    • Hash函数 执行的时间;
    • 关键字 的长度;
    • Hash表 的大小;
    • 关键字 的分布情况;
    • 记录 的查找频率;

    有如下一些常用的Hash函数 构造方法:

    1. 直接寻址法:

      f(k)=k” role=”presentation”>f(k)=kf(k)=k

      k k 的某个线性函数为Hash地址

      特点:由于直接地址法相当于有多少个关键字就必须有多少个相应地址去对应,所以不会产生冲突,也正因为此,所以实际中很少使用这种构造方法。

    2. 数字分析法:

      首先分析待存的一组关键字 ,比如是一个班级学生的出生年月日 ,我们发现他们的出生大体相同,那么我们肯定不能用他们的来作为存储地址 ,这样出现冲突 的几率很大;但是,我们发现月日 的具体数字差别很大,如果我们用月日 来作为Hash地址 ,则会明显降低冲突几率。因此,数字分析法就是找出关键字 的规律,尽可能用差异数据来构造Hash地址

      特点:需要提前知道所有可能的关键字,才能分析运用此种方法,所以不太常用。

    3. 平方取中法:

      先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。

      例:我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11,E的内部编码为05,Y的内部编码为25,A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501,同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后,取出第7到第9位作为该关键字哈希地址,如下图所示:

      关键字内部编码内部编码的平方值H(k)关键字的哈希地址
      KEYA11050201122157778355001778
      KYAB11250102126564795010404795
      AKEY01110525001233265775625265
      BKEY02110525004454315775625315

      [2]

      特点:较常用。

    4. 折叠法:

      将关键字分割成位数相同的几部分(最后一部分位数可以不同),然后取这几部分的叠加和(去除进位)作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。

    5. 随机数法:

      选择一个随机函数,取关键字的随机函数值作为Hash地址 ,通常用于关键字长度不同的场合。即
      f(key)=random(key)” role=”presentation”>f(key)=random(key)f(key)=random(key)

      特点:通常,关键字长度不相等时,采用此法构建Hash函数 较为合适。

    6. 除留取余法

      f(k)=k” role=”presentation”>f(k)=kf(k)=k

      取关键字被某个不大于Hash表 m 的数p 除后所得的余数为Hash地址

      特点:这是最简单也是最常用的Hash函数构造方法。可以直接取模,也可以在平法法、折叠法之后再取模。

      值得注意的是,在使用除留取余法 时,对p 的选择很重要,如果p 选的不好会容易产生同义词 。由经验得知:p 最好选择不大于表长m 的一个质数 、或者不包含小于20的质因数的合数。

    3. 处理冲突

    如何处理冲突是哈希造表不可缺少的一个方面。现在完整的描述一下处理冲突

    假设哈希表的地址集为0&#xA0;(n&#x2212;1)” role=”presentation”>0 (n1)0 (n−1)的位置上已存有记录,则“处理冲突”就是为该关键字的记录找到另一个“空”的哈希地址。
    在处理冲突的过程中可能得到一个地址序列Hi,i=1,2,...,k(Hi&#x2208;[0,n&#x2212;1])” role=”presentation”>Hi,i=1,2,...,k(Hi[0,n1])Hi,i=1,2,...,k(Hi∈[0,n−1])为记录在表中的地址。
    (需要注意此定义不太适合链地址法)

    那么,通常有以下4种方法:

    1. 开放定址法:

      Hi=(H(key)+di)modm&#xFF0C;i=1,2,...,k(k&#x2264;m&#x2212;1)” role=”presentation”>Hi=(H(key)+di)modmi=1,2,...,k(km1)Hi=(H(key)+di)modm,i=1,2,...,k(k≤m−1)

      H(key)” role=”presentation”>H(key)H(key) 为哈希表表长;
      di” role=”presentation”>didi 为增量序列,有3种取法:

      1. di=1,2,3,...,m&#x2212;1” role=”presentation”>di=1,2,3,...,m1di=1,2,3,...,m−1,称为线性探测再散列;
      2. di=12,&#x2212;12,22,&#x2212;22,32,...,&#x00B1;k2&#xFF0C;(k&#x2264;m2)” role=”presentation”>di=12,12,22,22,32,...,±k2(km2)di=12,−12,22,−22,32,...,±k2,(k≤m2),称为二次探测再散列;
      3. di=&#x4F2A;&#x968F;&#x673A;&#x6570;&#x5E8F;&#x5217;” role=”presentation”>di=di=伪随机数序列,称为伪随机探测再散列;
    2. 再哈希法:

      Hi=RHi(key),i=1,2,...,k” role=”presentation”>Hi=RHi(key),i=1,2,...,kHi=RHi(key),i=1,2,...,k

      RHi” role=”presentation”>RHiRHi 均是不同的哈希函数,即在同义词产生地址冲突时计算另一个哈希函数地址,直到冲突不再发生,这种方法不易产生聚集 ,但增加了计算时间;

    3. 链地址法

      将所有关键字为同义词的记录存储在同一线性表中。即在Hash 出来的哈希地址中不直接存Key ,而是存储一个Key 链表 ,当发生冲突 时,将同义的Key 加入链表

      这里写图片描述

    4. 公共溢出区:

      可以建立一个公共溢出区,用来存放有冲突的Key 。比如设立另一个哈希表,专门用来存放出现冲突的同义词。

    4. 查找及分析

    在哈希表上进行查找的过程和哈希造表的过程基本是一致的,过程就不累述了。我们需要看一看其查找的长度。

    1. 平均查找长度

      1. 虽然哈希表在关键字与记录的存储位置之间建立了直接映像,但由于“冲突”的存在,使得哈希表的查找过程仍然是一个“给定值和关键字进行比较”的过程。因此,仍需以平均查找长度作为衡量哈希表的查找效率的量度;

        (还记得上面我们说的“理想情况下”吗?~~ 现实告诉我们,一般情况下,还是不得不需要“比较”!)

      2. 查找过程中需要和给定值进行比较的关键字的个数取决于下列三个因素:

        • 哈希函数;
        • 处理冲突的方法;
        • 哈希表的装填因子;
    2. 装填因子

      在一般情况下,我们设计的哈希函数肯定是尽量均匀的,所以可以不考虑它对平均查找长度的影响。那么,处理冲突方法相同的哈希表,其平均查找长度就依赖于哈希表的装填因子了。其定义如下:

      &#x03B1;=&#x8868;&#x4E2D;&#x586B;&#x5165;&#x7684;&#x8BB0;&#x5F55;&#x6570;&#x54C8;&#x5E0C;&#x8868;&#x7684;&#x957F;&#x5EA6;” role=”presentation”>α=α=表中填入的记录数哈希表的长度标志哈希表的装满程度

      直观的看:

      • &#x03B1;” role=”presentation”>αα越小,发生冲突的可能性就越小;
      • &#x03B1;” role=”presentation”>αα越大,代表着表中已填入的元素越多,再填入元素时发生冲突的可能性就越大。那么在查找时,给定值需要比较的关键字的个数就越多;

    结论如下:

    哈希表的平均查找长度是&#x03B1;” role=”presentation”>αα的函数,而不是n的函数。因此,不管n多大,我们总是可以选择一个合适的装填因子以便将平均查找长度限定在一个范围内。(Java中HashMap的默认装填因子是0.75)




    三、数据结构、数据类型

    在看JavaHashMap之前,插播一点重要的数据结构要点

    1. 数据结构(data structure)

    1. 数据结构表达的是:用什么样的结构,组织一类数据。

    2. 分为逻辑结构和物理结构:

      • 基本的逻辑结构有:集合、线性结构、树形结构、图;
      • 物理结构:顺序存储、链式存储;

    2. 数据类型(data type)

    1. 数据类型是和数据结构密切相关的,它是:值的集合和定义在这个值集上的一组操作的总称。

      例如:C语言中的一种数据类型:整型变量,其值集为某个区间上的整数,定义在这些整数上的操作为加、减、乘、除和取模等算数运算。

    2. 高级语言中数据类型分为两类:

      • 原子类型:值不可分解,是什么就是什么。如整型、字符型等;

      • 结构类型:其值是由若干成分按某种结构组成的,因此可分解,并且它的成分可以是原子类型也可以是结构类型。比如数组,其值是由若干分量组成的,每个分量可以是整数,或者也可以是数组。

        • 所以,结构类型可以看成由一种数据结构和定义在其上的一组操作组成
    3. 所以你看,数据结构仅仅代表着一种结构,而我们在编程语言中是使用数据类型,如果编程语言想要实现某种数据结构,那么必须将其封装为一种数据类型,更狭义的说是数据类型中的结构类型。

    3. 深入理解

    也许你还是有些混沌,但是没关系,在哪里跌倒就在哪里睡着嘛~ 我再说点能让你深入理解的…

    1. 实际上,在计算机中,数据类型的概念并非局限于高级语言中,每个处理器[a]都提供了一组原子类型或结构类型。

      • 例如,一个计算机硬件系统通常含有“位”、“字节”、“字”等原子类型,他们的操作通过计算机设计的一套指令系统直接由电路系统完成;

      • 而高级程序语言提供的数据类型,其操作需要通过编译器或解释器转化为底层,即汇编语言或机器语言的数据类型来实现。

    2. 引入“数据类型”的目的,

      • 从硬件角度看,是作为解释计算机内存中信息含义的一种手段,

      • 而对使用数据类型的用户来说,实现了信息的隐蔽,即将一切用户不必了解的细节都封装在类型中。

        • 例如,用户在使用“整数”类型时,既不需要了解“整数”在计算机内部是如何表示的,也不需要知道其操作是如何实现的。
        • 如“两个整数求和”,程序员注重的仅仅是其“数学上求和”的抽象特性,而不是其硬件的“位”操作如何进行。

      ([a]:处理数据的单元,不局限于CPU,包括硬件系统、操作系统、高级语言、数据库等)




    所以,
    在编程语言中运用“数据结构”就是在使用被一层一层封装起来的某种数据类型
    在编程语言中运用“数据结构”就是在使用被一层一层封装起来的某种数据类型
    在编程语言中运用“数据结构”就是在使用被一层一层封装起来的某种数据类型




    四、Java的HashMap

    FAQ:

    1. 为什么要有HashMap

      答:我非常期待能在Java 中使用Hash表 这种数据结构 ,因为它的快速存取特性。

    2. Hash表 HashMap的关系?

      答:Hash表 是一种逻辑数据结构,HashMap是Java中的一种数据类型(结构类型),它通过代码实现了Hash表 这种数据结构,并在此结构上定义了一系列操作。

    3. 这一章节我们要干嘛?

      答:首先要明白我们是在干嘛,我们是在分析一个叫做哈希表的数据结构吗?

      不是!我们是在讨论一种高级程序设计语言中某个数据类型的实现,它实现了哈希表这种数据结构,但它绝不是哈希表本身,它就是它自己 - HashMap类型。

      不明白的话我再说一句:记不记得你学Map(HashMap父接口)时见到的第一句描述“An object that maps keys to values. ”简单翻译就是:Map是一个键值对对象。但是,可没人告诉过你哈希表是键值对结构。

    4. Java中的数据类型

      答:有些话不明白的说出来,其实容易让人想不明白。所以我想说:

      • 实际上,编程语言中数据类型都是层层封装的结果;
      • 实际上,Java 中只有3类数据类型:原生类型(primitive8个)、数组、Object;
      • 实际上,无论官方的集合框架也好,你自己创建的类也好,都只能是源自于Object并依赖于原有的这3类数据类型;
      • 最终,到现在你可能才会发现,“数组”这种类型竟是如此的重要,在Java 中,如果没有数组作为基础结构,你是不可能构造出任何想实现某种数据结构的Object类型的。

    其实有了以上内容,你应该可以轻松的看懂HashMap的源码了,不过我们还是一起来看一下↓


    1. 上帝视角的HashMap

      • HashMap是基于数组来实现哈希表的,数组就好比内存储空间,数组的index就好比内存的地址;

      • HashMap的每个记录就是一个Entry<K, V>对象,数组中存储的就是这些对象;

      • HashMap的哈希函数 = 计算出hashCode + 计算出数组的index

      • HashMap解决冲突:使用链地址法,每个Entry对象都有一个引用next来指向链表的下一个Entry

      • HashMap的装填因子:默认为0.75;

      • 基本上HashMap就像这样:

        这里写图片描述

    2. new HashMap

      /*** 1. 构造方法:最终使用的是这个构造方法 ***/
      // 初始容量initialCapacity为16,装填因子loadFactor为0.75
      public HashMap(int initialCapacity, float loadFactor) {
          if (initialCapacity < 0)
              throw new IllegalArgumentException("Illegal initial capacity: " +
                                                 initialCapacity);
          if (initialCapacity > MAXIMUM_CAPACITY)
              initialCapacity = MAXIMUM_CAPACITY;
          if (loadFactor <= 0 || Float.isNaN(loadFactor))
              throw new IllegalArgumentException("Illegal load factor: " +
                                                 loadFactor);
      
          this.loadFactor = loadFactor;
          threshold = initialCapacity;
          init();//init可以忽略,方法默认为空{},当你需要集成HashMap实现自己的类型时可以重写此方法做一些事
      }
      
      /*** 2. (静态/实例)成员变量 ***/
      /** 默认的容量,容量必须是2的幂 */
      static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
      /** 最大容量2的30次方 */
      static final int MAXIMUM_CAPACITY = 1 << 30;
      /** 默认装填因子0.75 */
      static final float DEFAULT_LOAD_FACTOR = 0.75f;
      /** 默认Entry数组 */
      static final Entry<?,?>[] EMPTY_TABLE = {};
      
      /** Entry数组:table */
      transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
      
      /** table中实际的Entry数量 */
      transient int size;
      
      /** 
       * size到达此门槛后,必须扩容table;
       * 值为capacity * load factor,默认为16 * 0.75 也就是12。
       * 意味着默认情况构造情况下,当你存够12个时,table会第一次扩容
       */
      int threshold;
      
      /** 装填因子,值从一开构造HashMap时就被确定了,默认为0.75 */
      final float loadFactor;
      
      /**
       * 哈希种子,实例化HashMap后在将要使用前设置的随机值,可以使得key的hashCode冲突更难出现
       */
      transient int hashSeed = 0;
      
      /**
       * The number of times this HashMap has been structurally modified
       * Structural modifications are those that change the number of mappings in
       * the HashMap or otherwise modify its internal structure (e.g.,
       * rehash).  This field is used to make iterators on Collection-views of
       * the HashMap fail-fast.  (See ConcurrentModificationException).
       */
      transient int modCount;
      
      /*** 3. Map.Entry<K,V>:数组table中实际存储的类型 ***/
      static class Entry<K,V> implements Map.Entry<K,V> {
          final K key;       // "Key-Value对"的Key
          V value;           // "Key-Value对"的Key
          Entry<K,V> next;    
          int hash;
      
          Entry(int h, K k, V v, Entry<K,V> n) {
              value = v;
              next = n;//链表的下一个Entry
              key = k;
              hash = h;
          }
          public final int hashCode() {
              return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
          }
      }
      
      
           
      • 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
    3. 存 - put(key, value)、解决冲突

      /** 存放 **/
      public V put(K key, V value) {
          if (table == EMPTY_TABLE) {
              inflateTable(threshold);//table会被初始化为长度16,且hashSeed会被赋值;
          }
          if (key == null)
              //HashMap允许key为null:在table中找到null key,然后设置Value,同时其hash为0;
              return putForNullKey(value);
      
          // a). 计算key的hashCode,下面详细说
          int hash = hash(key);
      
          // b). 根据hashCode计算index
          int i = indexFor(hash, table.length);
      
          // c). 做覆盖,遍历index位置的Entry链表,*不是解决*冲突
          for (Entry<K,V> e = table[i]; e != null; e = e.next) {
              Object k;
              if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                  // hashCode和equals都相等则表明:本次put是覆盖操作,下面return了被覆盖的老value
                  V oldValue = e.value;
                  e.value = value;
                  e.recordAccess(this);
                  return oldValue;
              }
          }
      
          modCount++;
          // d). 添加Entry,并解决冲突
          // 如果需要增加table长度(size>threshold)就乘2增加,并重新计算每个元素在新table中的位置和转移
          addEntry(hash, key, value, i);
          return null;//增加成功最后返回null
      }
      
      
      //详细说说上面的a). b). d).
      
      /** a). 为了防止低质量的hash函数,HashMap在这里会重新计算一遍key的hashCode **/
      final int hash(Object k) {
          int h = hashSeed;
          if (0 != h && k instanceof String) {//字符串会被特殊处理,返回32bit的整数(就是int)
              return sun.misc.Hashing.stringHash32((String) k);
          }
      
          h ^= k.hashCode();//将key的hashCode与h按位异或,最后赋值给h
      
          // This function ensures that hashCodes that differ only by
          // constant multiples at each bit position have a bounded
          // number of collisions (approximately 8 at default load factor).
          h ^= (h >>> 20) ^ (h >>> 12);
          return h ^ (h >>> 7) ^ (h >>> 4);
      }
      
      /**
       * b). 计算此hashCode该被放入table的哪个index
       */
      static int indexFor(int h, int length) {
          return h & (length-1);//与table的length - 1按位与,就能保证返回结果在0-length-1内
      }
      
      /**
       * 解决冲突:链地址法
       * d).  addEntry(hash, key, value, i)最终是调用了此函数
       */
      void createEntry(int hash, K key, V value, int bucketIndex) {
          Entry<K,V> e = table[bucketIndex];// index的Entry拿出来
          // put添加新元素是直接new Entry放在链头,如果有老的(有冲突)则将next设置为老的,如果没有正好设置next为null
          table[bucketIndex] = new Entry<>(hash, key, value, e);// 在构造函数中,e代表next
          size++;
      }
           
      • 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
    4. 取 - get(key)

      //其实看完了最精髓的存,取的话就比较简单,就不放代码在这里了,仅说下思路。
      
      // 1. 根据k使用hash(k)重新计算出hashCode
      // 2. 根据indexFor(int h, int length)计算出该k的index
      // 3. 如果该index处Entry的key与此k相等,就返回value,否则继续查看该Entry的next
           
      • 1
      • 2
      • 3
      • 4
      • 5

    HashMap延伸到Object对象

    不知道大家还记得Objectequals()和hashCode()方法吗?(Java - Object类),Object中这样描述道:

    • hashCode():general contract说到:equals的对象必须有相同的哈希码。
    • equals()方法说:覆盖此方法,通常有必要重写hashCode()方法,以维护其general contract;

    就是说要记住下面的话:

    覆盖equals方法通常有必要也覆盖hashCode方法,因为你必须保证对象equals,hashCode必须相等!
    覆盖equals方法通常有必要也覆盖hashCode方法,因为你必须保证对象equals,hashCode必须相等!
    覆盖equals方法通常有必要也覆盖hashCode方法,因为你必须保证对象equals,hashCode必须相等!

    那为什么要保证这个保证呢?学完HashMap我们就知道了原因:

    1. 首先,祖先类Object保证了以上话述

      • 从Objectequals()默认是使用==来判断的;
      • hashCode()native方法,它是直接依赖C来算出的。
    2. 所以,做子孙们的必须要遵循祖制!
      那如果不遵循呢?会造成使用Hash函数的数据类型出现错误!!!,你就用不了哈希表这种数据结构了!!!

    会出什么错?为什么会出错?我们上面看过了HashMap源码,可以容易知道:

    1. 导致错误计算index,覆盖操作失效!

    2. 原因:
      假设你将equals覆盖为name相等即相等(张三等于张三),不过你没覆盖hashCode()

      put(key)操作,由于你的新keyHashMap中原有的老key是两个不同的对象,尽管他们equals,不过由于继承自ObjecthashCode()方法给出了两个不同的hashCode,在根据hashCode计算出index这一步,它们两个属于不同的index

      这直接导致本该是一次覆盖的操作,却做成了新增了一个值的操作!

    所以,要避免出现这个问题,就必须在改写equals()的同时改写hashCode(),以保证对象equals则HashCode一致
    你可以看到官方提供的这些API类中,如果它需要覆盖equals()那么在同时也都覆盖了hashCode(),我们写class时也要这样。


    完。



    参考文献:
    [1] 严蔚敏,吴伟民.数据结构(C语言版).北京:清华大学出版社,2007

    [2] 哈希表及处理冲突的方法.新浪微博.2011-10-10

    展开全文
  • Hash表的存储结构

    千次阅读 2018-11-14 22:44:54
     * 1、底层数据结构:哈希  * 2、存储,拿取都比较快  * 3、 线程不安全,运行速度快 代码实现如下: package itcast.demo1; import java.util.HashSet; /* * HashSet集合的自身特点: * 底层数据...
  • Hash 的时间复杂度为什么是 O(1)(面试版)

    千次阅读 多人点赞 2020-04-14 14:22:26
    要了解 Hash ,需要先从数组说起。 数组 数组是最常用的数据结构,创建数组必须要内存中一块连续的空间,并且数组中必须存放相同的数据类型。比如我们创建一个长度为 10,数据类型为整型的数组,在内存中的地址是...
  • linux c实现通用hash表

    千次阅读 2018-06-10 12:18:35
    此博客只有代码,hash表概念等,请自行学习。此次hash中使用链表为本人所写。后续改写此hash表,使用内核链表,详情请查看下一个博客。 代码块 common.h: #pragma once #ifndef _COMMON_H_ #define _COMMON_...
  • hash表hash表平均查找长度(ASL)

    千次阅读 2019-08-28 14:00:41
      hash 在处理 collision 的时候有很多种方式,比如 线性探测(linear probing)、二次探测(quadratic probing)、开链法(seperate chaning) 等。   本文记录使用开链法的情况下,Hash 查找成功和查找不...
  • Hash表分析以及Java实现

    千次阅读 2016-06-23 23:28:35
    这篇博客主要探讨Hash表中的一些原理/概念,及根据这些原理/概念,自己设计一个用来存放/查找数据的Hash表,并且与JDK中的HashMap类进行比较。 我们分一下七个步骤来进行。  一。 Hash表概念 二 . Hash构造函数...
  • 一个 object 是可哈希的(hashable),是指这个 object 在其生存期内有一个不变的哈希值(hash value),也就是说同一个object用hash(object)计算出来的值是一样的, 如list 对象,改变了一个元素值之后,同一个list...
  • hash表底层实现的原理

    千次阅读 2019-06-01 15:11:31
  • linux内核 hash表的基本使用

    千次阅读 2018-11-13 15:24:18
    栗子如下: #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; #include "hlist.h" typedef struct list_test{ ...//计算hash值 stru...
  • hash表与数组

    千次阅读 2018-12-12 12:29:17
    hash表 hash表的查找/插入/删除的时间复杂度均为o(1), (因为hash表本身是一个数组,查找o(1), 而插入/删除时,根据hash值直接插入/删除) 数组的插入/删除需要移动元素,送、so,,,,,,,,其时间复杂度为O(n), ...
  • hash表建立,查找,详解

    万次阅读 2017-03-22 11:38:01
    散列表(Hash table,也叫哈希),是根据关键字(Key value)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到中一个位置来访问记录,这加快了查找速度。...
  • 所有的键值对都在hash表的第一项中,冲突键使用单链表连接起来了,具体是在插入新字符串键时先查找已有hash表中是否存在,如果键相等再比较字符串是否相等,见下: node* lookup( char *n){ unsigned int ...
  • 反向页表(基于hash表

    千次阅读 2019-11-10 10:35:08
    但是当物理内存特别大的时候,这个表也就很大了,访问一个地址可能需要遍历整个表(因为是按照物理地址建立的,所以要挨个访问、判断),那么有什么方法是可以缓减访问速度的压力吗,那就是基于hash表的访问 ...
  • hash表装载因子(load factor)的计算

    千次阅读 2020-01-07 21:20:49
    今有表长为10的hash表,里面包含7个元素,所以它的装载因子为: 7 / 10 = 0.7 装载因子的计算结果请注意使用小数表示。 ...
  • 字典与hash表

    千次阅读 2018-05-25 09:31:51
    ---》 存储位置=hash(键)在查找时,首先对键进行hash运算,把求得的值当做“键-值对”的存储位置,在结构中按照此位置取“键-值对”进行比较,若键相等,则表示搜索成功。在存储“键-值对”的时候,依照相同的hash...
  • c/c++ hash表 (哈希表、字典表)

    万次阅读 多人点赞 2018-01-30 10:10:05
    1: : 存储数据 key –> value; 2: 存储数据结构的困难: 怎么查找? 一个一个key去比较去查找?==效率不高 **3: Hash算法加快查找; 将字符串的key,转成整数,使用整数找到对应的value;** Hash...
  • Hash表的时间复杂度为什么是O(1)?

    千次阅读 2020-05-08 11:59:34
    hash表的时间复杂度】hash表的时间复杂度为什么是O(1)?能回答这个问题的答案之前,肯定必须先了解hash表的数据结构。如下图所示: 如图中清晰可知,hash表是基于数组+链表的实现的。数组在内存中是一块连续的...
  • HASH表的实现(拉链法)

    千次阅读 2018-07-07 19:02:30
    HASH表的实现(拉链法) 本文的一些基本概念参考了一部分百度百科,当然只保留了最有价值的部分,代码部分完全是自己实现!简介哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据...
  • redis如何批量更新HASH表value值? 不使用Java代码的情况下,单纯利用redis自身功能, 如何实现批量更新HASH表value值? 请教各位老师,谢谢。
  • Linux内核早就把HASH路由表去掉了,现在就只剩下TRIE了,不过我还是希望就这两种数据结构展开一些形而上的讨论。1.hash和trie/radixhash和tire其实是可以统一在一起的。具有相同hash值的多个项具有一个共同的特征,...
  • redis 学习笔记--hash表的渐进式rehash

    千次阅读 2018-07-02 18:41:33
    关于hash表,前面有文章介绍过,其原理并不难。 redis的数据库使用字典来作为底层实现的,对数据库的增删查改操作也是构建在对字典的操作之上。redis的字典使用hash表作为底层实现。 redis作为一个广泛使用的内存...
  • 数据结构与算法分析——Hash表

    千次阅读 2017-10-13 15:58:33
    Hash表  Hash表也称散列表,也有直接译作哈希表,Hash表是一种特殊的数据结构,它同数组、链表以及二叉排序树等相比较有很明显的区别,它能够快速定位到想要查找的记录,而不是与表中存在的记录的关键字进行比较来...
  • 溢出hash表

    千次阅读 2013-09-18 13:45:35
    溢出hash表设计图 来源:朱翔 [点击放大] 介绍溢出哈希表的实现机理,并给出具体实现代码。溢出哈希表是在hash 表填入过程中,将冲突的元素顺序填入到溢出表中,而当查找过程中发现冲突时,就在溢出表中进行顺序...
  • spring 批量获取redis hash表中的键值对

    千次阅读 2019-09-19 16:15:42
    String pattern="TEST" Map<String, Object> resMap=Maps.newHashMap(); BoundHashOperations<String, String, String> boundHashOps = redisTemplate.boundHashOps(pattern); try (Cursor<...
  • 哈希Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到中一个位置来访问记录,以加快查找的速度。具体的介绍网上有很详细的描述,如闲聊哈希...
  • 十一、从头到尾解析Hash表算法

    万次阅读 多人点赞 2011-03-17 15:40:00
    十一、从头到尾彻底解析Hash 表算法作者:July、wuliming、pkuoliver 出处:...第二部分为关于Hash表算法的详细阐述;第三部分为打造一个最快的Hash表算法。------------------------------------ 第
  • 从头到尾彻底解析Hash表算法

    千次阅读 2016-11-10 14:21:18
     而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位(文章第二、三部分,会针对Hash表详细阐述)。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,021,447
精华内容 408,578
关键字:

hash表