Hast Table

Space	Time
	Access	Lookup	Insertion	Deletion
O(n)	N/A	O(1)	O(1)	O(1)

Definition

Short

Hash Table is a data structure used to store and retrieve data using a hash function.

Simplified

You have a big box of toys and you want to find your favorite toy car quickly next time you play. So, you decide to keep each toy in a specific spot in the box. For example, you always put your toy car in the top left corner. This way, the next time you want to play with it, you know exactly where it is and can grab it quickly without having to search through the whole box.

Detailed

Hash Table is a data structure that pairs keys with values. It uses a hash function to calculate an index for each key, directing it to a specific bucket or slot where the corresponding value is stored. While the goal is for each key to have a unique index, some hash functions may assign the same index to multiple keys, causing what's known as a hash collision. These collisions need to be managed in the design of the hash table.

Practice

Practice

Aspect	Pseudo Code
Insertion	insert(key, value): index = key.hash_code() % HASH_MODULO table[index] = Pair(key, value)
Search	search(key): index = key.hash_code() % HASH_MODULO if table[index] != ø: return table[index] return ø
Deletion	delete(key): index = key.hash_code() % HASH_MODULO table[index] = null

Solution

type HashTable struct {
    table []*Pair
    size  int
}

type Pair struct {
    Key   string
    Value interface{}
}

func NewHashTable(size int) *HashTable {
    return &HashTable{
        table: make([]*Pair, size),
        size:  size,
    }
}

func (ht *HashTable) hash(key string) int {
    return int(crc32.ChecksumIEEE([]byte(key)) % uint32(ht.size))
}

func (ht *HashTable) Insert(key string, value interface{}) {
    index := ht.hash(key)
    ht.table[index] = &Pair{Key: key, Value: value}
}

func (ht *HashTable) Search(key string) interface{} {
    index := ht.hash(key)
    if ht.table[index] != nil {
        return ht.table[index].Value
    }
    return nil
}

func (ht *HashTable) Delete(key string) {
    index := ht.hash(key)
    ht.table[index] = nil
}

import java.util.ArrayList;
import java.util.List;

public class HashTable {

  private List<Pair<String, Object>> table;
  private int size;

  public HashTable() {
    this.table = new ArrayList<>();
    this.size = 10;
  }

  private int hash(String key) {
    return key.hashCode() % size;
  }

  public void insert(String key, Object value) {
    int index = hash(key);
    table.add(index, new Pair<>(key, value));
  }

  public Object search(String key) {
    int index = hash(key);
    if (table.get(index) != null) {
      return table.get(index).getValue();
    }
    return null;
  }

  public void delete(String key) {
    int index = hash(key);
    table.set(index, null);
  }
}

class HashTable {
  constructor() {
    this.table = [];
    this.size = 10;
  }

  hash(key) {
    return key.hashCode() % this.size;
  }

  insert(key, value) {
    const index = this.hash(key);
    this.table[index] = { key, value };
  }

  search(key) {
    const index = this.hash(key);
    if (this.table[index] !== undefined) {
      return this.table[index].value;
    }
    return null;
  }

  delete(key) {
    const index = this.hash(key);
    this.table[index] = null;
  }
}

class HashTable {
    private val table: MutableList<Pair<String, Any>?> = mutableListOf()
    private val size: Int = 10

    private fun hash(key: String): Int {
        return key.hashCode() % size
    }

    fun insert(key: String, value: Any) {
        val index = hash(key)
        table[index] = Pair(key, value)
    }

    fun search(key: String): Any? {
        val index = hash(key)
        return table[index]?.second
    }

    fun delete(key: String) {
        val index = hash(key)
        table[index] = null
    }
}

class HashTable:
    def __init__(self):
        self.table = [None] * 10

    def hash(self, key):
        return hash(key) % len(self.table)

    def insert(self, key, value):
        index = self.hash(key)
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash(key)
        if self.table[index] is not None:
            return self.table[index][1]
        return None

    def delete(self, key):
        index = self.hash(key)
        self.table[index] = None

use std::collections::HashMap;

struct HashTable {
    table: HashMap<String, Box<dyn Any>>,
}

impl HashTable {
    fn new() -> Self {
        HashTable {
            table: HashMap::new(),
        }
    }

    fn insert(&mut self, key: String, value: Box<dyn Any>) {
        self.table.insert(key, value);
    }

    fn search(&self, key: &str) -> Option<&dyn Any> {
        self.table.get(key).map(|value| value.as_ref())
    }

    fn delete(&mut self, key: &str) {
        self.table.remove(key);
    }
}

class HashTable {
  private table: { [key: string]: any } = {};
  private size: number = 10;

  insert(key: string, value: any) {
    const index = this.hash(key);
    this.table[index] = { key, value };
  }

  search(key: string): any {
    const index = this.hash(key);
    if (this.table[index] !== undefined) {
      return this.table[index].value;
    }
    return null;
  }

  delete(key: string) {
    const index = this.hash(key);
    delete this.table[index];
  }

  private hash(key: string): number {
    return key.hashCode() % this.size;
  }
}