datastructures6HashTableImpl

1package pkg3datastructures;2 3/*4 * datastructures6HashTableImpl.java5 * ------------------6 * A hash map using separate chaining (buckets of linked entries) with resizing.7 * Demonstrates how HashMap works under the hood.8 *9 * COMPLEXITY: get/put/remove O(1) average, O(n) worst (all collisions).10 * KEY IDEAS: hashCode -> bucket index; load factor triggers resize/rehash.11 */12public class datastructures6HashTableImpl {13 14    static class Entry<K, V> {15        final K key; V value; Entry<K, V> next;16        Entry(K key, V value) { this.key = key; this.value = value; }17    }18 19    static class MyHashMap<K, V> {20        private Entry<K, V>[] buckets;21        private int size;22        private static final double LOAD_FACTOR = 0.75;23 24        @SuppressWarnings("unchecked")25        MyHashMap() { buckets = new Entry[8]; }26 27        private int indexFor(K key) {28            int h = (key == null) ? 0 : key.hashCode();29            h ^= (h >>> 16);                       // spread bits (like HashMap)30            return (buckets.length - 1) & h;       // fast modulo for power-of-two size31        }32 33        void put(K key, V value) {34            int i = indexFor(key);35            for (Entry<K, V> e = buckets[i]; e != null; e = e.next) {36                if (java.util.Objects.equals(e.key, key)) { e.value = value; return; }37            }38            Entry<K, V> head = new Entry<>(key, value);39            head.next = buckets[i];40            buckets[i] = head;41            if (++size > buckets.length * LOAD_FACTOR) resize();42        }43 44        V get(K key) {45            for (Entry<K, V> e = buckets[indexFor(key)]; e != null; e = e.next) {46                if (java.util.Objects.equals(e.key, key)) return e.value;47            }48            return null;49        }50 51        boolean remove(K key) {52            int i = indexFor(key);53            Entry<K, V> prev = null, e = buckets[i];54            while (e != null) {55                if (java.util.Objects.equals(e.key, key)) {56                    if (prev == null) buckets[i] = e.next; else prev.next = e.next;57                    size--; return true;58                }59                prev = e; e = e.next;60            }61            return false;62        }63 64        int size() { return size; }65 66        @SuppressWarnings("unchecked")67        private void resize() {68            Entry<K, V>[] old = buckets;69            buckets = new Entry[old.length * 2];70            size = 0;71            for (Entry<K, V> head : old)72                for (Entry<K, V> e = head; e != null; e = e.next) put(e.key, e.value);73        }74    }75 76    public static void main(String[] args) {77        MyHashMap<String, Integer> map = new MyHashMap<>();78        map.put("one", 1); map.put("two", 2); map.put("three", 3);79        map.put("two", 22);                            // update existing80        System.out.println("get(two)=" + map.get("two") + " get(missing)=" + map.get("x"));81        System.out.println("size=" + map.size());82        System.out.println("remove(one)=" + map.remove("one") + " size=" + map.size());83 84        // Force several inserts to trigger a resize85        for (int i = 0; i < 20; i++) map.put("k" + i, i);86        System.out.println("after many puts size=" + map.size() + " get(k15)=" + map.get("k15"));87    }88}