哈希表（Hashtable，也叫哈希表），是一种根据键（Key）直接访问内存存储位置的数据结构。也就是说，它通过计算键值上的函数来访问记录，该函数将所需的查询数据映射到表中的某个位置，从而加快查找速度。这种映射函数称为哈希函数，存储记录的数组称为哈希表。———维基百科在一些合理的假设下，哈希表中所有操作的时间复杂度可以简单地看成是O(1)。它通过计算一个键的哈希值来快速定位键值在哈希表中的位置。实现一个好的哈希表的关键是好的哈希算法和处理哈希冲突的方法。常见的简单哈希算法包括BKDRHash、APHash、DJBHash、JSHash和RSHash。更复杂的算法包括MD5和SHA1。哈希算法的好坏直接影响到哈希表访问的效率。处理散列冲突的方法包括开放寻址和压缩。以下示例使用拉链方法BKDRHash哈希算法。在以上多种哈希算法中，BKDRHash在效率、均衡、均匀分布等方面表现突出，其实现方式也是最容易理解和记忆的。实现如下：/***BKDRhashfunctioninclang*@paramkeychar*string*@returninthashedvalue，我们会得到一个int值*/intbkdrHash(char*key){uintseed=131;//我可以是13、131、1313、131313等uinthash=0;while(*key!='\n'&&*key!=0){hash=hash*seed+(*key++);}return(hash&0x7FFFFFFF);}哈希表示意图（处理冲突的拉链法）：（图片来源：http://blog.csdn.net/v_JULY_v...）上图中，左边是一个数组，它存储指向链表头部的指针。链表中单向链表中节点的数据结构和数组定义代码存放的是实际值/**单向链表中节点的结构*/typedefstruct_htItem{struct_htItem*下一个;字符*key_string;uintfid；}htItem;/**获取Key在数组中的映射位置*/uinthtIndex(char*key,htItem**ht){uinthashedKey=bkdrHash(key);uint长度=(ht[0]->fid-1);return(uint)hashedKey%length+1;}/**定义一个数组*/htItem*item[21];//为了后台实现的方便，在定义数组的时候，我们给了一个额外的长度，第一个数据不存储数据，只存储数组的长度，剩下的元素空间初始化数组元素/**是需要用0值初始化数组元素*/voidhtInit(htItem**ht,uintlength){inti;for(i=0;ifid=length;}插入和更新数据，首先通过hash函数找到Key在数组中对应的位置，然后遍历链表。如果在链表中找到相同的key，则直接更新该节点的数据，否则malloC一个节点，并将该节点放在链表的尾部。/**设置哈希表元素*/uinthtSet(char*key,uintfid,htItem**ht){uinti=htIndex(key,ht);htItem*item=ht[i];while(item->next){if(strcmp(key,item->next->key_string)==0){item->next->fid=fid;返回0；}else{item=item->next;}}item->next=(htItem*)malloc(sizeof(htItem));项目->下一个->fid=fid;item->next->key_string=key;return0;}获取数据首先通过hash函数定位到KEY在数组中的位置，然后依次比较KEY值，命中则返回对应值，否则返回空值/**获取hashTableelements*/htItem*htGet(char*key,htItem**ht){uinti=htIndex(key,ht);htItem*item=ht[i]->下一个；htItem*tmp=(htItem*)malloc(sizeof(htItem));memset(tmp,0,sizeof(htItem));while(item){if(strcmp(key,item->key_string)==0){printf("hiting%s\n",key);tmp->fid=item->fid;tmp->key_string=item->key_string;返回tmp；}item=item->下一个；}return;}删除数据/**删除hashtable的一个元素*/inthtDel(char*key,htItem**ht){uinti=htIndex(key,ht);htItem*item=ht[i];while(item->next){if(strcmp(key,item->next->key_string)==0){htItem*tmp=item->next;item->next=tmp->next;免费（tmp）；返回0；}item=item->下一个；}return-1;}打印完成hashtable中的元素voidprint_hashTable(htItem**ht){uintlength=ht[0]->fid;单位我;ht项目*项目;for(i=1;inext;while(item){printf("%s=>%d\n",item->key_string,item->fid);item=item->下一个；}}}通过几个简单的方法对哈希表进行增删改查Example/**定义和初始化*/htItem*item[101];htInit（项目，101）；/**添加元素*/htSet("longmon",100,item);htSet("娜塔莉",1000,项目);htSet("小琼",99,item);/**打印(1)*/print_hashTable(item);/**删除一个元素*/htDel("natalie",item);/**打印(2)*/print_hashTable(item);/**获取键为longmon的值*/htItem*tmpitem=htGet("longmon",item);/**打印⑶*/printf("key:%s=>val:%d\n",tmpitem->key_string,tmpitem->fid);输出结果#print⑴xiaoqiong=>99natalie=>1000longmon=>100#Print⑵xiaoqiong=>99longmon=>100#Print⑶Key:longmon=>val:100完整代码https://github.com/longmon/hashTable_in_c哈希表是PHP核心的基石。PHP内核中的哈希表是一个非常重要的数据结构。PHP的大部分语言特性都是基于哈希表实现的，例如：变量作用域、函数表、类属性、方法等，Zend引擎内部有大量的数据存储在哈希表中。PHP内核中的哈希表也采用了zipper的方式来处理冲突。延伸阅读：PHP的哈希表实现PHP数组Hash冲突的例子
