当哈希表数据结构发生冲突的时候,我们有两种解决方法。第一种是分离链表的方法,指的是在哈希表的每一个单元存储指向链表表头的指针,当发生冲突时将数据存储到对应地址的链表当中。第二种是开放地址的方法,指的是哈希表比较大的时候,当发生冲突时,将新数据根据公式插入到新的地址单元中。下面小编介绍开放地址方法中的双重哈希的方法。
工具/原料
方法/步骤
1双重哈希的地址映射可以使用如下公式:(hash1(key) + i * hash2(key)) % TABLE_SIZEhash1与hash2为地址映射的哈希函数;table_size为哈希表的大小;key为插入的元素大小。当未发生冲突的时候i取0,如果发生冲突i取1,如果再次冲突的话i依次增大即可。
2一般来说双重哈希的哈希函数为hash1(key) = key % TABLE_SIZEhash2(key) = PRIME – (key % PRIME) 这里table_size为哈希表的大小,PRIME略小于TABLE_SIZE。
3举个例子:往大小为13的哈希表中插入数值19,27,36,10。哈希函数为如下图所示。
4插入19,27,36的时候发生冲突,其对应的索引地址为6,1,10.当插入10的时候,其对应的索引为10,与36发生冲突。
5使用双重哈希的方法解决冲突。一次增大i的取值,当i取2的时候10对应的索引地址为5,未发生冲突。在地址索引为5的位置插入10
6下面提供代码参考#include using namespace std;#define tablesize 13#define prime 7class doublehash{ int *table; int currsize;public: doublehash() { table=new int [tablesize]; currsize=0; for (int i=0;i=tablesize);} int hash1(int k){return k%tablesize;} int hash2(int k){return (prime-k%prime);} void insert(int k) { if (isfull()) return; int index=hash1(k); if (table[index]==-1) table[index]=k; else { int i=0;int newindex; while (1) { i++; newindex=(index+i*hash2(k))%tablesize; if (table[newindex]==-1) { table[newindex]=k; break; } } } currsize++; } void disiplay() { for (int i=0;i'<