又修改了一下,实现了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)是Java编程语言中广泛使用的数据结构之一,主要提供键值对的存储和查找功能。HashMap的实现基于哈希表的概念,它通过计算对象的哈希码来快速定位数据,从而实现了O(1)的平均时间复杂度。在深入...
hashmap的C++实现,对于学习C++方面的很有用
用js代码实现java中hashmap 的所有功能
Java语言使用hashmap实现向购物车添加删除修改商品,显示商品信息
C语言实现hashMap,包含创建hashMap、插入hashMap、查找hashMap、删除hashMap,已经若干经典的hash函数。文章链接:https://blog.csdn.net/sxf1061700625/article/details/109594495
listview实现,hashmaplistview实现,hashmaplistview实现,hashmaplistview实现,hashmaplistview实现,hashmaplistview实现,hashmaplistview实现,hashmaplistview实现,hashmap
- **HashMap**:HashMap是Java集合框架的一部分,它通过哈希函数将键(Key)映射到对应的值(Value),形成键值对。键必须是唯一的,而值可以重复。 - **哈希表**:HashMap的核心数据结构是哈希表,通常由一个数组...
HashMap的核心思想是通过哈希函数将键(key)映射到一个桶(bucket)中,以此实现快速存取。在JavaScript中,我们可以利用对象(object)作为HashMap的基础,因为JavaScript的对象本质上就是一个键值对的集合,其...
标题中的“asp hashmap,arraylist实现”指的是在ASP(Active Server Pages)编程中使用HashMap和ArrayList这两种数据结构的具体应用。HashMap和ArrayList是.NET框架中常用的数据集合类,它们在处理和组织数据方面各...
本话题主要关注如何利用HashMap这一数据结构来实现词典查询,以提供快速、便捷的字典服务。HashMap是Java编程语言中的一种内置数据结构,它提供了O(1)的平均时间复杂度来执行查找、插入和删除操作,这使得它成为构建...
在Java编程中,HashMap是一个非常重要的数据结构,它实现了Map接口,提供了键值对的存储功能,具有快速存取和高效查找的特点。HashMap基于哈希表(也称为散列表)原理,通过键对象的哈希码来定位元素,进而实现O(1)...
这篇博客“基于JavaScript的HashMap实现”可能详细阐述了如何通过自定义函数来创建一个高效且灵活的HashMap数据结构。 在JavaScript中,对象(Object)是哈希表的一种表现形式,其内部通过键(key)来定位值(value...
HashMap是一个基于哈希表实现的键值对存储结构,它提供了快速的插入、删除和查找操作,平均时间复杂度为O(1)。HashMap非线程安全,适合于单线程环境或已经通过并发工具类控制并发的场景。 二、HashMap底层原理 ...
在Java编程语言中,集合框架是开发者日常工作中不可或缺的一部分,HashMap作为其中的重要成员,它的实现原理对于理解Java性能优化和数据结构有深远的意义。HashMap是一个基于哈希表的数据结构,它实现了Map接口,...
HashMap是Java中常用的一种数据结构,它基于哈希表实现,提供快速的键值对存储和检索。HashMap的核心原理是通过散列函数将键对象转换为哈希码,然后使用这个哈希码来确定键值对在内部数组中的位置。哈希函数的设计...
在这个"用HashMap写的一个小Demo用来写游戏排名的一种方法"的示例中,我们很可能会看到如何利用HashMap来组织游戏分数并进行排序,以实现一个简单的游戏排名系统。 HashMap的特点在于它的键(key)是唯一的,每个键...
HashMap是Java集合框架的一个重要组成部分,它实现了Map接口,能够存储键值对映射。在Java编程语言中,最基本的数据结构有两种:数组和引用(模拟指针)。所有的复杂数据结构都可以基于这两种基本结构构建出来,...
HashMap类在Java编程语言中是集合框架的一部分,它是一个基于哈希表的Map接口实现。HashMap提供了快速的插入、删除和查找操作,平均时间复杂度为O(1)。在这个压缩包“HashMap类.rar”中,包含的是易语言版本的...
HashMap是Java编程语言中一个非常重要的数据结构,它属于集合框架的一部分,主要用于存储键值对(Key-Value)数据。HashMap在内部实现上基于哈希表,也称为散列表,它提供了一种快速查找、插入和删除数据的方法,...