手撕 简易HashMap

put()、get()、remove() 方法

计算存储数组位置和k-vNode节点

    public int indexOf(K key){return key.hashCode() & (table.length - 1);}static class Node<K, V>{K key;V value;Node<K, V> next;public Node(K key, V value){this.key = key;this.value = value;}}

• put(K key,V value)

向 HashMap 里存入数据的方法，逻辑是，先通过 hashCode() 方法获取 key 的 hash值，然后通过（ n - 1) & hash 来得到该键值对存储在数据上的位置。

假如插入的位置没有数据，则直接插入，如果有数据，判断其key是否相同，如果相同就覆盖掉，如果不相同，就遍历这个“哈希桶”中的链表，将其 k-v 以链表的方式插入链表的尾部。

public V put(K key, V value){int keyIndex = indexOf(key);Node<K, V> head = table[keyIndex];if(head == null){table[keyIndex] = new Node<>(key, value);size++;resizeIfNecessary();return null;}while(true){if(head.key.equals(key)){V oldValue = head.value;head.value = value;return oldValue;}if(head.next == null){head.next = new Node<>(key, value);size++;resizeIfNecessary();return null;}head = head.next;}}

• get(K key)

获取 HashMap 里数据的方法，逻辑是，先通过 hashCode() 方法获取 key 的 hash值，然后通过（ n - 1) & hash 来得到该键值对存储在数据上的位置。

假如该位置有数据并且与key相等，说明找到了直接返回，反之则遍历链表，没找到返回null。

    public V get(K key){int keyIndex = indexOf(key);Node<K, V> head = table[keyIndex];while(head != null){if(head.key.equals(key)){return head.value;}head = head.next;}return null;}

• remove(K key)

删除 HashMap 里数据的方法，逻辑是，先通过 hashCode() 方法获取 key 的 hash值，然后通过（ n - 1) & hash 来得到该键值对存储在数据上的位置。

假如为null，说明没有返回null，如果在数组上则直接删除，并将下一个节点放在数组位置上，若数组没有则需遍历链表寻找。注意在删除后需 “接上链表” 。

 public V remove(K key){int keyIndex = indexOf(key);Node<K, V> head = table[keyIndex];if(head == null){return null;}if(head.key.equals(key)){table[keyIndex] = head.next;size--;return head.value;}Node<K, V> pre = head;Node<K, V> current = head.next;while(current != null){if(current.key.equals(key)){pre.next = current.next;size--;return current.value;}pre = pre.next;current = current.next;}return null;}

扩容机制

负载因子为 0.75，也就是说当容量为 16 时，16 * 0.75 = 12 ，当存储第 13 个数据时，触发扩容机制。

扩容为原来数组的 2 倍。

遍历 HashMap 上的所有 k-v ，然后放在新的数组上。

 private void resizeIfNecessary(){if(this.size < table.length * 0.75){return;}Node<K, V>[] newTable = new Node[table.length * 2];for(Node<K, V> head : this.table){if(head == null){continue;}Node<K, V> current = head;while(current != null){int newIndex = current.key.hashCode() & (newTable.length - 1);if(newTable[newIndex] == null){newTable[newIndex] = current;Node<K, V> next = current.next;current.next = null;current = next;} else {Node<K, V> next = current.next;current.next = newTable[newIndex];newTable[newIndex] = current;current = next;}}}this.table = newTable;}