免费pc网站建设,做项目接任务的网站,微商城平台哪个好,今天上午北京发生了什么代码仓库地址 1. 功能说明
自定义初始容量和负载因子#xff1b;当键值对的个数与容量比值超过负载因子时#xff0c;自动扩容#xff1b;借鉴Java8的HashMap部分扩容逻辑#xff0c;定义了单独的桶结构体用于记录hash值#xff0c;以及2倍扩容#xff0c;减少了hash运算… 代码仓库地址 1. 功能说明
自定义初始容量和负载因子当键值对的个数与容量比值超过负载因子时自动扩容借鉴Java8的HashMap部分扩容逻辑定义了单独的桶结构体用于记录hash值以及2倍扩容减少了hash运算和移位的开销。
2. 实现原理
采用动态数组加链表的方式实现之后撸完红黑树增加动态数组链表红黑树的版本。 3. 定义头文件
#ifndef HASH_MAP_H
#define HASH_MAP_H
#include stdio.h
#include stdlib.h
#include stdbool.h
#include string.h
#include time.h
// 默认桶的个数(动态数组默认大小)
#define DEFAULT_CAPACITY 8
// 默认负载因子
#define DEFAULT_LOAD_FACTOR 0.75typedef char* K;
typedef char* V; // 定义hashmap的链表结点
typedef struct map_node {K key; // 键V value; // 值struct map_node *next; // 下一个结点
} MapNode;// 定义hashmap的桶结点
typedef struct {MapNode *head; // 桶中链表的第一个节点uint32_t hash_code; // 桶中键值对hash值
} Bucket;// 定义hashmap结构体
typedef struct {Bucket **buckets; // 存键值对的桶动态的Bucket指针数组int size; // map中键值对个数int capacity; // map的容量double load_factor; // map的负载因子uint32_t hash_seed; // hash函数的种子
} HashMap;// 创建HashMap容量和负载因子填NULL则使用默认值
HashMap* create_hashmap(const void* capacity_p, const void* load_factor_p);
// 销毁HashMap
void destroy_hashmap(HashMap *map);
// ---------------- 基本操作 ----------------
// 存入键值对
V put(HashMap *map, K key, V val);
// 查询键值对
V get(const HashMap *map, K key);
// 删除键值对
bool map_remove(HashMap *map, K key);
// 键key在表中是否有对应的值
bool contains(const HashMap *map, K key);
// 判断表是否为空
bool is_empty(const HashMap *map);// ---------------- 其他操作 ----------------
// 是否需要扩容
static bool is_need_resize(const HashMap *map);
// 扩容
static void resize(HashMap *map);
// murmur_hash2 哈希函数
static uint32_t hash(const void* key, int len, uint32_t seed);#endif4. 具体实现
1. 创建HashMap
需要注意buckets是动态数组需要手动初始化并且calloc(capacity, sizeof(Bucket*)注意是Bucket* 写成Bucket也不会报错但是会造成更耗内存
// 创建HashMap容量和负载因子填NULL则使用默认值
HashMap* create_hashmap(const void* capacity_p, const void* load_factor_p) {// 1. 创建hashmapHashMap *map calloc (1, sizeof(HashMap));if (map NULL) {puts(errorcreate_hashmap()内分配内存失败);return NULL;}//2. 初始化Bucket动态数组int capacity capacity_p NULL ? DEFAULT_CAPACITY : *(int*)capacity_p;Bucket **buckets calloc(capacity, sizeof(Bucket*));if (map NULL) {puts(errorcreate_hashmap()内分配内存失败);free(map);return NULL;}map-buckets buckets;// 3. 初始化hashmap的其他属性map-capacity capacity;double load_factor load_factor_p NULL ? DEFAULT_LOAD_FACTOR : *(double*)load_factor_p;map-load_factor load_factor;map-hash_seed time(NULL);return map;
}2. 销毁HashMap
要注意销毁桶避免造成内存泄漏
void destroy_hashmap(HashMap *map) {if (map NULL) {puts(errordestroy_hashmap()的参数map为NULL);exit(-1);}// 1. 销毁链表结点for (int i 0; i map-capacity; i) {Bucket *cur_bucket map-buckets[i];if (cur_bucket ! NULL) {MapNode *cur cur_bucket-head;while(cur ! NULL) {MapNode *temp cur-next;free(cur);cur temp;}// 2. 销毁桶free(cur_bucket);}}// 3. 销毁mapfree(map);
}3. 存入键值对
在存入时可以先判断一下key值在桶中是否存在然后再进行扩容这样对与重复键值对的存储速度有一定的提升。
V put(HashMap *map, K key, V val) {if (map NULL) {puts(errorput()的参数map为NULL);exit(-1);}// 1. 计算key的hash值以及桶的位置idxuint32_t hash_code hash(key, strlen(key), map-hash_seed);int idx hash_code % map-capacity;// 2. 判断idx位置的桶是否存在if (map-buckets[idx] ! NULL) {// 2-1. idx位置的桶已存在则判断idx桶中是否存在key值MapNode *cur map-buckets[idx]-head;while (cur ! NULL) {if (strcmp(cur-key, key) 0) {// 2-1-1. 若idx桶中已存在key值则更新value值并返回旧value值V old_val cur-value;cur-value val;return old_val;}cur cur-next;}}// 3. 判断是否需要扩容if (is_need_resize(map)) {// 3-1. 若需扩容则扩容并重新计算key的hash值和桶位置idxresize(map);hash_code hash(key, strlen(key), map-hash_seed);idx hash_code % map-capacity;}// 4. 重新判断idx位置的桶是否存在在‘2.’虽然判断了一次但有可能新的idx位置桶还未创建过if (map-buckets[idx] NULL) {// 4-1. idx位置的桶不存在则在idx位置创建桶并在桶中存入hash值Bucket *bucket calloc(1, sizeof(Bucket));if (bucket NULL) {puts(errorput()内分配内存失败);exit(-1);}bucket-hash_code hash_code;map-buckets[idx] bucket;}// 5. 在桶中插入这键值对用头插 O(1)MapNode *new_node calloc(1, sizeof(MapNode));if (new_node NULL) {puts(errorput()内分配内存失败);exit(-1);}new_node-key key;new_node-value val;new_node-next map-buckets[idx]-head;map-buckets[idx]-head new_node;// 6. 更新size map-size;return NULL;
}4. 查询键值对
注意要对桶进行判空不能直接map-buckets[idx]-head。
V get(const HashMap *map, K key) {if (map NULL) {puts(errorget()的参数map为NULL);exit(-1);}// 1. 计算key的hash值应存放的桶的位置idxint idx hash(key, strlen(key), map-hash_seed) % map-capacity;// 2. 在idx位置的桶中搜索对应key值if (map-buckets[idx] ! NULL) { // 先判断桶是否为空MapNode *cur map-buckets[idx]-head;while(cur ! NULL) {if (strcmp(cur-key, key) 0) {return cur-value;}cur cur-next;}}return NULL;
}5. 删除键值对
注意删除的结点是否是第一个节点要分情况处理。
bool map_remove(HashMap *map, K key) {if (map NULL) {puts(errormap_remove()的参数map为NULL);exit(-1);}// 1. 计算key的hash值应存放的桶的位置idxint idx hash(key, strlen(key), map-hash_seed) % map-capacity;// 2. 在idx位置的桶中搜索对应key值if (map-buckets[idx] ! NULL) { // 先判断桶是否为空MapNode *pre NULL;MapNode *cur map-buckets[idx]-head;while(cur ! NULL) {if (strcmp(cur-key, key) 0) {// 3. 删除结点if (pre NULL) { // 删除的是第一个结点map-buckets[idx]-head cur-next;}else {pre-next cur-next;}// 4. 释放内存free(cur);// 5. 更新size map-size--;return true;}pre cur;cur cur-next;}}return false;
}6. 扩容
注意扩容机制是采用每次库容2倍这样每次新下标就是old_idx或者为old_idx(new_cap-old_cap)不让会出现多个旧桶在新数组里下标冲突被覆盖抹除的问题
static void resize(HashMap *map) {// 1. 创建新的桶数组int old_cap map-capacity;// 每次扩容2倍好处是每次新下标就是old_idx或者为old_idx(new_cap-old_cap)详见Java8hashmap扩容int new_cap old_cap 1; Bucket **new_buckets calloc(new_cap, sizeof(Bucket*));// 2. 挪动旧桶中的数据到新桶中Bucket **old_buckets map-buckets;for (int idx 0; idx old_cap; idx) {Bucket *cur old_buckets[idx];if (cur ! NULL) { // 只操作非空桶// 2-1. 计算新的位置idxint new_idx cur-hash_code % new_cap;// 2-2. 挪动桶new_buckets[new_idx] old_buckets[idx];} }// 3. 将新桶交给hashmapmap-buckets new_buckets;// 4. 更新hashmap的容量map-capacity new_cap;// 5. 将就旧桶销毁free(old_buckets);
}7. 其他函数
剩下的几个函数简单不易出错此处不再赘述其中hash函数使用的开源的murmur_hush2详见开头处github代码仓库。
