Data Structures & Algorithms – Hash tables
Hash tables, also known as hash maps, are a data structure that maps keys to values using a hashing function. They are commonly used for tasks such as implementing dictionaries, caches, and sets. Hash tables are highly efficient, with an average time complexity of O(1) for both insertion and retrieval operations.
One common way to implement a hash table using only primitives is to use an array and a hash function to map keys to indices in the array. The hash function takes in a key and returns an index in the array where the value associated with that key should be stored. A collision occurs when the hash function maps two different keys to the same index in the array. To handle collisions, one common method is to use an open addressing scheme, where the array is searched for an empty slot after a collision occurs.
Here is an example of how to implement a hash table using primitives in Python:
class HashTable:
def __init__(self):
self.size = 10
self.table = [None] * self.size
def _hash_function(self, key):
return hash(key) % self.size
def set(self, key, value):
index = self._hash_function(key)
if self.table[index] is None:
self.table[index] = (key, value)
else:
for i in range(index, self.size):
if self.table[i] is None:
self.table[i] = (key, value)
break
def get(self, key):
index = self._hash_function(key)
if self.table[index] is not None and self.table[index][0] == key:
return self.table[index][1]
else:
for i in range(index, self.size):
if self.table[i] is not None and self.table[i][0] == key:
return self.table[i][1]
return None
And here is an example of how to implement a hash table using primitives in JavaScript:
class HashTable {
constructor() {
this.size = 10;
this.table = Array(this.size).fill(null);
}
_hashFunction(key) {
return key.toString().split('').reduce((acc, char) => acc + char.charCodeAt(0), 0) % this.size;
}
set(key, value) {
const index = this._hashFunction(key);
if (this.table[index] === null) {
this.table[index] = [key, value];
} else {
for (let i = index; i < this.size; i++) {
if (this.table[i] === null) {
this.table[i] = [key, value];
break;
}
}
}
}
get(key) {
const index = this._hashFunction(key);
if (this.table[index] !== null && this.table[index][0] === key) {
return this.table[index][1];
} else {
for (let i = index; i < this.size; i++) {
if (this.table[i] !== null && this.table[i][0] === key) {
return this.table[i][1];
}
}
}
return null;
}
}
And here is an example of how to implement a hash table using primitives in Java:
public class HashTable {
private int size;
private String[][] table;
public HashTable() {
size = 10;
table = new String[size][2];
}
private int hashFunction(String key) {
int hash = key.hashCode();
return hash % size;
}
public void set(String key, String value) {
int index = hashFunction(key);
if (table[index][0] == null) {
table[index][0] = key;
table[index][1] = value;
} else {
for (int i = index; i < size; i++) {
if (table[i][0] == null) {
table[i][0] = key;
table[i][1] = value;
break;
}
}
}
}
public String get(String key) {
int index = hashFunction(key);
if (table[index][0] != null && table[index][0].equals(key)) {
return table[index][1];
} else {
for (int i = index; i < size; i++) {
if (table[i][0] != null && table[i][0].equals(key)) {
return table[i][1];
}
}
}
return null;
}
}
And here is an example of how to implement a hash table using primitives in Rust:
struct HashTable {
table: Vec<Option<(String, String)>>,
size: usize,
}
impl HashTable {
fn new() -> Self {
HashTable {
table: vec![None; 10],
size: 10,
}
}
fn hash_function(&self, key: &str) -> usize {
let mut hash = 0;
for c in key.chars() {
hash += c as usize;
}
hash % self.size
}
fn set(&mut self, key: String, value: String) {
let index = self.hash_function(&key);
if self.table[index].is_none() {
self.table[index] = Some((key, value));
} else {
for i in index..self.size {
if self.table[i].is_none() {
self.table[i] = Some((key, value));
break;
}
}
}
}
fn get(&self, key: &str) -> Option<&String> {
let index = self.hash_function(key);
if let Some((k, v)) = &self.table[index] {
if k == key {
return Some(v);
}
}
for i in index..self.size {
if let Some((k, v)) = &self.table[i] {
if k == key {
return Some(v);
}
}
}
None
}
}
It’s important to note that these examples are provided for educational purposes only and should not be used in production as they do not include any collision handling strategy or resizing strategy in case the hash table becomes too full. Additionally, the hash function provided in the examples is not very robust and may lead to poor performance for certain types of keys. In practice, more robust and efficient hash functions should be used.