双重哈希是开放寻址哈希表中的冲突解决技术。双重哈希的思想是在发生冲突时对键做第二个哈希函数。
双重哈希可以处理 :(hash1(key) + i * hash2(key)) % TABLE_SIZE
这里 hash1() 、 hash2() 是hash 函数， TABLE_SIZE 是hash表大小
(如果发生冲突，i递增然后重复运算)
通俗的二次Hash函数：hash2(key) = PRIME – (key % PRIME)
PRIME一般选择小于 TABLE_SIZE 的质数
优质的二次Hash函数应该具备这些条件：
二次Hash函数结果不能为0第二个哈希函数要可以覆盖表的每一个单元
实例
// CPP program to implement double hashing
#include
using namespace std;
// Hash table size
#define TABLE_SIZE 13
// Used in second hash function.
#define PRIME 7
class DoubleHash
{
// Pointer to an array containing buckets
int *hashTable;
int curr_size;
public:
// function to check if hash table is full
bool isFull()
{
// if hash size reaches maximum size
return (curr_size == TABLE_SIZE);
}
// function to calculate first hash
int hash1(int key)
{
return (key % TABLE_SIZE);
}
// function to calculate second hash
int hash2(int key)
{
return (PRIME - (key % PRIME));
}
DoubleHash()
{
hashTable = new int[TABLE_SIZE];
curr_size = 0;
for (int i=0; i hashTable[i] = -1; } // function to insert key into hash table void insertHash(int key) { // if hash table is full if (isFull()) return; // get index from first hash int index = hash1(key); // if collision occurs if (hashTable[index] != -1) { // get index2 from second hash int index2 = hash2(key); int i = 1; while (1) { // get newIndex int newIndex = (index + i * index2) % TABLE_SIZE; // if no collision occurs, store // the key if (hashTable[newIndex] == -1) { hashTable[newIndex] = key; break; } i++; } } // if no collision occurs else hashTable[index] = key; curr_size++; } // function to display the hash table void displayHash() { for (int i = 0; i < TABLE_SIZE; i++) { if (hashTable[i] != -1) cout << i << " --> " << hashTable[i] << endl; else cout << i << endl; } } }; // Driver's code int main() { int a[] = {19, 27, 36, 10, 64}; int n = sizeof(a)/sizeof(a[0]); // inserting keys into hash table DoubleHash h; for (int i = 0; i < n; i++) h.insertHash(a[i]); // display the hash Table h.displayHash(); return 0; } 结果 0 1 --> 27 2 3 4 5 --> 10 6 --> 19 7 8 9 10 --> 36 11 12 --> 64