V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
bigshot
V2EX  ›  程序员

哈希表详解

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

    哈希表( 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   ·   实用小工具   ·   4229 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 04:12 · PVG 12:12 · LAX 20:12 · JFK 23:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.