本文和大家分享的主要是php內(nèi)核的HashTable相關(guān)使用，希望通過本文的分享，對(duì)大家學(xué)習(xí)php有所幫助。
　　typedef struct _Bucket
　　{
　　char *key;
　　void *value;
　　struct _Bucket *next;
　　} Bucket;
　　typedef struct _HashTable
　　{
　　int size;
　　int elem_num;
　　Bucket** buckets;
　　} HashTable;
　　這個(gè)是一個(gè)簡化過的哈希表結(jié)構(gòu)
　　Bucket是一個(gè)鏈表，而_HashTable用于存儲(chǔ)hash值并指向真正的數(shù)據(jù)儲(chǔ)存單位
　　解決沖突算法DJBX33A
　　而鏈表是為了解決沖突用的，沖突解決采用DJBX33A算法，算法的內(nèi)容如下
　　inlineunsignedtime33(charconst*str,intlen)
　　{
　　unsigned long hash = 5381;
　　/* variant with the hash unrolled eight times */
　　for (; len >= 8; len -= 8) {
　　hash = ((hash << 5) + hash) + *str++;
　　hash = ((hash << 5) + hash) + *str++;
　　hash = ((hash << 5) + hash) + *str++;
　　hash = ((hash << 5) + hash) + *str++;
　　hash = ((hash << 5) + hash) + *str++;
　　hash = ((hash << 5) + hash) + *str++;
　　hash = ((hash << 5) + hash) + *str++;
　　hash = ((hash << 5) + hash) + *str++;
　　}
　　switch (len) {
　　case 7: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
　　case 6: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
　　case 5: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
　　case 4: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
　　case 3: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
　　case 2: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
　　case 1: hash = ((hash << 5) + hash) + *str++; break;
　　case 0: break;
　　}
　　return hash;
　　}
 
HashTable的初始化
　　初始化，申請(qǐng)空間并且設(shè)置初始化值
　　inthash_init(HashTable *ht)
　　{
　　ht->size = HASH_TABLE_INIT_SIZE;
　　ht->elem_num = 0;
　　ht->buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *));
　　if(ht->buckets == NULL) return FAILED;
　　LOG_MSG("[init]\tsize: %i\n", ht->size);
　　return SUCCESS;
　　}
　　HashTable的插入
　　插入函數(shù)，插入時(shí)驗(yàn)證key是否存在，存在更新value值，不存在并取發(fā)生沖突則創(chuàng)建新節(jié)點(diǎn)并插入到原有鏈表的頭部
　　inthash_insert(HashTable *ht,char*key,void*value)
　　{
　　// check if we need to resize the hashtable
　　resize_hash_table_if_needed(ht);
　　int index = HASH_INDEX(ht, key);
　　Bucket *org_bucket = ht->buckets[index];
　　Bucket *tmp_bucket = org_bucket;
　　// check if the key exits already
　　while(tmp_bucket)
　　{
　　if(strcmp(key, tmp_bucket->key) == 0)
　　{
　　LOG_MSG("[update]\tkey: %s\n", key);
　　tmp_bucket->value = value;
　　return SUCCESS;
　　}
　　tmp_bucket = tmp_bucket->next;
　　}
　　Bucket *bucket = (Bucket *)malloc(sizeof(Bucket));
　　bucket->key = key;
　　bucket->value = value;
　　bucket->next = NULL;
　　ht->elem_num += 1;
　　if(org_bucket != NULL)
　　{
　　LOG_MSG("[collision]\tindex:%d key:%s\n", index, key);
　　bucket->next = org_bucket;
　　}
　　ht->buckets[index]= bucket;
　　LOG_MSG("[insert]\tindex:%d key:%s\tht(num:%d)\n",
　　index, key, ht->elem_num);
　　return SUCCESS;
　　}
　　HashTable的擴(kuò)容
　　當(dāng)Hash表容量滿了的時(shí)候，Hash表的性能會(huì)下降，這時(shí)候需要對(duì)Hash表進(jìn)行擴(kuò)容
　　先把原來Hash表容量變成兩倍，然后對(duì)其進(jìn)行重新插入操作，時(shí)間復(fù)雜度為O(n)
　　staticvoidresize_hash_table_if_needed(HashTable *ht)
　　{
　　if(ht->size - ht->elem_num < 1)
　　{
　　hash_resize(ht);
　　}
　　}
　　staticinthash_resize(HashTable *ht)
　　{
　　// double the size
　　int org_size = ht->size;
　　ht->size = ht->size * 2;
　　ht->elem_num = 0;
　　LOG_MSG("[resize]\torg size: %i\tnew size: %i\n", org_size, ht->size);
　　Bucket **buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *));
　　Bucket **org_buckets = ht->buckets;
　　ht->buckets = buckets;
　　int i = 0;
　　for(i=0; i < org_size; ++i)
　　{
　　Bucket *cur = org_buckets ;
　　Bucket *tmp;
　　while(cur)
　　{
　　// rehash: insert again
　　hash_insert(ht, cur->key, cur->value);
　　// free the org bucket, but not the element
　　tmp = cur;
　　cur = cur->next;
　　free(tmp);
　　}
　　}
　　free(org_buckets);
　　LOG_MSG("[resize] done\n");
　　return SUCCESS;
　　}
　　HashTable的查找
　　元素的查找和插入采取相同的策略，都是先獲得hash值，然后取得bucket鏈表，隨后比較鍵名進(jìn)行查找
　　inthash_lookup(HashTable *ht,char*key,void**result)
　　{
　　int index = HASH_INDEX(ht, key);
　　Bucket *bucket = ht->buckets[index];
　　if(bucket == NULL) goto failed;
　　while(bucket)
　　{
　　if(strcmp(bucket->key, key) == 0)
　　{
　　LOG_MSG("[lookup]\t found %s\tindex:%i value: %p\n",
　　key, index, bucket->value);
　　*result = bucket->value;
　　return SUCCESS;
　　}
　　bucket = bucket->next;
　　}
　　failed:
　　LOG_MSG("[lookup]\t key:%s\tfailed\t\n", key);
　　return FAILED;
}

來源：William的后花園