php中hashtable实现示例分享

对php内核有一定了解的人应该都知道php的精髓就是hashtable，hashtable在php的实现中无处不在。包括php的数组、什么全局变量、局部变量的作用域等等，php的hashtable拆开来说就是四部分：

hash函数：用的是time33的散列函数，将一个字符串的key转换成一个数字
一个c数组：用来储存桶(buckets)的
两个双向的链表：第一个双向链表是数组的每个元素（桶bucket）是一个双向链表，这样做是为了解决hash冲突；第二个双向链表是数组将每一个桶(bucket)连接起来，这里要连接的也就是第一个双向链表的链表头，这样做是为了遍历整个hash表用的,鸟哥有篇blog是讲php的foreach的，这里这样设计就是给foreach用的==>《深入理解php之数组(遍历顺序)》
我这里不再说hashtable的struct和bucket的struct了，因为下面的推荐链接几乎都讲了，我不觉得我能描述和说的比他们好，每个人的水平不一样，我就以我现在的技术水平来描述，所以我就只把我整理的一些东西记录一下

下面是php中hash实现的两个文件：zend_hash.c zend_hash.h。这两个文件里面实现了一堆的api，也引申出了一堆的api，下面是实现出来的api的原型

zend_api ulong zend_hash_func(const char *arkey, uint nkeylength)
zend_api ulong zend_get_hash_value(const char *arkey, uint nkeylength)
zend_api int _zend_hash_init(hashtable *ht, uint nsize, hash_func_t phashfunction, dtor_func_t pdestructor, zend_bool persistent zend_file_line_dc)
 zend_api void zend_hash_set_apply_protection(hashtable *ht, zend_bool bapplyprotection)
zend_api int _zend_hash_add_or_update(hashtable *ht, const char *arkey, uint nkeylength, void *pdata, uint ndatasize, void **pdest, int flag zend_file_line_dc)
zend_api int _zend_hash_quick_add_or_update(hashtable *ht, const char *arkey, uint nkeylength, ulong h, void *pdata, uint ndatasize, void **pdest, int flag zend_file_line_dc)
zend_api int _zend_hash_index_update_or_next_insert(hashtable *ht, ulong h, void *pdata, uint ndatasize, void **pdest, int flag zend_file_line_dc)
zend_api int zend_hash_rehash(hashtable *ht)
static int zend_hash_do_resize(hashtable *ht)
zend_api int zend_hash_del_key_or_index(hashtable *ht, const char *arkey, uint nkeylength, ulong h, int flag)
zend_api void zend_hash_destroy(hashtable *ht)
zend_api void zend_hash_clean(hashtable *ht)
static bucket *zend_hash_apply_deleter(hashtable *ht, bucket *p)
zend_api void zend_hash_graceful_destroy(hashtable *ht)
zend_api void zend_hash_graceful_reverse_destroy(hashtable *ht)
zend_api void zend_hash_apply(hashtable *ht, apply_func_t apply_func tsrmls_dc)
zend_api void zend_hash_apply_with_argument(hashtable *ht, apply_func_arg_t apply_func, void *argument tsrmls_dc)
zend_api void zend_hash_apply_with_arguments(hashtable *ht tsrmls_dc, apply_func_args_t apply_func, int num_args, …)
zend_api void zend_hash_reverse_apply(hashtable *ht, apply_func_t apply_func tsrmls_dc)
zend_api void zend_hash_copy(hashtable *target, hashtable *source, copy_ctor_func_t pcopyconstructor, void *tmp, uint size)
zend_api void _zend_hash_merge(hashtable *target, hashtable *source, copy_ctor_func_t pcopyconstructor, void *tmp, uint size, int overwrite zend_file_line_dc)
static zend_bool zend_hash_replace_checker_wrapper(hashtable *target, void *source_data, bucket *p, void *pparam, merge_checker_func_t merge_checker_func)
zend_api void zend_hash_merge_ex(hashtable *target, hashtable *source, copy_ctor_func_t pcopyconstructor, uint size, merge_checker_func_t pmergesource, void *pparam)   
zend_api int zend_hash_find(const hashtable *ht, const char *arkey, uint nkeylength, void **pdata)
zend_api int zend_hash_quick_find(const hashtable *ht, const char *arkey, uint nkeylength, ulong h, void **pdata)
zend_api int zend_hash_exists(const hashtable *ht, const char *arkey, uint nkeylength)
zend_api int zend_hash_quick_exists(const hashtable *ht, const char *arkey, uint nkeylength, ulong h)
zend_api int zend_hash_index_find(const hashtable *ht, ulong h, void **pdata)
zend_api int zend_hash_index_exists(const hashtable *ht, ulong h)
zend_api int zend_hash_num_elements(const hashtable *ht)
zend_api int zend_hash_get_pointer(const hashtable *ht, hashpointer *ptr)
zend_api int zend_hash_set_pointer(hashtable *ht, const hashpointer *ptr)
zend_api void zend_hash_internal_pointer_reset_ex(hashtable *ht, hashposition *pos)
zend_api void zend_hash_internal_pointer_end_ex(hashtable *ht, hashposition *pos)
zend_api int zend_hash_move_forward_ex(hashtable *ht, hashposition *pos)
zend_api int zend_hash_move_backwards_ex(hashtable *ht, hashposition *pos)
zend_api int zend_hash_get_current_key_ex(const hashtable *ht, char **str_index, uint *str_length, ulong *num_index, zend_bool duplicate, hashposition *pos)
zend_api int zend_hash_get_current_key_type_ex(hashtable *ht, hashposition *pos)
zend_api int zend_hash_get_current_data_ex(hashtable *ht, void **pdata, hashposition *pos)
zend_api int zend_hash_update_current_key_ex(hashtable *ht, int key_type, const char *str_index, uint str_length, ulong num_index, int mode, hashposition *pos)
zend_api int zend_hash_sort(hashtable *ht, sort_func_t sort_func, compare_func_t compar, int renumber tsrmls_dc)
zend_api int zend_hash_compare(hashtable *ht1, hashtable *ht2, compare_func_t compar, zend_bool ordered tsrmls_dc)
zend_api int zend_hash_minmax(const hashtable *ht, compare_func_t compar, int flag, void **pdata tsrmls_dc)
zend_api ulong zend_hash_next_free_element(const hashtable *ht)
void zend_hash_display_plisttail(const hashtable *ht)
void zend_hash_display(const hashtable *ht)