Double Hash

Double Hashing is a collision resolution technique used in hash tables. It works by applying two hash functions to determine the next available index when a collision occurs.

Here's an example of implementing Double Hashing in Python:

class DoubleHashing:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def _hash(self, key):
        return key % self.size

    def _hash2(self, key):
        return 1 + (key % (self.size - 1))

    def insert(self, key):
        index = self._hash(key)
        if self.table[index] is None:
            self.table[index] = key
        else:
            i = 1
            while True:
                next_index = (index + i * self._hash2(key)) % self.size
                if self.table[next_index] is None:
                    self.table[next_index] = key
                    break
                i += 1

    def search(self, key):
        index = self._hash(key)
        if self.table[index] == key:
            return True
        else:
            i = 1
            while True:
                next_index = (index + i * self._hash2(key)) % self.size
                if self.table[next_index] == key:
                    return True
                if self.table[next_index] is None:
                    return False
                i += 1

In this example, we create a DoubleHashing class with a specified size. The table is initialized as an array of None values.

The _hash() function calculates the initial hash value of the key using the modulo operation with the table size.

The _hash2() function calculates the second hash value of the key, ensuring it is different from 0 and the table size.

The insert() method inserts a key into the hash table. If the calculated index is empty, it inserts the key at that index. If the index is occupied, it applies double hashing by incrementing the index with the hash2 value until it finds an empty slot.

The search() method searches for a key in the hash table. It starts by checking the calculated index. If the key is found, it returns True. If not, it applies double hashing by incrementing the index with the hash2 value until it finds the key or an empty slot.

Now let's solve a problem using Double Hashing. The problem we'll solve is "Two Sum".

Problem Statement: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to the target.

Example:

nums = [2, 7, 11, 15]
target = 9

Output:

[0, 1]

Explanation: In this example, the numbers at indices 0 and 1 (2 and 7) add up to the target 9.

Solution: We can use Double Hashing to efficiently solve this problem. We'll iterate over the array and for each number, check if the complement (target minus the current number) is already in the hash table. If it is, we've found the two numbers that add up to the target. If not, we'll insert the current number into the hash table.

def twoSum(nums, target):
    hash_table = DoubleHashing(size=len(nums))
    for i, num in enumerate(nums):
        complement = target - num
        if hash_table.search(complement):
            return [hash_table.search(complement), i]
        hash_table.insert(num)

In this solution, we create an instance of the DoubleHashing class with a size equal to the length of the nums array. We iterate over the array and for each number, calculate the complement and search for it in the hash table. If the complement is found, we return the indices. Otherwise, we insert the current number into the hash table.

The time complexity of this solution is O(n) since we iterate over the array once. The space complexity is also O(n) since, in the worst case, we may need to store all the numbers in the hash table.