这是一个参考 JDK7 实现的非常简单的 HashMap,只实现了最最基础的 get、put、remove、containsKey 方法。解决冲突用的是最简单的拉链法,hash 用的是 JDK 自带的 hashCode() 提供的值。这份代码主要面向面试时的手撕 HashMap,本文会逐一介绍每个部分的实现,最后会在文末给出所有代码。
CONTENT关于头插和尾插的问题我是这么考虑的:
选用和 JDK 7 一样的头插,不考虑并发下头插成环问题,因为我觉得并发修改必然就得加锁,没有必要考虑并发下的一些问题,至于加锁后效率那是加锁需要考虑的问题。并且假设刚 put 的元素,最有可能马上 get,所以选用效率可能较高的头插。
- 接口
- Entry
- 全局变量 & 构造方法
- get & containsKey
- put
- 扩容
- remove
- entryList
- 全部代码
- 接口 MyMap
- 实现类 MyHashMap
- Reference
在 MyMap 接口中定义了要实现的方法,本次只准备实现 5 个基础方法,get、put、remove、containsKey 和 自创的 entryList(就是把所有 Entry 放进一个 List,只是为了方便打印全部元素看看效果)。
MyMap.Entry 接口定义了 MyHashMap 中存放的每个元素 Entry 将提供的方法。
public interface MyMapEntry{ V get(K key); V put(K key, V value); V remove(K key); boolean containsKey(K key); List > entryList(); interface Entry { K getKey(); V getValue(); void setKey(K key); void setValue(V value); } }
MyHashMap 中每个元素对象的类,正常的 key-value 键值对,因为拉链法,加上 next 指向下一个 Entry。
static class Entry全局变量 & 构造方法implements MyMap.Entry { K key; V value; Entry next; public Entry(K key, V value, Entry next) { this.key = key; this.value = value; this.next = next; } @Override public K getKey() { return key; } @Override public V getValue() { return value; } @Override public void setKey(K key) { this.key = key; } @Override public void setValue(V value) { this.value = value; } @Override public String toString() { return "Entry{" + "key=" + key + ", value=" + value + ", next=" + next + '}'; } }
loadFactor 是负载因子,默认为 0.75,当存储元素数量超过 capacity*loadFactor 时,进行扩容。
threshold = capacity*loadFactor,当 size >= threshold 时扩容。
size 是当前存储的 Entry 元素的数量。
table 数组用来存储 Entry 元素。
提供三个构造方法,初始化时,以及之后的扩容,保证 table 的 length 一定是 2 的次幂。
为什么 HashMap 的大小为什么必须是 2 的倍数?
- 利用 hash 值计算索引时,如果用取余 hash%length 效率较低,并且当 length 是 2 的倍数时,hash&(length-1) 和 取余的结果是一样的,但位运算比取余的效率高得多。
- length 是 2 的倍数,扩容时可以直接看 hash&oldLength 是不是等于 0,如果等于 0,那这个元素继续呆在原来的位置(比如说 j),如果不等于 0,那么这个元素放到新扩容出来的 j+oldLength 的位置,这和重新计算索引的结果是一样。但这样减少了对于每个元素都重新计算它的索引的开销。(JDK8 的实现)
class MyHashMapget & containsKeyimplements MyMap { private static final int DEFAULT_INITIAL_CAPACITY = 16; private static final float DEFAULT_LOAD_FACTOR = 0.75f; private final float loadFactor; private int threshold; private int size; private Entry [] table; public MyHashMap(int initCapacity, float loadFactor) { int capacity = 1; while (capacity < initCapacity) capacity <<= 1; this.loadFactor = loadFactor; table = new Entry[capacity]; threshold = (int) (capacity*loadFactor); size = 0; } public MyHashMap(int initCapacity) { this(initCapacity, DEFAULT_LOAD_FACTOR); } public MyHashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } }
这两个其实可以做成一个实现,因为他们本质上都是要找某一个 key 所属的 Entry,只不过 get 要求返回 key 所属的 Entry 中的 value,而 containsKey 只想知道这个 key 所属的 Entry 是否存在。所以完全可以实现一个 getEntry() 方法,返回 key 所属的 Entry。这样 get() 就是返回 getEntry() 找到的 Entry 中的 value,而 containsKey 则是判断 getEntry() 能否找到对应的 Entry。
getEntry() 先得到 key 对应 table 中的索引下标,拿到 table 下标处链表的头节点,遍历链表,用 key 做比较,如果找到直接返回当前 entry,找不到则返回 null。
@Override
public V get(K key) {
Entry entry = getEntry(key);
return entry == null ? null : entry.getValue();
}
private Entry getEntry(K key) {
int index = getKeyIndex(key);
for (Entry entry = table[index]; entry != null; entry = entry.next) {
if (entry.getKey() == key || entry.getKey().equals(key)) {
return entry;
}
}
return null;
}
private int getKeyIndex(K key) {
return key == null ? 0 : (key.hashCode() & (table.length-1));
}
@Override
public boolean containsKey(K key) {
return getEntry(key) != null;
}
put
这算是这里面最难的了,因为涉及到扩容 resize()。
put 思路比较简单,先得到 key 对应 table 中的索引下标,拿到 table 下标处链表的头节点,遍历链表,用 key 做比较,看有没有和 key 一样的 Entry,如果有,直接更新这个 Entry 的 value 并返回原来的 value (这部分 和 getEntry() 的逻辑一样)。如果 table 中没有这个 key,说明需要新建一个 Entry 存储这个 key-value 对。但在新建 Entry 前,先检查是否需要扩容,即 size >= threshold。然后新建一个 Entry 并头插到原来的链表里,并把新的链表头更新到 table[index] 中。
@Override
public V put(K key, V value) {
int index = getKeyIndex(key);
// 找有没有 key 一样的
for (Entry entry = table[index]; entry != null; entry = entry.next) {
if (entry.getKey() == key || entry.getKey().equals(key)) {
V oldValue = entry.getValue();
entry.setValue(value);
return oldValue;
}
}
// 没有一样的 key 只能新建一个 Entry
// 新建之前先检查是否需要扩容
if (size >= threshold) {
resize(table.length*2);
index = getKeyIndex(key); // 因为扩容了,原来的索引不一定对
}
table[index] = new Entry<>(key, value, table[index]);
size++;
return value;
}
private int getKeyIndex(K key) {
return key == null ? 0 : (key.hashCode() & (table.length-1));
}
扩容
resize() 新建一个是原来 table 长度二倍的 table,并将原来 table 的元素迁移到新建的 table 中去。最后更新 threshold = newCapacity*loadFactor。
这里迁移做的比较简单:遍历一遍原来的 table,在遍历的同时,计算每个元素在新的 table 中的索引下标,然后把它头插到新 table 中对应的索引下标的链表中去,并把新的链表头更新到新的 table[index] 中。
private void resize(int newCapacity) {
Entry[] oldTable = table;
table = new Entry[newCapacity];
for (Entry entry : oldTable) {
while (entry != null) {
Entry next = entry.next;
int index = getKeyIndex(entry.getKey());
entry.next = table[index];
table[index] = entry;
entry = next;
}
}
threshold = (int) (newCapacity*loadFactor);
}
remove
看过前面的 get、put 之后,remove 相比之下就非常简单了。计算得到 key 对应 table 中的索引下标,拿到 table 下标处链表的头节点,遍历链表,并记录当前节点的前一个节点 pre,然后用 key 做比较,看有没有和 key 一样的 Entry,如果有,用 pre 节点指向当前节点的 next,做一个链表删除操作即可。
@Override
public V remove(K key) {
int index = getKeyIndex(key);
Entry entry = table[index];
Entry pre = null;
while (entry != null) {
if (entry.getKey() == key || entry.getKey().equals(key)) {
if (pre != null) {
pre.next = entry.next;
} else {
table[index] = entry.next;
}
return entry.getValue();
}
pre = entry;
entry = entry.next;
}
return null;
}
private int getKeyIndex(K key) {
return key == null ? 0 : (key.hashCode() & (table.length-1));
}
entryList
entryList 非常简单,遍历一遍 table,把每个 Entry 添加到结果 List 中即可。这个方法只是为了方便打印全部元素看看效果。
@Override public List全部代码 接口 MyMap> entryList() { List > res = new ArrayList<>(); for (Entry entry : table) { while (entry != null) { res.add(entry); entry = entry.next; } } return res; }
import java.util.List; public interface MyMap实现类 MyHashMap{ V get(K key); V put(K key, V value); V remove(K key); boolean containsKey(K key); List > entryList(); interface Entry { K getKey(); V getValue(); void setKey(K key); void setValue(V value); } }
import java.util.ArrayList; import java.util.Arrays; import java.util.List; class MyHashMapReferenceimplements MyMap { private static final int DEFAULT_INITIAL_CAPACITY = 16; private static final float DEFAULT_LOAD_FACTOR = 0.75f; private final float loadFactor; private int threshold; private int size; private Entry [] table; public MyHashMap(int initCapacity, float loadFactor) { int capacity = 1; while (capacity < initCapacity) capacity <<= 1; this.loadFactor = loadFactor; table = new Entry[capacity]; threshold = (int) (capacity*loadFactor); size = 0; } public MyHashMap(int initCapacity) { this(initCapacity, DEFAULT_LOAD_FACTOR); } public MyHashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } @Override public V get(K key) { Entry entry = getEntry(key); return entry == null ? null : entry.getValue(); } private Entry getEntry(K key) { int index = getKeyIndex(key); for (Entry entry = table[index]; entry != null; entry = entry.next) { if (entry.getKey() == key || entry.getKey().equals(key)) { return entry; } } return null; } private int getKeyIndex(K key) { return key == null ? 0 : (key.hashCode() & (table.length-1)); } @Override public V put(K key, V value) { int index = getKeyIndex(key); // 找有没有 key 一样的 for (Entry entry = table[index]; entry != null; entry = entry.next) { if (entry.getKey() == key || entry.getKey().equals(key)) { V oldValue = entry.getValue(); entry.setValue(value); return oldValue; } } // 没有一样的 key 只能新建一个 Entry // 新建之前先检查是否需要扩容 if (size >= threshold) { resize(table.length*2); index = getKeyIndex(key); // 因为扩容了,原来的索引不一定对 } table[index] = new Entry<>(key, value, table[index]); size++; return value; } private void resize(int newCapacity) { Entry [] oldTable = table; table = new Entry[newCapacity]; for (Entry entry : oldTable) { while (entry != null) { Entry next = entry.next; int index = getKeyIndex(entry.getKey()); entry.next = table[index]; table[index] = entry; entry = next; } } threshold = (int) (newCapacity*loadFactor); } @Override public V remove(K key) { int index = getKeyIndex(key); Entry entry = table[index]; Entry pre = null; while (entry != null) { if (entry.getKey() == key || entry.getKey().equals(key)) { if (pre != null) { pre.next = entry.next; } else { table[index] = entry.next; } return entry.getValue(); } pre = entry; entry = entry.next; } return null; } @Override public boolean containsKey(K key) { return getEntry(key) != null; } @Override public List > entryList() { List > res = new ArrayList<>(); for (Entry entry : table) { while (entry != null) { res.add(entry); entry = entry.next; } } return res; } static class Entry implements MyMap.Entry { K key; V value; Entry next; public Entry(K key, V value, Entry next) { this.key = key; this.value = value; this.next = next; } @Override public K getKey() { return key; } @Override public V getValue() { return value; } @Override public void setKey(K key) { this.key = key; } @Override public void setValue(V value) { this.value = value; } @Override public String toString() { return "Entry{" + "key=" + key + ", value=" + value + ", next=" + next + '}'; } } }
- leishen6.github.io:木子雷的博客:面试手写HashMap,手撕HashMap
- JDK7源码:OpenJDK™ Source Releases:srcshareclassesjavautil
- JDK8源码:OpenJDK™ Source Releases:srcshareclassesjavautil
- CSDN:OnlyloveCuracao:HashMap的大小为什么必须是2的倍数
- CSDN:猿人小郑:HashMap初始容量为什么是2的n次幂及扩容为什么是2倍的形式



