Hash Table Concept and Hash Functions in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Hash Table Insertions with Simple Hash Function

What is the printed state of the hash table after inserting keys 10, 22, 31 using the hash function key % 10?

DSA Python

class SimpleHashTable:
    def __init__(self):
        self.size = 10
        self.table = [[] for _ in range(self.size)]

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

    def insert(self, key):
        index = self.hash_function(key)
        self.table[index].append(key)

    def __str__(self):
        result = []
        for i, bucket in enumerate(self.table):
            if bucket:
                result.append(f"{i}: {bucket}")
        return ' | '.join(result)

ht = SimpleHashTable()
ht.insert(10)
ht.insert(22)
ht.insert(31)
print(str(ht))

A 0: [10, 31] | 2: [22]

B 0: [10] | 2: [22, 31]

C 1: [10] | 2: [22] | 3: [31]

D 0: [10] | 1: [31] | 2: [22]

💡 Hint

Remember the hash function is key % 10, so find the remainder when dividing each key by 10.

The hash function returns the remainder of the key divided by 10.

10 % 10 = 0, so 10 goes to bucket 0.

22 % 10 = 2, so 22 goes to bucket 2.

31 % 10 = 1, so 31 goes to bucket 1.

Thus, the printed state shows these buckets with their keys.

🧠 Conceptual

intermediate

Understanding Hash Function Output Range

If a hash function is defined as h(key) = key % 7, what is the maximum number of buckets the hash table should have to avoid index errors?

A 7

B 6

C 8

D 10

💡 Hint

Think about the possible remainders when dividing by 7.

The remainder when dividing by 7 can be 0, 1, 2, 3, 4, 5, or 6.

So, the hash table needs 7 buckets indexed from 0 to 6.

🔧 Debug

advanced

Identify the Error in Hash Table Key Insertion

What error will this code produce when inserting keys into the hash table?

DSA Python

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

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

    def insert(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = key
        else:
            self.table[index].append(key)

ht = HashTable(5)
ht.insert(10)
ht.insert(15)
print(ht.table)

A No error, prints [10, 15, None, None, None]

B IndexError: list index out of range

C AttributeError: 'int' object has no attribute 'append'

D TypeError: unsupported operand type(s) for %: 'str' and 'int'

💡 Hint

Check what type is stored in the table before calling append.

The table is initialized with None values.

On first insert, the slot is set to an int key.

On second insert to the same slot, code tries to append to an int, which causes AttributeError.

❓ Predict Output

advanced

Output of Hash Table with Linear Probing

What is the printed state of the hash table after inserting keys 5, 15, 25 using linear probing with size 10 and hash function key % 10?

DSA Python

class LinearProbingHashTable:
    def __init__(self):
        self.size = 10
        self.table = [None] * self.size

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

    def insert(self, key):
        index = self.hash_function(key)
        start_index = index
        while self.table[index] is not None:
            index = (index + 1) % self.size
            if index == start_index:
                raise Exception('Hash table is full')
        self.table[index] = key

    def __str__(self):
        return str(self.table)

ht = LinearProbingHashTable()
ht.insert(5)
ht.insert(15)
ht.insert(25)
print(ht)

A [5, None, None, None, None, 15, 25, None, None, None]

B [5, 15, 25, None, None, None, None, None, None, None]

C [5, None, None, None, None, None, None, 15, 25, None]

D [5, None, None, None, None, None, None, None, None, 15]

💡 Hint

Check the hash index for each key and how linear probing moves to next slot if occupied.

5 % 10 = 5, placed at index 5.

15 % 10 = 5, index 5 occupied, move to 6.

25 % 10 = 5, indexes 5 and 6 occupied, move to 7.

So keys are at indexes 5, 6, and 7.

🧠 Conceptual

expert

Choosing a Good Hash Function Property

Which property is most important for a hash function to minimize collisions in a hash table?

A Fast computation time regardless of input size

B Uniform distribution of hash values across buckets

C Deterministic output for the same input

D Ability to produce very large hash values

💡 Hint

Think about how keys are spread in the table to avoid clustering.

A good hash function spreads keys evenly across all buckets to reduce collisions.

Deterministic output is necessary but not enough.

Fast computation is good but less important than distribution.

Large hash values are not needed if distribution is uniform.

Practice

1. What is the main purpose of a hash function in a hash table?

easy

A. To encrypt the data stored in the table

B. To sort the keys in ascending order

C. To convert a key into an index for storing data

D. To count the number of elements in the table

Solution

1. Step 1: Understand the role of a hash function

   A hash function takes a key and converts it into a number that can be used as an index in the hash table.

2. Step 2: Compare with other options

   Sorting keys, encrypting data, or counting elements are not the main roles of a hash function in a hash table.

3. Final Answer:

   To convert a key into an index for storing data -> Option C

4. Quick Check:

   Hash function = key to index [OK]

Hint: Hash function maps keys to indexes fast [OK]

Common Mistakes:

• Thinking hash function sorts keys
• Confusing hash function with encryption
• Assuming hash function counts elements

2. Which of the following is the correct syntax to define a simple hash function in Python that returns the remainder of a key divided by 10?

easy

A. def hash_func(key): return key % 10

B. def hash_func(key): return key / 10

C. def hash_func(key): return key * 10

D. def hash_func(key): return key + 10

Solution

1. Step 1: Identify the correct modulus operation

   The hash function should return the remainder when key is divided by 10, which is done using the modulus operator '%'.

2. Step 2: Check syntax correctness

   def hash_func(key): return key % 10 uses 'return key % 10' which is correct syntax and logic. Other options use division, multiplication, or addition which do not produce the remainder.

3. Final Answer:

   def hash_func(key): return key % 10 -> Option A

4. Quick Check:

   Use % for remainder in hash function [OK]

Hint: Use % operator for remainder in hash functions [OK]

Common Mistakes:

• Using division instead of modulus
• Multiplying or adding instead of modulus
• Incorrect function syntax

3. What will be the output of the following code?

def simple_hash(key):
    return key % 5

hash_table = [None] * 5
keys = [12, 22, 17]
for key in keys:
    index = simple_hash(key)
    hash_table[index] = key
print(hash_table)

medium

A. [None, None, 12, 17, 22]

B. [None, None, 17, None, None]

C. [None, 22, 12, None, 17]

D. [None, 12, 22, 17, None]

Solution

1. Step 1: Calculate hash indexes for each key

   12 % 5 = 2, 22 % 5 = 2, 17 % 5 = 2. All three keys map to the same index 2.

2. Step 2: Trace the assignments

   The code assigns directly to hash_table[index] with no collision handling, so later keys overwrite earlier ones at index 2: 12 -> 22 -> 17. Final state: [None, None, 17, None, None].

3. Final Answer:

   [None, None, 17, None, None] -> Option B

4. Quick Check:

   All keys hash to index 2, last key stored [OK]

Hint: Check hash index for each key carefully [OK]

Common Mistakes:

• Assuming keys store at different indexes without collision
• Ignoring overwriting in hash table
• Miscomputing modulus

4. Identify the error in the following hash function code:

def hash_func(key):
    return key // 10

hash_table = [None] * 10
index = hash_func(25)
hash_table[index] = 25
print(hash_table)

medium

A. No error, code runs correctly

B. hash_table size is too small for keys

C. Function should return key * 10 instead

D. Using integer division instead of modulus causes wrong indexing

Solution

1. Step 1: Understand the hash function logic

   The function uses integer division '//' which divides key by 10 and returns the quotient, not the remainder.

2. Step 2: Check impact on indexing

   For key=25, 25 // 10 = 2, which is a valid index but this is not a typical hash function behavior. Usually, modulus '%' is used to get remainder for index within table size.

3. Step 3: Identify the error

   Using '//' can cause indexes outside the hash table size if keys are large. Modulus '%' should be used to ensure index is within table size.

4. Final Answer:

   Using integer division instead of modulus causes wrong indexing -> Option D

5. Quick Check:

   Use % for index, not // [OK]

Hint: Use % to keep index within table size [OK]

Common Mistakes:

• Confusing integer division with modulus
• Ignoring table size limits
• Assuming code runs without error

5. You want to design a hash function for strings that returns an index between 0 and 9 for a hash table of size 10. Which of the following functions correctly implements this?

hard

A. def hash_func(s): return sum(ord(c) for c in s) % 10

B. def hash_func(s): return len(s) * 10

C. def hash_func(s): return ord(s[0])

D. def hash_func(s): return s.count('a')

Solution

1. Step 1: Understand the requirement

   The hash function must return an integer index between 0 and 9 for any string input.

2. Step 2: Analyze each option

   def hash_func(s): return sum(ord(c) for c in s) % 10 sums ASCII values of all characters and uses modulus 10 to keep index in range 0-9. def hash_func(s): return len(s) * 10 multiplies length by 10, which can exceed 9. def hash_func(s): return ord(s[0]) returns ASCII of first char, which can be larger than 9. def hash_func(s): return s.count('a') counts 'a's, which can be any number, possibly larger than 9.

3. Step 3: Choose correct function

   Only def hash_func(s): return sum(ord(c) for c in s) % 10 guarantees index in 0-9 range for any string.

4. Final Answer:

   def hash_func(s): return sum(ord(c) for c in s) % 10 -> Option A

5. Quick Check:

   Sum ASCII % table size for string hash [OK]

Hint: Sum ASCII codes and mod by table size [OK]

Common Mistakes:

• Using string length times 10 as index
• Using ASCII code directly without modulus
• Using character count without range check