HashMap代码实现（JDK7 数组+链表）

首先我们要手敲代码来实现HashMap，就要了解HashMap是什么？数据结构是怎么样的？底层原理是什么？

i hashMap是什么？

我们都知道也应该在项目中用到过hashMap，hashMap是一个存储单元，它通过key与value的形式来存储数据。而且hashMap是一个无序的存储结构，为什么是无序的呢后边我们会讲到。

ii HashMap的数据结构(数组和链表的优缺点在ArrayList和linkedList区别的文章里有)

JDK7：数组+链表

JDK8：数组+链表+红黑树

相信很多看过面试题的人也都了解了这个，我们今天手敲代码的实现就是基于JDK7的形式来实现的，JDK8后边也会涉及到一点。

HashMap是一个规定长度为16的一个存储工具（指HashMap中数组的长度）。在HashMap里我们常用的方法有put  和  get  方法。

iii 底层原理

1.put方法

刚才我们说到了HashMap是一个无序存储结构，同时数组长度只有16，那么HashMap是通过什么实现put方法的呢。废话不多说直接上原理：

首先HashMap的put方法会通过你传入的key值，计算出对应的hash值取16的余数（强制为int类型）[可能hashMap的计算更为复杂，但是基本原理就是如此]，我们称它为index，然后HashMap的put方法通过这个index值，来确定要把数据存储到数组下标为index的位置。那么链表又表现在那里呢？因为我们得到的index的值为除以16的余数，肯定会出现重复的index值，这时就会发生哈希冲突，而避免hash冲突的办法就是引入链表，当发现index值重复之后，HashMap会把数组里现在存的值替换为将要存储的值，并且指向现在存在的值。这么说可能就很片面，接下来我用图片的形式给大家展示：（图中的序号只是为了方便理解，并不是真实的数组或者链表编号）

 假设这就是长度为16的数组，我现在要先存储进去一些数据，一对Key和Value，

hash值就是我们计算得出的hash值，然后就是key和value， 但是现在如果又有一个值要存储到3的位置，这就产生了hash冲突，就需要引入链表了。（不要管next是什么，下边会提，往下看）

现在又要存一个值，假如他的hash：12587，key ：Map   value： Map接口，这个值通过计算也要存到图中3的位置那么应该怎么办呢？（多了一个b，不想改了，就这么看吧，不影响理解就好）

 现在我们就看到3里边的next就有值了，这个值就是链表第二个元素的key值，就这样HashMap解决了hash冲突。这就是HashMap的put方法的一个逻辑。（JDK8中引入了红黑树，在链表数据大于8个时，就会自动转换为红黑树存储）

2 HashMap get方法

说完put方法我们来说一下get 方法

hashMap的get方法逻辑也很简单，首先也是通过计算hash值，来找到数组对应的位置，然后再去判断key值是否和存储在数组中的值相等，相等则返回该值，不相等则会判断next中是否为空，不为空的话再去判断next节点中的key是否相等，直到相等才返回，或者返回为空。

HashMap的get、put方法原理说完了，我们就来用代码来实现它吧

iiii 代码实现（JDK7）

首先我们创建一个Map接口，定义get，put和size方法。

里边定义一个Entry接口，用来规范我们Map的格式。

package com.guozm.waimai1.hashmap;


//定义一个map类
public interface Map {


    //定义put方法
    V put(K k,V v);

    //定义gat方法
    V get(K k);

    //定义size
    int size();


    interface Entry{
        Object getKey();

        Object getValue();
    }
}

然后定义一个HashMap、Entry类来实现Map、Entry类里边的方法（包括计算index的方法、用递归地方式去查找key的方法）代码里都有注释，可以查看。

package com.guozm.waimai1.hashmap;


//Map实现类
public class HashMap implements Map {

    //创建数组对象
    private Entry table[] = null;

    //初始化size
    int size = 0;

    //构造方法
    public HashMap() {
        //hashMap数组容量为16
        table = new Entry[16];
    }

    
    @Override
    public V put(K k,V v) {
        //通过计算拿到hash值
        int index = hash(k);
        //拿到当前数组下标下的对象
        Entry entry = table[index];
        //判断当前对象是否含有数据
        if (entry == null){
            //将数据插入到数组里下标为index的位置
            table[index] = new  Entry(k,v,index,null);
            //每增加一个数据则size+1
            size++;
        }else{
            //将原有数据方法next里边进行存储
            table[index] = new  Entry(k,v,index,entry);
        }
        return (V) table[index].getValue();
    }

    
    private int hash(K k) {
        int i = k.hashCode()%16;
        if (i >= 0){
            return i;
        }else{
            return -i;
        }
    }


    
    @Override
    public V get(K k) {
        //首先判断map里边有没有存入数据
        if(size == 0){
            //没存入则返回为空
            return null;
        }
        //通过hash算法拿到下标，index的值
        int index = hash(k);
        //通过findValue方法寻找符合的entry值
        Entry entry = findValue(table[index] , k);
        //判断entry值是否为空
        if(entry != null){
            //返回Value
            return (V) entry.getValue();
        }
        return null;
    }


    
    private Entry findValue(Entry entry ,K k) {
        //判断k与entry对象里的key值是否相等
        if (k.equals(entry.getKey())|| k == entry.getKey()){
            //相等则直接返回
            return entry;
            //否则执行else
        }else {
            //判断链表里是否还含有数据
            if (entry.next != null){
                //采用递归的形式去找符合的值
                return   findValue(entry.next,k);
            }
        }
        return null;
    }

    @Override
    public int size() {
        return size;
    }


    //Entry实现类
    class Entry implements Map.Entry{

        //key
        K k;

        //value
        V v;

        //计算得出的hash值（index）
        int hash;

        //指针
        Entry next;

        //有参构造方法
        public Entry(K k, V v, int hash, Entry next) {
            this.k = k;
            this.v = v;
            this.hash = hash;
            this.next = next;
        }


        @Override
        public Object getKey() {
            return k;
        }

        @Override
        public Object getValue() {
            return v;
        }
    }
}

 最后建一个测试类，来测试一下我们的HashMap  put  和  get  方法

package com.guozm.waimai1.hashmap;



//测试类
public class HashTest {

    //主方法
    public static void main(String[] args) {
        Map map = new HashMap<>();
        map.put("Map","Map接口");
        map.put("HashMap","实现Map接口");
        map.put("HashTest","Map测试类");

        System.out.println(map.get("Map"));
        System.out.println(map.get("HashMap"));
        System.out.println(map.get("HashTest"));
        System.out.println(map.getSize);
    }
}

 运行结果

 到这里我们就写了一个简单的HashMap。

iiii JDK8为什么引入红黑树

如果我们的数据很大很多的话，HashMap毕竟只有16个大小，就会在一个index下放很多个数据，也就是链表长度会很长很长，当我们要在链表里查找数据时，就要遍历整个链表。时间效率低。所以在JDK8中加入了红黑树就是为了优化这一点。（个人理解，如有错误欢迎交流）