当前位置：网站首页>【哈希表】改进，拉链法哈希结构——直接用两个索引查找，不用每次都hash和%一遍
【哈希表】改进，拉链法哈希结构——直接用两个索引查找，不用每次都hash和%一遍
2022-06-26 02:48:00 【苏念心】
前言
古神以力破天，古魔杀戮逆天，古妖翻手灭道！
\;\\\;\\\;
Hash.h
//哈希表的容量，每个空就是一个bucket桶
#define HashTable_BUCKET_SIZE 50
//哈希坐标
typedef struct HashTable_coord{
u4 i; //数组索引
u4 j; //链表上的位置，从0开始
}HashTable_coord;
//哈希元素
typedef struct HashTable_kv{
struct HashTable_kv* next;
HashTable_coord co;
STRING* k;
void* v;
}HashTable_kv;
//哈希表
typedef struct HashTable {
struct HashTable_kv* tab[HashTable_BUCKET_SIZE];
}HashTable;
HashTable* newHashTable();
void destroyHashTable(HashTable* h);
HashTable_coord* putHashTable(HashTable* h,STRING* key, void* value); //push是从后面添加，put是插入
void* atHashTable(HashTable* h, HashTable_coord* co);
void delHashTable(HashTable* h, HashTable_coord* co);
u4 hash(STRING* key);
void printHashTable(HashTable* h, void(*print)(void*));
void printkvHashTable(HashTable* h,u4 position,void(*print)(void*));
\;\\\;\\\;
Hash.c
HashTable* newHashTable() {
HashTable* h = (HashTable*)malloc(sizeof(HashTable));
ASTRINGERT(h == null, "哈希表创建失败");
for (u4 i = 0; i < HashTable_BUCKET_SIZE; ++i)
h->tab[i] = null;
return h;
}
void destroyHashTable(HashTable* h) {
ASTRINGERT(h == null, "哈希表为空");
if (h!= null)
free(h);
}
HashTable_coord* putHashTable(HashTable* h, STRING* key, void* value) {
ASTRINGERT(h == null, "哈希表为空");
ASTRINGERT(key == null, "输入key为空");
ASTRINGERT(value == null, "输入value为空"); //不存在只有name没有值的标识符
u4 hashcode = hash(key);
//看看是否有冲突
u4 tmp = hashcode % HashTable_BUCKET_SIZE;
if (h->tab[tmp] == null) {
//无冲突
HashTable_kv* kv = (HashTable_kv*)malloc(sizeof(HashTable_kv));
ASTRINGERT(kv == null, "HashTable_kv创建失败1");
kv->co.i = tmp;
kv->co.j = 0;
kv->k = key;
kv->v = value;
kv->next = null;
h->tab[tmp] = kv;
return &(kv->co);
}
else {
//有冲突
//加在链表后面
HashTable_kv* it = h->tab[tmp];
u4 p = 1;
for (; it->next != null; it = it->next,++p){
}
//创建新的kv
HashTable_kv* kv = (HashTable_kv*)malloc(sizeof(HashTable_kv));
ASTRINGERT(kv == null, "HashTable_kv创建失败2");
kv->co.i = tmp;
kv->co.j = p;
kv->k = key;
kv->v = value;
kv->next = null;
it->next = kv;
return &(kv->co);
}
}
void* atHashTable(HashTable* h, HashTable_coord* co) {
ASTRINGERT(h == null, "哈希表为空");
ASTRINGERT(co->i > HashTable_BUCKET_SIZE, "哈希数组索引非法");
HashTable_kv* it = h->tab[co->i];
for (u4 i = 0;i<=co->j; ++i,it=it->next)
if (it == null)
return null;//没找到 ，找到之前的元素都不为空
return it->v;
}
void delHashTable(HashTable* h, HashTable_coord* co) {
ASTRINGERT(h == null, "哈希表为空");
ASTRINGERT(co->i >= HashTable_BUCKET_SIZE, "哈希数组索引非法");
HashTable_kv* it = h->tab[co->i];
if (it == null)
return;//不用找了
//删除头节点，就剩这个了
if (it->next == null) {
h->tab[co->i] = null;
return;
}
HashTable_kv* pre = ⁢
for (u4 i = 0; i < co->j ; ++i) {
pre = it;
it = it->next;
if (it == null)
return;
}
if (it->next != null) {
//不是最后一个
//后面的j都要减一
for (HashTable_kv* i = it->next; i != null; i=i->next)
--i->co.j;
*it = *(it->next); //后一个前移
}
else //最后一个
pre->next = null;
}
u4 hash(STRING* key) {
ASTRINGERT(key == null, "安全字符串为空");
ASTRINGERT(key->len == 0, "hash传入字符串为空");
//magic number
u4 seed = 131; /* 31 131 1313 13131 131313 etc.. */
u4 h = 0;
for (u4 i = 0; i < key->len; ++i)
h = (h * seed) + (key->s[i]) ;
return h;
}
void printHashTable(HashTable* h, void(*print)(void*)) {
ASTRINGERT(h == null, "哈希表为空");
for (u4 i = 0; i < HashTable_BUCKET_SIZE; ++i) {
printf("[%5d]",i);
HashTable_kv* it = h->tab[i];
if (it == null) {
printf("\n");
continue;
}
for (;it!=null;it=it->next) {
printf("[%7s,", it->k->s);
print(it->v);
if (it->next != null)
printf("]->");
else
printf("]");
}
printf("\n");
}
}
void printkvHashTable(HashTable* h, u4 position,void(*print)(void*)) {
ASTRINGERT(h == null, "哈希表为空");
ASTRINGERT(position >= HashTable_BUCKET_SIZE, "位置非法");
printf("[%5d]",position);
HashTable_kv* it = h->tab[position];
if (it == null) {
printf("\n");
return;
}
for (; it != null; it = it->next) {
printf("[%7s,", it->k->s);
print(it->v);
if (it->next != null)
printf("]->");
else
printf("]");
}
printf("\n");
}
\;\\\;\\\;
使用方法
u8 start_time = GetTickCount64();
//测试哈希表
HashTable* h = newHashTable();
#define NUM 50
char v1[20], v2[20];
static HashTable_coord* po[NUM];
static STRING* key[NUM];
static STRING* value[NUM];
for (u4 i = 0; i < NUM; ++i) {
key[i] = newSTRING(20);
memset(v1, 0, 20);
sprintf(v1, "[email protected]%d", i);
moveSTRING(key[i], v1, 0, 19);
value[i] = newSTRING(20);
memset(v2, 0, 20);
sprintf(v2, "[email protected]%d", i);
moveSTRING(value[i], v2, 0, 19);
po[i] = putHashTable(h, key[i], value[i]);
}
printHashTable(h, myprint);
delHashTable(h, po[4]);
printHashTable(h, myprint);
printf("cost %llu ms\n", GetTickCount64() - start_time);
\;\\\;\\\;
结果
[ 0][ [email protected]36, [email protected]36]
[ 1][ [email protected]37, [email protected]37]
[ 2][ [email protected]38, [email protected]38]
[ 3][ [email protected]39, [email protected]39]
[ 4]
[ 5]
[ 6]
[ 7]
[ 8]
[ 9]
[ 10]
[ 11]
[ 12]
[ 13][ [email protected]20, [email protected]20]
[ 14][ [email protected]21, [email protected]21]
[ 15][ [email protected]22, [email protected]22]
[ 16][ [email protected]23, [email protected]23]
[ 17][ [email protected]24, [email protected]24]
[ 18][ [email protected]25, [email protected]25]
[ 19][ [email protected]26, [email protected]26]
[ 20][ [email protected]27, [email protected]27]
[ 21][ [email protected]28, [email protected]28]
[ 22][ [email protected]29, [email protected]29]
[ 23]
[ 24]
[ 25][ [email protected]40, [email protected]40]
[ 26][ [email protected]41, [email protected]41]
[ 27][ [email protected]42, [email protected]42]
[ 28][ [email protected]43, [email protected]43]
[ 29][ [email protected]0, [email protected]0]->[ [email protected]44, [email protected]44]
[ 30][ [email protected]1, [email protected]1]->[ [email protected]45, [email protected]45]
[ 31][ [email protected]2, [email protected]2]->[ [email protected]46, [email protected]46]
[ 32][ [email protected]3, [email protected]3]->[ [email protected]10, [email protected]10]->[ [email protected]47, [email protected]47]
[ 33][ [email protected]4, [email protected]4]->[ [email protected]11, [email protected]11]->[ [email protected]48, [email protected]48]
[ 34][ [email protected]5, [email protected]5]->[ [email protected]12, [email protected]12]->[ [email protected]49, [email protected]49]
[ 35][ [email protected]6, [email protected]6]->[ [email protected]13, [email protected]13]
[ 36][ [email protected]7, [email protected]7]->[ [email protected]14, [email protected]14]
[ 37][ [email protected]8, [email protected]8]->[ [email protected]15, [email protected]15]
[ 38][ [email protected]9, [email protected]9]->[ [email protected]16, [email protected]16]
[ 39][ [email protected]17, [email protected]17]
[ 40][ [email protected]18, [email protected]18]
[ 41][ [email protected]19, [email protected]19]
[ 42]
[ 43]
[ 44][ [email protected]30, [email protected]30]
[ 45][ [email protected]31, [email protected]31]
[ 46][ [email protected]32, [email protected]32]
[ 47][ [email protected]33, [email protected]33]
[ 48][ [email protected]34, [email protected]34]
[ 49][ [email protected]35, [email protected]35]
[ 0][ [email protected]36, [email protected]36]
[ 1][ [email protected]37, [email protected]37]
[ 2][ [email protected]38, [email protected]38]
[ 3][ [email protected]39, [email protected]39]
[ 4]
[ 5]
[ 6]
[ 7]
[ 8]
[ 9]
[ 10]
[ 11]
[ 12]
[ 13][ [email protected]20, [email protected]20]
[ 14][ [email protected]21, [email protected]21]
[ 15][ [email protected]22, [email protected]22]
[ 16][ [email protected]23, [email protected]23]
[ 17][ [email protected]24, [email protected]24]
[ 18][ [email protected]25, [email protected]25]
[ 19][ [email protected]26, [email protected]26]
[ 20][ [email protected]27, [email protected]27]
[ 21][ [email protected]28, [email protected]28]
[ 22][ [email protected]29, [email protected]29]
[ 23]
[ 24]
[ 25][ [email protected]40, [email protected]40]
[ 26][ [email protected]41, [email protected]41]
[ 27][ [email protected]42, [email protected]42]
[ 28][ [email protected]43, [email protected]43]
[ 29][ [email protected]0, [email protected]0]->[ [email protected]44, [email protected]44]
[ 30][ [email protected]1, [email protected]1]->[ [email protected]45, [email protected]45]
[ 31][ [email protected]2, [email protected]2]->[ [email protected]46, [email protected]46]
[ 32][ [email protected]3, [email protected]3]->[ [email protected]10, [email protected]10]->[ [email protected]47, [email protected]47]
[ 33][ [email protected]11, [email protected]11]->[ [email protected]48, [email protected]48]
[ 34][ [email protected]5, [email protected]5]->[ [email protected]12, [email protected]12]->[ [email protected]49, [email protected]49]
[ 35][ [email protected]6, [email protected]6]->[ [email protected]13, [email protected]13]
[ 36][ [email protected]7, [email protected]7]->[ [email protected]14, [email protected]14]
[ 37][ [email protected]8, [email protected]8]->[ [email protected]15, [email protected]15]
[ 38][ [email protected]9, [email protected]9]->[ [email protected]16, [email protected]16]
[ 39][ [email protected]17, [email protected]17]
[ 40][ [email protected]18, [email protected]18]
[ 41][ [email protected]19, [email protected]19]
[ 42]
[ 43]
[ 44][ [email protected]30, [email protected]30]
[ 45][ [email protected]31, [email protected]31]
[ 46][ [email protected]32, [email protected]32]
[ 47][ [email protected]33, [email protected]33]
[ 48][ [email protected]34, [email protected]34]
[ 49][ [email protected]35, [email protected]35]
cost 78 ms
\;\\\;\\\;
边栏推荐
- [QT] custom control - air quality dashboard
- arduino字符串转16进制数 大彩串口屏用。
- Problems encountered in project deployment - production environment
- Use annotationdbi to convert gene names in R
- 图扑软件数字孪生海上风电 | 向海图强，奋楫争先
- Camtasia 2022全新版超清錄制電腦視頻
- UE5全局光照系统Lumen解析与优化
- Record a torture bug caused by restcontrol and controller
- 应届毕业生谈毕业的故事
- Clion项目中运行多个main函数
猜你喜欢
2021-08-04
Lumen Analysis and Optimization of ue5 global Lighting System
MySQL增删查改(进阶)
Network PXE starts winpe and supports UEFI and legacy boot
The "eye" of industrial robot -- machine vision
What can Arthas do for you?
Hardware creation principle of campus maker space
Analysis on the diversification of maker space mechanism construction
Camtasia 2022 nouvelle vidéo d'ordinateur d'enregistrement ultra - clair
Notes on the 3rd harmonyos training in the studio
随机推荐
Camtasia 2022 nouvelle vidéo d'ordinateur d'enregistrement ultra - clair
[solution] cmake was unable to find a build program corresponding to "UNIX makefiles"
[machinetranslation] - Calculation of Bleu value
【论文笔记】Supersizing Self-supervision: Learning to Grasp from 50K Tries and 700 Robot Hours
Please advise tonghuashun which securities firm to choose for opening an account? Is it safe to open an account online?
Modifying table names, deleting tables, obtaining table information, and deleting table records on specified dates for common MySQL statements
数据库查询语句SQL中like、%、-的区别
Utonmos adheres to the principle of "collection and copyright" to help the high-quality development of traditional culture
ArrayList＃subList这四个坑，一不小心就中招
stm32Cubemx:看门狗------独立看门狗和窗口看门狗
Win10 computer power management turns on excellence mode
R language Markov chain Monte Carlo: practical introduction
附加：HikariCP连接池简述；（并没有深究，只是对HikariCP连接池有个基本认识）
Distributed e-commerce project grain mall learning notes ＜ 3 ＞
Business process diagram design
UE5全局光照系统Lumen解析与优化
I am in Zhongshan. Where can I open an account? Is it safe to open an account online?
《你不可不知的人性》经典语录
Little p weekly Vol.10
应届毕业生谈毕业的故事