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

聊聊哈希表的设计与具体实现

  •  3
     
  •   Austin2035 · 2022-02-05 18:05:17 +08:00 · 2307 次点击
    这是一个创建于 1020 天前的主题,其中的信息可能已经有所发展或是发生改变。

    哈希表

    哈希表的概念

    散列表也叫哈希表( Hash table ),是根据关键字( key )而直接访问在内存存储位置的数据结构。
    在很多高级语言中都有哈希表的身影,比如在 Python 中,有一种数据结构叫做dict,中文翻译是字典,应该是基于哈希表实现的。下面以生活中查电话号码作为一个通俗的例子,讲解什么是哈希表。

    一个例子理解哈希表

    可以把哈希表想象成一本按照人名首字母顺序排列电话簿,当我们要查找张三的电话号码时,可以轻易得知张三的首字母是Z。理想情况下,张三可能在电话簿 Z 开头的第一个,不理想的情况下,可能要往后再找几个人。
    显然,根据姓名首字母查找电话,要比挨个查找快很多,这就是哈希表的特点,快。

    dict1.png

    与上面例子所对应的哈希表相关名词:

    1. 哈希表:电话簿
    2. 关键字(key):姓名,如张三
    3. 哈希函数(F):计算姓名的首字母的方法,参数是姓名,返回是对应的首字母
    4. 哈希地址:哈希函数的返回值,例子中,可以将 A-Z 理解为哈希地址

    什么是冲突

    对于不同关键词,经过哈希函数的计算,可能得到同一哈希地址。比如,尽管奔波儿灞(key1)和灞波儿奔(key2)是不同的名字(key1≠key2)但经过哈希函数计算得到的是同一结果(F(key1)=F(key2)=B),他们名字的首字母都是B。这种情况就叫做冲突。

    解决冲突的方法

    解决冲突的方法有很多种,比如开放地址法和链地址法,可以根据具体使用场景来选择。一般来说,在实际项目和开发中采用链地址法比较多。
    链地址法的基本思路是,把相同哈希地址的关键字放在同一个链表中。
    采用链地址法解决冲突的哈希表,可以理解为数组和链表的组合。在上图中,存放首字母的是一个长度为 26 的数组,而数组的每一个元素可以看作是一个单链表,链表的数据域存放着姓名,指针域指向下一个存放相同首字母的姓名的节点。

    字典的设计

    上面我们对哈希表有了一个大概的了解,接下来设计并实现一个字典(dict),在这个字典中,可以存放键值对,也可以根据键(key)获取对应的值(val)。

    1. 基本思想:采用链地址法,用定长数组(Array) + 单链表的方式表示字典,假定数组长度为SIZE,初始化状态的哈希表是一个元素全为 0 的数组。
    2. 存键值对:给定一个键值对(key1, val1),通过哈希函数 F 计算得到哈希值(hash_code),也即hash_code1 = F(key1)。然后,通过hash_code1 % SIZE得到地址(由于是在数组中的位置,这里用 Array[index]表示),取模操作是为了确保该地址在数组地址的范围内。接着,新建一个单链表节点(节点 1),指针域nextNULL,数据域存放 key1 和 val1 。最后,在 Array[index]中存放指向节点 1 的指针。
    3. 发生冲突:给定一个键值对(key2, val2),key2≠key1 ,如果通过哈希函数计算,hash_code2 = hash_code1 ,那么将得到同一个地址 Array[index],此时发生冲突,因为数组此位置中已经存放了指向节点 1 的指针。
    4. 解决冲突: 新建一个单链表节点(节点 2 ),数据域保存 key2 和 val2 ,指针域next为 NULL 。让节点 1 的next指针指向节点 2 即可解决冲突,这就是链地址法,也叫拉链法,后面的冲突,继续使用此方法解决即可。
    5. 更新操作:在前面我们插入了键值对(key1, val1), 如果在此基础上又需要插入新的键值对(key1, val0),其中 val0≠val1 ,就需要进行更新操作。有两种方法,第一种是直接将此键值的节点作为数组对应位置的第一个节点,第二种是在对应数组位置找到 key=key1 的节点,然后更新其 val 指针。
    6. 查字典:给定一个 key ,查 val 。首先要计算出地址 Array[index] = F(key) % SIZE ,如果有数据,此地址会存放一个指向单链表节点的指针,接着对比该指针指向的节点的数据域 key 是否与要查找的 key 相等。理想情况下是相等的,但由于冲突的存在,可能需要沿着节点的next指针往下找,也因此,哈希算法的时间复杂度并没有 O(1)。找到数据后,返回即可。如果没数据,Array[index]=0 ,返回 NULL 。

    字典的表示

    /* 字典类型 */
    #define DICT_TYPE_INT 0
    #define DICT_TYPE_STR 1
    
    typedef struct dict_entry {
        /* 后继节点 */
        struct dict_entry *next;
        /* 键 */
        void *key;
        /* 值 */
        void *val;
    }dict_entry;
    
    typedef struct dict {
        /* 哈希函数 */
        unsigned int (*hash)(void *key);
        /* table 数组用于存放 dict_entry 指针 */
        dict_entry **table;
        /* table 数组的长度 */
        int size;
        /* 掩码( size-1 ) */
        int sizemask;
    }dict;
    

    首先看dict_entry结构体,它有三个成员,分别用来表示后继节点next指针和键与值,用以表示单链表的节点。
    接着是dict结构体,用来表示字典本身。

    1. *hash:对于不同类型的键,比如整型或字符数组(字符串),需要用不同的 hash 函数来处理,该成员是指针函数,指向该字典的 hash 函数。
    2. table:注意,该成员 table 是一个数组,用来存放dict_entry类型的指针。可以用 dict_entry* table[size]来辅助理解。
    3. size:table 数组的长度。
    4. sizemask:掩码,用于通过与运算来计算数组索引。通常 sizemask = size-1 , 给定一个数 x, x % size 等价于 x & sizemask 。与运算可能会比模运算更快,所以选择前者。

    dict2.png

    函数清单

    下面是用于操作队列的函数名及其作用与复杂度

    函数 作用 算法复杂度
    hash_integer 计算整型 key 的 hash 值 O(1)
    hash_33 计算字符型 key 的 hash 值 O(N)
    dict_create 创建新字典 O(1)
    dict_create_entry 创建一个 dict_entry O(1)
    dict_put_entry 字典插入一个 entry O(1)
    dict_get_value 获取 key 对应的 val 最佳 O(1),最坏 O(N)
    dict_empty 清除字典所有 entry O(N2)
    dict_release 释放整个字典 O(N2)

    哈希函数的选择

    /* 哈希函数(适用整数) */
    static unsigned int hash_integer(void *key)
    {
        return (*(int *)key * 2654435769) >> 28;
    }
    
    /* 哈希函数 TIME33 算法 (适用字符串)*/
    static unsigned int hash_33(void *key)
    {   
        unsigned int hash = 0;
        while (*(char *)key != 0)
        {
            /* 左移 5 位相当于*32 ,再+hash 则相当于*33; */
            hash = (hash << 5) + hash + *(char *)key++;
        }
        return hash;
    }
    

    哈希函数是一种映射关系,构造哈希函数是一个数学问题,方法也很多,总的来说,要尽量减少冲突,地址尽量分布的均匀。
    这里我们选择一个简单的用于计算整数哈希值的函数,以及用于计算字符串哈希的 TIME33 算法。
    拓展,有一种叫MurmurHash的算法因为被 Redis 应用而广为人知, 由 Austin Appleby 在 2008 年发明, 发明者被邀到 google 工作。

    哈希表的创建

    /* 创建一个 dict */
    dict *dict_create(int type)
    {
        dict *dict = (struct dict *)malloc(sizeof(struct dict));
        if(dict == NULL) return NULL;
        if(type == DICT_TYPE_INT)
            dict->hash = &hash_integer;
        else
            dict->hash = &hash_33;
        dict->size = 1024;
        dict->sizemask = dict->size - 1;
        /* 为数组申请内存 */
        dict->table = (dict_entry **)malloc(sizeof(dict_entry *) *(dict->size));
        if (dict->table == NULL) return NULL;
        /* 数组元素全部置零 */
        memset(dict->table, 0, sizeof(dict_entry *) * (dict->size));
        return dict;
    }
    

    函数接受一个参数type,用以下面判断字典的类型,从而确定对应的 hash 函数。
    然后是设置字典的大小,并为table数组申请内存,然后 table 所有元素置 0 ,代表数组该位置为空。
    最后返回该新建的字典。

    创建 dict_entry

    /* 创建一个 dict_entry */
    dict_entry * dict_create_entry(void *key, void *val)
    {
        dict_entry * entry = (dict_entry *)malloc(sizeof(dict_entry));
        if(entry == NULL) return NULL;
        entry->key = key;
        entry->val = val;
        entry->next = NULL;
        return entry;
    }
    

    创建一个dict_entry,也即是单链表的节点。这里接受俩 void 类型指针为参数,使得字典可以保存各类数据。

    字典插入键值对

    第一种方法:

    /* 字典插入一个键值对 */
    dict *dict_put_entry(dict *dict, void *key, void *val)
    {
        unsigned int hash = dict->hash(key);
        int pos = hash & dict->sizemask;
        
        dict_entry *entry;
        entry = dict_create_entry(key, val);
        
        entry->next =  dict->table[pos];
        dict->table[pos] = entry;
    
        return dict;
    }
    

    这种方法简单有效,无论是新增、冲突或者更新操作,都以要插入的键值对生成的新结点作为对应数组位置的第一个节点。
    新增和冲突,本质都是链表插入,使用此方法时,更新并非实质更新。
    由于新结点作为对应数组位置的第一个节点,这就导致旧数据(相同 key 的节点)排列在新结点之后,而查询时,是从数组对应位置链表的第一个节点开始查找,所以总是先查找到新的键值对。

    优缺点:

    • 优点,操作简单、优雅,插入效率高,无需遍历链表和计算每个节点 key 的 hash 值。
    • 缺点,旧节点还存留在该链表中,所以多占了点内存。

    值得一提的是,Redis的 dcit 在插入键值对时,就使用了该方法。

    第二种方法:

    /* 字典插入一个键值对 */
    dict *dict_put_entry(dict *dict, void *key, void *val)
    {
        unsigned int hash = dict->hash(key);
        int pos = hash & dict->sizemask;
        dict_entry *entry, *current;
        /* 新增 */
        if(dict->table[pos]==0){
            printf("新增\n");
            entry = dict_create_entry(key, val);
            dict->table[pos] = entry;
        } else {
            current = dict->table[pos];
            
            /* 首先判断第一个节点是否符合更新的情况 */
            if(dict->hash(current->key) == dict->hash(key)) {
                printf("更新\n");
                current->val = val;
                return dict;
            }
    
            /* 如果不符合,往下找,直到找到 hash 值相等的 key 的节点,则更新,
             * 或者直到 next==NULL ,此时新增在链表尾部。 */
            while(current->next != NULL) {    
                printf("往下找\n");
                if(dict->hash(current->next->key) == dict->hash(key)) {
                    printf("更新\n");
                    current->next->val = val;
                    return dict;
                };
                current = current->next;
            }
    
            printf("尾部插入\n");
            entry = dict_create_entry(key, val);
            current->next = entry;
        }
        return dict;
    }
    

    这个方法可以参考上文提到的字典的设计,优点是利用内存更加少一点,缺点就是不够优雅,增加了算法复杂度。

    在调试和测试时,可以将 dict->size 设置为 1 ,进而观察新增、更新、冲突等情况。

    查字典

    /* dict 获取值 */
    void * dict_get_value(dict *dict, void *key) 
    {
        unsigned int hash = dict->hash(key);
        int pos = hash & dict->sizemask;
        if(dict->table[pos]==0) return NULL;
        dict_entry *current = dict->table[pos];
        while (current)
        {
            if(dict->hash(current->key) == dict->hash(key))
                return current->val;
            else
                current = current->next;
        }
        return NULL;
    }
    

    查字典就是给定一个 key ,查对应的 val 。
    参考上文提到的字典的设计

    字典的清除与释放

    /* 清除 dict 所有 entry ,而不清除 dict 本身 */
    void dict_empty(dict *dict)
    {
        int i;
        for(i=0;i<dict->size;i++){
            if(dict->table[i] != 0){
                dict_entry * current, *next;
                current = dict->table[i];
                while (current)
                {   
                    next = current->next;
                    free(current);
                    current = next;
                }
                dict->table[i] = 0;
            }
        }
    }
    
    /* 释放 dict */
    void dict_release(dict *dict)
    {
        dict_empty(dict);
        free(dict->table);
        free(dict);
    }
    

    在清除 dict 所有 entry ,而不清除 dict 本身时,只需要遍历 table 数组,发现不为 0 的元素时再遍历清除对应的链表即可。
    释放 dict 的操作,只需要释放所有 entry 后,再释放 dict 本身即可。

    在 main 函数中测试

    int main()
    {   
        /* 创建一个 key 为字符串类型的字典 */
        dict * dict = dict_create(1);
    
        char str[] = "name";
        char str2[] = "Austin";
        char str3[] = "Lookcos";
        char str4[] = "age";
        int age = 18;
    
        /* 键值对:("Austin", "Austin") */
        dict_put_entry(dict, &str2, &str2);
        puts(dict_get_value(dict, &str2));
    
        /* 键值对:("name", "Austin") */
        dict_put_entry(dict, &str, &str2);
        puts(dict_get_value(dict, &str));
    
        /* 键值对:("name", "Lookcos") */
        dict_put_entry(dict, &str, &str3);
        puts(dict_get_value(dict, &str));
        
        /* 键值对:("age", 18) */
        dict_put_entry(dict, &str4, &age);
        printf("age: %d\n", *(int *)dict_get_value(dict, &str4));
    
        /* 字典的释放 */
        dict_empty(dict);
        dict_release(dict);
    
        return 0;
    }
    

    测试时,插入键值对我使用的是第二种方法,此外我还将 dict 中的 size 设置为 1 ,这样 table 中就一个位置,方便观察插入、更新、冲突时,链表的变化。

    编译输出

    # gcc -fsanitize=address -fno-omit-frame-pointer  -g dict.c  && ./a.out
    新增
    Austin
    尾部插入
    Austin
    往下找
    更新
    Lookcos
    往下找
    尾部插入
    age: 18
    

    完整代码

    本篇摘录于我的原创系列文章(学习笔记)

    https://github.com/LookCos/learn-data-structures

    声明

    本人才疏学浅,文章难免有纰漏之处,还望大佬们指点。

    q474818917
        1
    q474818917  
       2022-02-05 19:03:05 +08:00   ❤️ 1
    发这儿干啥呢?不是很理解
    Austin2035
        2
    Austin2035  
    OP
       2022-02-05 19:08:51 +08:00
    @q474818917 回我干啥呢?不是很理解
    zhangjinghua
        3
    zhangjinghua  
       2022-02-05 20:55:56 +08:00
    建议日常使用 hash 表一定要多加统计,这玩意很容易造成内存溢出。千万注意节点的建立和释放
    Austin2035
        4
    Austin2035  
    OP
       2022-02-05 21:35:20 +08:00
    @zhangjinghua 谢谢提醒,文中我写的这个,在编译时通过了 sanitize 内存检查,所以目前问题不大。确实,C 语言得安排好内存。
    deplivesb
        5
    deplivesb  
       2022-02-05 22:39:12 +08:00   ❤️ 3
    1. 看了一下, 你写的这个不就是大学课本上讲的么?还以为你把哈希表玩出花了
    2. 看了眼你推广的 GitHub 。哦,原来都是大学课本的内容,可能是当年没好好学。原谅你了
    Zchary
        6
    Zchary  
       2022-02-05 23:34:45 +08:00 via iPhone   ❤️ 1
    戾气太重了,楼主才大三
    cooljiang
        7
    cooljiang  
       2022-02-06 11:08:01 +08:00 via Android   ❤️ 1
    对哈希表有更深入的了解了,谢谢楼主
    Austin2035
        8
    Austin2035  
    OP
       2022-02-06 12:29:01 +08:00
    @deplivesb 。。课本上有这些图文吗?课本上有这些代码吗?课本上的代码能看吗?
    你是不是没上过大学?
    Austin2035
        9
    Austin2035  
    OP
       2022-02-06 12:29:37 +08:00
    @deplivesb 还有,这不是课本上的,这是我参考 redis 源码写的,看来你什么都不懂!键盘侠一个。。。。。
    Austin2035
        10
    Austin2035  
    OP
       2022-02-06 12:30:20 +08:00
    @livid 举报 @deplivesb ,恶意破坏论坛交流氛围。
    VagrantZ
        11
    VagrantZ  
       2022-02-06 17:11:38 +08:00   ❤️ 1
    总有些人算是自己会了的要来刷一下存在感……楼主你回复这种人你就输了。
    JStone
        12
    JStone  
       2022-02-06 21:21:52 +08:00   ❤️ 2
    虽然很多人学过听过 但像楼主这么认真复述并实现一遍且是少数 赞!
    archxm
        13
    archxm  
       2022-02-06 22:07:54 +08:00
    今天看了一部老电影《闪电狗》。迪士尼的动画片
    Austin2035
        14
    Austin2035  
    OP
       2022-02-07 09:04:03 +08:00
    @VagrantZ 你说的对,学到了。
    wsseo
        15
    wsseo  
       2022-02-07 10:30:43 +08:00
    问个问题,为什么不能通过名字直接找到这个人的信息?楼主可以讲下这个。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5273 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 07:06 · PVG 15:06 · LAX 23:06 · JFK 02:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.