又修改了一下,实现了resize
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <math.h>
typedef struct bucket{
int h;
char* key;
void* pData;
struct bucket* pNext;
struct bucket* pLast;
}Bucket;
typedef struct hashtable{
int size;
int elementsNum;
int mask;
Bucket** arBuckets; //这是一个存放buckets的array
}HashTable;
/**
** 这是一个计算HASH值的算法
**/
int time33(char* arKey,int arlength){
int h = 0;
int i;
for(i=0;i<arlength;i++){
h = h*33 + (int)*arKey++;
}
return h;
}
/**
** 初始化一个大小是1的HASHTABLE
**/
int _init_hash_table(HashTable** ht){
*ht = (HashTable*)malloc(sizeof(HashTable));
(*ht)->size = 1;
(*ht)->mask = (*ht)->size - 1;
(*ht)->elementsNum = 1;
(*ht)->arBuckets = (Bucket**)malloc(sizeof(Bucket*)*(*ht)->size);
memset((*ht)->arBuckets,0,sizeof(Bucket*)*(*ht)->size);
return 1;
}
int _hash_link_bucket_to_bucket_head(Bucket** newBucket,Bucket** bucketHead){
if(*bucketHead==NULL){
*bucketHead = *newBucket;
}else{
(*newBucket)->pNext = (*bucketHead)->pNext;
(*newBucket)->pLast = (*bucketHead);
if((*bucketHead)->pNext != NULL){
(*bucketHead)->pNext->pLast = *newBucket;
}
(*bucketHead)->pNext = *newBucket;
}
return 1;
}
int _hash_new_bucket(Bucket** newBucket,int hash,char* arkey,void* pData){
(*newBucket) = (Bucket*)malloc(sizeof(Bucket));
(*newBucket)->h = hash;
(*newBucket)->key = arkey;
(*newBucket)->pData = pData;
(*newBucket)->pNext = NULL;
(*newBucket)->pLast = NULL;
return 1;
}
int _hash_rehash(HashTable* ht){
int i = 0;
//由于我没定义pListNext指针,所以只能这样rehash了。
for( ; i<ht->size ; i++){
if(ht->arBuckets[i] != NULL){
int index = ht->arBuckets[i]->h & ht->mask ;
if(i != index){
_hash_link_bucket_to_bucket_head(&ht->arBuckets[i],&ht->arBuckets[index]);
ht->arBuckets[i] = NULL;
}
}
}
return 1;
}
/**
** 将HASHTABLE的大小扩容1倍
**/
int _hash_resize(HashTable* ht){
if(ht != NULL){
ht->size = ht->size << 1;
ht->mask = ht->size - 1;
realloc(&ht->arBuckets,sizeof(Bucket*) * ht->size);
int i;
for(i=ht->size>>1;i<ht->size;i++){
ht->arBuckets[i] = NULL;
}
//memset(ht->arBuckets[0],NULL,sizeof(Bucket*) * (ht->size >> 1));
printf("resize:%i\r\n", ht->size);
_hash_rehash(ht);
return 1;
}
return 0;
}
/**
** 往HASHTABLE中添加元素
**/
int _hash_add_or_update(HashTable* ht,char* arKey,int arLength,void* pData){
int h = time33(arKey,arLength);
int index = h & ht->mask;
Bucket* p = ht->arBuckets[index];
while(p!=NULL){
if(strcmp(arKey,p->key)==0){
//这里应该执行更新操作
free(p->pData);
p->pData = pData;
return 1;
}
p = p->pNext;
}
Bucket* newBucket;
_hash_new_bucket(&newBucket,h,arKey,pData);
_hash_link_bucket_to_bucket_head(&newBucket,&ht->arBuckets[index]);
ht->elementsNum++;
if(ht->elementsNum = ht->size){
_hash_resize(ht);
}
return 0;
}
void* _hash_find(HashTable* ht,char* arKey,int arLength){
int h = time33(arKey,arLength);
int index = h & ht->mask;
Bucket* p = ht->arBuckets[index];
while(p!=NULL){
if(strcmp(arKey,p->key)==0){
return p->pData;
}
p = p->pNext;
}
return 0;
}
int PUT(HashTable* ht,void* key,void* value){
char* arKey = (char*)key;
int len = strlen(arKey);
return _hash_add_or_update(ht,arKey,len,value);
}
void* GET(HashTable* ht,void* key){
char* arKey = (char*)key;
int len = strlen(arKey);
return _hash_find(ht,arKey,len);
}
int main(){
printf("%s\r\n","这是一个hashtable的例子");
HashTable* ht;
_init_hash_table(&ht);
PUT(ht,"1","mengjun");
PUT(ht,"2","aaaaa");
PUT(ht,"3","fff");
PUT(ht,"24","eee");
PUT(ht,"25","ddd");
printf("%s\r\n",(char*)GET(ht,"1"));
printf("%s\r\n",(char*)GET(ht,"2"));
printf("%s\r\n",(char*)GET(ht,"3"));
printf("%s\r\n",(char*)GET(ht,"24"));
printf("%s\r\n",(char*)GET(ht,"25"));
printf("HASHTABLE总共有元素%i个\r\n",ht->elementsNum);
return 0;
}
分享到:
相关推荐
hashmap的底层及源码解析,很适合大家的学习,不要积分。
hashmap的C++实现,对于学习C++方面的很有用
用js代码实现java中hashmap 的所有功能
HashMap底层实现原理HashMap与HashTable区别HashMap与HashSet区别。HashMap、HashTable和HashSet是Java中常用的数据结构,它们的底层实现原理以及区别如下:HashMap底层实现原理: HashMap基于哈希表(HashTable)...
Java语言使用hashmap实现向购物车添加删除修改商品,显示商品信息
listview实现,hashmaplistview实现,hashmaplistview实现,hashmaplistview实现,hashmaplistview实现,hashmaplistview实现,hashmaplistview实现,hashmaplistview实现,hashmap
Javascript实现和操作HashMap,压缩包里面有hashmap定义和操作的例子
C语言实现hashMap,包含创建hashMap、插入hashMap、查找hashMap、删除hashMap,已经若干经典的hash函数。文章链接:https://blog.csdn.net/sxf1061700625/article/details/109594495
用数据结构的思想实现java中的类hashmap
HashMap数据结构,HashMap的构造方法,HashMap的put,HashMap的get
HashMap的实现原理
一线大厂BATJ面试题讲解-hashmap原理实现
用hashmap结构将字典文件中的词条装入内存,并基于该结构进行查询
一个用于js里面 用javascript实现的HashMap类
HashMap重写实现 轻量级实现 使用自定义的轻量对象HashObjectMap替代jdk的HahMap HashMap里的Entry占用较大内存,可以用自己实现的轻量级容器替换,步骤如下: 1、 缓存的对象需要继承BaseHashObject /** * 这个类...
hashMap排序,hashmap使用还是比较频繁。这时自己写的一个实现hashmap排序的例子
HashMap介绍和使用
用HashMap写的一个小的一个游戏排名的小demo。
hashmap实例 hashmap实例hashmap实例hashmap实例
hashmap实现原理.pdf