Double hashing là gì?

Băm kép (double hashing) là một kỹ thuật giải quyết xung đột (collision) trong băm địa chỉ mở (open addressing) của bảng băm (hash table). Băm kép (double hashing) sử dụng ý tưởng áp dụng hàm băm thứ hai (hash function) cho khóa (key) khi xảy ra xung đột.

Băm kép có thể được thực hiện bằng cách sử dụng: (hash1(key) + i * hash2(key))% TABLE_SIZE Ở đây hash1() và hash2() là các hàm băm và TABLE_SIZE là kích thước của bảng băm. Chúng ta lặp lại bằng cách tăng i khi xảy ra xung đột.

Hàm băm đầu tiên thường là hash1(key) = key% TABLE_SIZE. Một hàm băm thứ hai phổ biến là: hash2 (key) = PRIME - (key% PRIME) trong đó PRIME là một số nguyên tố nhỏ hơn TABLE_SIZE. Một hàm băm thứ hai tốt là:

• Nó không bao giờ được ước lượng (evaluate) bằng 0
• Phải đảm bảo rằng tất cả các ô (cell) đều có thể được thăm dò (probe).

Bên dưới là code minh học trong C++:

/*
** Handling of collision via open addressing
** Method for Probing: Double Hashing
*/
 
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
#define MAX_SIZE 10000001ll
 
class doubleHash {
 
    int TABLE_SIZE, keysPresent, PRIME;
    vector<int> hashTable;
    bitset<MAX_SIZE> isPrime;
 
    /* Function to set sieve of Eratosthenes. */
    void __setSieve(){
        isPrime[0] = isPrime[1] = 1;
        for(long long i = 2; i*i <= MAX_SIZE; i++)
            if(isPrime[i] == 0)
                for(long long j = i*i; j <= MAX_SIZE; j += i)
                    isPrime[j] = 1;
 
    }
 
    int inline hash1(int value){
        return value%TABLE_SIZE;
    }
     
    int inline hash2(int value){      
        return PRIME - (value%PRIME);
    }
 
    bool inline isFull(){
        return (TABLE_SIZE == keysPresent);
    }
 
    public:
 
    doubleHash(int n){
        __setSieve();
        TABLE_SIZE = n;
 
        /* Find the largest prime number smaller than hash table's size. */
        PRIME = TABLE_SIZE - 1;
        while(isPrime[PRIME] == 1)
            PRIME--;
 
        keysPresent = 0;
 
        /* Fill the hash table with -1 (empty entries). */
        for(int i = 0; i < TABLE_SIZE; i++)
            hashTable.push_back(-1);
    }
 
    void __printPrime(long long n){
        for(long long i = 0; i <= n; i++)
            if(isPrime[i] == 0)
                cout<<i<<", ";
        cout<<endl;
    }
 
    /* Function to insert value in hash table */
    void insert(int value){
 
        if(value == -1 || value == -2){
            cout<<("ERROR : -1 and -2 can't be inserted in the tablen"); 
        }
 
        if(isFull()){
            cout<<("ERROR : Hash Table Fulln");
            return;
        }
         
        int probe = hash1(value), offset = hash2(value); // in linear probing offset = 1;
         
        while(hashTable[probe] != -1){
            if(-2 == hashTable[probe])                 
                break;                                  // insert at deleted element's location
            probe = (probe+offset) % TABLE_SIZE;
        }
 
        hashTable[probe] = value;
        keysPresent += 1;
    }
 
    void erase(int value){
        /* Return if element is not present */
        if(!search(value))
            return;    
         
        int probe = hash1(value), offset = hash2(value);
 
        while(hashTable[probe] != -1)
            if(hashTable[probe] == value){
                hashTable[probe] = -2;          // mark element as deleted (rather than unvisited(-1)).
                keysPresent--;
                return;
            }
            else
                probe = (probe + offset) % TABLE_SIZE;
 
    }
 
    bool search(int value){
        int probe = hash1(value), offset = hash2(value), initialPos = probe;
        bool firstItr = true;
 
        while(1){
            if(hashTable[probe] == -1)                   // Stop search if -1 is encountered.
                break;
            else if(hashTable[probe] == value)           // Stop search after finding the element.
                return true;
            else if(probe == initialPos && !firstItr)    // Stop search if one complete traversal of hash table is completed.
                return false;
            else
                probe = ((probe + offset) % TABLE_SIZE);  // if none of the above cases occur then update the index and check at it.
 
            firstItr = false;
        }
        return false;
    }
 
    /* Function to display the hash table. */
    void print(){
        for(int i = 0; i < TABLE_SIZE; i++)
            cout<<hashTable[i]<<", ";
        cout<<"n";
    }
 
};
 
int main(){
    doubleHash myHash(13); // creates an empty hash table of size 13
 
    /* Inserts random element in the hash table */
     
    int insertions[] = {115, 12, 87, 66, 123},
        n1 = sizeof(insertions)/sizeof(insertions[0]);
     
    for(int i = 0; i < n1; i++)
        myHash.insert(insertions[i]);
     
    cout<< "Status of hash table after initial insertions : "; myHash.print();
     
 
    /*
    ** Searches for random element in the hash table,
    ** and prints them if found.
    */
     
    int queries[] = {1, 12, 2, 3, 69, 88, 115},
        n2 = sizeof(queries)/sizeof(queries[0]);
     
    cout<<"n"<<"Search operation after insertion : n";
 
    for(int i = 0; i < n2; i++)
        if(myHash.search(queries[i]))
            cout<<queries[i]<<" presentn";
     
 
    /* Deletes random element from the hash table. */
     
    int deletions[] = {123, 87, 66},
        n3 = sizeof(deletions)/sizeof(deletions[0]);
     
    for(int i = 0; i < n3; i++)
        myHash.erase(deletions[i]);
 
    cout<< "Status of hash table after deleting elements : "; myHash.print();
     
    return 0;
}

Output:

Status of hash table after initial insertions : -1, 66, -1, -1, -1, -1, 123, -1, -1, 87, -1, 115, 12, 

Search operation after insertion : 
12 present
115 present
Status of hash table after deleting elements : -1, -2, -1, -1, -1, -1, -2, -1, -1, -2, -1, 115, 12,