本文共 3543 字,大约阅读时间需要 11 分钟。
1.哈希表的定义
这里先说一下哈希(hash)表的定义:哈希表是一种根据关键码去寻找值的数据映射结构,该结构通过把关键码映射的位置去寻找存放值的地方,说起来可能感觉有点复杂,我想我举个例子你就会明白了,最典型的的例子就是字典,大家估计小学的时候也用过不少新华字典吧,如果我想要获取“按”字详细信息,我肯定会去根据拼音an去查找 拼音索引(当然也可以是偏旁索引),我们首先去查an在字典的位置,查了一下得到“安”,结果如下。这过程就是键码映射,在公式里面,就是通过key去查找f(key)。其中,按就是关键字(key),f()就是字典索引,也就是哈希函数,查到的页码4就是哈希值。unsigned long hash(const char* key){ unsigned long hash=0; for(int i=0;i
3.哈希冲突解决办法
如果遇到冲突,哈希表一般是怎么解决的呢?具体方法有很多,百度也会有一堆,最常用的就是开发定址法和链地址法。
1.开发定址法 如果遇到冲突的时候怎么办呢?就找hash表剩下空余的空间,找到空余的空间然后插入。就像你去商店买东西,发现东西卖光了,怎么办呢?找下一家有东西卖的商家买呗。 由于我没有深入试验过,所以贴上在书上的解释:#define HASHSIZE 10 typedef unsigned int uint; typedef struct Node{ const char* key; const char* value; Node *next; }Node; class HashTable{ private: Node* node[HASHSIZE]; public: HashTable(); uint hash(const char* key); Node* lookup(const char* key); bool install(const char* key,const char* value); const char* get(const char* key); void display(); };
然后定义哈希表的构造方法
HashTable::HashTable(){ for (int i = 0; i < HASHSIZE; ++i) { node[i] = NULL; } }
第二步。
定义哈希表的Hash算法,在这里我使用time33算法uint HashTable::hash(const char* key){ uint hash=0; for (; *key; ++key) { hash=hash*33+*key; } return hash%HASHSIZE; }
第三步。
定义一个查找根据key查找结点的方法,首先是用Hash函数计算头地址,然后根据头地址向下一个个去查找结点,如果结点的key和查找的key值相同,则匹配成功。Node* HashTable::lookup(const char* key){ Node *np; uint index; index = hash(key); for(np=node[index];np;np=np->next){ if(!strcmp(key,np->key)) return np; } return NULL; }
第四步。
定义一个插入结点的方法,首先是查看该key值的结点是否存在,如果存在则更改value值就好,如果不存在,则插入新结点。bool HashTable::install(const char* key,const char* value){ uint index; Node *np; if(!(np=lookup(key))){ index = hash(key); np = (Node*)malloc(sizeof(Node)); if(!np) return false; np->key=key; np->next = node[index]; node[index] = np; } np->value=value; return true; }
4.关于哈希表的性能
由于哈希表高效的特性,查找或者插入的情况在大多数情况下可以达到O(1),时间主要花在计算hash上,当然也有最坏的情况就是hash值全都映射到同一个地址上,这样哈希表就会退化成链表,查找的时间复杂度变成O(n),但是这种情况比较少,只要不要把hash计算的公式外漏出去并且有人故意攻击(用兴趣的人可以搜一下基于哈希冲突的拒绝服务攻击),一般也不会出现这种情况。转载地址:http://uwyhj.baihongyu.com/