Algorithm
A hash table, also known as a hash map, is a data structure that implements an associative array abstract data type. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. The hash function takes an input (or key) and returns a fixed-size string of characters, which is typically a hash code.
The key idea behind a hash table is to provide efficient data retrieval by reducing the key space into a smaller array index. This allows for constant time average-case complexity for basic operations like inserting, deleting, and finding elements, under the assumption that the hash function distributes keys uniformly across the array.
Here's a basic overview of how a hash table works:
-
Hash Function:
- A hash function takes a key as input and produces a hash code, which is an integer or a fixed-size string.
-
Indexing:
- The hash code is used to determine the index in the array (bucket) where the corresponding value will be stored or retrieved.
-
Collision Handling:
-
Collisions occur when two different keys produce the same hash code. Hash tables use various techniques to handle collisions, such as chaining or open addressing.
-
Chaining: Each bucket in the array is a linked list, and when a collision occurs, the new key-value pair is simply appended to the list.
-
Open Addressing: When a collision occurs, the algorithm looks for the next available slot in the array until an empty slot is found.
-
-
-
Load Factor:
- The load factor is the ratio of the number of elements to the number of buckets. A higher load factor means more collisions are likely, potentially reducing performance. Dynamic resizing of the array (rehashing) is often performed when the load factor exceeds a certain threshold.
Hash tables are widely used in various applications and programming languages due to their efficiency in providing constant-time average-case complexity for basic operations. They are fundamental in the implementation of dictionaries, sets, caches, and other data structures where quick data retrieval is crucial.
Code Examples
#1 Simple example of a hash table implemented in Python:
Code -
Python Programming
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def _hash_function(self, key):
# A simple hash function for demonstration purposes
return hash(key) % self.size
def insert(self, key, value):
index = self._hash_function(key)
if self.table[index] is None:
self.table[index] = [(key, value)]
else:
# Handling collisions using chaining (each bucket is a list of key-value pairs)
for pair in self.table[index]:
if pair[0] == key:
# Update the value if the key already exists
pair = (key, value)
break
else:
# If key doesn't exist in the bucket, append it
self.table[index].append((key, value))
def get(self, key):
index = self._hash_function(key)
if self.table[index] is not None:
for pair in self.table[index]:
if pair[0] == key:
return pair[1] # Return the value associated with the key
raise KeyError(f"Key not found: {key}")
def remove(self, key):
index = self._hash_function(key)
if self.table[index] is not None:
for i, pair in enumerate(self.table[index]):
if pair[0] == key:
del self.table[index][i] # Remove the key-value pair
return
raise KeyError(f"Key not found: {key}")
# Example usage:
hash_table = HashTable(size=10)
hash_table.insert("name", "John")
hash_table.insert("age", 25)
hash_table.insert("city", "New York")
print("Value for 'name':", hash_table.get("name"))
print("Value for 'age':", hash_table.get("age"))
print("Value for 'city':", hash_table.get("city"))
hash_table.remove("age")
# This will raise a KeyError because "age" has been removed
# print("Value for 'age':", hash_table.get("age"))
#2 Simple example of using a hash table in Java
Code -
Java Programming
import java.util.HashMap;
import java.util.Map;
public class HashTableExample {
public static void main(String[] args) {
// Create a HashMap
Map < String, Integer> hashMap = new HashMap<>();
// Adding key-value pairs to the hash table
hashMap.put("John", 25);
hashMap.put("Jane", 30);
hashMap.put("Doe", 22);
// Accessing values using keys
System.out.println("John's age: " + hashMap.get("John"));
System.out.println("Jane's age: " + hashMap.get("Jane"));
// Updating the value for a key
hashMap.put("John", 26);
System.out.println("Updated John's age: " + hashMap.get("John"));
// Removing a key-value pair
hashMap.remove("Doe");
// Checking if a key is present
System.out.println("Is Jane present? " + hashMap.containsKey("Jane"));
// Iterating through the hash table
System.out.println("Iterating through the hash table:");
for (Map.Entry < String, Integer> entry : hashMap.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
#3 Simple example of using a hash table in C:
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10
// Define a structure for a key-value pair
typedef struct {
char key[50];
int value;
} KeyValuePair;
// Define a structure for the hash table
typedef struct {
KeyValuePair* table[TABLE_SIZE];
} HashTable;
// Hash function to convert a key into an index
unsigned int hash(char* key) {
unsigned int hash_value = 0;
for (int i = 0; i < strlen(key); i++) {
hash_value = hash_value * 31 + key[i];
}
return hash_value % TABLE_SIZE;
}
// Function to initialize a hash table
void initializeHashTable(HashTable* ht) {
for (int i = 0; i < TABLE_SIZE; i++) {
ht->table[i] = NULL;
}
}
// Function to insert a key-value pair into the hash table
void insertIntoHashTable(HashTable* ht, char* key, int value) {
unsigned int index = hash(key);
// Create a new key-value pair
KeyValuePair* new_pair = (KeyValuePair*)malloc(sizeof(KeyValuePair));
strcpy(new_pair->key, key);
new_pair->value = value;
// Insert the new pair into the hash table
ht->table[index] = new_pair;
}
// Function to retrieve the value associated with a key from the hash table
int getFromHashTable(HashTable* ht, char* key) {
unsigned int index = hash(key);
// Retrieve the key-value pair from the hash table
KeyValuePair* pair = ht->table[index];
// Check if the key exists in the hash table
if (pair != NULL && strcmp(pair->key, key) == 0) {
return pair->value;
} else {
// Key not found
return -1;
}
}
int main() {
// Create a hash table
HashTable myHashTable;
initializeHashTable(&myHashTable);
// Insert key-value pairs into the hash table
insertIntoHashTable(&myHashTable, "one", 1);
insertIntoHashTable(&myHashTable, "two", 2);
insertIntoHashTable(&myHashTable, "three", 3);
// Retrieve values from the hash table
printf("Value for key 'one': %d\n", getFromHashTable(&myHashTable, "one"));
printf("Value for key 'two': %d\n", getFromHashTable(&myHashTable, "two"));
printf("Value for key 'three': %d\n", getFromHashTable(&myHashTable, "three"));
printf("Value for key 'four': %d\n", getFromHashTable(&myHashTable, "four")); // Key not found
return 0;
}
#4 Simple example of using a hash table in C++
Code -
C++ Programming
#include <iostream>
#include <unordered_map>
int main() {
// Creating a hash table (unordered_map) with string keys and int values
std::unordered_map < std::string, int> hashTable;
// Inserting values into the hash table
hashTable["apple"] = 5;
hashTable["banana"] = 3;
hashTable["orange"] = 7;
// Accessing values using keys
std::cout << "Number of apples: " << hashTable["apple"] << std::endl;
std::cout << "Number of bananas: " << hashTable["banana"] << std::endl;
// Checking if a key exists in the hash table
std::string keyToCheck = "grape";
if (hashTable.find(keyToCheck) != hashTable.end()) {
std::cout << "Number of " << keyToCheck << "s: " << hashTable[keyToCheck] << std::endl;
} else {
std::cout << keyToCheck << " not found in the hash table." << std::endl;
}
// Iterating through the hash table
std::cout << "Iterating through the hash table:" << std::endl;
for (const auto& entry : hashTable) {
std::cout << entry.first << ": " << entry.second << std::endl;
}
return 0;
}
Demonstration
Hash Table - Data Structure and Algorithms-DevsEnv