c 中的哈希表-EW帮帮网

哈希是一种可以接受各种类型、大小的输入，输出一个固定长度整数的过程。

你可以将哈希理解成一种特殊的映射，哈希映射，将一个理论无限的集合A映射到有限整数集合B上。

哈希函数：哈希函数是哈希过程的核心，它决定了哈希映射过程的规则。

哈希冲突：哈希是一种化无限为有限的映射，允许出现多对一，但绝不允许出现一对多。若映射中出现多对一，就是哈希冲突。哈希冲突可以减少，但绝不可能没有。

哈希函数

/* murmur_hash2 */
static uint32_t hash(const void* key, int len, uint32_t seed) {
    const uint32_t m = 0x5bd1e995;
    const int r = 24;
    uint32_t h = seed ^ len;
    const unsigned char* data = (const unsigned char*)key;

    while (len >= 4) {
        uint32_t k = *(uint32_t*)data;
        k *= m;
        k ^= k >> r;
        k *= m;
        h *= m;
        h ^= k;
        data += 4;
        len -= 4;
    }

    switch (len) {
        case 3: h ^= data[2] << 16;
        case 2: h ^= data[1] << 8;
        case 1: h ^= data[0];
            h *= m;
    };

    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return h;
}
MurmurHash 是一种非加密哈希函数，适用于一般的哈希检索操作。它以高运行速度和分布均匀性而闻名。其中uint32_t表示无符号 32 位整型，要想使用它需要包含头文件<stdint.h>。

该函数调用需要三个参数：

void* key，也就是需要计算哈希值的key元素。此形参的类型是void*，这意味着它可以传入任何类型的数据，提高了函数的通用性。

如果key是基本数据类型，那就传入指向基本数据类型的指针

如果key本身就是一个指针类型，比如字符串，那么就直接传入这个指针就可以了。

int len，表示哈希函数要处理的key的大小长度。key若是字符串可以使用函数strlen计算，若是其它类型可以使用sizeof计算。

uint32_t seed，种子值。

此哈希函数会根据key和seed共同生成一个哈希值

不同的种子值会导致相同的数据产生不同的哈希值。需要注意的是，在程序一次运行中，同一个哈希表应该具有相同的种子值！

最常见的设置种子值的方式就是用时间戳，也就是time(NULL);函数调用。这对于大家而言，应该都比较熟悉了。

拉链法实现固定容量的哈希表

#ifndef HASH_MAP_H
#define HASH_MAP_H

#include <stdint.h> // 包含它是为了使用别名uint32_t
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define HASHMAP_CAPACITY 10 // 哈希表中数组的长度固定是10

// 此时哈希表用于存储字符串类型的键值对
typedef char *KeyType;
typedef char *ValueType;

// 键值对结点
typedef struct node_s {
    KeyType key;
    ValueType val;
    struct node_s *next;
} KeyValueNode;

typedef struct {
    // 哈希桶
    KeyValueNode *buckets[HASHMAP_CAPACITY];    // 直接给定哈希桶的数量是10个
    // 哈希函数需要的种子值
    uint32_t hash_seed;
} HashMap;

// 创建一个固定容量的哈希表
HashMap *hashmap_create();
// 销毁一个哈希表
void hashmap_destroy(HashMap *map);
// 插入一个键值对
ValueType hashmap_put(HashMap *map, KeyType key, ValueType val);
// 查询一个键值对
ValueType hashmap_get(HashMap *map, KeyType key);
// 删除某个键值对
bool hashmap_remove(HashMap *map, KeyType key);

#endif // !HASH_MAP_H

实现创建哈希表

// 创建一个固定容量的哈希表
HashMap *hashmap_create() {
    HashMap *map = calloc(1, sizeof(HashMap));
    if (map == NULL) {
        printf("error: calloc failed in hashmap_create.\n");
        exit(-1);
    }
    map->hash_seed = time(NULL);
    return map;
}

实现哈希表销毁

// 销毁一个哈希表
void hashmap_destroy(HashMap *map) {
    // 遍历数组,然后销毁哈希桶中的链表,最后销毁HashMap结构体
    for (size_t i = 0; i < HASHMAP_CAPACITY; i++) {
        KeyValueNode *curr = map->buckets[i];
        while (curr != NULL) {
            KeyValueNode *tmp = curr->next;
            free(curr);
            curr = tmp;
        }
    }
    free(map);
}

实现插入键值对

// 插入一个键值对
ValueType hashmap_put(HashMap *map, KeyType key, ValueType val) {
    // 1.计算哈希值确定哈希桶的位置
    int idx = hash(key, strlen(key), map->hash_seed) % HASHMAP_CAPACITY;

    // 2.遍历哈希桶，查找Key是否重复
    KeyValueNode *curr = map->buckets[idx];
    while (curr != NULL) {
        // 比较字符串
        if (strcmp(key, curr->key) == 0) {
            // key已存在,更新value,并返回旧value
            ValueType old_val = curr->val;
            curr->val = val;
            return old_val;
        }
        curr = curr->next;
    }

    // 3.只要Key不重复肯定都要插入，于是无脑使用链表头插法插入结点
    KeyValueNode *new_node = malloc(sizeof(KeyValueNode));
    if (new_node == NULL) {
        printf("Error: malloc failed in hashmap_put.\n");
        exit(1);
    }
    new_node->key = key;    // key和val都是指针类型，可以直接"="赋值
    new_node->val = val;

    // 链表头插法
    new_node->next = map->buckets[idx]; // 新结点指向原本的第一个结点
    map->buckets[idx] = new_node;   // 更新头指针

    // 没有更新键值对返回空指针
    return NULL;
}

实现键值对查询

// 查询一个键值对
ValueType hashmap_get(HashMap *map, KeyType key) {
    // 1.计算哈希值确定哈希桶的位置
    int idx = hash(key, strlen(key), map->hash_seed) % HASHMAP_CAPACITY;
    // 2.遍历哈希桶，查找Key是否存在
    KeyValueNode *curr = map->buckets[idx];
    while (curr != NULL) {
        // 比较字符串
        if (strcmp(key, curr->key) == 0) {
            // 已找到目标键值对
            return curr->val;
        }
        curr = curr->next;
    }
    // 目标键值对不存在
    return NULL;
}

实现键值对删除

// 删除某个键值对
bool hashmap_remove(HashMap *map, KeyType key) {
    // 1.计算哈希值确定哈希桶的位置
    int idx = hash(key, strlen(key), map->hash_seed) % HASHMAP_CAPACITY;
    // 2.初始化两个指针,用于删除结点
    KeyValueNode *curr = map->buckets[idx];
    KeyValueNode *prev = NULL;
    // 3.遍历链表查找目标Key
    while (curr != NULL) {
        // 比较字符串
        if (strcmp(key, curr->key) == 0) {
            // 已找到目标键值对
            if (prev == NULL) {
                // 删除的是第一个结点
                map->buckets[idx] = curr->next;
            }
            else
            {
                // 删除的不是第一个结点
                prev->next = curr->next;
            }
            // free结点
            free(curr);
            return true;    // 删除成功
        }
        prev = curr;        // 更新prev为当前节点
        curr = curr->next;  // 当前结点向后移动
    }
    // 没找到目标键值对,删除失败
    return false;
}

负载因子(Load Factor ）

一般来说，负载因子在0.7/0.75以下时，哈希表处在健康、性能优秀的状态。但一旦超出这个阈值，就意味着哈希冲突会增多，链表平均长度变长，从而导致性能下降。

在最佳情况下，即哈希函数均匀分布且冲突较少时，哈希表的插入、查询和删除操作的效率非常高，接近 O(1)。

在最坏情况下，特别是哈希冲突很多导致链表过长时，这些操作的效率会降低，接近 O(L)，因为此时的哈希表访问几乎相当于链表的访问。

实现动态哈希表

头文件

#ifndef DYNAMIC_HASHMAP_H
#define DYNAMIC_HASHMAP_H

typedef char *KeyType;
typedef char *ValueType;

#include <stdint.h>

typedef struct node_s {
    KeyType key;
    ValueType val;
    struct node_s *next;
} KeyValueNode;

typedef struct {
    KeyValueNode **buckets;     // 此时哈希桶是一个动态数组，指向char*元素的指针，所以是一个二级指针
    int size;               // 键值对的个数
    int capacity;           // 数组的长度
    uint32_t hash_seed;     // 哈希函数需要的种子值
} DynamicHashMap;

// 创建一个固定容量的哈希表
DynamicHashMap *hashmap_create();
// 销毁一个哈希表
void hashmap_destroy(DynamicHashMap *map);
// 插入一个键值对
ValueType hashmap_put(DynamicHashMap *map, KeyType key, ValueType val);
// 查询一个键值对
ValueType hashmap_get(DynamicHashMap *map, KeyType key);
// 删除某个键值对
bool hashmap_remove(DynamicHashMap *map, KeyType key);

#endif // !DYNAMIC_HASHMAP_H

实现创建和销毁动态哈希表

#include "dynamic_hashmap.h"
#define DEFAULT_CAPACITY 8  // 哈希表的初始默认容量是8

// 创建一个固定容量的哈希表
DynamicHashMap *hashmap_create() {
    DynamicHashMap *map = malloc(sizeof(DynamicHashMap));
    if (map == NULL) {
        printf("Error: malloc failed in hashmap_create\n");
        exit(1);
    }
    map->buckets = calloc(DEFAULT_CAPACITY, sizeof(KeyValueNode *));
    if (map->buckets == NULL) {
        // 不要忘记先free结构体
        free(map);
        printf("Error: calloc failed in hashmap_create\n");
        exit(1);
    }
    // 初始化其它成员
    map->size = 0;
    map->capacity = DEFAULT_CAPACITY;
    map->hash_seed = time(NULL);
    return map;
}

// 销毁一个哈希表
void hashmap_destroy(DynamicHashMap *map) {
    // 1.先遍历动态数组销毁链表的每一个结点
    for (int i = 0; i < map->capacity; i++) {
        KeyValueNode *curr = map->buckets[i];
        while (curr != NULL) {
            KeyValueNode *tmp = curr->next;
            free(curr);
            curr = tmp;
        }
    }
    // 2.再销毁动态数组
    free(map->buckets);
    // 3.最后销毁哈希表结构体
    free(map);
}

实现插入和扩容功能

#define LOAD_FACTOR_THRESHOLD  0.75     // 负载因子的阈值
#define CAPACITY_THRESHOLE 1024     // 数组容量的阈值

/* murmur_hash2 */
static uint32_t hash(const void* key, int len, uint32_t seed) {
    const uint32_t m = 0x5bd1e995;
    const int r = 24;
    uint32_t h = seed ^ len;
    const unsigned char* data = (const unsigned char*)key;

    while (len >= 4) {
        uint32_t k = *(uint32_t*)data;
        k *= m;
        k ^= k >> r;
        k *= m;
        h *= m;
        h ^= k;
        data += 4;
        len -= 4;
    }

    switch (len) {
        case 3: h ^= data[2] << 16;
        case 2: h ^= data[1] << 8;
        case 1: h ^= data[0];
            h *= m;
    };

    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return h;
}

static void rehash(KeyValueNode *curr, KeyValueNode **new_table, int new_capacity, uint32_t seed) {
    // 计算 key 的哈希值
    int len = strlen(curr->key);
    int idx = hash(curr->key, len, seed) % new_capacity;
    // 头插法
    curr->next = new_table[idx];
    new_table[idx] = curr;
}

// 对哈希表进行扩容操作
static void grow_capacity(DynamicHashMap *map) {
    /*
    * 扩容策略：
    * 1.如果容量没有达到阈值，那就每次将长度扩大为原先的2倍
    * 2.如果容量达到阈值，此时哈希表已经很长了，为了避免扩容过程性能损耗过大
    *   所以扩容保守一些，每次只扩容阈值长度的容量
    *
    * 扩容的过程：
    * 1.每个键值对结点都要重新计算哈希值，重新映射到新哈希桶中(新数组)
    * 2.原先的动态数组的链表很复杂，难以进行重哈希操作，建议直接丢弃它
    * 重新创建一个新动态数组
    */
    int new_capacity =
        (map->capacity <= CAPACITY_THRESHOLE) ?
        (map->capacity << 1) :
    (map->capacity + CAPACITY_THRESHOLE);

    // 动态数组扩容需要使用 calloc
    KeyValueNode **new_buckets = calloc(new_capacity, sizeof(KeyValueNode *));
    if (new_buckets == NULL) {
        printf("Error: calloc failed in grow_capacity\n");
        exit(1);
    }
    // 每次扩容都更改一次哈希种子，提高安全性
    uint32_t seed = time(NULL);

    // 将所有键值对重新映射到新数组中
    for (int i = 0; i < map->capacity; i++) {
        KeyValueNode *curr = map->buckets[i];
        while (curr != NULL) {
            KeyValueNode *next = curr->next;
            // 重新进行哈希映射
            rehash(curr, new_buckets, new_capacity, seed);
            curr = next;
        }
    }
    // 将旧动态数组free，但是注意不要free键值对结点，结点已经被链接到新数组中了。
    free(map->buckets);
    // 更新 HashMap 的信息
    map->buckets = new_buckets;
    map->capacity = new_capacity;
    map->hash_seed = seed;
}

// 插入一个键值对
// 1. 如果key不存在，则添加键值对结点
// 2. 如果key存在，则更新val，将旧的val返回
ValueType hashmap_put(DynamicHashMap *map, KeyType key, ValueType val) {
    // 计算key的哈希值确定存储位置
    int idx = hash(key, strlen(key), map->hash_seed) % (map->capacity);

    // 遍历链表
    KeyValueNode *curr = map->buckets[idx];
    while (curr != NULL) {
        if (strcmp(key, curr->key) == 0) {
            // 更新 key 关联的 val, 并将旧的value返回
            ValueType old_val = curr->val;
            curr->val = val;
            return old_val;
        }
        curr = curr->next;
    } // while循环结束时, curr是一个NULL

    // 键值对不存在，即需要将键值对插入
    // 插入操作前需要计算当前哈希表的负载因子
    double load_factor = (1.0 * map->size) / (map->capacity);
    if (load_factor >= LOAD_FACTOR_THRESHOLD) {
        // 当前哈希表负载因子已达到阈值，将动态数组进行扩容
        grow_capacity(map);
        // 数组长度已变，需要再哈希确定当前键值对的存储位置
        idx = hash(key, strlen(key), map->hash_seed) % (map->capacity);
    }
    // 开始插入新键值对
    KeyValueNode *new_node = malloc(sizeof(KeyValueNode));
    if (new_node == NULL) {
        printf("Error: malloc failed in hashmap_put\n");
        exit(1);
    }
    // 初始化结点
    new_node->key = key;
    new_node->val = val;
    // 链表的头插法
    new_node->next = map->buckets[idx];
    map->buckets[idx] = new_node;

    // 不要忘记更新size
    map->size++;
    return NULL;
}

访问和删除键值对

// 查询一个键值对
ValueType hashmap_get(DynamicHashMap *map, KeyType key) {
    // 计算key的哈希值，从而确定哈希桶
    int idx = hash(key, strlen(key), map->hash_seed) % map->capacity;
    // 遍历哈希桶的链表，判断 key 是否存在
    KeyValueNode *curr = map->buckets[idx];
    while (curr != NULL) {
        if (strcmp(key, curr->key) == 0) {
            // 找到目标键值对
            return curr->val;
        }
        curr = curr->next;
    } // curr == NULL
    // 没找到目标键值对
    return NULL;
}

// 删除某个键值对
bool hashmap_remove(DynamicHashMap *map, KeyType key) {
    // 计算key的哈希值，从而确定哈希桶
    int idx = hash(key, strlen(key), map->hash_seed) % map->capacity;
    // 初始化两个指针，一个指向链表当前结点，一个指向当前结点的前驱
    KeyValueNode *prev = NULL;
    KeyValueNode *curr = map->buckets[idx];
    while (curr != NULL) {
        if (strcmp(key, curr->key) == 0) {
            // 找到了要删除的节点
            if (prev == NULL) {
                // 删除的是哈希桶的第一个节点，于是更新头指针
                map->buckets[idx] = curr->next;
            }
            else {
                // 删除的是哈希桶中的非第一个节点，只需要让当前结点的前驱结点指向当前结点的后继
                prev->next = curr->next;
            }
            free(curr);
            map->size--;
            return true;
        }
        // 继续遍历链表
        prev = curr;
        curr = curr->next;
    }
    // 没找到指定key的节点
    return false;
}

扩展：利用哈希表判断单链表有环

头文件

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

#define CAPACITY 10  // 哈希表的底层数组长度是10

typedef struct node {
    int data;
    struct node *next;
}Node;  // 哈希表当中存储的链表结点类型

// 此哈希表只存储键,不存储value
// key值存储链表结点的指针
typedef Node *KeyType;

// 键值对结点，此时无需存储值了
typedef struct node_s {
    KeyType key;    // 键
    struct node_s *next;
} HashNode; // 键值对结点类型

typedef struct {
    HashNode *buckets[CAPACITY];
    uint32_t hash_seed;
} HashMap;    // 哈希表结构体类型

// 创建一个固定容量的哈希表
HashMap *hashmap_create();
// 销毁哈希表
void hashmap_destroy(HashMap *map);

/*
    尝试将链表结点的指针(地址)插入哈希表
    若发现结点已存入哈希表, 则函数返回true
    若结点未存入, 则将结点地址存入哈希表并返回false
*/
bool hashmap_put(HashMap *map, KeyType key);

该哈希表的实现代码如下所示：

#include "hash_map.h"

/* murmur_hash2 */
static uint32_t hash(const void *key, int len, uint32_t seed) {
    const uint32_t m = 0x5bd1e995;
    const int r = 24;
    uint32_t h = seed ^ len;
    const unsigned char *data = (const unsigned char *)key;

    while (len >= 4) {
        uint32_t k = *(uint32_t *)data;
        k *= m;
        k ^= k >> r;
        k *= m;
        h *= m;
        h ^= k;
        data += 4;
        len -= 4;
    }

    switch (len) {
        case 3: h ^= data[2] << 16;
        case 2: h ^= data[1] << 8;
        case 1: h ^= data[0];
            h *= m;
    };

    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return h;
}

// 创建一个固定容量的哈希表
HashMap *hashmap_create() {
    HashMap *map = calloc(1, sizeof(HashMap));
    if (map == NULL) {
        printf("error: calloc failed in hashmap_create.\n");
        return NULL;
    }
    map->hash_seed = time(NULL);
    return map;
}

// 销毁哈希表
void hashmap_destroy(HashMap *map) {
    // 遍历每一个哈希桶(也就是遍历数组的每一个元素)，逐一销毁链表结点，最后销毁结构体自身
    for (int i = 0; i < CAPACITY; i++) {
        HashNode *curr = map->buckets[i];
        while (curr != NULL) {
            HashNode *tmp = curr->next;
            free(curr);
            curr = tmp;
        }
    }
    free(map);
}

/*
    该函数会将链表结点的地址作为一个结点key值,存入哈希表当中
    在存入的过程中,如果发现key值重复,说明有环,直接返回true
    如果key值不重复,那就将key结点正常存入哈希表,并且返回false
*/
bool hashmap_put(HashMap *map, KeyType key) {
    // 1.根据key这个结点地址数据来计算哈希值,确定哈希桶的位置
    int idx = hash(key, sizeof(KeyType), map->hash_seed) % CAPACITY;
    // 2.遍历哈希桶,确定这个结点地址是否已经出现
    HashNode *curr = map->buckets[idx];
    while (curr != NULL) {
        if (key == curr->key) {
            // 当前结点已经重复出现了,说明有环
            return true;
        }
        curr = curr->next;
    }
    // 3.key是不存在的,于是新增这个结点
    HashNode *new_node = malloc(sizeof(HashNode));
    if (new_node == NULL) {
        printf("error: malloc failed in hashmap_put.\n");
        exit(-1);
    }
    new_node->key = key;    // 由于key是Node结点指针类型,是地址,所以可以直接用=赋值

    // 4.执行链表的头插法,将新结点链接到链表中
    new_node->next = map->buckets[idx];
    map->buckets[idx] = new_node;

    return false;   // 表示当前结点还没有重复,所以插入哈希表成功了
}

// 利用哈希表来判断单链表有环
bool has_circle(Node *head) {
    // 1.创建一个哈希表
    HashMap *map = hashmap_create();
    // 2.遍历整条单链表,并且将每一个结点的地址存入哈希表
    Node *curr = head;
    while (curr != NULL) {
        if (hashmap_put(map, curr)) {
            // 已经存储了重复结点,有环
            hashmap_destroy(map);
            return true;
        }
        curr = curr->next;
    }
    // 如果while循环能够结束,且能够执行到这里,说明链表没环
    hashmap_destroy(map);
    return false;
}

c 中的哈希表

哈希函数

拉链法实现固定容量的哈希表

实现创建哈希表

实现哈希表销毁

实现插入键值对

实现键值对查询

实现键值对删除

负载因子(Load Factor ）

实现动态哈希表

实现创建和销毁动态哈希表

实现插入和扩容功能

访问和删除键值对

扩展：利用哈希表判断单链表有环

网站公告

今日签到

热门文章

最新发布