哈希表详解 - V2EX
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
请不要在回答技术问题时复制粘贴 AI 生成的内容
bigshot
V2EX    程序员

哈希表详解

  •  
  •   bigshot 2018-02-28 21:20:46 +08:00 2298 次点击
    这是一个创建于 2789 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    顺序搜索以及二叉树搜索树中,元素存储位置和元素各关键码之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。搜索的效率取决于搜索过程中元素的比较次数。

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

    当向该结构中: 插入元素时:根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放 搜索元素时:对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功 该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者 称散列表) 例如:数据集合{180,750,600,430,541,900,460} 这里写图片描述 用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快 问题:按照上述哈希方式,向集合中插入元素 443,会出现什么问题? 这回就要引出一个概念叫哈希冲突:对于两个数据元素的关键字 和 ( i !=j ),有 != ,但有:HashFun(Ki) == HashFun(Kj)即不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

    解决哈希冲突两种常见的方法是:闭散列和开散列 闭散列: 闭散列:也叫开放地址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把 key 存放到表中“下一个” 空位中去 那如何寻找下一个空余位置? 这里就要用到两种方法:线性探测和二次探测 线性探测 设关键码集合为{37, 25, 14, 36, 49, 68, 57, 11},散列表为 HT[12],表的大小 m = 12,假设哈希函数为:Hash(x) = x %p ( p = 11,是最接近 m 的质数),就有: Hash(37) = 4 Hash(25) = 3 Hash(14) = 3 Hash(36) = 3 Hash(49) = 5 Hash(68) = 2 Hash(57) = 2 Hash(11) = 0 其中 25,14,36 以及 68,57 发生哈希冲突,一旦冲突必须要找出下一个空余位置 线性探测找的处理为:从发生冲突的位置开始,依次继续向后探测,直到找到空位置为止 [插入] 1 ). 使用哈希函数找到待插入元素在哈希表中的位置 2 ). 如果该位置中没有元素则直接插入新元素;如果该位置中有元素且和待插入元素相同,则不用插入;如果该位置中有元素但不是待插入元素则发生哈希冲突,使用线性探测找到下一个空位置,插入新元素; 采用线性探测,实现起来非常简单,缺陷是: 一旦发生哈希冲突,所有的冲突连在一起,容易产生数据“堆积”,即:不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要许多次比较,导致搜索效率降低。 如何缓解呢? 引入新概念负载因子(负载因子的应用在下一篇博文)和二次探测 负载因子 二次探测 发生哈希冲突时,二次探查法在表中寻找“下一个”空位置的公式为: Hi= (Ho + i^2) % m,Hi = (Ho -i^2 ) % m, i = 1,2,3 …,(m-1)/Ho. 是通过散列函数 Hash(x)对元素的关键码 key 进行计算得到的位置,m 是表的大小假设数组的关键码为 37, 25, 14, 36, 49, 68, 57, 11,取 m = 19,这样可设定为 HT[19],采用散列函数 Hash(x) = x % 19,则: Hash(37)=18 Hash(25)=6 Hash(14)=14 Hash(36)=17 Hash(49)=11 Hash(68)=11 Hash(57)=0 Hash(11)=11 采用二次探测处理哈希冲突: 二次探测 研究表明:当表的长度为质数且表装载因子 a 不超过 0.5 时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子 a 不超过 0.5 ;如果超出必须考虑增容

    开散列法又叫链地址法(开链法)。(将在下一篇博文中写出) 开散列法:首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。

    设元素的关键码为 37, 25, 14, 36, 49, 68, 57, 11, 散列表为 HT[12],表的大小为 12,散列函数为 Hash(x) = x % 11 Hash(37)=4 Hash(25)=3 Hash(14)=3 Hash(36)=3 Hash(49)=5 Hash(68)=2 Hash(57)=2 Hash(11)=0 使用哈希函数计算出每个元素所在的桶号,同一个桶的链表中存放哈希冲突的元素。 开散列 通常,每个桶对应的链表结点都很少,将 n 个关键码通过某一个散列函数,存放到散列表中的 m 个桶中,那么每一个桶中链表的平均长度为。以搜索平均长度为的链表代替了搜索长度为 n 的顺序表,搜索效率快的多。 应用链地址法处理溢出,需要增设链接指针,似乎增加了存储开销。事实上: 由于开地址法必须保持大量的空闲空间以确保搜索效率,如二次探查法要求装载因子 a <= 0.7,而表项所占空间又比指针大的多,所以使用链地址法反而比开地址法节省存储空间。

    引起哈希冲突的一个原因可能是:哈希函数设计不够合理。 哈希函数设计原则: **.**哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有 m 个地址时,其值域必须在 0 到 m-1 之间 **.**哈希函数计算出来的地址能均匀分布在整个空间中 **.**哈希函数应该比较简单 下面简单介绍了一些哈希函数: 1.直接定址法 取关键字的某个线性函数为散列地址:Hash ( Key )= A*Key + B 优点:简单、均匀 缺点:需要事先知道关键字的分布情况 适合查找比较小且连续的情况 2.除留余数法 设散列表中允许的地址数为 m,取一个不大于 m,但最接近或者等于 m 的质数 p 作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址 3.平方取中法 假设关键字为 1234,对它平方就是 1522756,抽取中间的 3 位 227 作为哈希地址; 再比如关键字为 4321,对它平方就是 18671041,抽取中间的 3 位 671(或 710)作为哈希地址 平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况 4.折叠法 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况 5.随机数法 选择一个随机函数,取关键字的随机函数值为它的哈希地址,即 H(key) = random(key),其中 random 为随机数函数通常应用于关键字长度不等时采用此法 6.数学分析法 设有 n 个 d 位数,每一位可能有 r 种不同的符号,这 r 种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。 例如:假设要存储某家公司员工登记表,如果用手机号作为关键字,那么极有可能前 7 位都是 相同的,那么我们可以选择后面的四位作为散列地址,如果这样的抽取工作还容易出现 冲突,还可以对抽取出来的数字进行反转(如 1234 改成 4321)、右环位移(如 1234 改成 4123)、左环移位、前两数与后两数叠加(如 1234 改成 12+34=46)等方法 说了这么多概念,来看看代码。 哈希表的结构定义:

    typedef int KeyType; typedef int ValueType; typedef enum Status { EMPTY, EXIST, DELETE, }Status; typedef struct HashNode { KeyType _key; ValueType _value; Status _status; }HashNode; typedef struct HashTable { HashNode *_table; size_t _size; size_t _N; }HashTable; 

    哈希表的初始化:

    void HashTableInit(HashTable* ht) //初始化 { size_t i = 0; assert(ht); ht->_size = 0; ht->_N = HashTablePrime(0); ht->_table = (HashNode *)malloc(sizeof(HashNode)*ht->_N); assert(ht->_table); for (i=0; i<ht->_N; i++) ht->_table[i]._status = EMPTY; } 

    哈希函数:

    KeyType HashFunc(KeyType key,size_t n) { return key%n; } 

    看看哈希表的插入:(这里处理哈希冲突时采用线性探测,二次探测将在下一次博客中写出) 扩容时要特别注意,不能简单的用 malloc 和 realloc 开出空间后直接付给哈希表,一定记得扩容之后需要重新映射原表的所有值。

    int HashTableInsert(HashTable* ht, KeyType key, ValueType value) //插入 { KeyType index = key; assert(ht); **if (ht->_N == ht->_size) //扩容 { KeyType index; size_t newN = HashTablePrime(ht->_N); HashNode *tmp = (HashNode *)malloc(sizeof(HashNode)*newN); size_t i = 0; assert(tmp); //HashTablePrint(ht); //扩容调试使用 for (i=0; i<newN; i++) tmp[i]._status = EMPTY; for (i=0; i<ht->_N; i++) //扩容之后把以前的表中元素重新映射 { if (ht->_table[i]._status == EXIST) //原表存在时 { index = HashFunc(ht->_table[i]._key,newN); if (tmp[index]._status == EXIST) //发生哈希冲突时 { while (1) { index +=1; if ((size_t)index > newN) index %= newN; if (tmp[index]._status != EXIST) break; } } tmp[index]._key = ht->_table[i]._key; tmp[index]._value = ht->_table[i]._value; tmp[index]._status = EXIST; } else tmp[i]._status = ht->_table[i]._status; } ht->_table = tmp; ht->_N = newN; }** index = HashFunc(key,ht->_N); if (ht->_table[index]._status == EXIST) //发生哈希冲突 { size_t i = 0; for (i=0; i<ht->_N;i++ ) { if (ht->_table[index]._key == key) return -1; index +=i; if ((size_t)index >ht->_N) index %= ht->_N; if (ht->_table[index]._status != EXIST) break; } } ht->_table[index]._key = key; ht->_table[index]._value = value; ht->_table[index]._status = EXIST; ht->_size++; return 0; } 

    哈希表的查找:

    HashNode* HashTableFind(HashTable* ht, KeyType key) //查找 { size_t i = 0; KeyType index = key; assert(ht); index = HashFunc(key,ht->_N); if (ht->_table[index]._key == key) return ∓(ht->_table[index]); else { for (i=0; i<ht->_N; i++) { index += i; if (ht->_table[index]._key == key) return &(ht->_table[index]); if (ht->_table[index]._status == EMPTY) return NULL; } } return NULL; } 

    哈希表的删除:

    int HashTableRemove(HashTable* ht, KeyType key) //删除 { assert(ht); if(HashTableFind(ht,key)) { HashTableFind(ht,key)->_status = DELETE; return 0; } else return -1; } 

    哈希表的销毁:(使用了 malloc 开辟空间必须手动销毁)

    void HashTableDestory(HashTable* ht)//销毁 { free(ht->_table); ht->_table = NULL; ht->_size = 0; ht->_N = 0; } 

    哈希表的打印:

    void HashTablePrint(HashTable *ht) //打印 hash 表 { size_t i = 0; assert(ht); for (i=0; i<ht->_N; i++) { if (ht->_table[i]._status == EXIST) printf("[%d]%d ",i,ht->_table[i]._key); else if (ht->_table[i]._status == EMPTY) printf("[%d]E ",i); else printf("[%d]D ",i); } printf("\n\n"); } 

    哈希表整个在插入这块会比较ran,要仔细理解,特别是扩容那块。

    测试案例:

    void TestHashTable() { HashTable ht; HashTableInit(&ht); HashTableInsert(&ht,53,0); HashTableInsert(&ht,54,0); HashTableInsert(&ht,55,0); HashTableInsert(&ht,106,0); HashTableInsert(&ht,1,0); HashTableInsert(&ht,15,0); HashTableInsert(&ht,10,0); HashTablePrint(&ht); printf("%d ",HashTableFind(&ht,53)->_key); printf("%d ",HashTableFind(&ht,54)->_key); printf("%d ",HashTableFind(&ht,10)->_key); printf("%d ",HashTableFind(&ht,15)->_key); printf("%p ",HashTableFind(&ht,3)); printf("\n\n"); HashTableRemove(&ht,53); HashTableRemove(&ht,54); HashTableRemove(&ht,106); HashTableRemove(&ht,10); HashTableRemove(&ht,5); HashTablePrint(&ht); HashTableInsert(&ht,53,0); HashTableInsert(&ht,54,0); HashTableInsert(&ht,106,0); HashTablePrint(&ht); HashTableDestory(&ht); HashTablePrint(&ht); } 

    测试结果: 哈希表测试案例

    更多内容请关注本文博客:请戳关注链接 如需转载和翻译请联系本人。

    motoon
        1
    motoon  
       2018-02-28 21:55:30 +08:00
    好东西,记得大学学过,但是没理解透彻,工作后都是坑,读完恍然大悟
    关于     帮助文档     自助推广系统     博客     API     FAQ     Solana     1158 人在线   最高记录 6679       Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 605ms UTC 17:58 PVG 01:58 LAX 10:58 JFK 13:58
    Do have faith in what you're doing.
    ubao msn snddm index pchome yahoo rakuten mypaper meadowduck bidyahoo youbao zxmzxm asda bnvcg cvbfg dfscv mmhjk xxddc yybgb zznbn ccubao uaitu acv GXCV ET GDG YH FG BCVB FJFH CBRE CBC GDG ET54 WRWR RWER WREW WRWER RWER SDG EW SF DSFSF fbbs ubao fhd dfg ewr dg df ewwr ewwr et ruyut utut dfg fgd gdfgt etg dfgt dfgd ert4 gd fgg wr 235 wer3 we vsdf sdf gdf ert xcv sdf rwer hfd dfg cvb rwf afb dfh jgh bmn lgh rty gfds cxv xcv xcs vdas fdf fgd cv sdf tert sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf shasha9178 shasha9178 shasha9178 shasha9178 shasha9178 liflif2 liflif2 liflif2 liflif2 liflif2 liblib3 liblib3 liblib3 liblib3 liblib3 zhazha444 zhazha444 zhazha444 zhazha444 zhazha444 dende5 dende denden denden2 denden21 fenfen9 fenf619 fen619 fenfe9 fe619 sdf sdf sdf sdf sdf zhazh90 zhazh0 zhaa50 zha90 zh590 zho zhoz zhozh zhozho zhozho2 lislis lls95 lili95 lils5 liss9 sdf0ty987 sdft876 sdft9876 sdf09876 sd0t9876 sdf0ty98 sdf0976 sdf0ty986 sdf0ty96 sdf0t76 sdf0876 df0ty98 sf0t876 sd0ty76 sdy76 sdf76 sdf0t76 sdf0ty9 sdf0ty98 sdf0ty987 sdf0ty98 sdf6676 sdf876 sd876 sd876 sdf6 sdf6 sdf9876 sdf0t sdf06 sdf0ty9776 sdf0ty9776 sdf0ty76 sdf8876 sdf0t sd6 sdf06 s688876 sd688 sdf86