Hash Table Implementation in Rust

1. Introduction

A hash table, also known as a hash map, is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. Given its nature, hash tables achieve constant time average complexity for search operations, provided the key space is evenly distributed.

2. Implementation Steps

1. Define a structure for each Bucket that can hold key-value pairs.

2. Initialize a vector of Buckets which will be our hash table.

3. Define a hash_function to compute an index for our key.

4. Implement functions for insert, get, and remove.

5. Handle collisions using chaining - where each bucket contains a list of key-value pairs.

3. Implementation in Rust Programming

const TABLE_SIZE: usize = 1024;
type KeyValuePair<K, V> = (K, V);
type Bucket<K, V> = Vec<KeyValuePair<K, V>>;
pub struct HashTable<K, V>
where
    K: std::hash::Hash + std::cmp::PartialEq,
{
    table: Vec<Bucket<K, V>>,
}
impl<K, V> HashTable<K, V>
where
    K: std::hash::Hash + std::cmp::PartialEq + Clone,
    V: Clone,
{
    pub fn new() -> Self {
        HashTable {
            table: vec![Vec::new(); TABLE_SIZE],
        }
    }
    fn hash_function(&self, key: &K) -> usize {
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        key.hash(&mut hasher);
        hasher.finish() as usize % TABLE_SIZE
    }
    pub fn insert(&mut self, key: K, value: V) {
        let index = self.hash_function(&key);
        let bucket = &mut self.table[index];
        for &mut (ref existing_key, ref mut existing_value) in bucket.iter_mut() {
            if existing_key == &key {
                *existing_value = value.clone();
                return;
            }
        }
        bucket.push((key, value));
    }
    pub fn get(&self, key: K) -> Option<V> {
        let index = self.hash_function(&key);
        for &(ref existing_key, ref value) in &self.table[index] {
            if existing_key == &key {
                return Some(value.clone());
            }
        }
        None
    }
    pub fn remove(&mut self, key: K) {
        let index = self.hash_function(&key);
        let bucket = &mut self.table[index];
        bucket.retain(|&(ref existing_key, _)| existing_key != &key);
    }
}
fn main() {
    let mut hash_table = HashTable::new();
    hash_table.insert("key1", "value1");
    hash_table.insert("key2", "value2");
    println!("{:?}", hash_table.get("key1".to_string())); // Prints: Some("value1")
    hash_table.remove("key1".to_string());
    println!("{:?}", hash_table.get("key1".to_string())); // Prints: None
}

Output:

Some("value1")
None

Explanation:

1. We define a Bucket to be a vector of key-value pairs. This allows us to handle collisions using chaining, where each collided item will simply be appended to the respective bucket.

2. The HashTable struct holds our table of buckets.

3. The new function initializes our hash table with a predetermined size.

4. The hash_function computes an index for a given key. Here, we use Rust's built-in hash functions for convenience.

5. The insert function first checks if a key already exists in the table. If it does, the value is updated; otherwise, a new key-value pair is added.

6. The get function retrieves the value associated with a given key.

7. The remove function deletes a key-value pair from the table by retaining all items in the bucket except the one with the specified key.