数据结构-哈希表

标签：属性 dictEntry 键值 哈希 数据结构 指针

 哈希表hashtable数据结构

dictht是hashtable的数据结构，dictEntry是每个entry元素的数据结构。

typedef struct dictht {
    //指针数组，这个hash的桶
    dictEntry **table;
    //元素个数
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

• table属性是一个数组，数组中的每个元素都是一个指向哈希表节点的指针，每个哈希表节点都保存着一个键值对。
• size属性记录了哈希表的大小，也即table数组的大小。
• used属性记录了哈希表目前已有节点的数量。
• sizemask属性的值总是等于size-1,这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上。

哈希表节点数据结构

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        // 指向具体redisObject
        void *val;
        // 
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

• key属性保存键值对中的键
• v属性保存键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_t整数，或者是一个int64_t整数
• next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决键冲突（collision）的问题

哈希冲突

Redis 解决哈希冲突的方式，就是链式哈希。链式哈希也很容易理解，就是指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。

 

 

 

 

标签：属性,dictEntry,键值,哈希,数据结构,指针
From： https://www.cnblogs.com/zhengbiyu/p/17255073.html