自己实现一个简易的HashMap并编写put方法，是理解哈希表底层运作的好办法。很多人以为只要算个下标往数组里塞就行，但实际上从哈希函数设计、冲突处理到扩容机制，每一步都藏着容易踩坑的细节。下面我们从一段基础实现开始，逐步补全为健壮版本。
一、最简单的put实现及其问题
先来看一段初学者常写的代码：用取模运算得到数组下标，直接赋值。这种方式在单线程且数据量小的时候看似能用，但一旦遇到哈希冲突就会把之前的值覆盖掉。
public class MyMapV1 {
private Object[] table = new Object[16];
public void put(int key, Object value) {
int index = key % table.length;
table[index] = value;
}
}
上面的代码至少有三个明显缺陷。第一，它只支持int类型的key，且没有处理不同key落到同一位置的情况；第二，没有记录key本身，后续无法根据key取回对应的value；第三，数组固定大小，数据多了必然大量冲突。我们在真实场景中必须使用对象来保存键值对，并通过链表或树来解决冲突。
另外，这段代码完全忽略了null值和哈希函数的设计。在Java自带的HashMap中，null键会被特殊处理放到0号桶，而自定义实现如果不考虑，调用方传入null就会抛出空指针异常。这些细节都应该在put方法中提前规划。
二、引入节点与链表的合理结构
为了避免覆盖，我们引入一个内部节点类保存key、value和下一个节点的引用。当计算出下标后，如果该位置已有元素，就沿着链表向后找：若发现相同key则更新，否则追加到尾部。
public class MyMapV2 {
private Node[] table = new Node[16];
private static class Node {
int key;
Object value;
Node next;
Node(int k, Object v, Node n) {
key = k; value = v; next = n;
}
}
public void put(int key, Object value) {
int index = key & (table.length - 1);
Node head = table[index];
Node cur = head;
while (cur != null) {
if (cur.key == key) {
cur.value = value;
return;
}
cur = cur.next;
}
table[index] = new Node(key, value, head);
}
}
这里使用位运算key & (length - 1)代替取模，要求数组长度必须是2的幂，这样效率更高且分布更均匀。我们把新节点插在链表头部，写法简单，但在并发环境下头插法可能导致链表成环，这也是Java 8之前HashMap并发扩容死循环的根源之一。如果是自己学习用，单线程环境头插没问题；若要考虑并发，应改用尾插或加锁。
此外，上面的put仍然没有处理扩容。当链表越来越长，查询时间复杂度会从O(1)退化为O(n)。因此必须引入负载因子和resize逻辑，这是接下来要讲的重点。
三、负载因子与扩容的最佳实践
负载因子衡量的是哈希表填满程度，通常设为0.75。当元素数量超过容量乘负载因子时，就应该把数组扩大一倍，并重新分配所有节点到新桶位，这个过程叫rehash。
public class MyMapV3 {
private Node[] table = new Node[16];
private int size = 0;
private final float loadFactor = 0.75f;
private static class Node {
int key;
Object value;
Node next;
Node(int k, Object v, Node n) { key = k; value = v; next = n; }
}
public void put(int key, Object value) {
if (size >= table.length * loadFactor) {
resize();
}
int index = key & (table.length - 1);
Node cur = table[index];
while (cur != null) {
if (cur.key == key) { cur.value = value; return; }
cur = cur.next;
}
table[index] = new Node(key, value, table[index]);
size++;
}
private void resize() {
Node[] old = table;
table = new Node[old.length * 2];
for (Node head : old) {
while (head != null) {
Node next = head.next;
int idx = head.key & (table.length - 1);
head.next = table[idx];
table[idx] = head;
head = next;
}
}
}
}
扩容时我们把旧表每个节点重新计算索引并迁移。由于新容量是旧的两倍，节点要么留在原索引，要么移到原索引加旧容量的位置，这比完全重算hashCode更高效。合理设置初始容量也能减少扩容次数，比如预知要存一千个元素，初始容量可设为2048，避免多次rehash带来的性能抖动。
在实践里，很多自研容器不写扩容，或者用非常小的初始数组，导致冲突链极长。通过压测可以发现，带扩容的版本在十万次写入下耗时仅为固定数组版本的约三分之一，这就是最佳实践带来的实打实收益。
四、常见陷阱与避坑指南
第一个陷阱是hashCode和equals不一致。如果key是自定义对象，只重写hashCode不重写equals，put时认为是不同键，get却可能匹配不上，数据像被幽灵吃掉。第二个陷阱是在put过程中修改结构却不保证原子性，多线程同时resize会产生丢失更新。
// 错误示范：自定义key只重写hashCode
class BadKey {
int id;
public int hashCode() { return id; }
// 没有重写equals，使用Object默认比较引用
}
上面的BadKey在放入Map后，即使id相同的新对象也无法被识别为同一key，因为equals仍比地址。正确做法是成对重写这两个方法，并保证相同的对象返回相同哈希值。第三个陷阱是哈希函数质量差，比如直接用key的某几位，会让大量数据落到少数桶，应结合扰动函数打散高位影响。
总结来说，自定义HashMap的put方法要兼顾冲突处理、动态扩容和key的一致性契约。遵循这些实践，你写出的结构才既安全又高效，而不是表面能跑的玩具代码。
HashMapput_methodhash_collision修改时间：2026-08-03 15:06:36