带你手写一个hashMap,通过手写hashMap带你剖析hashMap的源码

**HashMap源码分析**

在Java中，HashMap是最常用的散列集合类之一。它提供了快速查找、插入和删除元素的功能。然而，很多人可能对HashMap的内部实现机制并不熟悉。在本文中，我们将手写一个简单的HashMap，并通过源码分析来剖析其内部工作原理。

**HashMap基本结构**

首先，让我们看一下HashMap的基本结构：

javapublic class HashMap extends AbstractMap
 implements Map, Cloneable, java.io.Serializable {
 // ...
}

从上面的代码中，我们可以看到HashMap继承了AbstractMap类，并实现了Map接口。HashMap还实现了Cloneable和Serializable接口。

**HashMap内部结构**

下面是HashMap的内部结构：

javapublic class HashMap extends AbstractMap
 implements Map, Cloneable, java.io.Serializable {
 // ...

 private static final int DEFAULT_INITIAL_CAPACITY =16;
 private static final float DEFAULT_LOAD_FACTOR =0.75f;

 private Node[] table; // 散列数组 private int size; // 元素数量 private int threshold; // 阈值 // ...
}

从上面的代码中，我们可以看到HashMap有三个重要的成员变量：

* `table`:散列数组，用于存储元素。
* `size`:元素数量。
* `threshold`:阈值。

**Node类**

在HashMap内部结构中，我们还定义了一个Node类：

javaprivate static class Node {
 K key;
 V value;
 Node next;

 public Node(K key, V value) {
 this.key = key;
 this.value = value;
 }
}

从上面的代码中，我们可以看到Node类有三个成员变量：

* `key`:键。
* `value`:值。
* `next`:下一个节点。

**put方法**

下面是HashMap的put方法：

javapublic V put(K key, V value) {
 // ...
}

从上面的代码中，我们可以看到put方法用于将元素添加到HashMap中。具体实现如下：

javapublic V put(K key, V value) {
 int hash = hash(key);
 int i = indexFor(hash);

 for (Node bin = table[i]; bin != null; bin = bin.next) {
 if (bin.key.equals(key)) {
 V oldValue = bin.value;
 bin.value = value;
 return oldValue;
 }
 }

 addEntry(hash, key, value);
 return null;
}

从上面的代码中，我们可以看到put方法的实现步骤如下：

1. 计算键的散列值。
2. 根据散列值找到对应的桶。
3. 遍历桶中的元素，检查是否有相同的键。
4. 如果有相同的键，则更新其值并返回旧值。
5. 如果没有相同的键，则添加新元素。

**addEntry方法**

下面是HashMap的addEntry方法：

javaprivate void addEntry(int hash, K key, V value) {
 int i = indexFor(hash);
 if ((tab[i] = new Node(key, value)) == null) {
 throw new OutOfMemoryError();
 }
}

从上面的代码中，我们可以看到addEntry方法用于添加新元素到HashMap中。具体实现如下：

1. 根据散列值找到对应的桶。
2. 如果桶为空，则创建新的Node对象并赋值给桶。

**get方法**

下面是HashMap的get方法：

javapublic V get(Object key) {
 // ...
}

从上面的代码中，我们可以看到get方法用于查找指定键对应的值。具体实现如下：

javapublic V get(Object key) {
 int hash = (key == null) ?0 : System.identityHashCode(key);
 int i = indexFor(hash);

 for (Node bin = table[i]; bin != null; bin = bin.next) {
 if (bin.key.equals(key)) {
 return bin.value;
 }
 }

 return null;
}

从上面的代码中，我们可以看到get方法的实现步骤如下：

1. 计算键的散列值。
2. 根据散列值找到对应的桶。
3. 遍历桶中的元素，检查是否有相同的键。
4. 如果有相同的键，则返回其值。
5. 如果没有相同的键，则返回null。

**总结**

在本文中，我们手写了一个简单的HashMap，并通过源码分析来剖析其内部工作原理。从上面的代码中，我们可以看到HashMap的基本结构、内部结构和Node类都非常重要。put方法用于添加元素到HashMap中，get方法用于查找指定键对应的值。通过理解HashMap的内部实现机制，我们可以更好地使用它来管理我们的数据。

**参考**

* Java API文档：[ />* HashMap源码分析：[