Mastering Hash Tables: A Comprehensive Guide with Examples

Hash tables are data structures that allow for efficient storage and retrieval of key-value pairs. They provide an average time complexity of O(1) for both insertion, deletion, and lookup operations, making them highly suitable for applications like caching, routing tables, and dictionary implementations.

The core logic behind hash tables involves using a hash function to map keys to indices in an array. This is crucial for efficient data retrieval. A collision occurs when two different keys produce the same index, which can be managed through various strategies such as chaining, open addressing, or using separate chaining.

python
def hash_function(key: str) -> int:
    return sum(ord(char) for char in key) % 100

javascript
function hashFunction(key) {
    let total = 0;
    for (let i = 0; i < key.length; i++) {
        total += key.charCodeAt(i);
    }
    return total % 100;
}

go
type HashTable struct {
	data map[int][]interface{}
}
func (ht *HashTable) put(key string, value interface{}) {
	index := hashFunction(key)
	if ht.data[index] == nil {
		ht.data[index] = []interface{}{value}
	} else {
		ht.data[index] = append(ht.data[index], value)
	}
}

rust
struct HashTable {
	hash_map: std::collections::HashMap) {
		let index = self.hash_function(key.as_str()) as i32;
		if let Some(values) = self.hash_map.get_mut(&index) {
			values.push(value);
		} else {
			self.hash_map.insert(index, vec![value]);
		}
	}

	named fn hash_function(key: &str) -> i32 {
		key.chars().map(|c| c as i32).sum() % 100
	}
}

The time complexity of hash table operations is generally O(1) under normal circumstances, assuming a good hash function that distributes keys evenly across the array. However, in cases of collisions (multiple keys mapping to the same index), the worst-case time complexity can degrade to O(n). The space complexity depends on the number of elements and the size of the hash table.