Hash Table Concept and Hash Functions in DSA Python - Build from Scratch

Hash Table Concept and Hash Functions

📖 Scenario: Imagine you are organizing a small library. You want to quickly find books by their titles. To do this, you decide to use a simple hash table where each book title is linked to its shelf number.

🎯 Goal: You will create a hash table using a Python dictionary, write a simple hash function to assign shelf numbers, and then store and display the books with their shelf numbers.

📋 What You'll Learn

Create a dictionary called books with given book titles as keys and empty values.

Create a simple hash function called simple_hash that takes a book title and returns a shelf number.

Use the hash function to assign shelf numbers to each book in the books dictionary.

Print the final books dictionary showing book titles and their shelf numbers.

💡 Why This Matters

🌍 Real World

Hash tables help organize data for quick searching, like finding books in a library by their titles.

💼 Career

Understanding hash tables and hash functions is important for software development, database indexing, and efficient data retrieval.

1

Create the initial books dictionary

Create a dictionary called books with these exact keys and empty values: 'Python Basics', 'Data Science', 'Machine Learning', 'Deep Learning', 'Artificial Intelligence'.

DSA Python

# Create the books dictionary with given titles and empty values
# Your code here

Hint

Use a dictionary with book titles as keys and null as values for now.

2

Define a simple hash function

Define a function called simple_hash that takes a parameter title. It should return the sum of the Unicode values of all characters in title modulo 10.

DSA Python

books = {
    'Python Basics': null,
    'Data Science': null,
    'Machine Learning': null,
    'Deep Learning': null,
    'Artificial Intelligence': null
}

# Define the simple_hash function below
# Your code here

Hint

Use ord() to get Unicode values and sum() to add them up. Use modulo 10 to limit shelf numbers.

3

Assign shelf numbers using the hash function

Use a for loop with variables title and _ to iterate over books.items(). Inside the loop, assign books[title] the value returned by simple_hash(title).

DSA Python

books = {
    'Python Basics': null,
    'Data Science': null,
    'Machine Learning': null,
    'Deep Learning': null,
    'Artificial Intelligence': null
}

def simple_hash(title):
    return sum(ord(char) for char in title) % 10

# Assign shelf numbers to each book using simple_hash
# Your code here

Hint

Use for title, _ in books.items(): to loop and assign shelf numbers.

4

Print the books dictionary with shelf numbers

Write print(books) to display the dictionary showing book titles and their assigned shelf numbers.

DSA Python

books = {
    'Python Basics': null,
    'Data Science': null,
    'Machine Learning': null,
    'Deep Learning': null,
    'Artificial Intelligence': null
}

def simple_hash(title):
    return sum(ord(char) for char in title) % 10

for title, _ in books.items():
    books[title] = simple_hash(title)

# Print the books dictionary
# Your code here

Hint

The printed dictionary shows each book title with its shelf number.

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