What is the idea of a Hash Table?

A hash table, also known as a hash map, is a data structure that allows you to store and retrieve values
based on their associated keys. The main idea behind a hash table is to provide fast and efficient access
to values using a hash function, which converts the key into an index for an underlying array or list.

The key components of a hash table are:

1. Keys: Unique identifiers used to store and retrieve associated values.

2. Values: Data associated with the keys.

3. Hash function: A function that takes a key as input and returns an index (also called a hash code)
for the underlying array or list. A good hash function distributes keys uniformly across the array,
minimizing collisions.

4. Array or list: The underlying data structure that stores the values, usually indexed by the hash
codes generated by the hash function.

When you want to store a value in a hash table, the hash function computes an index based on the key.
The value is then stored at that index in the array or list. If multiple keys produce the same index (a
collision), various techniques can be employed to resolve the conflict, such as separate chaining or open
addressing.

To retrieve a value from a hash table, the same hash function is used to compute the index for the given
key, and the value is retrieved from the corresponding index in the array or list.

The main advantage of hash tables is their ability to provide near-constant time complexity (O(1)) for
common operations such as insertion, deletion, and search, making them highly efficient for storing and
retrieving data in various applications. However, their performance depends on the quality of the hash
function and the chosen collision resolution strategy.

What is the idea of Hashing (or a hash function)?

Hashing is a fundamental concept in computer science and cryptography, which involves converting
data (usually a string or a file) into a fixed-size output, known as a hash value or hash digest. The process
is carried out using a mathematical algorithm called a hash function.

The idea behind hashing is to create a unique representation of the input data, with the following
properties:

1. Deterministic: The same input data should always produce the same hash value.

2. Fast computation: Hash functions should be computationally efficient, producing hash values
quickly.

Page 1 of 5
 3. Avalanche effect: Small changes in input data should result in vastly different hash values,
making it difficult to predict or reverse-engineer the original data from the hash.

4. Collision resistance: It should be extremely difficult to find two different inputs that produce the
same hash value.

Hashing has several practical applications, including:

 Data integrity: Hash values can be used to verify if data has been altered or tampered with,
ensuring the integrity of the information.

 Digital signatures and message authentication codes: Hash functions are used to create digital
signatures and message authentication codes, ensuring the authenticity and integrity of
messages and documents.

 Password storage: Storing hashed versions of passwords can help protect sensitive user
information. When a user logs in, their password is hashed, and the result is compared to the
stored hash value.

 Data indexing and retrieval: Hash tables and other data structures use hash functions to map
keys to values, enabling efficient data indexing and retrieval.

Overall, hashing plays a crucial role in various aspects of computing and security, providing an efficient
and secure way to handle data.

Implementation
To implement a simple hash table using object-oriented programming in Python, you can create a
custom class called HashTable with the required methods for adding, retrieving, and deleting key-value
pairs. Here's a basic example:

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

def _hash(self, key):

return hash(key) % self.size

def set(self, key, value):

index = self._hash(key)

if not self.table[index]:
self.table[index] = [(key, value)]
else:
for i, pair in enumerate(self.table[index]):
if pair[0] == key:
self.table[index][i] = (key, value)
break
else:

Page 2 of 5
 self.table[index].append((key, value))

def get(self, key):

index = self._hash(key)

if self.table[index]:
for pair in self.table[index]:
if pair[0] == key:
return pair[1]

raise KeyError(f"Key '{key}' not found.")

def delete(self, key):

index = self._hash(key)

if self.table[index]:
for i, pair in enumerate(self.table[index]):
if pair[0] == key:
del self.table[index][i]
break
else:
raise KeyError(f"Key '{key}' not found.")
else:
raise KeyError(f"Key '{key}' not found.")

# Example usage
hash_table = HashTable(10)
hash_table.set("apple", 1)
hash_table.set("banana", 2)
hash_table.set("orange", 3)

print(hash_table.get("apple")) # Output: 1
print(hash_table.get("banana")) # Output: 2
print(hash_table.get("orange")) # Output: 3

hash_table.delete("apple")

Code Explanation
The above code defines a simple HashTable class in Python using object-oriented programming. It
demonstrates basic functionality for adding, retrieving, and deleting key-value pairs in a hash table.
Here's a step-by-step explanation of how the code works:

1. __init__: This is the constructor of the HashTable class. It takes one argument, size, which is the
size of the hash table. It initializes the table attribute as a list of None values with the specified
size.

2. _hash: This is a private helper method that calculates the hash value for a given key. It uses the
built-in hash() function to compute the hash value and then takes the modulo with the size of
the hash table to ensure the index is within the bounds of the table.

Page 3 of 5
 3. set: This method is used to add a key-value pair to the hash table. It first calculates the index in
the table using the _hash() method. If the index is empty (i.e., contains None), it creates a new
list with a single tuple (key-value pair) and assigns it to that index. If the index already contains a
list, it iterates through the list to check if the key already exists. If it does, it updates the value of
the key. If it doesn't, it appends the key-value pair to the list.

4. get: This method is used to retrieve the value associated with a given key in the hash table. It
calculates the index in the table using the _hash() method. If the index contains a list, it iterates
through the list to find the tuple with the matching key and returns its associated value. If the
key is not found, it raises a KeyError.

5. delete: This method is used to remove a key-value pair from the hash table. It calculates the
index in the table using the _hash() method. If the index contains a list, it iterates through the
list to find the tuple with the matching key and deletes it. If the key is not found, it raises a
KeyError.

The example usage at the end of the code demonstrates how to create a HashTable object, add key-
value pairs to it, retrieve values, and delete keys. Note that this implementation is simplistic and may
not be suitable for production use. In real-world applications, you would typically use Python's built-in
dict data structure or a specialized library for more advanced hashing needs.

What makes a good hash function (Properties of a good functions)

A good hash function has several important properties to ensure efficiency and security. Here are some
key characteristics of a good hash function:

1. Deterministic: The hash function must always produce the same output for the same input data.
This ensures consistency and repeatability when using the hash function.

2. Fast computation: A good hash function should be computationally efficient, meaning it can
quickly generate hash values, especially in applications where large amounts of data need to be
processed.

3. Uniform distribution: The hash function should distribute the hash values uniformly across the
entire range of possible outputs. This minimizes the chances of collisions and helps maintain the
performance of the underlying data structures like hash tables.

4. Avalanche effect: A small change in the input data should result in a significantly different hash
value. This property makes it difficult to predict or reverse-engineer the original data based on
the hash value, which is essential in cryptographic applications.

5. Collision resistance: It should be extremely difficult to find two different inputs that produce the
same hash value. This property is important for the security of hash functions used in
cryptographic applications.

6. Non-invertible: A good hash function should be one-way, meaning it's infeasible to reconstruct
the original input data from the hash value. This is particularly important for cryptographic
applications and secure storage of sensitive data (e.g., passwords).

Page 4 of 5
Examples of popular hash functions:

1. MD5: Message-Digest Algorithm 5 (MD5) is a widely-used cryptographic hash function that

produces a 128-bit (16-byte) hash value. It was designed by Ronald Rivest in 1991. However, due
to security vulnerabilities, it is not recommended for cryptographic use today.

2. SHA-1: Secure Hash Algorithm 1 (SHA-1) is a cryptographic hash function that produces a 160-bit
(20-byte) hash value. It was developed by the National Security Agency (NSA) in the United
States. Similar to MD5, SHA-1 is no longer considered secure for cryptographic purposes due to
vulnerability to collision attacks.

3. SHA-2: The SHA-2 family of hash functions includes SHA-224, SHA-256, SHA-384, SHA-512, SHA-
512/224, and SHA-512/256. These functions were also designed by the NSA and offer improved
security over SHA-1. They are widely used in various cryptographic applications, including digital
signatures and password hashing.

4. SHA-3: SHA-3 is the latest family of hash functions, which includes SHA3-224, SHA3-256, SHA3-
384, and SHA3-512. It was developed as a result of the NIST hash function competition and is
based on the Keccak algorithm. SHA-3 provides even stronger security properties than SHA-2
and is recommended for new applications requiring cryptographic hash functions.

In non-cryptographic applications, hash functions like MurmurHash, CityHash, and xxHash are popular
due to their computational efficiency and good distribution properties. These functions are commonly
used for tasks like data indexing and retrieval in hash tables.

Page 5 of 5