哈希表数据结构的双重哈希如何用c++实现
1、双重哈希的地址映射可以使用如下公式：
(hash1(key) + i * hash2(key)) % TABLE_SIZE
hash1与hash2为地址映射的哈希函数；table_size为哈希表的大小；key为插入的元素大小。
当未发生冲突的时候i取0，如果发生冲突i取1，如果再次冲突的话i依次增大即可。
2、一般来说双重哈希的哈希函数为
hash1(key) = key % TABLE_SIZE
hash2(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 <iostream>
using namespace std;
#define tablesize 13
#define prime 7
class doublehash
{
int *table;
int currsize;
public:
doublehash()
{
table=new int [tablesize];
currsize=0;
for (int i=0;i<tablesize;i++)
table[i]=-1;
}
bool isfull() {return (currsize>=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<tablesize;i++)
{
cout<<i;
if (table[i]!=-1)
cout<<"---->"<<table[i];
cout<<endl;
}
}
};
int main()
{
int a[]={19, 27, 36, 10, 64};
int n=sizeof(a)/sizeof(a[0]);
doublehash h;
for (int i=0;i<n;i++)
h.insert(a[i]);
h.disiplay();
return 0;
}
