1. php hash表 0x1: 基本概念
哈希表在实践中使用的非常广泛，例如编译器通常会维护的一个符号表来保存标记，很多高级语言中也显式的支持哈希表。 哈希表通常提供查找(search)，插入(insert)，删除(delete)等操作，这些操作在最坏的情况
下和链表的性能一样为o(n)。 不过通常并不会这么坏，合理设计的哈希算法能有效的避免这类情况，通常哈希表的这些操作时间复杂度为o(1)。 这也是它被钟爱的原因
正是因为哈希表在使用上的便利性及效率上的表现，目前大部分动态语言的实现中都使用了哈希表
哈希表是一种通过哈希函数，将特定的键映射到特定值的一种数据结构，它维护键和值之间一一对应关系
1. 键(key): 用于操作数据的标示，例如php数组中的索引，或者字符串键等等 2. 槽(slot/bucket): 哈希表中用于保存数据的一个单元，也就是数据真正存放的容器 3. 哈希函数(hash function): 将key映射(map)到数据应该存放的slot所在位置的函数 4. 哈希冲突(hash collision): 哈希函数将两个不同的key映射到同一个索引的情况
哈希表可以理解为数组的扩展或者关联数组，数组使用数字下标来寻址，如果关键字(key)的范围较小且是数字的话， 我们可以直接使用数组来完成哈希表，而如果关键字范围太大，如果直接使用数组我们需要为所有可能的key申请空间。 很多情况下这是不现实的。即使空间足够，空间利用率也会很低，这并不理想。同时键也可能并不是数字， 在php中尤为如此，所以人们使用一种映射函数(哈希函数)来将key映射到特定的域中
h(key) -> index
通过合理设计的哈希函数，我们就能将key映射到合适的范围，因为我们的key空间可以很大(例如字符串key)， 在映射到一个较小的空间中时可能会出现两个不同的key映射被到同一个index上的情况， 这就是我们所说的出现了冲突。 目前解决hash冲突的方法主要有两种：链接法和开放寻址法
1. 冲突解决: 链接法
链接法通过使用一个链表来保存slot值的方式来解决冲突，也就是当不同的key映射到一个槽中的时候使用链表来保存这些值。 所以使用链接法是在最坏的情况下，也就是所有的key都映射到同一个槽中了，这样哈希表就退化成了一个链表， 这样的话操作链表的时间复杂度则成了o(n)，这样哈希表的性能优势就没有了， 所以选择一个合适的哈希函数是最为关键的
由于目前大部分的编程语言的哈希表实现都是开源的，大部分语言的哈希算法都是公开的算法， 虽然目前的哈希算法都能良好的将key进行比较均匀的分布，而这个假使的前提是key是随机的，正是由于算法的确定性， 这就导致了别有用心的黑客能利用已知算法的可确定性来构造一些特殊的key，让这些key都映射到同一个槽位导致哈希表退化成单链表，导致程序的性能急剧下降，从而造成一些应用的吞吐能力急剧下降， 尤其是对于高并发的应用影响很大，通过大量类似的请求可以让服务器遭受dos(服务拒绝攻击)
哈希冲突攻击利用的哈希表最根本的弱点是:
开源算法和哈希实现的确定性以及可预测性， 这样攻击者才可以利用特殊构造的key来进行攻击。要解决这个问题的方法则是让攻击者无法轻易构造 能够进行攻击的key序列
目前php中hashtable的哈希冲突解决方法就是链接法
2. 冲突解决: 开放寻址法
通常还有另外一种解决冲突的方法：开放寻址法。使用开放寻址法是槽本身直接存放数据，在插入数据时如果key所映射到的索引已经有数据了，这说明发生了冲突，这是会寻找下一个槽， 如果该槽也被占用了则继续寻找下一个槽，直到寻找到没有被占用的槽，在查找时也使用同样的策略来进行 由于开放寻址法处理冲突的时候占用的是其他槽位的空间,这可能会导致后续的key在插入的时候更加容易出现 哈希冲突，所以采用开放寻址法的哈希表的装载因子不能太高，否则容易出现性能下降
装载因子是哈希表保存的元素数量和哈希表容量的比1. 通常采用链接法解决冲突的哈希表的装载，因子最好不要大于1(等于1意味着hash表已经存满了，接下来开始保存的键值都会导致冲突发生即链表增长，而链表的效率是低于hash表的)2. 而采用开放寻址法的哈希表最好不要大于0.5
0x2: 哈希表的实现
实现一个哈希表也很容易，主要需要完成的工作只有三点
1. 实现哈希函数2. 冲突的解决3. 操作接口的实现
在开始学习php原生内核的hash表实现前，我们自己可以先手工实现一个简易版的hash表
1. 基础数据结构定义
#ifndef _hash_table_h_#define _hash_table_h_ 1typedef struct _bucket{ char *key; void *value; struct _bucket *next;} bucket;typedef struct _hashtable{ int size; //hashtable size/lines int elem_num; //total elements count bucket** buckets;} hashtable;#endif
2. 哈希函数实现
哈希函数需要尽可能的将不同的key映射到不同的槽(slot或者bucket)中，首先我们采用一种最为简单的哈希算法实现： 将key字符串的所有字符加起来，然后以结果对哈希表的大小取模，这样索引就能落在数组索引的范围之内了
//hashtable.c#include #include #include #include hashtable.h int hash_str(char *key); int hash_str(char *key){ int hash = 0; char *cur = key; while(*cur != '\0') { hash += *cur; ++cur; } return hash;}//hashtable.h#define hash_index(ht, key) (hash_str((key)) % (ht)->size)
3. 操作接口的实现
为了操作哈希表，实现了如下几个操作接口函数
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);
4. 完整源代码
hashtable.c
#include #include #include #include hashtable.hstatic void resize_hash_table_if_needed(hashtable *ht);static int hash_str(char *key);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;}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;}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;}int hash_remove(hashtable *ht, char *key){ int index = hash_index(ht, key); bucket *bucket = ht->buckets[index]; bucket *prev = null; if(bucket == null) return failed; // find the right bucket from the link list while(bucket) { if(strcmp(bucket->key, key) == 0) { log_msg([remove]\tkey:(%s) index: %d\n, key, index); if(prev == null) { ht->buckets[index] = bucket->next; } else { prev->next = bucket->next; } free(bucket); return success; } prev = bucket; bucket = bucket->next; } log_msg([remove]\t key:%s not found remove \tfailed\t\n, key); return failed;}int hash_destroy(hashtable *ht){ int i; bucket *cur = null; bucket *tmp = null; for(i=0; i size; ++i) { cur = ht->buckets[i]; while(cur) { tmp = cur; cur = cur->next; free(tmp); } } free(ht->buckets); return success;}static int hash_str(char *key){ int hash = 0; char *cur = key; while(*cur != '\0') { hash += *cur; ++cur; } return hash;}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 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;}// if the elem_num is almost as large as the capacity of the hashtable// we need to resize the hashtable to contain enough elementsstatic void resize_hash_table_if_needed(hashtable *ht){ if(ht->size - ht->elem_num size)#if defined(debug)# define log_msg printf#else# define log_msg(...)#endif#define success 0#define failed -1typedef struct _bucket{ char *key; void *value; struct _bucket *next;} bucket;typedef struct _hashtable{ int size; // 哈希表的大小 int elem_num; // 已经保存元素的个数 bucket **buckets;} hashtable;int hash_init(hashtable *ht);int hash_lookup(hashtable *ht, char *key, void **result);int hash_insert(hashtable *ht, char *key, void *value);int hash_remove(hashtable *ht, char *key);int hash_destroy(hashtable *ht);#endif
main.c
#include #include #include #include #include hashtable.h#define test(tcase) printf(>>> [start case] tcase [passed] tcase test key not found test key not found <= 0x80000000) { /* prevent overflow */ //hash表大小大于0x80000000则初始化为0x80000000 ht->ntablesize = 0x80000000; } else { while ((1u
0x2: 数组添加键值
0x3: 操作php数组的api
//初始化php数组array_init(zval *arg);array_init_size(zval *arg, uint size); //关联数组赋值的操作函数，等同于$array[$stringkey] = $value;add_assoc_null(zval *aval, char *key);add_assoc_bool(zval *aval, char *key, zend_bool bval);add_assoc_long(zval *aval, char *key, long lval);add_assoc_double(zval *aval, char *key, double dval);add_assoc_string(zval *aval, char *key, char *strval, int dup);add_assoc_stringl(zval *aval, char *key,char *strval, uint strlen, int dup);add_assoc_zval(zval *aval, char *key, zval *value);//上述函数均为宏函数，都是对add_assoc_*_ex函数的封装 //数字索引数组赋值的操作函数，等效于$array[$numkey] = $value;zend_api int add_index_long(zval *arg, ulong idx, long n);zend_api int add_index_null(zval *arg, ulong idx);zend_api int add_index_bool(zval *arg, ulong idx, int b);zend_api int add_index_resource(zval *arg, ulong idx, int r);zend_api int add_index_double(zval *arg, ulong idx, double d);zend_api int add_index_string(zval *arg, ulong idx, const char *str, int duplicate);zend_api int add_index_stringl(zval *arg, ulong idx, const char *str, uint length, int duplicate);zend_api int add_index_zval(zval *arg, ulong index, zval *value); //使用内置数字索引的数组赋值的操作函数，等效于$array[] = $value;zend_api int add_next_index_long(zval *arg, long n);zend_api int add_next_index_null(zval *arg);zend_api int add_next_index_bool(zval *arg, int b);zend_api int add_next_index_resource(zval *arg, int r);zend_api int add_next_index_double(zval *arg, double d);zend_api int add_next_index_string(zval *arg, const char *str, int duplicate);zend_api int add_next_index_stringl(zval *arg, const char *str, uint length, int duplicate);zend_api int add_next_index_zval(zval *arg, zval *value); //数组元素赋值并返回，等效于{ $array[$key] = $value; return $value; }zend_api int add_get_assoc_string_ex(zval *arg, const char *key, uint key_len, const char *str, void **dest, int duplicate);zend_api int add_get_assoc_stringl_ex(zval *arg, const char *key, uint key_len, const char *str, uint length, void **dest, int duplicate);#define add_get_assoc_string(__arg, __key, __str, __dest, __duplicate) add_get_assoc_string_ex(__arg, __key, strlen(__key)+1, __str, __dest, __duplicate)#define add_get_assoc_stringl(__arg, __key, __str, __length, __dest, __duplicate) add_get_assoc_stringl_ex(__arg, __key, strlen(__key)+1, __str, __length, __dest, __duplicate)zend_api int add_get_index_long(zval *arg, ulong idx, long l, void **dest);zend_api int add_get_index_double(zval *arg, ulong idx, double d, void **dest);zend_api int add_get_index_string(zval *arg, ulong idx, const char *str, void **dest, int duplicate);zend_api int add_get_index_stringl(zval *arg, ulong idx, const char *str, uint length, void **dest, int duplicate);
relevant link:
http://thiniki.sinaapp.com/?p=155http://www.imsiren.com/archives/250http://www.cnblogs.com/ohmygirl/p/internal-4.htmlhttp://weizhifeng.net/write-php-extension-part2-1.htmlhttp://blog.csdn.net/a600423444/article/details/7073854
copyright (c) 2016 little5ann all rights reserved