从一个简易的哈希表入手，会让你更好的理解php的哈希表，他们的本质是一样的，只是php的哈希表做了更多的功能扩展，php的哈希表是php语言的一个重要核心，大量的内核代码使用到哈希表。
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define HASH_ADD 0
#define HASH_UPDATE 1 typedef unsigned long ulong;
typedef unsigned int uint; typedef struct bucket {
ulong h; //字符数组的key哈希值或者数字数组的key值
uint nKeyLength;//字符数组的key长度，数字数组为0
void *pData;//存储的数据
struct bucket *pListNext;//在哈希表中的下一个元素
struct bucket *pListLast;//在哈希表中的下一个元素
struct bucket *pNext;//哈希值冲突时，同一哈希值链表的下一个元素
struct bucket *pLast;//哈希值冲突时，同一哈希值链表的上一个元素
const char *arKey;//字符数组的key值，数字数组为NULL
} Bucket; typedef struct _hashtable {
uint nTableSize;//哈希表的大小
uint nTableMask;//用来计算哈希值所在当前哈希表的位置
uint nNumOfElements;//哈希表的元素数量
ulong nNextFreeElement;//下一个自动插入的位置
Bucket *pListHead;//哈希表的第一个元素
Bucket *pListTail;//哈希表的最后一个元素
Bucket **arBuckets;//哈希表存储数据的数组
} HashTable; int hash_init(HashTable *ht, uint nSize);
int hash_add(HashTable *ht, const char *arKey, uint nKeyLength, void *pData);
int hash_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData);
int _hash_add_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, int flag);
int hash_index_add(HashTable *ht, ulong h, void *pData);
int hash_index_update(HashTable *ht, ulong h, void *pData);
int hash_foreach(HashTable *ht);
static int hash_resize_if_full(HashTable *ht);
int hash_resize(HashTable *ht);
char * hash_find(HashTable *ht,const char *arKey);
char * hash_index_find(HashTable *ht,ulong h); int hash_init(HashTable *ht, uint nSize){
uint i = ; if (nSize >= 0x80000000) {
/* prevent overflow */
ht->nTableSize = 0x80000000;
} else {
while ((1U << i) < nSize) {
i++;
}
ht->nTableSize = << i;
}
ht->nTableMask = ht->nTableSize - ;
ht->nNumOfElements = ;
ht->nNextFreeElement = ;
ht->pListHead = NULL;
ht->pListTail = NULL;
ht->arBuckets = (Bucket **)calloc(ht->nTableSize,sizeof(Bucket *));
return ;
} static inline ulong hash_func(const char *arKey, uint nKeyLength)
{
register ulong hash = ; /* variant with the hash unrolled eight times */
for (; nKeyLength >= ; nKeyLength -= ) {
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
}
switch (nKeyLength) {
case : hash = ((hash << ) + hash) + *arKey++; /* fallthrough... */
case : hash = ((hash << ) + hash) + *arKey++; /* fallthrough... */
case : hash = ((hash << ) + hash) + *arKey++; /* fallthrough... */
case : hash = ((hash << ) + hash) + *arKey++; /* fallthrough... */
case : hash = ((hash << ) + hash) + *arKey++; /* fallthrough... */
case : hash = ((hash << ) + hash) + *arKey++; /* fallthrough... */
case : hash = ((hash << ) + hash) + *arKey++; break;
case : break;
}
return hash;
} int hash_add(HashTable *ht, const char *arKey, uint nKeyLength, void *pData){
return _hash_add_update(ht, arKey, nKeyLength, pData, HASH_ADD);
} int hash_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData){
return _hash_add_update(ht, arKey, nKeyLength, pData, HASH_UPDATE);
} int _hash_add_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, int flag){
Bucket *p;
ulong h;
ulong nIndex;
h = hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
p = ht->arBuckets[nIndex];
while (p != NULL) {
//printf("nIndex=>%d,arKey=>%s,p=>%s,%s\n",nIndex,arKey,p->arKey,p->pData);
if (p->arKey == arKey){
if(flag == HASH_ADD){
//已经存在同样的key
return -;
}else{
p->pData = pData;
return ;
}
}
p = p->pNext;
}
p = (Bucket *)malloc(sizeof(Bucket));
p->h = h;
p->nKeyLength = nKeyLength;
p->pData = pData;
p->pNext = ht->arBuckets[nIndex];
p->pLast = NULL;
if(p->pNext != NULL){
p->pNext->pLast = p;
}
p->arKey = arKey;
ht->arBuckets[nIndex] = p;
ht->nNumOfElements++;
if(ht->pListHead == NULL){
ht->pListHead = p;
p->pListNext = NULL;
p->pListLast = NULL;
ht->pListTail = p;
}else{
p->pListLast = ht->pListTail;
p->pListLast->pListNext = p;
p->pListNext = NULL;
ht->pListTail = p;
}
hash_resize_if_full(ht);
return ;
} int hash_index_add(HashTable *ht, ulong h, void *pData){
return _hash_index_add_update(ht,h,pData,HASH_ADD);
} int hash_index_update(HashTable *ht, ulong h, void *pData){
return _hash_index_add_update(ht,h,pData,HASH_UPDATE);
} int hash_next_add(HashTable *ht,void *pData){
ulong h = ht->nNextFreeElement;
return _hash_index_add_update(ht,h,pData,HASH_ADD);
} int _hash_index_add_update(HashTable *ht, ulong h,void *pData,int flag){
Bucket *p;
ulong nIndex;
nIndex = h & ht->nTableMask;
p = ht->arBuckets[nIndex];
while (p != NULL) {
if (p->arKey == NULL && p->nKeyLength == ){
if(flag == HASH_ADD){
//已经存在同样的key
return -;
}else{
p->pData = pData;
return ;
}
}
p = p->pNext;
}
p = (Bucket *)malloc(sizeof(Bucket));
p->h = h;
p->nKeyLength = ;
p->pData = pData;
p->pNext = ht->arBuckets[nIndex];
p->pLast = NULL;
if(p->pNext != NULL){
p->pNext->pLast = p;
}
p->arKey = NULL;
ht->arBuckets[nIndex] = p;
ht->nNumOfElements++;
if(h >= ht->nNextFreeElement){
ht->nNextFreeElement = h + ;
}
if(ht->pListHead == NULL){
ht->pListHead = p;
p->pListNext = NULL;
p->pListLast = NULL;
ht->pListTail = p;
}else{
p->pListLast = ht->pListTail;
p->pListLast->pListNext = p;
p->pListNext = NULL;
ht->pListTail = p;
}
hash_resize_if_full(ht);
return ;
} int hash_foreach(HashTable *ht){
if(ht->pListHead == NULL){
return ;
}
Bucket *p;
p = ht->pListHead;
while(p != NULL){
if(p->nKeyLength > ){
printf("h=>%ld,index=>%ld,%s=>%s\n",p->h,p->h & ht->nTableMask,p->arKey,p->pData);
}else{
printf("h=>%ld,index=>%ld,%d=>%s\n",p->h,p->h & ht->nTableMask,p->h,p->pData);
}
p=p->pListNext;
}
} static int hash_resize_if_full(HashTable *ht){
//printf("if_null,num=>%d,size=>%d\n",ht->nNumOfElements,ht->nTableSize);
if(ht->nNumOfElements >= ht->nTableSize){
return hash_resize(ht);
}
} int hash_resize(HashTable *ht){
printf("before resize:%d\n",ht->nTableSize);
hash_foreach(ht);
ht->nTableSize = ht->nTableSize << ;
ht->nTableMask = ht->nTableSize - ;
Bucket **t;
t = realloc(ht->arBuckets,ht->nTableSize * sizeof(Bucket*));
memset(t,,ht->nTableSize * sizeof(Bucket *));
ht->arBuckets = t;
Bucket *p;
ulong nIndex;
for(p=ht->pListHead;p!=NULL;p=p->pListNext){
nIndex = p->h & ht->nTableMask;
p->pNext = ht->arBuckets[nIndex];
if(p->pNext != NULL){
p->pNext->pLast = p;
}
ht->arBuckets[nIndex] = p;
}
printf("after resize:%d\n",ht->nTableSize);
hash_foreach(ht);
return ;
} char * hash_find(HashTable *ht,const char *arKey){
ulong h;
int nKeyLength = strlen(arKey);
h = hash_func(arKey, nKeyLength);
ulong nIndex = h & ht->nTableMask;
Bucket *p;
for(p=ht->arBuckets[nIndex];p!=NULL;p=p->pNext){
if(strcmp(p->arKey,arKey) == && p->nKeyLength == nKeyLength){
return p->pData;
}
printf("hash_find,arKey=>%s,nKeyLength=>%d,pData=>%s\n",p->arKey,p->nKeyLength,p->pData);
}
return NULL;
} char * hash_index_find(HashTable *ht,ulong h){
ulong nIndex = h & ht->nTableMask;
Bucket *p;
for(p=ht->arBuckets[nIndex];p!=NULL;p=p->pNext){
if(p->nKeyLength == && p->arKey == NULL){
return p->pData;
}
}
} int main(){
HashTable *ht;
ht = (HashTable *)malloc(sizeof(HashTable));
hash_init(ht,);//初始化哈希表，nTableSize=1
char *arKey = "keya";
int len = strlen(arKey);
char *pData = "valuea";
hash_add(ht,arKey,len,pData);//插入字符串数据
arKey = "keyb";
len = strlen(arKey);
pData = "valueb";
hash_add(ht,arKey,len,pData);
arKey = "keyb";
len = strlen(arKey);
pData = "valueb";
int ret = hash_add(ht,arKey,len,pData);//插入失败，key已经存在
printf("ret=>%d\n",ret);
char c;
//char buffer[100];
char *buffer;
for(c='c';c<='z';c++){
buffer = (char *)malloc();
sprintf(buffer,"key%c",c);
arKey = buffer;
len = strlen(arKey);
buffer = (char *)malloc();
sprintf(buffer,"value%c",c);
pData = buffer;
printf("%s,%s\n",arKey,pData);
hash_add(ht,arKey,len,pData);//批量插入
}
for(c='A';c<='Z';c++){
buffer = (char *)malloc();
sprintf(buffer,"value%c",c);
pData = buffer;
hash_next_add(ht,pData);//使用数字数组，自动插入元素，不需要指定key
}
hash_index_add(ht,,"index3");//使用数字数组，指定索引位置。
hash_next_add(ht,"");
hash_next_add(ht,"");
hash_index_update(ht,,"100 -> 102");//更新指定位置的值
hash_foreach(ht);//遍历数组
char *finda = hash_find(ht,"keya");//查找指定字符串key的值
printf("finda=>%s\n",finda);
char *findb = hash_index_find(ht,);//查找指定索引的值
printf("findb=>%s\n",findb);
}