10 Hashing Interview Questions and Answers

Hashing is a fundamental concept in computer science, playing a crucial role in data structures, cryptography, and database indexing. It involves transforming input data of any size into a fixed-size value, typically for fast data retrieval. Hashing algorithms are designed to distribute data uniformly across a hash table, minimizing collisions and ensuring efficient performance.

This article provides a curated selection of hashing-related interview questions and answers. By familiarizing yourself with these questions, you will gain a deeper understanding of hashing principles and be better prepared to demonstrate your knowledge and problem-solving abilities in technical interviews.

Hashing Interview Questions and Answers

1. Describe how hash tables work and their typical use cases.

Hash tables use a hash function to convert a key into an index in an array, determining where the corresponding value is stored. They offer average-case constant time complexity, O(1), for insertion and lookup, making them efficient for quick data retrieval. Typical use cases include implementing associative arrays, database indexing, caching, counting occurrences, and removing duplicates.

hash_table = {}

# Insertion
hash_table["key1"] = "value1"
hash_table["key2"] = "value2"

# Lookup
value = hash_table.get("key1")

# Deletion
del hash_table["key2"]

2. What are collision resolution techniques in hash tables? Describe one in detail.

Collisions in hash tables occur when two keys hash to the same index. Collision resolution techniques ensure the hash table functions correctly. Common methods include separate chaining, open addressing, double hashing, and quadratic probing. Separate chaining uses a linked list at each index to store elements that hash to the same location.

class HashTable:
    def __init__(self):
        self.table = [[] for _ in range(10)]
    
    def hash_function(self, key):
        return key % 10
    
    def insert(self, key, value):
        index = self.hash_function(key)
        self.table[index].append((key, value))
    
    def get(self, key):
        index = self.hash_function(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

hash_table = HashTable()
hash_table.insert(10, 'Value for 10')
hash_table.insert(20, 'Value for 20')
print(hash_table.get(10))  # Output: Value for 10
print(hash_table.get(20))  # Output: Value for 20

3. Explain the concept of load factor in a hash table and its significance.

The load factor in a hash table is the ratio of the number of elements to the number of buckets. It impacts performance, with a low load factor leading to fewer collisions and faster access times. A high load factor increases collision likelihood and can degrade performance. To maintain efficiency, hash tables often resize and rehash elements when the load factor exceeds a threshold.

4. Discuss the differences between cryptographic hash functions and non-cryptographic hash functions.

Cryptographic hash functions are designed for security, offering properties like pre-image resistance and collision resistance. They are used in digital signatures and security protocols. Non-cryptographic hash functions prioritize efficiency and speed, lacking strong security guarantees, and are used in data structures like hash tables.

5. Write a function to detect if two strings are anagrams using hashing.

To detect if two strings are anagrams using hashing, use a hash map to count character frequencies. If the counts match for all characters, the strings are anagrams.

def are_anagrams(str1, str2):
    if len(str1) != len(str2):
        return False

    char_count = {}

    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1

    for char in str2:
        if char not in char_count:
            return False
        char_count[char] -= 1
        if char_count[char] < 0:
            return False

    return True

# Example usage
print(are_anagrams("listen", "silent"))  # True
print(are_anagrams("hello", "world"))    # False

6. Implement a bloom filter using hashing.

A Bloom filter is a data structure for efficient membership testing, using multiple hash functions to map elements to a bit array. It allows for quick checks with a possibility of false positives.

class BloomFilter:
    def __init__(self, size, hash_count):
        self.size = size
        self.hash_count = hash_count
        self.bit_array = [0] * size

    def add(self, item):
        for i in range(self.hash_count):
            index = hash(item + str(i)) % self.size
            self.bit_array[index] = 1

    def check(self, item):
        for i in range(self.hash_count):
            index = hash(item + str(i)) % self.size
            if self.bit_array[index] == 0:
                return False
        return True

# Example usage
bloom = BloomFilter(100, 3)
bloom.add("apple")
print(bloom.check("apple"))  # True
print(bloom.check("banana")) # False

7. Explain how hash functions are used in blockchain technology.

Hash functions are integral to blockchain technology, ensuring data integrity and enabling proof of work. They create a chain of blocks by hashing each block’s data, including the previous block’s hash. This makes tampering evident. In proof of work, miners solve cryptographic puzzles involving hash functions to add new blocks, securing the network.

8. Explain the difference between open addressing and separate chaining in hash tables.

Open addressing and separate chaining are techniques to resolve hash table collisions. Open addressing finds another open slot within the table, using methods like linear probing. Separate chaining uses a linked list at each index to store elements that hash to the same location, allowing the table to handle more elements without significant performance degradation.

9. Discuss the role of hash functions in digital signatures.

Hash functions are used in digital signatures to verify message integrity and authenticity. A message is hashed, and the hash is encrypted with the sender’s private key to create the digital signature. The recipient decrypts the signature with the sender’s public key and compares the hash to ensure the message is unaltered.

10. What are the potential vulnerabilities of hash functions and how can they be mitigated?

Hash functions have vulnerabilities like collision attacks, preimage attacks, and length extension attacks. Mitigation strategies include using strong hash functions like SHA-256, adding a unique salt to inputs, and employing HMAC to protect against length extension attacks.