#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashmap.h"
//参考了java的HashMap.java中的hash算法
static int hash(int h)
{
/*
//java
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
*/
unsigned int x = h; //由于要无符号右移,左边补0
x ^= (x >> 20) ^ (x >> 12);
return x ^ (x >> 7) ^ (x >> 4);
}
//参考了java的HashMap.java中的indexFor()
static int indexFor(int h, int length)
{
return h & (length-1);
}
//字符串的hashcode,改写java的String.hashCode();
static int stringHashCode(char *pStr)
{
int size = strlen(pStr);
if(size == 0)
{
return 0;
}
else
{
int i,h=0;
for(i=0; i<size; i++)
{
h = 31 * h + *pStr;
pStr++;
}
return h;
}
}
//扩大容量
static void resize(HashMap this,int newCapacity)
{
//printf("resize 前, capacity:%d,threshold:%d\n",this->capacity,this->threshold);
int oldCapacity = this->capacity;
Entry newTable = malloc(sizeof(struct _entry) * newCapacity);
//初始化为NULL;
int i;
for(i=0; i<newCapacity; i++)
{
(newTable + i)->next = NULL;
}
//由src指向地址为起始地址的连续n个字节的数据复制到以dest指向地址为起始地址的空间内。
//由于hash表的容量扩大,indexFor(int hash,int length)由于length改变,返回值也将改变,所以此处不能简单的使用memcpy
//memcpy(newTable,this->table,sizeof(struct _entry) * oldCapacity);
//重新确定新的位置indexFor(....)
//以下实现参照java的HashMap.java中的void transfer(Entry[] newTable)部分
int m,n;
for(m=0; m<oldCapacity; m++)
{
Entry e = (this->table + m)->next;
if(e!=NULL)
{
do
{
Entry next = e->next;
n = indexFor(e->hash,newCapacity);
e->next = (newTable + n)->next;
(newTable + n)->next = e;
e = next;
}
while(e!=NULL);
}
}
this->table = newTable;
this->capacity = newCapacity;
this->threshold = (int)(newCapacity * this->factor);
//printf("resize 后, capacity:%d,threshold:%d\n\n",this->capacity,this->threshold);
}
//添加一个结点到链表中
static void addEntry(HashMap this,void *k,void *v,int hashCode,int i)
{
Entry e = this->table + i; //先定位到一个链表的head 结点
//添加到链表中
do
{
if(e->next == NULL)
{
//新的结点
Entry item = malloc(sizeof(struct _entry));
item->hash = hashCode;
item->key = k;
item->value = v;
item->next = NULL;
e->next = item; //加入链表中
break;
}
}
while((e = e->next) != NULL);
this->size++; //size + 1
if (this->size >= this->threshold)
{
resize(this,2 * this->size); //扩大一倍容量
}
}
//初始化
void *hashmap_init(int k_e,int v_e)
{
HashMap map = malloc(sizeof(struct _hashmap));
map->K_E = k_e;
map->V_E = v_e;
map->size = 0;
map->capacity = 16;
map->factor = 0.75f;
map->threshold = (int)(map->capacity * map->factor);
map->table = malloc(sizeof(struct _entry) * map->capacity);
//初始化为NULL
int i;
int capacity = map->capacity;
for(i=0; i<capacity; i++)
{
(map->table+i)->next = NULL; //初始化
//printf("init %d address:%d\n",i,map->table + i);
}
//printf("capacity address:%d\n",&map->capacity);
return map;
}
//在此映射中关联指定值与指定键。
void *hashmap_put(HashMap this,void *k,void *v)
{
int hashCode;
if(this->K_E == E_STRING)
{
hashCode = hash(stringHashCode(k));
//printf("-----------%s:%d\n",k,hashCode);
}
else if(this->K_E == E_INT)
{
hashCode = hash(k);
}
else
{
hashCode = hash(k);
}
int i = indexFor(hashCode,this->capacity);
Entry e;
if(this->K_E == E_STRING || this->K_E == E_INT)
{
for(e = this->table + i,e=e->next; e!=NULL; e=e->next)
{
if((e->hash == hashCode) && (e->key == k || strcmp(e->key,k) == 0))
{
void *oldValue = e->value; //取原来的旧的值
e->value = v; //设置新值
return oldValue; //返回旧值
}
}
}
else
{
//这里不太完善,有待改进
for(e = this->table + i,e=e->next; e!=NULL; e=e->next)
{
if((e->hash == hashCode) && e->key == k)
{
void *oldValue = e->value; //取原来的旧的值
e->value = v; //设置新值
return oldValue; //返回旧值
}
}
}
//新的
addEntry(this,k,v,hashCode,i);
return NULL;
}
//返回指定键在此标识哈希映射中所映射的值，如果对于此键来说，映射不包含任何映射关系，则返回 null。
void *hashmap_get(HashMap this,void *k)
{
int hashCode;
if(this->K_E == E_STRING)
{
hashCode = hash(stringHashCode(k));
}
else if(this->K_E == E_INT)
{
hashCode = hash(k);
}
else
{
hashCode = hash(k);
}
int i = indexFor(hashCode,this->capacity);
Entry e;
if(this->K_E == E_STRING || this->K_E == E_INT)
{
for(e=this->table + i,e=e->next; e!=NULL; e=e->next)
{
if(e->hash == hashCode && (e->key == k || strcmp(e->key,k) == 0))
{
return e->value;
}
}
return NULL;
}
else
{
//这里不太完善,有待改进
for(e=this->table + i,e=e->next; e!=NULL; e=e->next)
{
if(e->hash == hashCode && e->key == k)
{
return e->value;
}
}
return NULL;
}
return NULL;
}
//如果此映射中存在该键的映射关系，则将其删除。
//注意在返回处理完成后,free();
void *hashmap_remove(HashMap this,void *k)
{
int hashCode;
if(this->K_E == E_STRING)
{
hashCode = hash(stringHashCode(k));
}
else if(this->K_E == E_INT)
{
hashCode = hash(k);
}
else
{
hashCode = hash(k);
}
int i = indexFor(hashCode,this->capacity);
Entry e;
Entry preE=NULL; //上一个
for(e=this->table+i,preE=e,e=e->next; e!=NULL; preE=e,e=e->next)
{
if(e->hash == hashCode && (e->key == k || strcmp(e->key,k) == 0))
{
if(e->next == NULL)
{
preE->next = NULL;
}
else
{
preE->next = e->next; //将此结点删除
}
e->next = NULL; //设置为NULL
this->size--; //size - 1
//free(e); //这里释放内存后,为什么下面还能正常返回值?
return e->value;
}
}
return NULL;
}
//返回此映射中所包含的键的 set 视图
//注意在返回处理完成后,free();
HashMapSet hashmap_keySet(HashMap this)
{
int size = this->size;
if(size == 0)
{
return NULL;
}
else
{
HashMapSet set = malloc(sizeof(struct _hashmapset));
set->key = NULL;
set->next = NULL;
int i;
Entry e;
HashMapSet preSet = set; //上一个Set
int capacity = this->capacity;
for(i=0; i<capacity; i++)
{
for(e = this->table + i,e=e->next; e!=NULL; e=e->next)
{
if(preSet->key == NULL)
{
//第一次赋值
preSet->key = e->key;
preSet->next = NULL;
}
else
{
//添加一个新结点
HashMapSet item = malloc(sizeof(struct _hashmapset));
item->key = e->key;
item->next = NULL;
preSet->next = item;
preSet = item; //
}
}
}
return set;
}
}
//从此映射中移除所有映射关系。
void hashmap_clear(HashMap this)
{
int capacity = this->capacity;
int i;
Entry e,item;
for(i=0; i<capacity; i++)
{
for(e = this->table + i,e=e->next; e!=NULL; item = e,e=e->next,free(item))
{
}
(this->table + i)->next = NULL; //重置为NULL
}
//free(this->table);
this->size = 0;
}
//释放内存
void hashmap_free(HashMap this)
{
int capacity = this->capacity;
Entry e,item;
int i;
for(i=0; i<capacity; i++)
{
for(e=this->table + i, e=e->next; e!=NULL; item=e,e=e->next,free(item))
{
}
}
this->capacity = 0;
this->size = 0;
free(this->table);
free(this);
}