Core Principles of ADTs

Overview: Hash Tables & Sets

• High-level ADT: define operations put, get, remove for maps; add, contains, remove for sets.
• Hash table: data stored in an array; a hash function maps keys to bucket indices.
• Load factor: ratio of stored entries to bucket count; controls resizing to maintain efficiency.
• Collision resolution: techniques like chaining (linked lists per bucket) or open addressing (probing).
• Built-ins: Python’s dict/set and Java’s HashMap/HashSet abstract these details away.

Deep Dive: Hash Table Structure

A hash table stores entries as key:value pairs in an underlying array of buckets. When you insert an entry, its key is run through the hash function to compute an index, and the (key, value) pair is placed in the corresponding bucket. By directing each lookup or insertion to a single bucket, hash tables achieve average O(1) performance without scanning the entire data set.

Example: Simple Hash Table (no collisions)

Scenario: Mapping a student to his or her awarded grade

We maintain a small hash table that maps each student’s numeric ID to their final grade. Our hash function is simply studentID mod 10, and because our IDs are chosen carefully, no two students collide in the same bucket. Our student IDs are 1001, 1002, 1004, 1006, 1007, and 1008.

Index   Bucket → Entry
-----   ---------------------
   0    → null
   1    → 1001 → “A”
   2    → 1002 → “B+”
   3    → null
   4    → 1004 → “C”
   5    → null
   6    → 1006 → “A–”
   7    → 1007 → “B”
   8    → 1008 → “A”
   9    → null
    

Here, each bucket directly holds one (ID, grade) pair because our student IDs (1001, 1002, 1004, 1006, 1007, 1008) all hash to distinct slots. Lookups and inserts require only one array access: true O(1) performance.

Deep Dive: Hash Functions & Load Factor

A hash function transforms a key into an integer (the hash code) and then into a bucket index via index = hashCode mod tableSize. Using our Student ID → Grade example above, for student 1001 we compute 1001 mod 10 = 1, so their grade “A” is stored in bucket 1; because no two IDs collide, each lookup or insert is a single array access.

As you insert more entries, the load factor (n / tableSize) rises. With chaining, buckets hold more items on average; with open addressing, collisions (meaning longer probe sequences) become more likely. High load factors lead to longer bucket lists (in chaining) or more probes (in open addressing), which degrades lookup and insertion performance toward O(n).

To prevent this, once the load factor exceeds a threshold (commonly 0.75), the table is resized, typically doubling its capacity, and all entries are rehashed into the larger array, restoring O(1) average-time operations.

// Pseudocode for resizing
if (size / capacity > LOAD_FACTOR_THRESHOLD):
    oldTable = table
    capacity = capacity * 2
    table = new array[capacity]
    for each bucket in oldTable:
        for each entry in bucket:
            index = hash(entry.key) mod capacity
            table[index].add(entry)
    

Deep Dive: Collision Resolution with Chaining

In chaining, each bucket holds a linked list of all entries whose keys hash to that index. New entries simply append to the list; lookups scan the list. Even when collisions occur, other buckets are unaffected. In the example below, in student 1011 we compute 1011 mod 10 = 1: which collides with student 1001 - but we chain collisions (using a linked list).

  Buckets (array of lists):
  [0] → null
  [1] → (1001, “A”) → (1011, “B”) → null
  [2] → null
  [3] → (1003, “C”) → null
  [4] → null
  [5] → null
  [6] → (1006, “A–”) → null
  [7] → null
  [8] → null
  [9] → null
    

• Both student IDs 1001 and 1011 hash to bucket 1
• The bucket’s list chains them together
• Lookup “1011” scans 1001 then 1011 and finds it

Pseudocode for Chaining

// Pseudocode: put with chaining
function put(key, value):
    index = hash(key) mod capacity
    for entry in table[index]:
        if entry.key == key:
            entry.value = value   // update existing
            return
    table[index].append((key,value))  // new entry
    

Deep Dive: Collision Resolution with Open Addressing (Linear Probing)

In Open addressing with linear probing, each bucket holds at most one entry. On collision, the algorithm checks successive buckets (wrapping around to the beginning, if necessary) until an empty slot is found. Lookups follow the same probe sequence until the key is found or an empty bucket is reached.

  Buckets (single-entry array):
  [0]   -  
  [1]  → (1001, “A”)
  [2]   -  
  [3]  → (1003, “C”)
  [4]   -  
  [5]   -  
  [6]  → (1006, “A–”)
  [7]   -  
  [8]   -  
  [9]   -  

  Insert 1011 (“B”):
    1011 mod 10 = 1 → bucket 1 occupied
    probe → 2: empty → place (1011,“B”) at bucket 2

  Final state:
  [1] → (1001,“A”)
  [2] → (1011,“B”)
  [3] → (1003,“C”)
  [6] → (1006,“A–”)

  Lookup 1011:
    check bucket 1 → no
    check bucket 2 → yes → found
    

Pseudocode for Probing

// Pseudocode: get with open addressing
function get(key):
    index = hash(key) mod capacity
    for i from 0 to capacity-1:
        probe = (index + i) mod capacity
        if table[probe] is empty:
            return null           // not found
        if table[probe].key == key:
            return table[probe].value
    return null
    

Built-in Hash-based Collections

dict (Python)

Python’s dict is a hash-table‐backed map from arbitrary immutable keys to values. Under the hood, each key’s built-in __hash__() (or hash()) produces an integer, which is reduced modulo the current table size to pick a bucket. Collisions are handled via open addressing (perturbed probing), and when the load factor (≈2/3 by default) is exceeded, the table resizes and all entries are rehashed. All lookups, inserts and deletes run in O(1) average time.

set (Python)

A Python set is, in effect, a dict that stores keys only (each mapped to a dummy value). It uses exactly the same hashing, probing and resizing mechanisms as dict, guaranteeing O(1) average‐time membership tests (x in myset), additions and removals.

HashMap (Java)

Java’s java.util.HashMap<K,V> implements a hash‐table map using separate chaining by default. Each bucket in the underlying array holds a (initially) linked list of Node<K,V> entries whose keys’ hashCode() map to that index. After a bucket’s chain grows beyond a threshold, it may be converted to a tree for performance. The default load factor is 0.75; when exceeded, the table is resized (usually doubled) and all entries are rehashed. This delivers O(1) average‐time put, get and remove.

HashSet (Java)

A Java java.util.HashSet<E> is simply a thin wrapper around a HashMap<E, Object> that uses a constant dummy value. All add, contains and remove operations delegate directly to the backing HashMap, yielding the same O(1) average‐time performance and collision‐resolution behavior.

Scenarios & Applications

Web Cache

A hash map caches HTTP responses keyed by URL. Fast get and put ensure page loads reuse recent results instead of fetching anew.

Word Frequency Counter

Counting word occurrences in a document uses a hash map from word→count. Each tokenised word increments its count in O(1) average time.

Session Management

A web server stores active user sessions in a HashSet of session tokens to quickly validate incoming requests.

Examples: Python & Java - Dictionaries/Sets and Hash Tables

Example 1: Collections - Frequency & Uniqueness

• Python
• Java

# Word frequency using dict
def word_freq(text):
    freq = {}  # dict ADT
    for w in text.split():
        freq[w] = freq.get(w, 0) + 1
    return freq

# Unique items using set
def unique_items(seq):
    return set(seq)  # built-in set ADT

if __name__ == "__main__":
    doc = "to be or not to be"
    print(word_freq(doc))     # {'to':2,'be':2,'or':1,'not':1}
    print(unique_items([1,2,2,3]))  # {1,2,3}

import java.util.*;

public class MapSetDemo {
    public static Map<String,Integer> wordFreq(String text) {
        Map<String,Integer> freq = new HashMap<>();
        for (String w : text.split("\s+")) {
            freq.put(w, freq.getOrDefault(w, 0) + 1);
        }
        return freq;
    }

    public static Set<Integer> uniqueItems(java.util.List<Integer> list) {
        return new java.util.HashSet<>(list);
    }

    public static void main(String[] args) {
        String doc = "to be or not to be";
        System.out.println(wordFreq(doc));      // {not=1, or=1, to=2, be=2}

        java.util.List<Integer> nums = java.util.Arrays.asList(1,2,2,3);
        System.out.println(uniqueItems(nums));  // [1, 2, 3]
    }
}

Example 2: Hash Table (Chaining)

Separate chaining: each bucket holds a list of key–value pairs.

• Python
• Java

class HashTableChaining:
    def __init__(self, capacity=8):
        self.capacity = capacity
        self.size = 0
        # initialize buckets: a list of lists
        self.buckets = [[] for _ in range(capacity)]

    def _hash(self, key):
        # compute bucket index
        return hash(key) % self.capacity

    def put(self, key, value):
        """Insert or update the key/value pair."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # update existing
                return
        bucket.append((key, value))      # new entry
        self.size += 1

    def get(self, key):
        """Retrieve value by key, or None if not found."""
        index = self._hash(key)
        for k, v in self.buckets[index]:
            if k == key:
                return v
        return None

    def remove(self, key):
        """Remove entry by key if present."""
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return

# Usage example
if __name__ == "__main__":
    ht = HashTableChaining()
    ht.put("Alice", 85)
    ht.put("Bob", 92)
    ht.put("Charlie", 78)
    print("Bob’s grade:", ht.get("Bob"))   # 92
    ht.remove("Alice")
    print("Alice’s grade:", ht.get("Alice"))  # None

import java.util.LinkedList;

public class HashTableChaining<K, V> {
    private java.util.LinkedList<Entry<K, V>>[] buckets;
    private int capacity;
    private int size = 0;

    @SuppressWarnings("unchecked")
    public HashTableChaining(int capacity) {
        this.capacity = capacity;
        buckets = new java.util.LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            buckets[i] = new java.util.LinkedList<>();
        }
    }

    private int hash(K key) {
        return Math.abs(key.hashCode()) % capacity;
    }

    public void put(K key, V value) {
        int idx = hash(key);
        for (Entry<K, V> e : buckets[idx]) {
            if (e.key.equals(key)) {
                e.value = value;  // update existing
                return;
            }
        }
        buckets[idx].add(new Entry<>(key, value));  // new entry
        size++;
    }

    public V get(K key) {
        int idx = hash(key);
        for (Entry<K, V> e : buckets[idx]) {
            if (e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }

    public void remove(K key) {
        int idx = hash(key);
        buckets[idx].removeIf(e -> e.key.equals(key));
    }

    private static class Entry<K, V> {
        K key; V value;
        Entry(K k, V v) { key = k; value = v; }
    }

    // Demonstration
    public static void main(String[] args) {
        HashTableChaining<String, Integer> ht = new HashTableChaining<>(8);
        ht.put("Alice", 85);
        ht.put("Bob", 92);
        ht.put("Charlie", 78);
        System.out.println("Bob’s grade: " + ht.get("Bob"));  // 92
        ht.remove("Alice");
        System.out.println("Alice’s grade: " + ht.get("Alice"));  // null
    }
}

Example 3: Hash Table (Linear Probing)

Open addressing with linear probing; buckets hold single entries.

• Python
• Java

class HashTableProbing:
    def __init__(self, capacity=8):
        self.capacity = capacity
        self.keys = [None] * capacity
        self.values = [None] * capacity
        self.size = 0

    def _hash(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        """Insert or update via linear probing."""
        idx = self._hash(key)
        for _ in range(self.capacity):
            if self.keys[idx] is None or self.keys[idx] == key:
                # empty slot or update existing
                if self.keys[idx] is None:
                    self.size += 1
                self.keys[idx], self.values[idx] = key, value
                return
            idx = (idx + 1) % self.capacity
        raise Exception("Hash table full")

    def get(self, key):
        """Retrieve value or None if not found."""
        idx = self._hash(key)
        for _ in range(self.capacity):
            if self.keys[idx] is None:
                return None
            if self.keys[idx] == key:
                return self.values[idx]
            idx = (idx + 1) % self.capacity
        return None

    def remove(self, key):
        """Remove entry and rehash subsequent cluster."""
        idx = self._hash(key)
        for _ in range(self.capacity):
            if self.keys[idx] == key:
                self.keys[idx] = self.values[idx] = None
                self.size -= 1
                # rehash following cluster
                next_idx = (idx + 1) % self.capacity
                while self.keys[next_idx] is not None:
                    k, v = self.keys[next_idx], self.values[next_idx]
                    self.keys[next_idx] = self.values[next_idx] = None
                    self.size -= 1
                    self.put(k, v)
                    next_idx = (next_idx + 1) % self.capacity
                return
            if self.keys[idx] is None:
                return
            idx = (idx + 1) % self.capacity

# Usage example
if __name__ == "__main__":
    ht = HashTableProbing()
    ht.put("Alice", 85)
    ht.put("Bob", 92)
    ht.put("Charlie", 78)
    print("Bob’s grade:", ht.get("Bob"))   # 92
    ht.remove("Alice")
    print("Alice’s grade:", ht.get("Alice"))  # None

public class HashTableProbing<K, V> {
    private static final Object TOMBSTONE = new Object();
    private Object[] keys;
    private Object[] values;
    private int capacity;
    private int size = 0;

    public HashTableProbing(int capacity) {
        this.capacity = capacity;
        keys = new Object[capacity];
        values = new Object[capacity];
    }

    private int hash(Object key) {
        return Math.abs(key.hashCode()) % capacity;
    }

    public void put(K key, V value) {
        int idx = hash(key);
        for (int i = 0; i < capacity; i++) {
            int probe = (idx + i) % capacity;
            Object k = keys[probe];
            if (k == null || k == TOMBSTONE || k.equals(key)) {
                if (k == null) size++;
                keys[probe] = key;
                values[probe] = value;
                return;
            }
        }
        throw new RuntimeException("Hash table full");
    }

    @SuppressWarnings("unchecked")
    public V get(K key) {
        int idx = hash(key);
        for (int i = 0; i < capacity; i++) {
            int probe = (idx + i) % capacity;
            Object k = keys[probe];
            if (k == null) return null;
            if (!(k == TOMBSTONE) && k.equals(key)) {
                return (V) values[probe];
            }
        }
        return null;
    }

    public void remove(K key) {
        int idx = hash(key);
        for (int i = 0; i < capacity; i++) {
            int probe = (idx + i) % capacity;
            Object k = keys[probe];
            if (k == null) return;
            if (!(k == TOMBSTONE) && k.equals(key)) {
                keys[probe] = TOMBSTONE;
                values[probe] = null;
                size--;
                return;
            }
        }
    }

    // Demonstration
    public static void main(String[] args) {
        HashTableProbing<String, Integer> ht = new HashTableProbing<>(8);
        ht.put("Alice", 85);
        ht.put("Bob", 92);
        ht.put("Charlie", 78);
        System.out.println("Bob’s grade: " + ht.get("Bob"));  // 92
        ht.remove("Alice");
        System.out.println("Alice’s grade: " + ht.get("Alice"));  // null
    }
}