手撕HashMap！（JDK7版本）

你能自己实现一个 HashMap 吗

六个字段，十四个方法

  
class MyHashMap<K, V> {  // 节点类（用于链表）    
static class Node<K, V> {  private K key;  private V value;  private Node<K, V> next;  public Node(K key, V value) {  this.key = key;  this.value = value;  }  public Node(K key, V value, Node<K, V> next) {  this.key = key;  this.value = value;  this.next = next;  }  }  // 初始容量    
static final int DEFAULT_CAPACITY = 16;  // 负载因子    
static final float LOAD_FACTOR = 0.75f;  //最大容量  static final int MAX_CAPACITY = 1 << 30;  private int size;  private Node<K, V>[] buckets;  // 无参构造    
public MyHashMap() {  buckets = new Node[DEFAULT_CAPACITY];  size = 0;  }  // 有参构造    
public MyHashMap(int capacity) {  if (capacity <= 0) {  throw new IllegalArgumentException("Capacity must be greater than 0");  }  // 找到大于等于传入容量的最小 2 的幂    
int cap = tableSizeFor(capacity);  buckets = new Node[cap];  size = 0;  }  private int tableSizeFor(int cap) {  int n = cap - 1;  n |= n >>> 1;  n |= n >>> 2;  n |= n >>> 4;  n |= n >>> 8;  n |= n >>> 16;  return (n < 0) ? 1 : (n >= MAX_CAPACITY) ? MAX_CAPACITY : n + 1;  }  // 高位扰动函数，提升 hash 的随机性  private int hash(Object key) {  int h;  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  }  // 获取桶索引（取模优化为位运算）    
private int getIndex(Object key, int length) {  return hash(key) & (length - 1);  }  // put 方法（公开接口）    
public void put(K key, V value) {  if (size >= buckets.length * LOAD_FACTOR) {  resize(); // 扩容    
}  putVal(key, value, buckets);  }  // put 逻辑（链表插入或更新）    
private void putVal(K key, V value, Node<K, V>[] table) {  int index = getIndex(key, table.length);  Node<K, V> node = table[index];  // 如果该桶是空的，直接放入    
if (node == null) {  table[index] = new Node<>(key, value);  size++;  return;  }  // 否则遍历链表，若 key 存在则更新，否则插入到链表头    
while (node != null) {  if (node.key.hashCode() == key.hashCode() &&  (node.key == key || node.key.equals(key))) {  node.value = value;  return;  }  node = node.next;  }  // 新节点插入链表头    
Node<K, V> newNode = new Node<>(key, value, table[index]);  table[index] = newNode;  size++;  }  // 扩容    
private void resize() {  Node<K, V>[] newBuckets = new Node[buckets.length * 2];  rehash(buckets, newBuckets);  buckets = newBuckets;  }  // 重新哈希，把旧桶的数据重新分配到新桶    
private void rehash(Node<K, V>[] oldBuckets, Node<K, V>[] newBuckets) {  for (int i = 0; i < oldBuckets.length; i++) {  if (oldBuckets[i] == null) {  continue;  }  Node<K, V> node = oldBuckets[i];  while (node != null) {  putVal(node.key, node.value, newBuckets);  node = node.next;  }  oldBuckets[i] = null;  }  }  // 获取值    
public V get(K key) {  int index = getIndex(key, buckets.length);  if (buckets[index] == null) {  return null;  }  Node<K, V> node = buckets[index];  while (node != null) {  if (node.key.hashCode() == key.hashCode() &&  (node.key == key || node.key.equals(key))) {  return node.value;  }  node = node.next;  }  return null;  }  // 获取当前元素个数    
public int size() {  return size;  }  // 判断 key 是否存在    
public boolean containsKey(K key) {  int index = getIndex(key, buckets.length);  Node<K, V> node = buckets[index];  while (node != null) {  if (node.key.hashCode() == key.hashCode() &&  (node.key == key || node.key.equals(key))) {  return true;  }  node = node.next;  }  return false;  }  // 删除指定 key    public V remove(K key) {  int index = getIndex(key, buckets.length);  Node<K, V> node = buckets[index];  Node<K, V> prev = null;  while (node != null) {  if (node.key.hashCode() == key.hashCode() &&  (node.key == key || node.key.equals(key))) {  // 如果是头节点  if (prev == null) {  buckets[index] = node.next;  } else {  prev.next = node.next;  }  size--;  return node.value; // 返回被删除的值  }  prev = node;  node = node.next;  }  return null; // 未找到 key         }  // 清空所有键值对    
public void clear() {  // 将桶数组置空    
for (int i = 0; i < buckets.length; i++) {  buckets[i] = null;  }  size = 0;  }  
}