正文
手撕HashMap
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
前言：
平时工作的时候，用的最多的就是ArrayList和HashMap了，今天看了遍HashMap的源码，决定自己手写一遍HashMap。
一、创建MyHashMap接口
我们首先创建一个 MyHashMap 的入口，暴露一个外部调用的接口，里面简单的定义一下 put 和 get。
public interface MyHashMap<K,V> {
public V put(K k,V v);
public V get(K k);
interface Entry<K,V>{
public K getKey();
public V getValue();
}
}
二、建一个实现类MyHashMapImpl
接口定义完成之后，那就要开始实现了，我们首先创建一个类 MyHashMapImpl 来实现 MyHashMap。 然后我们定义一些变量。以及构造函数，比如我们定义的数组初始长度为16，加载因子为0.75。这两个参数会涉及到自动扩容，我们后面再说。
public class MyHashMapImpl<K, V> implements MyHashMap<K, V> {
//数组的初始长度
private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//阀值比例(加载因子)
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private int defaultInitSize;
private final float defaultLoadFactor;
//Map当中entry的数量
private int entryUseSize;
//数组
private Entry<K, V>[] table;
//构造函数
public MyHashMapImpl() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public MyHashMapImpl(int defaultInitialCapacity, float defaultLoadFactor) {
if (defaultInitialCapacity < 0)
//容量不合规
throw new IllegalArgumentException("Illegal initial capacity" + defaultInitialCapacity);
if (defaultLoadFactor <= 0 || Float.isNaN(defaultLoadFactor))
//不合规的加载因子
throw new IllegalArgumentException("Illegal load factor" + defaultLoadFactor);
this.defaultInitSize = defaultInitialCapacity;
this.defaultLoadFactor = defaultLoadFactor;
table = new Entry[this.defaultInitSize];
}
}
三、重写put方法
我们首先重写下put方法，可以看到，当Map中存储的数据大于加载因子*初始化数据长度的时候，会第一时间触发扩容机制，扩容的过程也就是重新设置一个更大的数组，并把原本的数组地址指过去，并且把原本的值重新put进去。这个过程如果频繁发生还是很消耗机器性能的，所以我们在写代码的时候最好是预估好初始大小，尽量不触发扩容机制。
@Override
public V put(K k, V v) {
V oldValue;
//是否需要扩容
//扩容完毕，肯定需要重新散列
if (entryUseSize >= defaultInitSize * defaultLoadFactor) {
resize(2 * defaultInitSize);
}
int index = hash(k) & (defaultInitSize - 1);
if (table[index] == null) {
table[index] = new Entry<K, V>(k, v, null);
++entryUseSize;
} else {
Entry<K, V> entry = table[index];
Entry<K, V> e = entry;
while (e != null) {
if (k == e.getKey() || k.equals(e.getKey())) {
oldValue = e.value;
e.value = v;
return oldValue;
}
e = e.next;
}
table[index] = new Entry<K, V>(k, v, entry);
++entryUseSize;
} return null;
} private void resize(int i) {
Entry[] newTable = new Entry[i];
defaultInitSize = i;
entryUseSize = 0;
rehash(newTable);
} private void rehash(Entry<K, V>[] newTable) {
//得到原来老得entry集合，注意遍历单链表
List<Entry<K, V>> entryList = new ArrayList<Entry<K, V>>();
for (Entry<K, V> entry : table) {
if (entry != null) {
do {
entryList.add(entry);
entry = entry.next;
} while (entry != null);
} }
//覆盖旧的引用
if (newTable.length > 0) {
table = newTable;
}
//重新hash也就是重新put entry到hashmap
for (Entry<K, V> entry : entryList) {
put(entry.getKey(), entry.getValue());
} } class Entry<K, V> implements MyHashMap.Entry<K, V> { private K key;
private V value;
private Entry<K, V> next; public Entry() { } public Entry(K key, V value, Entry<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
} @Override
public K getKey() {
return key;
} @Override
public V getValue() {
return value;
} }
四、重写get方法
如果要拿到数组中的值，我们首先要获取对应的位置。其中有一个基本概念要说一下，每一个数据通过hash函数都会得到一个值，并且这个值是固定的，所以我们可以通过k.hashCode()
来获取对应的hash值，然后按照散列算法均匀分散hash值，然后通过hashcode获取对应的值，得到基本数组的下标。这时候就能拿到我们存在map中的值了，但是hash值并不是一定是唯一的，也就是说可以能a.hash和b.hash值是一样的，但是a不等于b，所以如果两个数据hash值相同，会触发hash冲突。严重降低hashmap的性能，本次hash方法的作用也就是尽量减少hash冲突。使数据排列的更加均匀一些。当我们遇到hash冲突的时候可以再次hash解决冲突。
@Override
public V get(K k) {
int index = hash(k) & (defaultInitSize - 1);
if (table[index] == null) {
return null;
} else {
Entry<K, V> entry = table[index];
do {
if (k == entry.getKey() || k.equals(entry.getKey())) {
return entry.value;
}
entry = entry.next; } while (entry != null);
} return null;
}
