哈希表实现的hashmap，支持扩容减容，坛友帮忙测测
自己测试太难发现问题了，帮下忙啊
实现参考了这个文章 https://blog. 中的链地址法
程序代码：
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
typedef struct ztl_hashmap_kv ztl_hashmap_kv_t;
typedef ztl_hashmap_kv_t* ztl_hashmap_kv_p;
struct ztl_hashmap_kv{
char* key;
size_t value;
ztl_hashmap_kv_p next;
};
typedef struct ztl_hashmap ztl_hashmap_t;
typedef ztl_hashmap_t* ztl_hashmap_p;
struct ztl_hashmap{
int size;
int capacity;
ztl_hashmap_kv_p* array;
};
ztl_hashmap_p ztl_hashmap_init(int capacity);
void ztl_hashmap_put(ztl_hashmap_p map, char* key, size_t value);
size_t ztl_hashmap_get(ztl_hashmap_p map,char* key);
size_t ztl_hashmap_remove(ztl_hashmap_p map, char* key);
static void ztl_hashmap_resize(ztl_hashmap_p map, int type);
void ztl_hashmap_destory(ztl_hashmap_p map);
uint64_t fnv1a(char* buf, size_t len);
ztl_hashmap_p ztl_hashmap_init(int capacity)
{
ztl_hashmap_p map = calloc(1, sizeof(ztl_hashmap_t));
map->size = 0;
map->capacity = capacity;
map->array = calloc(capacity, sizeof(ztl_hashmap_kv_p));
return map;
}
void ztl_hashmap_put(ztl_hashmap_p map, char* key, size_t value)
{
int hash = fnv1a(key, strlen(key))%map->capacity;
ztl_hashmap_kv_p* kvp = map->array + hash;
ztl_hashmap_kv_p kv = *kvp;
if(kv){
while(kv){
if(0 == strcmp(key, kv->key)){
kv->value = value;
return;
}
if(kv->next){
kv = kv->next;
}else{
ztl_hashmap_kv_p nkv = calloc(1, sizeof(ztl_hashmap_kv_t));
nkv->key = key;
nkv->value = value;
kv->next = nkv;
map->size++;
break;
}
}
}else{
ztl_hashmap_kv_p nkv = calloc(1, sizeof(ztl_hashmap_kv_t));
nkv->key = key;
nkv->value = value;
*kvp = nkv;
map->size++;
}
ztl_hashmap_resize(map, 1);
}
int hashmap_getnum=0;
size_t ztl_hashmap_get(ztl_hashmap_p map,char* key)
{
int hash = fnv1a(key, strlen(key))%map->capacity;
ztl_hashmap_kv_p* kvp = map->array+hash;
ztl_hashmap_kv_p kv = *kvp;
hashmap_getnum = 0;
if(kv){
while(kv){ hashmap_getnum++;
if(0 == strcmp(key, kv->key)){
printf("hashmap get num: %d\n", hashmap_getnum);
return kv->value;
}
if(kv->next){
kv = kv->next;
}else{
break;
}
}
}
printf("hashmap get num: %d\n", hashmap_getnum);
return -1;
}
size_t ztl_hashmap_remove(ztl_hashmap_p map, char* key)
{
int hash = fnv1a(key, strlen(key))%map->capacity;
ztl_hashmap_kv_p* kvp = map->array+hash;
ztl_hashmap_kv_p kv = *kvp;
if(kv){
ztl_hashmap_kv_p prev=0;
while(kv){
if(0 == strcmp(key, kv->key)){
if(prev){
if(kv->next)prev->next = kv->next;
else prev->next = 0;
}else{
if(kv->next)*kvp = kv->next;
else *kvp = 0;
}
size_t rv = kv->value;
free(kv);
map->size--;
ztl_hashmap_resize(map, 0);
return rv;
}
if(kv->next){
prev = kv;
kv = kv->next;
}else{
break;
}
}
}
return -1;
}
//扩容与减容
static void ztl_hashmap_resize(ztl_hashmap_p map, int type)
{
int osiz = map->size;
int ocap = map->capacity;
ztl_hashmap_kv_p* oarray = map->array;
float s = osiz * 1.0;
float c = ocap * 1.0;
int ncap;
if(type){
if(s/c<0.8)return;
ncap = ocap*1.51;
}else{
if(s/c>0.3)return;
ncap = ocap*0.57;
}
map->size = 0;
map->capacity = ncap;
map->array = calloc(ncap, sizeof(ztl_hashmap_kv_p));
//printf("ztl_hashmap_resize------->ocap: %d, osiz:%d, s/c: %f\n", ocap, osiz, s/c);
for(int i=0; i<ocap; i++){
ztl_hashmap_kv_p okv = *(oarray + i);
while(okv){
int hash = fnv1a(okv->key, strlen(okv->key))%map->capacity;
ztl_hashmap_kv_p* kvp = map->array + hash;
ztl_hashmap_kv_p kv = *kvp;
if(kv){
while(kv->next){
kv = kv->next;
}
kv->next = okv;
map->size++;
}else{
*kvp = okv;
map->size++;
}
ztl_hashmap_kv_p tkv = okv->next;
okv->next = 0;
okv = tkv;
}
}
free(oarray);
}
void ztl_hashmap_destory(ztl_hashmap_p map)
{
for(int i=0; i<map->capacity; i++){
ztl_hashmap_kv_p kv = *(map->array + i);
while(kv){
ztl_hashmap_kv_p tkv = kv->next;
free(kv);
kv = tkv;
}
}
free(map->array);
free(map);
}
uint64_t fnv1a(char* buf, size_t len)
{
uint64_t hv = 0xcbf29ce484222325ULL;
char* bp = buf;
char* be = bp + len;
while (bp < be) {
hv ^= (uint64_t) *bp++;
hv += (hv << 1) + (hv << 4) + (hv << 5) +
(hv << 7) + (hv << 8) + (hv << 40);
}
return hv;
}
int main(int argc, char** argv)
{
ztl_hashmap_p map = ztl_hashmap_init(23);
ztl_hashmap_put(map, "长烟一空", 111111);
ztl_hashmap_put(map, "上下天光", 222222222);
ztl_hashmap_put(map, "一碧万顷", 333333333);
ztl_hashmap_put(map, "长烟一空", 7777777);
ztl_hashmap_put(map, "abc", 1234);
ztl_hashmap_put(map, "aac", 2345);
ztl_hashmap_put(map, "acc", 3456);
ztl_hashmap_put(map, "acca", 4567);
printf("000----hashmap cap: %d, size: %d\n", map->capacity, map->size);
for(int i=0; i<53; i++){
char* str = calloc(10,sizeof(char));//动态内存存储字符串
sprintf( str, "mapkey%d", i);
ztl_hashmap_put(map, str, i+1);
}
printf("111----hashmap cap: %d, size: %d\n", map->capacity, map->size);
printf("pl: %d, pr: %d, pb: %d\n\n",
(int)ztl_hashmap_get(map, "长烟一空"),
(int)ztl_hashmap_get(map, "上下天光"),
(int)ztl_hashmap_get(map, "一碧万顷")
);
printf(" %d, %d, %d, %d, %d\n\n",
(int)ztl_hashmap_get(map, "abc"),
(int)ztl_hashmap_get(map, "aac"),
(int)ztl_hashmap_get(map, "acc"),
(int)ztl_hashmap_get(map, "acca"),
(int)ztl_hashmap_get(map, "mapkey11")
);
for(int i=0; i<76; i++){
char* str = calloc(10,sizeof(char));//动态内存存储字符串
sprintf( str, "mapkey%d", i);
ztl_hashmap_remove(map, str);
}
ztl_hashmap_remove(map, "acca");
printf(" %d, %d, %d, %d, %d\n\n",
(int)ztl_hashmap_get(map, "abc"),
(int)ztl_hashmap_get(map, "aac"),
(int)ztl_hashmap_get(map, "acc"),
(int)ztl_hashmap_get(map, "acca"),
(int)ztl_hashmap_get(map, "mapkey11")
);
// printf("-------------------\n");
// for(int i=0; i<map->capacity; i++){
// ztl_hashmap_kv_p kv = *(map->array + i);
// while(kv){
// printf("%s = %d\n", kv->key, (int)kv->value);
// kv = kv->next;
// }
//
// }
printf("222----hashmap cap: %d, size: %d\n", map->capacity, map->size);
ztl_hashmap_destory(map);
return 0;
}
[此贴子已经被作者于2021-8-31 15:08编辑过]
