首先我们要手敲代码来实现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<K,V> {//定义put方法V put(K k,V v);//定义gat方法V get(K k);//定义sizeint size();interface Entry<K,V>{Object getKey();Object getValue();}
}

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

package com.guozm.waimai1.hashmap;//Map实现类
public class HashMap<K,V> implements Map<K,V> {//创建数组对象private Entry table[] = null;//初始化sizeint size = 0;//构造方法public HashMap() {//hashMap数组容量为16table = new Entry[16];}/**** 1.通过key进行hash运算* 2.拿到index-->数组下标--->数组对应的对象--->Entry* 3.判断当前对象是否为空，为空：可以直接进行数据存储，不为空：hash冲突* 4.解决hash冲突就要使用链表* 5.返回存储结果* @param k* @param v* @return*/@Overridepublic 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>(k,v,index,null);//每增加一个数据则size+1size++;}else{//将原有数据方法next里边进行存储table[index] = new  Entry<K,V>(k,v,index,entry);}return (V) table[index].getValue();}/**** 通过传入的key值计算数组下标的方法* @param k* @return*/private int hash(K k) {int i = k.hashCode()%16;if (i >= 0){return i;}else{return -i;}}/**** 1.通过key进行hash，计算出数组下标index* 2.通过index找到entry对象* 3.判断entry对象是否为空 为空：直接返回 没有找到对应的数据* 4.不为空：判断key是否和对象里的key相等 相等：返回value* 5.不相等：判断next是否为空，如果不为空  则判断next里的key与要找到key是否相等  直到相等才返回  或者  返回为空* @param k* @return*/@Overridepublic V get(K k) {//首先判断map里边有没有存入数据if(size == 0){//没存入则返回为空return null;}//通过hash算法拿到下标，index的值int index = hash(k);//通过findValue方法寻找符合的entry值Entry<K,V> entry = findValue(table[index] , k);//判断entry值是否为空if(entry != null){//返回Valuereturn (V) entry.getValue();}return null;}/**** 递归方式实现  链表寻找符合要求的entry对象* 有则返回entry对象* 无则返回null* @param entry* @param k* @return*/private Entry<K,V> findValue(Entry<K,V> 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;}@Overridepublic int size() {return size;}//Entry实现类class Entry<K,V> implements Map.Entry<K,V>{//keyK k;//valueV v;//计算得出的hash值（index）int hash;//指针Entry<K,V> next;//有参构造方法public Entry(K k, V v, int hash, Entry<K, V> next) {this.k = k;this.v = v;this.hash = hash;this.next = next;}@Overridepublic Object getKey() {return k;}@Overridepublic Object getValue() {return v;}}
}

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

package com.guozm.waimai1.hashmap;//测试类
public class HashTest {//主方法public static void main(String[] args) {Map<String,String> 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中加入了红黑树就是为了优化这一点。（个人理解，如有错误欢迎交流）