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

    2018-01-04 18:19:35
    Hash表也称散列表,也有直接译作哈希表,Hash表是一种特殊的数据结构,它同数组、链表以及二叉排序树等相比较有很明显的区别,它能够快速定位到想要查找的记录,而不是与表中存在的记录的关键字进行比较来进行查找。...

    Hash表也称散列表,也有直接译作哈希表,Hash表是一种特殊的数据结构,它同数组、链表以及二叉排序树等相比较有很明显的区别,它能够快速定位到想要查找的记录,而不是与表中存在的记录的关键字进行比较来进行查找。这个源于Hash表设计的特殊性,它采用了函数映射的思想将记录的存储位置与记录的关键字关联起来,从而能够很快速地进行查找。

    1.Hash表的设计思想

      对于一般的线性表,比如链表,如果要存储联系人信息: 

    张三 13980593357
    李四 15828662334
    王五 13409821234
    张帅 13890583472

      那么可能会设计一个结构体包含姓名,手机号码这些信息,然后把4个联系人的信息存到一张链表中。当要查找”李四 15828662334“这条记录是否在这张链表中或者想要得到李四的手机号码时,可能会从链表的头结点开始遍历,依次将每个结点中的姓名同”李四“进行比较,直到查找成功或者失败为止,这种做法的时间复杂度为O(n)。即使采用二叉排序树进行存储,也最多为O(logn)。假设能够通过”李四“这个信息直接获取到该记录在表中的存储位置,就能省掉中间关键字比较的这个环节,复杂度直接降到O(1)。Hash表就能够达到这样的效果。

      Hash表采用一个映射函数 f : key —> address 将关键字映射到该记录在表中的存储位置,从而在想要查找该记录时,可以直接根据关键字和映射关系计算出该记录在表中的存储位置,通常情况下,这种映射关系称作为Hash函数,而通过Hash函数和关键字计算出来的存储位置(注意这里的存储位置只是表中的存储位置,并不是实际的物理地址)称作为Hash地址。比如上述例子中,假如联系人信息采用Hash表存储,则当想要找到“李四”的信息时,直接根据“李四”和Hash函数计算出Hash地址即可。下面讨论一下Hash表设计中的几个关键问题。

    1. Hash函数的设计

      Hash函数设计的好坏直接影响到对Hash表的操作效率。下面举例说明:

      假如对上述的联系人信息进行存储时,采用的Hash函数为:姓名的每个字的拼音开头大写字母的ASCII码之和。

      因此address(张三)=ASCII(Z)+ASCII(S)=90+83=173;

        address(李四)=ASCII(L)+ASCII(S)=76+83=159;

        address(王五)=ASCII(W)+ASCII(W)=87+87=174;

        address(张帅)=ASCII(Z)+ASCII(S)=90+83=173;

      假如只有这4个联系人信息需要进行存储,这个Hash函数设计的很糟糕。首先,它浪费了大量的存储空间,假如采用char型数组存储联系人信息的话,则至少需要开辟174*12字节的空间,空间利用率只有4/174,不到5%;另外,根据Hash函数计算结果之后,address(张三)和address(李四)具有相同的地址,这种现象称作冲突,对于174个存储空间中只需要存储4条记录就发生了冲突,这样的Hash函数设计是很不合理的。所以在构造Hash函数时应尽量考虑关键字的分布特点来设计函数使得Hash地址随机均匀地分布在整个地址空间当中。通常有以下几种构造Hash函数的方法:

      1)直接定址法

      取关键字或者关键字的某个线性函数为Hash地址,即address(key)=a*key+b;如知道学生的学号从2000开始,最大为4000,则可以将address(key)=key-2000作为Hash地址。

      2)平方取中法

      对关键字进行平方运算,然后取结果的中间几位作为Hash地址。假如有以下关键字序列{421,423,436},平方之后的结果为{177241,178929,190096},那么可以取{72,89,00}作为Hash地址。

      3)折叠法

      将关键字拆分成几部分,然后将这几部分组合在一起,以特定的方式进行转化形成Hash地址。假如知道图书的ISBN号为8903-241-23,可以将address(key)=89+03+24+12+3作为Hash地址。

      4)除留取余法

      如果知道Hash表的最大长度为m,可以取不大于m的最大质数p,然后对关键字进行取余运算,address(key)=key%p。

      在这里p的选取非常关键,p选择的好的话,能够最大程度地减少冲突,p一般取不大于m的最大质数。

    2.Hash表大小的确定

      Hash表大小的确定也非常关键,如果Hash表的空间远远大于最后实际存储的记录个数,则造成了很大的空间浪费,如果选取小了的话,则容易造成冲突。在实际情况中,一般需要根据最终记录存储个数和关键字的分布特点来确定Hash表的大小。还有一种情况时可能事先不知道最终需要存储的记录个数,则需要动态维护Hash表的容量,此时可能需要重新计算Hash地址。

    3.冲突的解决

      在上述例子中,发生了冲突现象,因此需要办法来解决,否则记录无法进行正确的存储。通常情况下有2种解决办法:

      1)开放定址法

      即当一个关键字和另一个关键字发生冲突时,使用某种探测技术在Hash表中形成一个探测序列,然后沿着这个探测序列依次查找下去,当碰到一个空的单元时,则插入其中。比较常用的探测方法有线性探测法,比如有一组关键字{12,13,25,23,38,34,6,84,91},Hash表长为14,Hash函数为address(key)=key%11,当插入12,13,25时可以直接插入,而当插入23时,地址1被占用了,因此沿着地址1依次往下探测(探测步长可以根据情况而定),直到探测到地址4,发现为空,则将23插入其中。

      2)链地址法

       采用数组和链表相结合的办法,将Hash地址相同的记录存储在一张线性表中,而每张表的表头的序号即为计算得到的Hash地址。如上述例子中,采用链地址法形成的Hash表存储表示为:   

       虽然能够采用一些办法去减少冲突,但是冲突是无法完全避免的。因此需要根据实际情况选取解决冲突的办法。

    4.Hash表的平均查找长度

      Hash表的平均查找长度包括查找成功时的平均查找长度和查找失败时的平均查找长度。

      查找成功时的平均查找长度=表中每个元素查找成功时的比较次数之和/表中元素个数;

      查找不成功时的平均查找长度相当于在表中查找元素不成功时的平均比较次数,可以理解为向表中插入某个元素,该元素在每个位置都有可能,然后计算出在每个位置能够插入时需要比较的次数,再除以表长即为查找不成功时的平均查找长度。

      下面举个例子:

      有一组关键字{23,12,14,2,3,5},表长为14,Hash函数为key%11,则关键字在表中的存储如下:

      地址     0     1     2     3      4     5    6   7   8    9  10   11   12    13

      关键字        23    12   14     2     3    5

     比较次数         1      2    1     3     3     2

      因此查找成功时的平均查找长度为(1+2+1+3+3+2)/6=11/6;

      查找失败时的平均查找长度为(1+7+6+5+4+3+2+1+1+1+1+1+1+1)/14=38/14;

      这里有一个概念装填因子=表中的记录数/哈希表的长度,如果装填因子越小,表明表中还有很多的空单元,则发生冲突的可能性越小;而装填因子越大,则发生冲突的可能性就越大,在查找时所耗费的时间就越多。因此,Hash表的平均查找长度和装填因子有关。有相关文献证明当装填因子在0.5左右的时候,Hash的性能能够达到最优。因此,一般情况下,装填因子取经验值0.5。

    5.Hash表的优缺点

      Hash表存在的优点显而易见,能够在常数级的时间复杂度上进行查找,并且插入数据和删除数据比较容易。但是它也有某些缺点,比如不支持排序,一般比用线性表存储需要更多的空间,并且记录的关键字不能重复。

     

    代码实现:

    复制代码
    /*Hash表,采用数组实现,2012.9.28*/ 
    
    #include<stdio.h>
    #define DataType int
    #define M 30
     
    typedef struct HashNode    
    {
        DataType data;    //存储值 
        int isNull;           //标志该位置是否已被填充 
    }HashTable;
    
    HashTable hashTable[M];
    
    void initHashTable()     //对hash表进行初始化 
    {
        int i;
        for(i = 0; i<M; i++)
        {
            hashTable[i].isNull = 1;    //初始状态为空 
        }
    }
    
    int getHashAddress(DataType key)    //Hash函数 
    {
        return key % 29;     //Hash函数为 key%29 
    }
    
    int insert(DataType key)    //向hash表中插入元素 
    {
        int address = getHashAddress(key);       
        if(hashTable[address].isNull == 1)  //没有发生冲突 
        {
            hashTable[address].data = key;
            hashTable[address].isNull = 0;
        }
        else    //当发生冲突的时候 
        {
            while(hashTable[address].isNull == 0 && address<M)
            {
                address++;     //采用线性探测法,步长为1 
            }
            if(address == M)    //Hash表发生溢出 
                return -1;
            hashTable[address].data = key;
            hashTable[address].isNull = 0;
        }
        return 0;
    }
    
    int find(DataType key)      //进行查找 
    {
        int address = getHashAddress(key);
        while( !(hashTable[address].isNull == 0 && hashTable[address].data == key && address<M))
        {
            address++;
        } 
        if( address == M)
            address = -1;
        return address;
    }
    
    
    int main(int argc, char *argv[])
    {
        int key[]={123,456,7000,8,1,13,11,555,425,393,212,546,2,99,196};
        int i;
        initHashTable();
        for(i = 0; i<15; i++)
        {
            insert(key[i]);
        }
        
        for(i = 0; i<15; i++)
        {
            int address;
            address = find(key[i]);
            printf("%d %d\n", key[i],address);
        }
        return 0;
    }
    
    
    
    
    作者:海子
            
    本博客中未标明转载的文章归作者海子和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
    展开全文
  • 数据结构 Hash表(哈希表)

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

    参考链接:数据结构(严蔚敏)

    一、什么是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表建立如下

    index key 年龄 人数(假设数据)
    0 2018 0-10 200W
    1 2008 10-20 250W
    2 1998 20-30 253W
    3 1988 30-40 300W
    ……

    数字分析法
    假设关键字集合中的每个关键字key都是由s位数字组成(k1,k2,,knk_1,k_2,……,k_n),分析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 那么存储如下

    index 0 1 2 3 4 5 6 7 8
    key 7 21(冲突后移) 24 4 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存储位置Hi=(H(key)+di)MODmH_i=(H(key)+d_i)MOD mm为表长
    did_i有三种取法
    1)线性探测再散列
    di=cid_i=c*i
    2)平方探测再散列
    di=12,12,22,22d_i=1^2,-1^2,2^2,-2^2……
    3)随机探测在散列(双探测再散列)
    did_i是一组伪随机数列
    注意
    增量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,即冲突后存储在冲突后一个位置,如果仍然冲突继续向后

    index 0 1 2 3 4 5 6 7 8 9 10
    key 55 1 14 19 86
    23冲突 23
    68冲突 68冲突 68
    11冲突 11冲突 11冲突 11冲突 11冲突 11
    37冲突 37冲突 37
    最终存储结果 55 1 23 14 68 11 37 19 86
    **平方探测再散列**
    index 0 1 2 3 4 5 6 7 8 9 10
    key 55 1 14 37 19 86
    23冲突 H(23)+1
    H(68)-1冲突 68冲突 H(68)+1冲突 H(68)+4
    11冲突 H(11)+1冲突 H(11)-1
    最终存储结果 55 1 23 14 37 68 19 86 11
    **随机探测在散列(双探测再散列)** 发生冲突后 H(key)‘=(H(key)+di)MOD m 在该例子中 H(key)=key MOD 11 我们取di=key MOD 10 +1 则有如下结果:
    index 0 1 2 3 4 5 6 7 8 9 10
    key 55 1 68 14 19 86
    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冲突
    最终存储结果 55 1 68 14 23 11 37 19 86

    链地址法

    产生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链表

    千次阅读 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表

    2011-04-13 22:55:00
    hash表

     

    hash


             hash 表是使用 O(1) 时间进行数据的插入删除和查找,但是 hash 表不保证表中数据的有序性,这样在 hash 表中查找最大数据或者最小数据的时间是 O(N)


    1 寻址和 hash 函数

             理想状态下 hash 足够大,每一数据保存在一个 hash 存储单元内,这样对于插入删除和查找某一个数据就可以直接得到。但是现实情况下 hash 表不可能无限大,而且理论上保存的数据的个数是没有限制的,这样保存的数据的数量就远远大于 hash 表的存储单元的数量。

             为了实现在 O(1) 内对数据进行插入删除和查找,就必须将一个数据映射到 hash 表中的固定位置,这个映射函数就是 hash 函数。 Hash 函数通过对数据进行计算得到一个在 hash 表中的位置地址。


    图 1.1 理想的 hash 表

             要选择较好的 hash 函数,以及 hash 表存储单元的数量,这样才能使保存在 hash 表中的数据均匀分布。

             理想状态不太可能实现,由于存储的数据数量远远大于 hash 表存储单元的数量,所以再好的 hash 函数也可能使不同的数据得到相同的映射位置,这就造成了冲突。但是好的 hash 函数可以将这种冲突降到最低。

    2 分离链接

             解决这种冲突的第一种方法是借助链表来实现,就是将数据实际存放在与 hash 表存储单元相链接的链表中,而不是 hash 的存储单元中。


    图 2.1 分离链表

             当产生冲突的时候,将两个数据都链接在同一 hash 存储单元保存的链表中。当一个存储单元保存的链表中有多个数据的时候,对于链表后面的数据的查找添加和删除就是不是严格意义上的 O(1) 了。一个好的 hash 函数可以使得这个链表很短。最坏情况下,当所有的数据都保存在一个 hash 单元指定的链表中的时候,那么这个 hash 就和链表一样了。


    3 开放地址

             使用开放地址方法解决冲突的时候,数据仍然保存在 hash 表的存储单元中,但是当冲突发生的时候,要再次计算新的地址。

             常用的开放地址法是线性探查,就是当对一个数据进行插入删除或者查找的时候,通过 hash 函数计算,发现这个位置不是要找的数据,这时候就检查下一个存储单元,一直找到要操作的数据为止。

             除了线性探查外还有二次探查,再 hash 等等方法,都是当一次计算得到的位置不是要找到的数据的时候,怎样再次确定新的位置。


    4 完全 hash

             采用分离链表的方式解决冲突的时候,当多个数据被映射到一个地址的时候,它们就形成了一个链表,要操作这其中的一个数据,那么就必须在这个链表中进行操作。如果 hash 函数选择的好的话,链表会很短,这样的操作近似 O(1) ,但并不是精确的等于 O(1) ,它与链表的长度有关。对于数据的访问的最坏情况的访问也是 O(1) 的 hash 叫做完全 hash 表。

             这样的 hash 表是一个两级的 hash 表,第一级的 hash 与使用分离链接方法的 hash 一样,但是 hash 存储单元中指向的不是一个链表,而是另一个 hash 表。


    图 4.1 完全 hash 表

             要小心的选择一级以及二级的 hash 函数可以完全保证在二级 hash 表中不会出现冲突。


    展开全文
  • hash链表

    千次阅读 2014-03-23 19:29:32
    hash链表是hash表和链表的结合,使用比较方便。 hash链表实现 本文的hash链表实现:hash头部用单链表、其他的hash节点用双向链表。实现主要取自Linux内核实现,本文做了移植。本文代码可从...
  • C++ Hash表模板

    千次阅读 2018-03-27 14:39:37
    1.简介 利用C++类模板实现任意类型的Hash表,提供的功能有: (1)指定shmkey或内存地址创建Hash表; (2)获取指定key元素; (3)遍历指定范围的元素,进行指定...缺点:该hash表模板未实现动态扩展,hash表容...
  • hash表hash表平均查找长度(ASL)

    千次阅读 2019-08-28 14:00:41
      hash 在处理 collision 的时候有很多种方式,比如 线性探测(linear probing)、二次探测(quadratic probing)、开链法(seperate chaning) 等。   本文记录使用开链法的情况下,Hash 查找成功和查找不...
  • Hash表、Hash函数和HashCode ** Hash函数和Hash表: Hash函数就是根据key计算出应该存储的位置,而Hash表则是基于Hash函数建立的一种查找表。给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能...
  • 十一、从头到尾解析Hash表算法

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

    2017-07-07 19:30:51
    Hash表通过Hash函数将关键字映射到该记录在表中的存储位置(注意这里的存储位置只是表中的存储位置,并不是实际的物理地址,称作为Hash地址)。  由于很容易产生冲突(不同的键值,经过Hash函数计算后Hash值是一样的...
  • Hash表和Hash冲突

    2016-06-24 21:24:07
    Hash表和Hash冲突Hash表中的元素存储地址是通过Hash函数计算出来的,当要取出指定元素的时候,直接通过Hash函数计算出元素的存储地址。有时候会出现KEY不同,但是通过Hash函数计算出来的值相同,这个值相同意味着这...
  • Hash表技术:线性hash表

    千次阅读 2012-10-08 09:07:19
    1. Hash表技术的基本思想是:对被查元素的关键字做某种运算后直接确定所要查找项目在表中位置。 2.线性Hash表类:Linear_hash.h #include using namespace std; //线性hash表结点类型 template struct ...
  • python hash表

    千次阅读 2018-04-19 17:12:51
    在查找过程中不经过关键字的比较. 在待查的关键字值和它的存储位置之间建立一个确定的对应关系,则查找时不必再进行关键字值...python内部的字典数据类型就是hash表实现的. 哈希函数方法: 1.直接定址法 H(key)=ke...
  • hash表与数组

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

    千次阅读 2016-04-28 11:18:21
    1、什么是哈希表?  哈希表(Hash table,也叫散列表),是根据key而直接进行访问的数据结构。也就是说,它通过把key映射到表中一个位置来访问记录,以加快查找的速度。... ② Hash表出现的目的:加快查找的速

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,574
精华内容 13,029
关键字:

hash表