第二节 哈希表(HashTable)

• 键(key)：用于操作数据的标示，例如PHP数组中的索引，或者字符串键等等。
• 槽(slot/bucket)：哈希表中用于保存数据的一个单元，也就是数据真正存放的容器。
• 哈希函数(hash function)：将key映射(map)到数据应该存放的slot所在位置的函数。
• 哈希冲突(hash collision)：哈希函数将两个不同的key映射到同一个索引的情况。

h(key) -> index

NOTE 在笔者编写这节内容的时候PHP语言也采取了相应的措施来防止这类的攻击，PHP采用的是一种 治标不治本的做法: 限制用户提交数据字段数量 这样可以避免大部分的攻击，不过应用程序通常会有很多的数据输入方式，比如，SOAP，REST等等， 比如很多应用都会接受用户传入的JSON字符串，在执行json_decode()的时候也可能会遭受攻击。 所以最根本的解决方法是让哈希表的碰撞key序列无法轻易的构造，目前PHP中还没有引入不增加额外的复杂性情况下的完美解决方案。

NOTE 装载因子 是哈希表保存的元素数量和哈希表容量的比，通常采用链接法解决冲突的哈希表的装载 因子最好不要大于1，而采用开放寻址法的哈希表最好不要大于0.5。

1. 实现哈希函数
2. 冲突的解决
3. 操作接口的实现

[c]
typedef struct _Bucket
{
	char *key;
	void *value;
	struct _Bucket *next;
} Bucket;
typedef struct _HashTable
{
	int size;
	int elem_num;
	Bucket** buckets;
} HashTable;

[c]
static int hash_str(char *key)
{
	int hash = 0;
	char *cur = key;
	while(*cur != '\0') {
		hash +=	*cur;
		++cur;
	}
	return hash;
}
// 使用这个宏来求得key在哈希表中的索引
#define HASH_INDEX(ht, key) (hash_str((key)) % (ht)->size)

[c]
int hash_init(HashTable *ht);  								// 初始化哈希表
int hash_lookup(HashTable *ht, char *key, void **result);	// 根据key查找内容
int hash_insert(HashTable *ht, char *key, void *value);		// 将内容插入到哈希表中
int hash_remove(HashTable *ht, char *key);					// 删除key所指向的内容
int hash_destroy(HashTable *ht);

[c]
int hash_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;
}

[c]
int hash_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;
}

[c]
static void resize_hash_table_if_needed(HashTable *ht)
{
	if(ht->size - ht->elem_num < 1)
	{
		hash_resize(ht);
	}
}
static int hash_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[i];
		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;
}

[c]
int hash_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;
}

NOTE 本小节的HashTable实例完整代码可以在$TIPI_ROOT/book/sample/chapt03/03-01-01-hashtable目录中找到。 或者在GitHub上浏览: https://github.com/reeze/tipi/tree/master/book/sample/chapt03/03-01-01-hashtable

• 《Data.Structures.and.Algorithm.Analysis.in.C》
• 《算法导论: 第二版》