Hash Tables
In the world of data structures, hash tables are powerful tools that provide efficient data retrieval based on key-value pairs.
A hash table, also known as a hash map, is a data structure that uses a hash function to map keys to indices within an array. This allows for constant-time (O(1)) access, insertion, and deletion of elements.
The idea behind a hash table is to store the data in an array using a unique index generated by the hash function. The hash function takes a key as input and returns an index where the value associated with the key should be stored.
Here's an example of creating a hash table using Python:
PYTHON
1class HashTable:
2 def __init__(self):
3 self.size = 10
4 self.table = [None] * self.size
5
6 def _hash(self, key):
7 hash_value = 0
8 for char in str(key):
9 hash_value += ord(char)
10 return hash_value % self.size
11
12 def insert(self, key, value):
13 index = self._hash(key)
14 self.table[index] = value
15
16 def get(self, key):
17 index = self._hash(key)
18 return self.table[index]
19
20# Creating a hash table
21ht = HashTable()
22
23# Inserting key-value pairs
24ht.insert('apple', 'red')
25ht.insert('banana', 'yellow')
26
27# Get values using keys
28print(ht.get('apple')) # Output: red
29print(ht.get('banana')) # Output: yellow