HashMap实现原理

前言

HashMap是Java中常用的集合，而且HashMap的一些思想，对于我们平时解决业务上的一些问题，在思路上有帮助，基于此，本篇博客将分析HashMap底层设计思想，并手写一个迷你版的HashMap！

 

对HashMap的思考

HashMap底层数据结构

第一，如图所示，HashMap有3个要素：hash函数+数组+单链表

第二，对于hash函数而言，需要考虑些什么？

要快，对于给定的Key，要能够快速计算出在数组中的index。那么什么运算够快呢？显然是位运算！

要均匀分布，要较少碰撞。说白了，我们希望通过hash函数，让数据均匀分布在数组中，不希望大量数据发生碰撞，导致链表过长。那么怎么办到呢？也是利用位运算，通过对数据的二进制的位进行移动，让hash函数得到的数据散列开来，从而减低了碰撞的概率。

如果发生了碰撞怎么办？上面的图其实已经说明了JDK的HashMap是如何处理hash冲突的，就是通过单链表解决的。那么除了这个方法，还有其他思路么？比如说，如果发生冲突，那么记下这个冲突的位置为index，然后在加上固定步长，即index+step，找到这个位置，看一下是否仍然冲突，如果继续冲突，那么按照这个思路，继续加上固定步长。其实这就是所谓的线性探测来解决Hash冲突的方法！

 

通过写一个迷你版的HashMap来深刻理解

定义接口

接口

定义一个接口，对外暴露快速存取的方法。

注意MyMap接口内部定义了一个内部接口Entry。

接口实现

MyHashMap定义

HashMap的要素之一，就是数组，自然在这里，我们要定义数组，数组的初始化大小，还要考虑扩容的阀值。

看MyHashMap的构造

构造方法

构造方法有什么好说的呢？

仔细观察下，你会发现，其实这里使用到了“门面模式”。这里的2个构造方法其实指向的是同一个，但是对外却暴露了2个“门面”！

Entry

Entry

HashMap的要素之一，单链表的体现就在这里！

看put如何实现

put

第一，要考虑是否扩容？

HashMap中的Entry的数量（数组以及单链表中的所有Entry）是否达到阀值？

第二，如果扩容，意味着新生成一个Entry[]，不仅如此还得重新散列。

第三，要根据Key计算出在Entry[]中的位置，定位后，如果Entry[]中的元素为null，那么可以放入其中，如果不为空，那么得遍历单链表，要么更新value，要么形成一个新的Entry“挤压”单链表！

hash函数

MyHashMap提供的hash函数

JDK的HashMap提供的hash函数

我这里参考了JDK的HashMap的hash函数的实现，这里也再次说明了：要想散列均匀，就得进行二进制的位运算！

resize和rehash

resize/rehash

这里可以看出，对于HashMap而言，如果频繁进行resize/rehash操作，是会影响性能的。

resize/rehash的过程，就是数组变大，原来数组中的entry元素一个个的put到新数组的过程，需要注意的是一些状态变量的改变。

get实现

get

get很简单，只需要注意在遍历单链表的过程中使用== or equals来判断下即可。

Test测试

利用MyHashMap进行存取

运行结果

result

OK，一个迷你版的HashMap就写好了，你学到了么？

注：关注作者微信公众号，了解更多分布式架构、微服务、netty、MySQL、spring、JVM、算法、性能优化、等知识点。

 

 

package com.suning.map;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by 17030057 on 2018/8/16.
 */
public class MyHashMap<K,V> implements MyMap<K,V> {

    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //数组默认长度
private static final int MAXIMUM_CAPACITY = 1 << 30;//数组最大长度
private static final float DEFAULT_LOAD_FACTOR = 0.75f; //数组扩容阀值默认比例
private Entry<K,V>[] table = null; //数组
private int initialCapacity;//数组长度
private float loadFactor;//数组扩容阀值比例
private int entryUseSize; //map中entry数量
public MyHashMap(){
        this(DEFAULT_INITIAL_CAPACITY,DEFAULT_LOAD_FACTOR);
}

    public MyHashMap(int initialCapacity,float loadFactor){
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                    loadFactor);
this.initialCapacity = initialCapacity;
this.loadFactor = loadFactor;
table = new Entry[this.initialCapacity];
}

    //单链表(可以转换成list)
class Entry<K,V> implements MyMap.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;
}
    }

    //hash函数 让key均匀分布
private int hash(K k) {
        int hashCode = k.hashCode();
hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12);
return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4);
}

    //扩容
private void resize(int newCapacity) {
        Entry[] newTable = new Entry[newCapacity];
//修改数组大小
initialCapacity = newCapacity;
entryUseSize = 0;
//重新hash
List<Entry<K,V>> entryList = new ArrayList<>();//得到老entry链表
for (Entry<K,V> entry : table) {
            if(null != entry) {
                do {
                    entryList.add(entry);
entry = entry.next;
} while (entry != null);
}
        }
        //覆盖就数组
if(newTable.length > 0) {
            table = newTable;
}
        //重新组建hashMap
for (Entry<K,V> entry : entryList) {
            put(entry.getKey(),entry.getValue());
}
    }

    @Override
public V put(K k, V v) {
        V oldValue = null;
//是否需要扩容
if(entryUseSize >= initialCapacity*loadFactor) {
            resize(2 * initialCapacity);
}
        //得出hash值，计算位置
int index = hash(k) & (initialCapacity - 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 == entry) {
                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 oldValue;
}

    @Override
public V get(K k) {
        int index = hash(k) & (initialCapacity - 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;
}

    public static void main(String[] args) {

        System.out.println(1 << 5);
System.out.println(1 << 30);
System.out.println(16 >>> 2);
//        MyHashMap<String,String> map = new MyHashMap<>();
//        for (int i =0;i<1000;i++) {
//            map.put("key"+i , "value"+i);
//        }
//        for (int i =0;i<1000;i++) {
//            System.out.println(map.get("key"+i));
//        }
}
}