1import java.util.Objects;
2
3public class MyHashMap<K, V> {
4    private static class Entry<K, V> {
5        final K key;
6        V value;
7        Entry<K, V> next;
8
9        Entry(K key, V value, Entry<K, V> next) {
10            this.key = key;
11            this.value = value;
12            this.next = next;
13        }
14    }
15
16    private Entry<K, V>[] buckets;
17    private int size;
18    private final double loadFactor;
19
20    @SuppressWarnings("unchecked")
21    public MyHashMap(int capacity, double loadFactor) {
22        this.buckets = (Entry<K, V>[]) new Entry[capacity];
23        this.loadFactor = loadFactor;
24    }
25
26    public MyHashMap() {
27        this(16, 0.75);
28    }
29
30    private int indexFor(K key, int length) {
31        int hash = Objects.hashCode(key);
32        return (hash & 0x7fffffff) % length;
33    }
34
35    public V get(K key) {
36        int index = indexFor(key, buckets.length);
37        Entry<K, V> current = buckets[index];
38
39        while (current != null) {
40            if (Objects.equals(current.key, key)) {
41                return current.value;
42            }
43            current = current.next;
44        }
45
46        return null;
47    }
48
49    public void put(K key, V value) {
50        int index = indexFor(key, buckets.length);
51        Entry<K, V> current = buckets[index];
52
53        while (current != null) {
54            if (Objects.equals(current.key, key)) {
55                current.value = value;
56                return;
57            }
58            current = current.next;
59        }
60
61        buckets[index] = new Entry<>(key, value, buckets[index]);
62        size++;
63
64        if ((double) size / buckets.length > loadFactor) {
65            resize();
66        }
67    }
68
69    public V remove(K key) {
70        int index = indexFor(key, buckets.length);
71        Entry<K, V> current = buckets[index];
72        Entry<K, V> previous = null;
73
74        while (current != null) {
75            if (Objects.equals(current.key, key)) {
76                if (previous == null) {
77                    buckets[index] = current.next;
78                } else {
79                    previous.next = current.next;
80                }
81                size--;
82                return current.value;
83            }
84            previous = current;
85            current = current.next;
86        }
87
88        return null;
89    }
90
91    public int size() {
92        return size;
93    }
94
95    @SuppressWarnings("unchecked")
96    private void resize() {
97        Entry<K, V>[] oldBuckets = buckets;
98        buckets = (Entry<K, V>[]) new Entry[oldBuckets.length * 2];
99        size = 0;
100
101        for (Entry<K, V> head : oldBuckets) {
102            Entry<K, V> current = head;
103            while (current != null) {
104                put(current.key, current.value);
105                current = current.next;
106            }
107        }
108    }
109}