Storing Key-Value Pairs with Hash Table

A Hash Table is a data structure that stores data in key-value pairs, enabling fast data retrieval, insertion, and deletion.

In Python, a hash table is implemented as a Dictionary.

The hash table uses a Hash Function to calculate the storage location (address) for each key.

Imagine storing names and phone numbers in a hash table.

Here, a hash function could use the sum of the digits in a phone number modulus 10 as a hash code.

For a phone number like 010-1234-5678, the hash function calculates 0+1+0+1+2+3+4+5+6+7+8 = 37, and the remainder when divided by 10, which is 7, is used as the hash code.

By using hash codes to store data, you can quickly retrieve data using the phone number as a key.

Data is stored at the address calculated by the hash function, and later, the same hash function finds this storage location to retrieve the data.

Hashing is the process of transforming data into a unique hash code using a hash function.

The hash code is a unique value reflecting the data's characteristics and is used as an address (index) for storage.

For instance, the hash code for 010-1234-5678 is 7, which determines the storage address (index).

A Hash Collision occurs when different keys have the same hash code.

When a hash collision occurs, it is necessary to decide how to store data with the same hash code.

For example, in the case of 010-4321-8765, which also has a hash code of 7, the second entry needs special handling.

A common method to handle hash collisions is Chaining, where data with the same hash code values are linked in a Linked List.

Below is a simple hash table implementation in Python.

Copy
# Initialize Hash Table
hash_table = ["", "", "", "", "", "", "", ""]

# Convert key to hash value
def get_key(data):
    return hash(data)

# Define hash function
def hash_function(key):
    return key % 8

# Store data (key-value pair)
def save_data(data, value):
    hash_address = hash_function(get_key(data))
    hash_table[hash_address] = value

# Retrieve data
def read_data(data):
    hash_address = hash_function(get_key(data))
    return hash_table[hash_address]

# Add data
save_data(2, 'Apple')
save_data(11, 'Banana')

# Retrieve data
print("Key2:", read_data(2))
# Output: Apple
print("Key11:", read_data(11))
# Output: Banana

In the above code, the hash function hash_function is defined to return the remainder when the key is divided by 8.

For instance, calling save_data(11, 'Banana') will pass 11 to the hash function, which will return 3.

Then 'Banana' will be stored at hash_table[3].

Because a hash table allows direct access to data using a key, it can add, search, and delete data in average constant time O(1).

Thus, hash tables are utilized in various fields such as databases and caching due to their fast data retrieval capabilities.

However, performance can degrade from constant time O(1) to linear time O(n) due to key collisions.

Additionally, hash tables do not guarantee data order, so if order is important, other structures like Lists may be more suitable.