#include<stdio.h>
#include "hash_table.h"
int main() {
ht_hash_table* ht = ht_new();
const char* a="1" ;
const char* b="2" ;
ht_insert(ht,a,b);
printf(*ht_search(ht, 1));
ht_del_hash_table(ht);
return 0;
}//main.c
#include <stdlib.h>
#include <string.h>
#include<math.h>
#include"prime.h""
#include "hash_table.h"
#define HT_PRIME_1 151
#define HT_PRIME_2 152
#define HT_INITIAL_BASE_SIZE 50
static void ht_resize_up(ht_hash_table* ht);
static void ht_resize_down(ht_hash_table* ht);
static ht_item HT_DELETED_ITEM = { NULL, NULL };
static ht_item* ht_new_item( const char* k, const char* v) {
ht_item* i = (ht_item*)malloc(sizeof(ht_item));
i->key = _strdup(k);
i->value = _strdup(v);
return i;
}
static void ht_del_item(ht_item* i) {
free(i->key);
free(i->value);
free(i);
}
void ht_del_hash_table(ht_hash_table* ht) {
for (int i = 0; i < ht->size; i++) {
ht_item* item = ht->items[i];
if (item != NULL) {
ht_del_item(item);
}
}
free(ht->items);
free(ht);
}
static int ht_hash(const char* s, const int a, const int m) {
long hash = 0;
const int len_s = strlen(s);
for (int i = 0; i < len_s; i++) {
hash += (long)pow(a, len_s - (i + 1)) * s[i];
hash = hash % m;
}
return (int)hash;
}
static int ht_get_hash(const char* s, const int num_buckets, const int attempt) {
const int hash_a = ht_hash(s, HT_PRIME_1, num_buckets);
const int hash_b = ht_hash(s, HT_PRIME_2, num_buckets);
return (hash_a + (attempt * (hash_b + 1))) % num_buckets;
}
void ht_insert(ht_hash_table* ht, const char* key, const char* value) {
const int load = ht->count * 100 / ht->size;
if (load > 75) {
ht_resize_up(ht);
}
ht_item* item = ht_new_item(key, value);
int index = ht_get_hash(item->key, ht->size, 0);
ht_item* cur_item = ht->items[index];
int i = 1;
while (cur_item != NULL ) {
if (cur_item != &HT_DELETED_ITEM) {
if (strcmp(cur_item->key, key) == 0) {
ht_del_item(cur_item);
ht->items[index] = item;
return;
}
}
index = ht_get_hash(item->key, ht->size, i);
cur_item = ht->items[index];
i++;
}
ht->items[index] = item;
ht->count++;
}
char* ht_search(ht_hash_table* ht, const char* key) {
int index = ht_get_hash(key, ht->size, 0);
ht_item* item = ht->items[index];
int i = 1;
while (item != NULL) {
if (item != &HT_DELETED_ITEM) {
if (strcmp(item->key, key) == 0) {
return item->value;
}
}
index = ht_get_hash(key, ht->size, i);
item = ht->items[index];
i++;
}
return NULL;
}
void ht_delete(ht_hash_table* ht, const char* key) {
const int load = ht->count * 100 / ht->size;
if (load < 10) {
ht_resize_down(ht);
}
int index = ht_get_hash(key, ht->size, 0);
ht_item* item = ht->items[index];
int i = 1;
while (item != NULL) {
if (item != &HT_DELETED_ITEM) {
if (strcmp(item->key, key) == 0) {
ht_del_item(item);
ht->items[index] = &HT_DELETED_ITEM;
}
}
index = ht_get_hash(key, ht->size, i);
item = ht->items[index];
i++;
}
ht->count--;
}
static ht_hash_table* ht_new_sized(const int base_size) {
ht_hash_table* ht = malloc(sizeof(ht_hash_table));
ht->base_size = base_size;
ht->size = next_prime(ht->base_size);
ht->count = 0;
ht->items = calloc((size_t)ht->size, sizeof(ht_item*));
return ht;
}
ht_hash_table* ht_new() {
return ht_new_sized(HT_INITIAL_BASE_SIZE);
}
static void ht_resize(ht_hash_table* ht, const int base_size) {
if (base_size < HT_INITIAL_BASE_SIZE) {
return;
}
ht_hash_table* new_ht = ht_new_sized(base_size);
for (int i = 0; i < ht->size; i++) {
ht_item* item = ht->items[i];
if (item != NULL && item != &HT_DELETED_ITEM) {
ht_insert(new_ht, item->key, item->value);
}
}
ht->base_size = new_ht->base_size;
ht->count = new_ht->count;
// To delete new_ht, we give it ht's size and items
const int tmp_size = ht->size;
ht->size = new_ht->size;
new_ht->size = tmp_size;
ht_item** tmp_items = ht->items;
ht->items = new_ht->items;
new_ht->items = tmp_items;
ht_del_hash_table(new_ht);
}
static void ht_resize_up(ht_hash_table* ht) {
const int new_size = ht->base_size * 2;
ht_resize(ht, new_size);
}
static void ht_resize_down(ht_hash_table* ht) {
const int new_size = ht->base_size / 2;
ht_resize(ht, new_size);
}//hash_table.c
typedef struct {
char* key;
char* value;
} ht_item;
typedef struct {
int size;
int count;
int base_size;
ht_item** items;
} ht_hash_table;
void ht_insert(ht_hash_table* ht, const char* key, const char* value);
char* ht_search(ht_hash_table* ht, const char* key);
void ht_delete(ht_hash_table* h, const char* key);
//hash_table.h
#pragma once
int is_prime(const int x);
int next_prime(int x);
//prime.h
#include <math.h>
#include "prime.h"
int is_prime(const int x) {
if (x < 2) { return -1; }
if (x < 4) { return 1; }
if ((x % 2) == 0) { return 0; }
for (int i = 3; i <= floor(sqrt((double)x)); i += 2) {
if ((x % i) == 0) {
return 0;
}
}
return 1;
}
int next_prime(int x) {
while (is_prime(x) != 1) {
x++;
}
return x;
}
//prime.c
vs2019报错访问冲突
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- WindMLATGLS 2021-01-11 12:22关注
static ht_item* ht_new_item( const char* k, const char* v) { ht_item* i = (ht_item*)malloc(sizeof(ht_item)); i->key = _strdup(k); i->value = _strdup(v); return i; }
strdup那里报错访问冲突
解决 无用评论 打赏 举报
悬赏问题
- ¥15 centos7系统下abinit安装时make出错
- ¥15 hbuildex运行微信小程序报错
- ¥50 HAL ADCDMA单次触发转换
- ¥15 关于#python#的问题:我知道这个问题对你们来说肯定so easy
- ¥15 wpf datagrid如何实现多层表头
- ¥15 为啥画版图在Run DRC会出现Connect Error?可我Calibre的hostname和计算机的hostname已经设置成一样的了。
- ¥20 网站后台使用极速模式非常的卡
- ¥20 Keil uVision5创建project没反应
- ¥15 mmseqs内存报错
- ¥15 vika文档如何与obsidian同步