关于hashmap:java-hashmap

## 手写Java HashMap外围源码
上一章手写LinkedList外围源码，本章咱们来手写Java HashMap的外围源码。
咱们来先理解一下HashMap的原理。HashMap 字面意思 hash + map，map是映射的意思，HashMap就是用hash进行映射的意思。不明确？没关系。咱们来具体解说一下HashMap的原理。

HashMap 应用剖析

//1 存HashMap<String,String> map = new HashMap<>();map.put("name","tom");//2 取System.out.println(map.get("name"));//输入 tom

应用就是这么简略。

HashMap 原理剖析

咱们晓得，Object类有一个hashCode()办法，返回对象的hashCode值，能够了解为返回了对象的内存地址，暂且不论返回的是内存地址或者其它什么也好，先不论，至于hashCode()办法回返的数是怎么算的？咱们也不论

第1 咱们只须要记住：这个函数返回的是一个数就行了。
第2 HashMap外部是用了一个数组来存放数据

1 HashMap是如何把 name,tom寄存的？
上面咱们用一张图来演示

从上图能够看出：
注：上图中数组的大小是7，是多少都行，只是咱们这里就画了7个元素，咱们就以数组大小为7来阐明HashMap的原理。

1. 数组的大小是7，那么数组的索引范畴是[0 , 6]
2. 获得key也就是"name"的hashCode，这是一个数，不论这个数是多少，对7进行取余数，那么范畴必定是 [0 , 6]，正好和数组的索引是一样的。
3. "name".hashCode() % 7 的值如果为2 ，那么value也就是"tom"应该寄存的地位就是2
4. data[2] = "tom" ,存到数组中。是不是很奇妙。

2 上面再来看看如何取？
也用一张图来演示底层原理，如下

由上图可知:

1. 首先也是获取key也就是"name"的hashCode值
2. 用hashCode值对数组的大小 7 进行取余数，和存的时候运行一样，必定也是2
3. 从数组的第 2 个地位把value取出，即: String value = data[2]

注：有几点须要留神

1. 某个对象的hashCode()办法返回的值，在任何时候调用，返回的值都是一样的
2. 对一个数 n 取余数 ,范畴是 [ 0, n - 1 ]

注：有几个问题须要解决

1. 存的时候，如果不同的key的hashCode对数组取余数，都正好雷同了，也就是都映射在了数组的同一地位，怎么办？这就是hash抵触问题

比方 9 % 7 == 2 ， 16 % 7 == 2都等于2
答：数组中寄存的是一个节点的数据结构，节点有next属性，如果hash抵触了，单链表进行寄存，取的时候也是一样，遍历链表

1. 如果数组曾经存满了怎么办？

答：和ArrayList一样，进行扩容，从新映射

1. 间接应用hashCode()值进行映射，产生hash抵触的概论很大，怎么办？

答：参考JDK中HashMap中的实现，有一个hash()函数，再对hashCode()的值进行运行一下，再进行映射

由上可知：HashMap是用一个数组来存放数据，如果遇到映射的地位下面曾经有值了，那么就用链表寄存在以后的后面。数组+链表构造，是HashMap的底层构造
如果咱们的数组外面寄存的元素是QEntry，如下图：

手写 HashMap 外围源码

下面剖析了原理，接下来咱们用起码的代码来提醒HashMap的原理。
咱们就叫QHashMap类，同时数组外面的元素须要也须要定义一个类，咱们定义在QHashMap类的外部。就叫QEntry

QEntry的定义如下：

    //底层数组中寄存的元素类   public static class QEntry<K, V> {        K key;      //寄存key        V value;    //寄存value        int hash;   //key对应的hash值                //hash抵触时，也就是映射的地位上曾经有一个元素了        //那么新加的元素作为链表头，曾经寄存的放在前面        //即保留在next中，一句话：增加新元素时，增加在表头        QEntry<K, V> next;          public QEntry(K key, V value, int hash, QEntry<K, V> next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }    }

QEntry类的定义有了，上面看下QHashMap类中须要哪些属性？
QHashMap类的定义如下图：

public class QHashMap<K, V> {    //默认的数组的大小    private static final int DEFAULT_INITIAL_CAPACITY = 16;    //默认的扩容因子，当数据中元素的个数越多时，hash抵触也容易产生    //所以，须要在数组还没有用完的状况下就开始扩容    //这个 0.75 就是元素的个数达到了数组大小的75%的时候就开始扩容    //比方数组的大小是100，当外面的元素减少到75的时候，就开始扩容    private static final float DEFAULT_LOAD_FACTOR = 0.75f;    //寄存元素的数组    private QEntry[] table;    //数组中元素的个数    private int size;     ......}    

只须要两个常量和两个变量就够了。
上面咱们看下QHashMap的构造函数，为了简略，只实现一个默认的构造函数

  public QHashMap() {        //创立一个数组，默认大小为16        table = new QEntry[DEFAULT_INITIAL_CAPACITY];                //此时元素个数是0        size = 0;    }

咱们来看下QHashMap是如何存放数据的 map.put("name","tom")
put()函数的实现如下：

    /**     * 1 参数key,value很容易了解     * 2 返回V，咱们晓得，HashMap有一个特点，     * 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");     * 前面的值会把后面的笼罩，如果呈现这种状况，返回旧值，在这里返回"tom"     */    public V put(K key, V value) {        //1 为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //不间接用key.hashCode()，咱们对key.hashCode()再作一次运算作为hash值        //这个hash()的办法我是间接从HashMap源码拷贝过去的。能够不必关怀hash()算法自身        //只须要晓得hash()输出一个数，返回一个数就行了。        int hash = hash(key.hashCode());        //用key的hash值和数组的大小，作一次映射，失去应该寄存的地位        int index = indexFor(hash, table.length);        //看看数组中，有没有已存在的元素的key和参数中的key是相等的        //相等则把老的值替换成新的，而后返回旧值        QEntry<K, V> e = table[index];        while (e != null) {            //先比拟hash是否相等，再比拟对象是否相等，或者比拟equals办法            //如果相等了，阐明有一样的key,这时要更新旧值为新的value,同时返回旧的值            if (e.hash == hash && (key == e.key || key.equals(e.key))) {                V oldValue = e.value;                e.value = value;                return oldValue;            }            e = e.next;        }        //如果数组中没有元素的key与传的key相等的话        //把以后地位的元素保留下来        QEntry<K, V> next = table[index];        //next有可能为null，也有可能不为null，不论是否为null        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)        //而后新的元素保留在了index这个地位        table[index] = new QEntry<>(key, value, hash, next);        //如果须要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，教训)        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {            resize();        }        return null;    }

正文很具体，这里有几个函数
hash()函数是间接从HashMap源码中拷贝的，不必纠结这个算法。
indexFor()，传入hash和数组的大小，从而晓得咱们应该去哪个地位查找或保留
这两个函数的源码如下：

   //对hashCode进行运算，JDK中HashMap的实现，间接拷贝过去了    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    //依据 h 求key落在数组的哪个地位    static int indexFor(int h, int length) {        //或者  return h & (length-1) 性能更好        //这里咱们用最容易了解的形式，对length取余数，范畴就是[0,length - 1]        //正好是table数组的所有的索引的范畴        h = h > 0 ? h : -h; //避免正数        return h % length;    }

还有一个扩容函数。当元素的个数大于 table.length * 0.75时，咱们就开始扩容
resize()的源码如下 ：

  //扩容，元素的个数大于 table.length * 0.75    //数组扩容到原来大小的2倍    private void resize() {        //新建一个数组，大小为原来数组大小的2倍        int newCapacity = table.length * 2;        QEntry[] newTable = new QEntry[newCapacity];        QEntry[] src = table;        //遍历旧数组，从新映射到新的数组中        for (int j = 0; j < src.length; j++) {            //获取旧数组元素            QEntry<K, V> e = src[j];            //开释旧数组            src[j] = null;            //因为e是一个链表，有可能有多个节点，循环遍历进行映射            while (e != null) {                //把e的下一个节点保留下来                QEntry<K, V> next = e.next;                //e这个以后节点进行在新的数组中映射                int i = indexFor(e.hash, newCapacity);                //newTable[i] 地位上有可能是null，也有可能不为null                //不论是否为null，都作为e这个节点的下一个节点                e.next = newTable[i];                //把e保留在新数组的 i 的地位                newTable[i] = e;                //持续e的下一个节点的同样的解决                e = next;            }        }        //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table        table = newTable;    }

相比put()函数来说，get()就简略多了。
只须要通过hash值找到相应的数组的地位，再遍历链表，找到一个元素外面的key与传的key相等就行了。
put()办法的源码如下：

    //依据key获取value    public V get(K key) {        //同样为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //对key进行求hash值        int hash = hash(key.hashCode());        //用hash值进行映射，失去应该去数组的哪个地位上取数据        int index = indexFor(hash, table.length);        //把index地位的元素保留下来进行遍历        //因为e是一个链表，咱们要对链表进行遍历        //找到和key相等的那个QEntry，并返回value        QEntry<K, V> e = table[index];        while (e != null) {            //比拟 hash值是否相等            if (hash == e.hash && (key == e.key || key.equals(e.key))) {                return e.value;            }                            //如果不相等，持续找下一个                e = e.next;        }        return null;    }

下面就是QHashMap的外围源码，咱们没有实现删除。
上面是把QHashMap整个类的源码收回来

QHashMap残缺源码如下：

public class QHashMap<K, V> {    //默认的数组的大小    private static final int DEFAULT_INITIAL_CAPACITY = 16;    //默认的扩容因子，当数组的大小大于或者等于以后容量 * 0.75的时候，就开始扩容    private static final float DEFAULT_LOAD_FACTOR = 0.75f;    //底层用一个数组来存放数据    private QEntry[] table;    //数组大小    private int size;    //一个点节，数组中寄存的单位    public static class QEntry<K, V> {        K key;        V value;        int hash;        QEntry<K, V> next;        public QEntry(K key, V value, int hash, QEntry<K, V> next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }    }    public QHashMap() {        table = new QEntry[DEFAULT_INITIAL_CAPACITY];        size = 0;    }    //依据key获取value    public V get(K key) {        //同样为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //对key进行求hash值        int hash = hash(key.hashCode());        //用hash值进行映射，失去应该去数组的哪个地位上取数据        int index = indexFor(hash, table.length);        //把index地位的元素保留下来进行遍历        //因为e是一个链表，咱们要对链表进行遍历        //找到和key相等的那个QEntry，并返回value        QEntry<K, V> e = table[index];        while (e != null) {            //比拟 hash值是否相等            if (hash == e.hash && (key == e.key || key.equals(e.key))) {                return e.value;            }                        //如果不相等，持续找下一个                e = e.next;        }        return null;    }    /**     * 1 参数key,value很容易了解     * 2 返回V，咱们晓得，HashMap有一个特点，     * 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");     * 前面的值会把后面的笼罩，如果呈现这种状况，返回旧值，在这里返回"tom"     */    public V put(K key, V value) {        //1 为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //不间接用key.hashCode()，咱们对key.hashCode()再作一次运算作为hash值        //这个hash()的办法我是间接从HashMap源码拷贝过去的。能够不必关怀hash()算法自身        //只须要晓得hash()输出一个数，返回一个数就行了。        int hash = hash(key.hashCode());        //用key的hash值和数组的大小，作一次映射，失去应该寄存的地位        int index = indexFor(hash, table.length);        //看看数组中，有没有已存在的元素的key和参数中的key是相等的        //相等则把老的值替换成新的，而后返回旧值        QEntry<K, V> e = table[index];        while (e != null) {            //先比拟hash是否相等，再比拟对象是否相等，或者比拟equals办法            //如果相等了，阐明有一样的key,这时要更新旧值为新的value,同时返回旧的值            if (e.hash == hash && (key == e.key || key.equals(e.key))) {                V oldValue = e.value;                e.value = value;                return oldValue;            }            e = e.next;        }        //如果数组中没有元素的key与传的key相等的话        //把以后地位的元素保留下来        QEntry<K, V> next = table[index];        //next有可能为null，也有可能不为null，不论是否为null        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)        //而后新的元素保留在了index这个地位        table[index] = new QEntry<>(key, value, hash, next);        //如果须要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，教训)        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {            resize();        }        return null;    }    //扩容，元素的个数大于 table.length * 0.75    //数组扩容到原来大小的2倍    private void resize() {        //新建一个数组，大小为原来数组大小的2倍        int newCapacity = table.length * 2;        QEntry[] newTable = new QEntry[newCapacity];        QEntry[] src = table;        //遍历旧数组，从新映射到新的数组中        for (int j = 0; j < src.length; j++) {            //获取旧数组元素            QEntry<K, V> e = src[j];            //开释旧数组            src[j] = null;            //因为e是一个链表，有可能有多个节点，循环遍历进行映射            while (e != null) {                //把e的下一个节点保留下来                QEntry<K, V> next = e.next;                //e这个以后节点进行在新的数组中映射                int i = indexFor(e.hash, newCapacity);                //newTable[i] 地位上有可能是null，也有可能不为null                //不论是否为null，都作为e这个节点的下一个节点                e.next = newTable[i];                //把e保留在新数组的 i 的地位                newTable[i] = e;                //持续e的下一个节点的同样的解决                e = next;            }        }        //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table        table = newTable;    }    //对hashCode进行运算，JDK中HashMap的实现，间接拷贝过去了    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    //依据 h 求key落在数组的哪个地位    static int indexFor(int h, int length) {        //或者  return h & (length-1) 性能更好        //这里咱们用最容易了解的形式，对length取余数，范畴就是[0,length - 1]        //正好是table数组的所有的索引的范畴        h = h > 0 ? h : -h; //避免正数        return h % length;    }}

下面就是QHashMap的原理。上面咱们写一段测试代码来看下咱们的QHashMap能不能失常运行。测试代码如下：

 public static void main(String[] args) {        QHashMap<String, String> map = new QHashMap<>();        map.put("name", "tom");        map.put("age", "23");        map.put("address", "beijing");        String oldValue = map.put("address", "shanghai"); //key一样，返回旧值，保留新值        System.out.println(map.get("name"));        System.out.println(map.get("age"));        System.out.println("旧值=" + oldValue);        System.out.println("新值=" + map.get("address"));    }

输入如下：

tom23旧值=beijing新值=shanghai

通过下面的简略的实现了QHashMap,还有好多功能没有实现，比拟remove,clear,containsKey()等，还有遍历相干，有趣味的读者能够本人实现

## 手写Java HashMap外围源码
上一章手写LinkedList外围源码，本章咱们来手写Java HashMap的外围源码。
咱们来先理解一下HashMap的原理。HashMap 字面意思 hash + map，map是映射的意思，HashMap就是用hash进行映射的意思。不明确？没关系。咱们来具体解说一下HashMap的原理。

HashMap 应用剖析

//1 存HashMap<String,String> map = new HashMap<>();map.put("name","tom");//2 取System.out.println(map.get("name"));//输入 tom

应用就是这么简略。

HashMap 原理剖析

咱们晓得，Object类有一个hashCode()办法，返回对象的hashCode值，能够了解为返回了对象的内存地址，暂且不论返回的是内存地址或者其它什么也好，先不论，至于hashCode()办法回返的数是怎么算的？咱们也不论

第1 咱们只须要记住：这个函数返回的是一个数就行了。
第2 HashMap外部是用了一个数组来存放数据

1 HashMap是如何把 name,tom寄存的？
上面咱们用一张图来演示

从上图能够看出：
注：上图中数组的大小是7，是多少都行，只是咱们这里就画了7个元素，咱们就以数组大小为7来阐明HashMap的原理。

1. 数组的大小是7，那么数组的索引范畴是[0 , 6]
2. 获得key也就是"name"的hashCode，这是一个数，不论这个数是多少，对7进行取余数，那么范畴必定是 [0 , 6]，正好和数组的索引是一样的。
3. "name".hashCode() % 7 的值如果为2 ，那么value也就是"tom"应该寄存的地位就是2
4. data[2] = "tom" ,存到数组中。是不是很奇妙。

2 上面再来看看如何取？
也用一张图来演示底层原理，如下

由上图可知:

1. 首先也是获取key也就是"name"的hashCode值
2. 用hashCode值对数组的大小 7 进行取余数，和存的时候运行一样，必定也是2
3. 从数组的第 2 个地位把value取出，即: String value = data[2]

注：有几点须要留神

1. 某个对象的hashCode()办法返回的值，在任何时候调用，返回的值都是一样的
2. 对一个数 n 取余数 ,范畴是 [ 0, n - 1 ]

注：有几个问题须要解决

1. 存的时候，如果不同的key的hashCode对数组取余数，都正好雷同了，也就是都映射在了数组的同一地位，怎么办？这就是hash抵触问题

比方 9 % 7 == 2 ， 16 % 7 == 2都等于2
答：数组中寄存的是一个节点的数据结构，节点有next属性，如果hash抵触了，单链表进行寄存，取的时候也是一样，遍历链表

1. 如果数组曾经存满了怎么办？

答：和ArrayList一样，进行扩容，从新映射

1. 间接应用hashCode()值进行映射，产生hash抵触的概论很大，怎么办？

答：参考JDK中HashMap中的实现，有一个hash()函数，再对hashCode()的值进行运行一下，再进行映射

由上可知：HashMap是用一个数组来存放数据，如果遇到映射的地位下面曾经有值了，那么就用链表寄存在以后的后面。数组+链表构造，是HashMap的底层构造
如果咱们的数组外面寄存的元素是QEntry，如下图：

手写 HashMap 外围源码

下面剖析了原理，接下来咱们用起码的代码来提醒HashMap的原理。
咱们就叫QHashMap类，同时数组外面的元素须要也须要定义一个类，咱们定义在QHashMap类的外部。就叫QEntry

QEntry的定义如下：

    //底层数组中寄存的元素类   public static class QEntry<K, V> {        K key;      //寄存key        V value;    //寄存value        int hash;   //key对应的hash值                //hash抵触时，也就是映射的地位上曾经有一个元素了        //那么新加的元素作为链表头，曾经寄存的放在前面        //即保留在next中，一句话：增加新元素时，增加在表头        QEntry<K, V> next;          public QEntry(K key, V value, int hash, QEntry<K, V> next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }    }

QEntry类的定义有了，上面看下QHashMap类中须要哪些属性？
QHashMap类的定义如下图：

public class QHashMap<K, V> {    //默认的数组的大小    private static final int DEFAULT_INITIAL_CAPACITY = 16;    //默认的扩容因子，当数据中元素的个数越多时，hash抵触也容易产生    //所以，须要在数组还没有用完的状况下就开始扩容    //这个 0.75 就是元素的个数达到了数组大小的75%的时候就开始扩容    //比方数组的大小是100，当外面的元素减少到75的时候，就开始扩容    private static final float DEFAULT_LOAD_FACTOR = 0.75f;    //寄存元素的数组    private QEntry[] table;    //数组中元素的个数    private int size;     ......}    

只须要两个常量和两个变量就够了。
上面咱们看下QHashMap的构造函数，为了简略，只实现一个默认的构造函数

  public QHashMap() {        //创立一个数组，默认大小为16        table = new QEntry[DEFAULT_INITIAL_CAPACITY];                //此时元素个数是0        size = 0;    }

咱们来看下QHashMap是如何存放数据的 map.put("name","tom")
put()函数的实现如下：

    /**     * 1 参数key,value很容易了解     * 2 返回V，咱们晓得，HashMap有一个特点，     * 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");     * 前面的值会把后面的笼罩，如果呈现这种状况，返回旧值，在这里返回"tom"     */    public V put(K key, V value) {        //1 为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //不间接用key.hashCode()，咱们对key.hashCode()再作一次运算作为hash值        //这个hash()的办法我是间接从HashMap源码拷贝过去的。能够不必关怀hash()算法自身        //只须要晓得hash()输出一个数，返回一个数就行了。        int hash = hash(key.hashCode());        //用key的hash值和数组的大小，作一次映射，失去应该寄存的地位        int index = indexFor(hash, table.length);        //看看数组中，有没有已存在的元素的key和参数中的key是相等的        //相等则把老的值替换成新的，而后返回旧值        QEntry<K, V> e = table[index];        while (e != null) {            //先比拟hash是否相等，再比拟对象是否相等，或者比拟equals办法            //如果相等了，阐明有一样的key,这时要更新旧值为新的value,同时返回旧的值            if (e.hash == hash && (key == e.key || key.equals(e.key))) {                V oldValue = e.value;                e.value = value;                return oldValue;            }            e = e.next;        }        //如果数组中没有元素的key与传的key相等的话        //把以后地位的元素保留下来        QEntry<K, V> next = table[index];        //next有可能为null，也有可能不为null，不论是否为null        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)        //而后新的元素保留在了index这个地位        table[index] = new QEntry<>(key, value, hash, next);        //如果须要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，教训)        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {            resize();        }        return null;    }

正文很具体，这里有几个函数
hash()函数是间接从HashMap源码中拷贝的，不必纠结这个算法。
indexFor()，传入hash和数组的大小，从而晓得咱们应该去哪个地位查找或保留
这两个函数的源码如下：

   //对hashCode进行运算，JDK中HashMap的实现，间接拷贝过去了    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    //依据 h 求key落在数组的哪个地位    static int indexFor(int h, int length) {        //或者  return h & (length-1) 性能更好        //这里咱们用最容易了解的形式，对length取余数，范畴就是[0,length - 1]        //正好是table数组的所有的索引的范畴        h = h > 0 ? h : -h; //避免正数        return h % length;    }

还有一个扩容函数。当元素的个数大于 table.length * 0.75时，咱们就开始扩容
resize()的源码如下 ：

  //扩容，元素的个数大于 table.length * 0.75    //数组扩容到原来大小的2倍    private void resize() {        //新建一个数组，大小为原来数组大小的2倍        int newCapacity = table.length * 2;        QEntry[] newTable = new QEntry[newCapacity];        QEntry[] src = table;        //遍历旧数组，从新映射到新的数组中        for (int j = 0; j < src.length; j++) {            //获取旧数组元素            QEntry<K, V> e = src[j];            //开释旧数组            src[j] = null;            //因为e是一个链表，有可能有多个节点，循环遍历进行映射            while (e != null) {                //把e的下一个节点保留下来                QEntry<K, V> next = e.next;                //e这个以后节点进行在新的数组中映射                int i = indexFor(e.hash, newCapacity);                //newTable[i] 地位上有可能是null，也有可能不为null                //不论是否为null，都作为e这个节点的下一个节点                e.next = newTable[i];                //把e保留在新数组的 i 的地位                newTable[i] = e;                //持续e的下一个节点的同样的解决                e = next;            }        }        //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table        table = newTable;    }

相比put()函数来说，get()就简略多了。
只须要通过hash值找到相应的数组的地位，再遍历链表，找到一个元素外面的key与传的key相等就行了。
put()办法的源码如下：

    //依据key获取value    public V get(K key) {        //同样为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //对key进行求hash值        int hash = hash(key.hashCode());        //用hash值进行映射，失去应该去数组的哪个地位上取数据        int index = indexFor(hash, table.length);        //把index地位的元素保留下来进行遍历        //因为e是一个链表，咱们要对链表进行遍历        //找到和key相等的那个QEntry，并返回value        QEntry<K, V> e = table[index];        while (e != null) {            //比拟 hash值是否相等            if (hash == e.hash && (key == e.key || key.equals(e.key))) {                return e.value;            }                            //如果不相等，持续找下一个                e = e.next;        }        return null;    }

下面就是QHashMap的外围源码，咱们没有实现删除。
上面是把QHashMap整个类的源码收回来

QHashMap残缺源码如下：

public class QHashMap<K, V> {    //默认的数组的大小    private static final int DEFAULT_INITIAL_CAPACITY = 16;    //默认的扩容因子，当数组的大小大于或者等于以后容量 * 0.75的时候，就开始扩容    private static final float DEFAULT_LOAD_FACTOR = 0.75f;    //底层用一个数组来存放数据    private QEntry[] table;    //数组大小    private int size;    //一个点节，数组中寄存的单位    public static class QEntry<K, V> {        K key;        V value;        int hash;        QEntry<K, V> next;        public QEntry(K key, V value, int hash, QEntry<K, V> next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }    }    public QHashMap() {        table = new QEntry[DEFAULT_INITIAL_CAPACITY];        size = 0;    }    //依据key获取value    public V get(K key) {        //同样为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //对key进行求hash值        int hash = hash(key.hashCode());        //用hash值进行映射，失去应该去数组的哪个地位上取数据        int index = indexFor(hash, table.length);        //把index地位的元素保留下来进行遍历        //因为e是一个链表，咱们要对链表进行遍历        //找到和key相等的那个QEntry，并返回value        QEntry<K, V> e = table[index];        while (e != null) {            //比拟 hash值是否相等            if (hash == e.hash && (key == e.key || key.equals(e.key))) {                return e.value;            }                        //如果不相等，持续找下一个                e = e.next;        }        return null;    }    /**     * 1 参数key,value很容易了解     * 2 返回V，咱们晓得，HashMap有一个特点，     * 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");     * 前面的值会把后面的笼罩，如果呈现这种状况，返回旧值，在这里返回"tom"     */    public V put(K key, V value) {        //1 为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //不间接用key.hashCode()，咱们对key.hashCode()再作一次运算作为hash值        //这个hash()的办法我是间接从HashMap源码拷贝过去的。能够不必关怀hash()算法自身        //只须要晓得hash()输出一个数，返回一个数就行了。        int hash = hash(key.hashCode());        //用key的hash值和数组的大小，作一次映射，失去应该寄存的地位        int index = indexFor(hash, table.length);        //看看数组中，有没有已存在的元素的key和参数中的key是相等的        //相等则把老的值替换成新的，而后返回旧值        QEntry<K, V> e = table[index];        while (e != null) {            //先比拟hash是否相等，再比拟对象是否相等，或者比拟equals办法            //如果相等了，阐明有一样的key,这时要更新旧值为新的value,同时返回旧的值            if (e.hash == hash && (key == e.key || key.equals(e.key))) {                V oldValue = e.value;                e.value = value;                return oldValue;            }            e = e.next;        }        //如果数组中没有元素的key与传的key相等的话        //把以后地位的元素保留下来        QEntry<K, V> next = table[index];        //next有可能为null，也有可能不为null，不论是否为null        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)        //而后新的元素保留在了index这个地位        table[index] = new QEntry<>(key, value, hash, next);        //如果须要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，教训)        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {            resize();        }        return null;    }    //扩容，元素的个数大于 table.length * 0.75    //数组扩容到原来大小的2倍    private void resize() {        //新建一个数组，大小为原来数组大小的2倍        int newCapacity = table.length * 2;        QEntry[] newTable = new QEntry[newCapacity];        QEntry[] src = table;        //遍历旧数组，从新映射到新的数组中        for (int j = 0; j < src.length; j++) {            //获取旧数组元素            QEntry<K, V> e = src[j];            //开释旧数组            src[j] = null;            //因为e是一个链表，有可能有多个节点，循环遍历进行映射            while (e != null) {                //把e的下一个节点保留下来                QEntry<K, V> next = e.next;                //e这个以后节点进行在新的数组中映射                int i = indexFor(e.hash, newCapacity);                //newTable[i] 地位上有可能是null，也有可能不为null                //不论是否为null，都作为e这个节点的下一个节点                e.next = newTable[i];                //把e保留在新数组的 i 的地位                newTable[i] = e;                //持续e的下一个节点的同样的解决                e = next;            }        }        //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table        table = newTable;    }    //对hashCode进行运算，JDK中HashMap的实现，间接拷贝过去了    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    //依据 h 求key落在数组的哪个地位    static int indexFor(int h, int length) {        //或者  return h & (length-1) 性能更好        //这里咱们用最容易了解的形式，对length取余数，范畴就是[0,length - 1]        //正好是table数组的所有的索引的范畴        h = h > 0 ? h : -h; //避免正数        return h % length;    }}

下面就是QHashMap的原理。上面咱们写一段测试代码来看下咱们的QHashMap能不能失常运行。测试代码如下：

 public static void main(String[] args) {        QHashMap<String, String> map = new QHashMap<>();        map.put("name", "tom");        map.put("age", "23");        map.put("address", "beijing");        String oldValue = map.put("address", "shanghai"); //key一样，返回旧值，保留新值        System.out.println(map.get("name"));        System.out.println(map.get("age"));        System.out.println("旧值=" + oldValue);        System.out.println("新值=" + map.get("address"));    }

输入如下：

tom23旧值=beijing新值=shanghai

通过下面的简略的实现了QHashMap,还有好多功能没有实现，比拟remove,clear,containsKey()等，还有遍历相干，有趣味的读者能够本人实现

## 手写Java HashMap外围源码
上一章手写LinkedList外围源码，本章咱们来手写Java HashMap的外围源码。
咱们来先理解一下HashMap的原理。HashMap 字面意思 hash + map，map是映射的意思，HashMap就是用hash进行映射的意思。不明确？没关系。咱们来具体解说一下HashMap的原理。

HashMap 应用剖析

//1 存HashMap<String,String> map = new HashMap<>();map.put("name","tom");//2 取System.out.println(map.get("name"));//输入 tom

应用就是这么简略。

HashMap 原理剖析

咱们晓得，Object类有一个hashCode()办法，返回对象的hashCode值，能够了解为返回了对象的内存地址，暂且不论返回的是内存地址或者其它什么也好，先不论，至于hashCode()办法回返的数是怎么算的？咱们也不论

第1 咱们只须要记住：这个函数返回的是一个数就行了。
第2 HashMap外部是用了一个数组来存放数据

1 HashMap是如何把 name,tom寄存的？
上面咱们用一张图来演示

从上图能够看出：
注：上图中数组的大小是7，是多少都行，只是咱们这里就画了7个元素，咱们就以数组大小为7来阐明HashMap的原理。

1. 数组的大小是7，那么数组的索引范畴是[0 , 6]
2. 获得key也就是"name"的hashCode，这是一个数，不论这个数是多少，对7进行取余数，那么范畴必定是 [0 , 6]，正好和数组的索引是一样的。
3. "name".hashCode() % 7 的值如果为2 ，那么value也就是"tom"应该寄存的地位就是2
4. data[2] = "tom" ,存到数组中。是不是很奇妙。

2 上面再来看看如何取？
也用一张图来演示底层原理，如下

由上图可知:

1. 首先也是获取key也就是"name"的hashCode值
2. 用hashCode值对数组的大小 7 进行取余数，和存的时候运行一样，必定也是2
3. 从数组的第 2 个地位把value取出，即: String value = data[2]

注：有几点须要留神

1. 某个对象的hashCode()办法返回的值，在任何时候调用，返回的值都是一样的
2. 对一个数 n 取余数 ,范畴是 [ 0, n - 1 ]

注：有几个问题须要解决

1. 存的时候，如果不同的key的hashCode对数组取余数，都正好雷同了，也就是都映射在了数组的同一地位，怎么办？这就是hash抵触问题

比方 9 % 7 == 2 ， 16 % 7 == 2都等于2
答：数组中寄存的是一个节点的数据结构，节点有next属性，如果hash抵触了，单链表进行寄存，取的时候也是一样，遍历链表

1. 如果数组曾经存满了怎么办？

答：和ArrayList一样，进行扩容，从新映射

1. 间接应用hashCode()值进行映射，产生hash抵触的概论很大，怎么办？

答：参考JDK中HashMap中的实现，有一个hash()函数，再对hashCode()的值进行运行一下，再进行映射

由上可知：HashMap是用一个数组来存放数据，如果遇到映射的地位下面曾经有值了，那么就用链表寄存在以后的后面。数组+链表构造，是HashMap的底层构造
如果咱们的数组外面寄存的元素是QEntry，如下图：

手写 HashMap 外围源码

下面剖析了原理，接下来咱们用起码的代码来提醒HashMap的原理。
咱们就叫QHashMap类，同时数组外面的元素须要也须要定义一个类，咱们定义在QHashMap类的外部。就叫QEntry

QEntry的定义如下：

    //底层数组中寄存的元素类   public static class QEntry<K, V> {        K key;      //寄存key        V value;    //寄存value        int hash;   //key对应的hash值                //hash抵触时，也就是映射的地位上曾经有一个元素了        //那么新加的元素作为链表头，曾经寄存的放在前面        //即保留在next中，一句话：增加新元素时，增加在表头        QEntry<K, V> next;          public QEntry(K key, V value, int hash, QEntry<K, V> next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }    }

QEntry类的定义有了，上面看下QHashMap类中须要哪些属性？
QHashMap类的定义如下图：

public class QHashMap<K, V> {    //默认的数组的大小    private static final int DEFAULT_INITIAL_CAPACITY = 16;    //默认的扩容因子，当数据中元素的个数越多时，hash抵触也容易产生    //所以，须要在数组还没有用完的状况下就开始扩容    //这个 0.75 就是元素的个数达到了数组大小的75%的时候就开始扩容    //比方数组的大小是100，当外面的元素减少到75的时候，就开始扩容    private static final float DEFAULT_LOAD_FACTOR = 0.75f;    //寄存元素的数组    private QEntry[] table;    //数组中元素的个数    private int size;     ......}    

只须要两个常量和两个变量就够了。
上面咱们看下QHashMap的构造函数，为了简略，只实现一个默认的构造函数

  public QHashMap() {        //创立一个数组，默认大小为16        table = new QEntry[DEFAULT_INITIAL_CAPACITY];                //此时元素个数是0        size = 0;    }

咱们来看下QHashMap是如何存放数据的 map.put("name","tom")
put()函数的实现如下：

    /**     * 1 参数key,value很容易了解     * 2 返回V，咱们晓得，HashMap有一个特点，     * 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");     * 前面的值会把后面的笼罩，如果呈现这种状况，返回旧值，在这里返回"tom"     */    public V put(K key, V value) {        //1 为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //不间接用key.hashCode()，咱们对key.hashCode()再作一次运算作为hash值        //这个hash()的办法我是间接从HashMap源码拷贝过去的。能够不必关怀hash()算法自身        //只须要晓得hash()输出一个数，返回一个数就行了。        int hash = hash(key.hashCode());        //用key的hash值和数组的大小，作一次映射，失去应该寄存的地位        int index = indexFor(hash, table.length);        //看看数组中，有没有已存在的元素的key和参数中的key是相等的        //相等则把老的值替换成新的，而后返回旧值        QEntry<K, V> e = table[index];        while (e != null) {            //先比拟hash是否相等，再比拟对象是否相等，或者比拟equals办法            //如果相等了，阐明有一样的key,这时要更新旧值为新的value,同时返回旧的值            if (e.hash == hash && (key == e.key || key.equals(e.key))) {                V oldValue = e.value;                e.value = value;                return oldValue;            }            e = e.next;        }        //如果数组中没有元素的key与传的key相等的话        //把以后地位的元素保留下来        QEntry<K, V> next = table[index];        //next有可能为null，也有可能不为null，不论是否为null        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)        //而后新的元素保留在了index这个地位        table[index] = new QEntry<>(key, value, hash, next);        //如果须要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，教训)        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {            resize();        }        return null;    }

正文很具体，这里有几个函数
hash()函数是间接从HashMap源码中拷贝的，不必纠结这个算法。
indexFor()，传入hash和数组的大小，从而晓得咱们应该去哪个地位查找或保留
这两个函数的源码如下：

   //对hashCode进行运算，JDK中HashMap的实现，间接拷贝过去了    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    //依据 h 求key落在数组的哪个地位    static int indexFor(int h, int length) {        //或者  return h & (length-1) 性能更好        //这里咱们用最容易了解的形式，对length取余数，范畴就是[0,length - 1]        //正好是table数组的所有的索引的范畴        h = h > 0 ? h : -h; //避免正数        return h % length;    }

还有一个扩容函数。当元素的个数大于 table.length * 0.75时，咱们就开始扩容
resize()的源码如下 ：

  //扩容，元素的个数大于 table.length * 0.75    //数组扩容到原来大小的2倍    private void resize() {        //新建一个数组，大小为原来数组大小的2倍        int newCapacity = table.length * 2;        QEntry[] newTable = new QEntry[newCapacity];        QEntry[] src = table;        //遍历旧数组，从新映射到新的数组中        for (int j = 0; j < src.length; j++) {            //获取旧数组元素            QEntry<K, V> e = src[j];            //开释旧数组            src[j] = null;            //因为e是一个链表，有可能有多个节点，循环遍历进行映射            while (e != null) {                //把e的下一个节点保留下来                QEntry<K, V> next = e.next;                //e这个以后节点进行在新的数组中映射                int i = indexFor(e.hash, newCapacity);                //newTable[i] 地位上有可能是null，也有可能不为null                //不论是否为null，都作为e这个节点的下一个节点                e.next = newTable[i];                //把e保留在新数组的 i 的地位                newTable[i] = e;                //持续e的下一个节点的同样的解决                e = next;            }        }        //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table        table = newTable;    }

相比put()函数来说，get()就简略多了。
只须要通过hash值找到相应的数组的地位，再遍历链表，找到一个元素外面的key与传的key相等就行了。
put()办法的源码如下：

    //依据key获取value    public V get(K key) {        //同样为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //对key进行求hash值        int hash = hash(key.hashCode());        //用hash值进行映射，失去应该去数组的哪个地位上取数据        int index = indexFor(hash, table.length);        //把index地位的元素保留下来进行遍历        //因为e是一个链表，咱们要对链表进行遍历        //找到和key相等的那个QEntry，并返回value        QEntry<K, V> e = table[index];        while (e != null) {            //比拟 hash值是否相等            if (hash == e.hash && (key == e.key || key.equals(e.key))) {                return e.value;            }                            //如果不相等，持续找下一个                e = e.next;        }        return null;    }

下面就是QHashMap的外围源码，咱们没有实现删除。
上面是把QHashMap整个类的源码收回来

QHashMap残缺源码如下：

public class QHashMap<K, V> {    //默认的数组的大小    private static final int DEFAULT_INITIAL_CAPACITY = 16;    //默认的扩容因子，当数组的大小大于或者等于以后容量 * 0.75的时候，就开始扩容    private static final float DEFAULT_LOAD_FACTOR = 0.75f;    //底层用一个数组来存放数据    private QEntry[] table;    //数组大小    private int size;    //一个点节，数组中寄存的单位    public static class QEntry<K, V> {        K key;        V value;        int hash;        QEntry<K, V> next;        public QEntry(K key, V value, int hash, QEntry<K, V> next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }    }    public QHashMap() {        table = new QEntry[DEFAULT_INITIAL_CAPACITY];        size = 0;    }    //依据key获取value    public V get(K key) {        //同样为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //对key进行求hash值        int hash = hash(key.hashCode());        //用hash值进行映射，失去应该去数组的哪个地位上取数据        int index = indexFor(hash, table.length);        //把index地位的元素保留下来进行遍历        //因为e是一个链表，咱们要对链表进行遍历        //找到和key相等的那个QEntry，并返回value        QEntry<K, V> e = table[index];        while (e != null) {            //比拟 hash值是否相等            if (hash == e.hash && (key == e.key || key.equals(e.key))) {                return e.value;            }                        //如果不相等，持续找下一个                e = e.next;        }        return null;    }    /**     * 1 参数key,value很容易了解     * 2 返回V，咱们晓得，HashMap有一个特点，     * 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");     * 前面的值会把后面的笼罩，如果呈现这种状况，返回旧值，在这里返回"tom"     */    public V put(K key, V value) {        //1 为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //不间接用key.hashCode()，咱们对key.hashCode()再作一次运算作为hash值        //这个hash()的办法我是间接从HashMap源码拷贝过去的。能够不必关怀hash()算法自身        //只须要晓得hash()输出一个数，返回一个数就行了。        int hash = hash(key.hashCode());        //用key的hash值和数组的大小，作一次映射，失去应该寄存的地位        int index = indexFor(hash, table.length);        //看看数组中，有没有已存在的元素的key和参数中的key是相等的        //相等则把老的值替换成新的，而后返回旧值        QEntry<K, V> e = table[index];        while (e != null) {            //先比拟hash是否相等，再比拟对象是否相等，或者比拟equals办法            //如果相等了，阐明有一样的key,这时要更新旧值为新的value,同时返回旧的值            if (e.hash == hash && (key == e.key || key.equals(e.key))) {                V oldValue = e.value;                e.value = value;                return oldValue;            }            e = e.next;        }        //如果数组中没有元素的key与传的key相等的话        //把以后地位的元素保留下来        QEntry<K, V> next = table[index];        //next有可能为null，也有可能不为null，不论是否为null        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)        //而后新的元素保留在了index这个地位        table[index] = new QEntry<>(key, value, hash, next);        //如果须要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，教训)        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {            resize();        }        return null;    }    //扩容，元素的个数大于 table.length * 0.75    //数组扩容到原来大小的2倍    private void resize() {        //新建一个数组，大小为原来数组大小的2倍        int newCapacity = table.length * 2;        QEntry[] newTable = new QEntry[newCapacity];        QEntry[] src = table;        //遍历旧数组，从新映射到新的数组中        for (int j = 0; j < src.length; j++) {            //获取旧数组元素            QEntry<K, V> e = src[j];            //开释旧数组            src[j] = null;            //因为e是一个链表，有可能有多个节点，循环遍历进行映射            while (e != null) {                //把e的下一个节点保留下来                QEntry<K, V> next = e.next;                //e这个以后节点进行在新的数组中映射                int i = indexFor(e.hash, newCapacity);                //newTable[i] 地位上有可能是null，也有可能不为null                //不论是否为null，都作为e这个节点的下一个节点                e.next = newTable[i];                //把e保留在新数组的 i 的地位                newTable[i] = e;                //持续e的下一个节点的同样的解决                e = next;            }        }        //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table        table = newTable;    }    //对hashCode进行运算，JDK中HashMap的实现，间接拷贝过去了    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    //依据 h 求key落在数组的哪个地位    static int indexFor(int h, int length) {        //或者  return h & (length-1) 性能更好        //这里咱们用最容易了解的形式，对length取余数，范畴就是[0,length - 1]        //正好是table数组的所有的索引的范畴        h = h > 0 ? h : -h; //避免正数        return h % length;    }}

下面就是QHashMap的原理。上面咱们写一段测试代码来看下咱们的QHashMap能不能失常运行。测试代码如下：

 public static void main(String[] args) {        QHashMap<String, String> map = new QHashMap<>();        map.put("name", "tom");        map.put("age", "23");        map.put("address", "beijing");        String oldValue = map.put("address", "shanghai"); //key一样，返回旧值，保留新值        System.out.println(map.get("name"));        System.out.println(map.get("age"));        System.out.println("旧值=" + oldValue);        System.out.println("新值=" + map.get("address"));    }

输入如下：

tom23旧值=beijing新值=shanghai

通过下面的简略的实现了QHashMap,还有好多功能没有实现，比拟remove,clear,containsKey()等，还有遍历相干，有趣味的读者能够本人实现

## 手写Java HashMap外围源码
上一章手写LinkedList外围源码，本章咱们来手写Java HashMap的外围源码。
咱们来先理解一下HashMap的原理。HashMap 字面意思 hash + map，map是映射的意思，HashMap就是用hash进行映射的意思。不明确？没关系。咱们来具体解说一下HashMap的原理。

HashMap 应用剖析

//1 存HashMap<String,String> map = new HashMap<>();map.put("name","tom");//2 取System.out.println(map.get("name"));//输入 tom

应用就是这么简略。

HashMap 原理剖析

咱们晓得，Object类有一个hashCode()办法，返回对象的hashCode值，能够了解为返回了对象的内存地址，暂且不论返回的是内存地址或者其它什么也好，先不论，至于hashCode()办法回返的数是怎么算的？咱们也不论

第1 咱们只须要记住：这个函数返回的是一个数就行了。
第2 HashMap外部是用了一个数组来存放数据

1 HashMap是如何把 name,tom寄存的？
上面咱们用一张图来演示

从上图能够看出：
注：上图中数组的大小是7，是多少都行，只是咱们这里就画了7个元素，咱们就以数组大小为7来阐明HashMap的原理。

1. 数组的大小是7，那么数组的索引范畴是[0 , 6]
2. 获得key也就是"name"的hashCode，这是一个数，不论这个数是多少，对7进行取余数，那么范畴必定是 [0 , 6]，正好和数组的索引是一样的。
3. "name".hashCode() % 7 的值如果为2 ，那么value也就是"tom"应该寄存的地位就是2
4. data[2] = "tom" ,存到数组中。是不是很奇妙。

2 上面再来看看如何取？
也用一张图来演示底层原理，如下

由上图可知:

1. 首先也是获取key也就是"name"的hashCode值
2. 用hashCode值对数组的大小 7 进行取余数，和存的时候运行一样，必定也是2
3. 从数组的第 2 个地位把value取出，即: String value = data[2]

注：有几点须要留神

1. 某个对象的hashCode()办法返回的值，在任何时候调用，返回的值都是一样的
2. 对一个数 n 取余数 ,范畴是 [ 0, n - 1 ]

注：有几个问题须要解决

1. 存的时候，如果不同的key的hashCode对数组取余数，都正好雷同了，也就是都映射在了数组的同一地位，怎么办？这就是hash抵触问题

比方 9 % 7 == 2 ， 16 % 7 == 2都等于2
答：数组中寄存的是一个节点的数据结构，节点有next属性，如果hash抵触了，单链表进行寄存，取的时候也是一样，遍历链表

1. 如果数组曾经存满了怎么办？

答：和ArrayList一样，进行扩容，从新映射

1. 间接应用hashCode()值进行映射，产生hash抵触的概论很大，怎么办？

答：参考JDK中HashMap中的实现，有一个hash()函数，再对hashCode()的值进行运行一下，再进行映射

由上可知：HashMap是用一个数组来存放数据，如果遇到映射的地位下面曾经有值了，那么就用链表寄存在以后的后面。数组+链表构造，是HashMap的底层构造
如果咱们的数组外面寄存的元素是QEntry，如下图：

手写 HashMap 外围源码

下面剖析了原理，接下来咱们用起码的代码来提醒HashMap的原理。
咱们就叫QHashMap类，同时数组外面的元素须要也须要定义一个类，咱们定义在QHashMap类的外部。就叫QEntry

QEntry的定义如下：

    //底层数组中寄存的元素类   public static class QEntry<K, V> {        K key;      //寄存key        V value;    //寄存value        int hash;   //key对应的hash值                //hash抵触时，也就是映射的地位上曾经有一个元素了        //那么新加的元素作为链表头，曾经寄存的放在前面        //即保留在next中，一句话：增加新元素时，增加在表头        QEntry<K, V> next;          public QEntry(K key, V value, int hash, QEntry<K, V> next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }    }

QEntry类的定义有了，上面看下QHashMap类中须要哪些属性？
QHashMap类的定义如下图：

public class QHashMap<K, V> {    //默认的数组的大小    private static final int DEFAULT_INITIAL_CAPACITY = 16;    //默认的扩容因子，当数据中元素的个数越多时，hash抵触也容易产生    //所以，须要在数组还没有用完的状况下就开始扩容    //这个 0.75 就是元素的个数达到了数组大小的75%的时候就开始扩容    //比方数组的大小是100，当外面的元素减少到75的时候，就开始扩容    private static final float DEFAULT_LOAD_FACTOR = 0.75f;    //寄存元素的数组    private QEntry[] table;    //数组中元素的个数    private int size;     ......}    

只须要两个常量和两个变量就够了。
上面咱们看下QHashMap的构造函数，为了简略，只实现一个默认的构造函数

  public QHashMap() {        //创立一个数组，默认大小为16        table = new QEntry[DEFAULT_INITIAL_CAPACITY];                //此时元素个数是0        size = 0;    }

咱们来看下QHashMap是如何存放数据的 map.put("name","tom")
put()函数的实现如下：

    /**     * 1 参数key,value很容易了解     * 2 返回V，咱们晓得，HashMap有一个特点，     * 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");     * 前面的值会把后面的笼罩，如果呈现这种状况，返回旧值，在这里返回"tom"     */    public V put(K key, V value) {        //1 为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //不间接用key.hashCode()，咱们对key.hashCode()再作一次运算作为hash值        //这个hash()的办法我是间接从HashMap源码拷贝过去的。能够不必关怀hash()算法自身        //只须要晓得hash()输出一个数，返回一个数就行了。        int hash = hash(key.hashCode());        //用key的hash值和数组的大小，作一次映射，失去应该寄存的地位        int index = indexFor(hash, table.length);        //看看数组中，有没有已存在的元素的key和参数中的key是相等的        //相等则把老的值替换成新的，而后返回旧值        QEntry<K, V> e = table[index];        while (e != null) {            //先比拟hash是否相等，再比拟对象是否相等，或者比拟equals办法            //如果相等了，阐明有一样的key,这时要更新旧值为新的value,同时返回旧的值            if (e.hash == hash && (key == e.key || key.equals(e.key))) {                V oldValue = e.value;                e.value = value;                return oldValue;            }            e = e.next;        }        //如果数组中没有元素的key与传的key相等的话        //把以后地位的元素保留下来        QEntry<K, V> next = table[index];        //next有可能为null，也有可能不为null，不论是否为null        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)        //而后新的元素保留在了index这个地位        table[index] = new QEntry<>(key, value, hash, next);        //如果须要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，教训)        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {            resize();        }        return null;    }

正文很具体，这里有几个函数
hash()函数是间接从HashMap源码中拷贝的，不必纠结这个算法。
indexFor()，传入hash和数组的大小，从而晓得咱们应该去哪个地位查找或保留
这两个函数的源码如下：

   //对hashCode进行运算，JDK中HashMap的实现，间接拷贝过去了    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    //依据 h 求key落在数组的哪个地位    static int indexFor(int h, int length) {        //或者  return h & (length-1) 性能更好        //这里咱们用最容易了解的形式，对length取余数，范畴就是[0,length - 1]        //正好是table数组的所有的索引的范畴        h = h > 0 ? h : -h; //避免正数        return h % length;    }

还有一个扩容函数。当元素的个数大于 table.length * 0.75时，咱们就开始扩容
resize()的源码如下 ：

  //扩容，元素的个数大于 table.length * 0.75    //数组扩容到原来大小的2倍    private void resize() {        //新建一个数组，大小为原来数组大小的2倍        int newCapacity = table.length * 2;        QEntry[] newTable = new QEntry[newCapacity];        QEntry[] src = table;        //遍历旧数组，从新映射到新的数组中        for (int j = 0; j < src.length; j++) {            //获取旧数组元素            QEntry<K, V> e = src[j];            //开释旧数组            src[j] = null;            //因为e是一个链表，有可能有多个节点，循环遍历进行映射            while (e != null) {                //把e的下一个节点保留下来                QEntry<K, V> next = e.next;                //e这个以后节点进行在新的数组中映射                int i = indexFor(e.hash, newCapacity);                //newTable[i] 地位上有可能是null，也有可能不为null                //不论是否为null，都作为e这个节点的下一个节点                e.next = newTable[i];                //把e保留在新数组的 i 的地位                newTable[i] = e;                //持续e的下一个节点的同样的解决                e = next;            }        }        //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table        table = newTable;    }

相比put()函数来说，get()就简略多了。
只须要通过hash值找到相应的数组的地位，再遍历链表，找到一个元素外面的key与传的key相等就行了。
put()办法的源码如下：

    //依据key获取value    public V get(K key) {        //同样为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //对key进行求hash值        int hash = hash(key.hashCode());        //用hash值进行映射，失去应该去数组的哪个地位上取数据        int index = indexFor(hash, table.length);        //把index地位的元素保留下来进行遍历        //因为e是一个链表，咱们要对链表进行遍历        //找到和key相等的那个QEntry，并返回value        QEntry<K, V> e = table[index];        while (e != null) {            //比拟 hash值是否相等            if (hash == e.hash && (key == e.key || key.equals(e.key))) {                return e.value;            }                            //如果不相等，持续找下一个                e = e.next;        }        return null;    }

下面就是QHashMap的外围源码，咱们没有实现删除。
上面是把QHashMap整个类的源码收回来

QHashMap残缺源码如下：

public class QHashMap<K, V> {    //默认的数组的大小    private static final int DEFAULT_INITIAL_CAPACITY = 16;    //默认的扩容因子，当数组的大小大于或者等于以后容量 * 0.75的时候，就开始扩容    private static final float DEFAULT_LOAD_FACTOR = 0.75f;    //底层用一个数组来存放数据    private QEntry[] table;    //数组大小    private int size;    //一个点节，数组中寄存的单位    public static class QEntry<K, V> {        K key;        V value;        int hash;        QEntry<K, V> next;        public QEntry(K key, V value, int hash, QEntry<K, V> next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }    }    public QHashMap() {        table = new QEntry[DEFAULT_INITIAL_CAPACITY];        size = 0;    }    //依据key获取value    public V get(K key) {        //同样为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //对key进行求hash值        int hash = hash(key.hashCode());        //用hash值进行映射，失去应该去数组的哪个地位上取数据        int index = indexFor(hash, table.length);        //把index地位的元素保留下来进行遍历        //因为e是一个链表，咱们要对链表进行遍历        //找到和key相等的那个QEntry，并返回value        QEntry<K, V> e = table[index];        while (e != null) {            //比拟 hash值是否相等            if (hash == e.hash && (key == e.key || key.equals(e.key))) {                return e.value;            }                        //如果不相等，持续找下一个                e = e.next;        }        return null;    }    /**     * 1 参数key,value很容易了解     * 2 返回V，咱们晓得，HashMap有一个特点，     * 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");     * 前面的值会把后面的笼罩，如果呈现这种状况，返回旧值，在这里返回"tom"     */    public V put(K key, V value) {        //1 为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //不间接用key.hashCode()，咱们对key.hashCode()再作一次运算作为hash值        //这个hash()的办法我是间接从HashMap源码拷贝过去的。能够不必关怀hash()算法自身        //只须要晓得hash()输出一个数，返回一个数就行了。        int hash = hash(key.hashCode());        //用key的hash值和数组的大小，作一次映射，失去应该寄存的地位        int index = indexFor(hash, table.length);        //看看数组中，有没有已存在的元素的key和参数中的key是相等的        //相等则把老的值替换成新的，而后返回旧值        QEntry<K, V> e = table[index];        while (e != null) {            //先比拟hash是否相等，再比拟对象是否相等，或者比拟equals办法            //如果相等了，阐明有一样的key,这时要更新旧值为新的value,同时返回旧的值            if (e.hash == hash && (key == e.key || key.equals(e.key))) {                V oldValue = e.value;                e.value = value;                return oldValue;            }            e = e.next;        }        //如果数组中没有元素的key与传的key相等的话        //把以后地位的元素保留下来        QEntry<K, V> next = table[index];        //next有可能为null，也有可能不为null，不论是否为null        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)        //而后新的元素保留在了index这个地位        table[index] = new QEntry<>(key, value, hash, next);        //如果须要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，教训)        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {            resize();        }        return null;    }    //扩容，元素的个数大于 table.length * 0.75    //数组扩容到原来大小的2倍    private void resize() {        //新建一个数组，大小为原来数组大小的2倍        int newCapacity = table.length * 2;        QEntry[] newTable = new QEntry[newCapacity];        QEntry[] src = table;        //遍历旧数组，从新映射到新的数组中        for (int j = 0; j < src.length; j++) {            //获取旧数组元素            QEntry<K, V> e = src[j];            //开释旧数组            src[j] = null;            //因为e是一个链表，有可能有多个节点，循环遍历进行映射            while (e != null) {                //把e的下一个节点保留下来                QEntry<K, V> next = e.next;                //e这个以后节点进行在新的数组中映射                int i = indexFor(e.hash, newCapacity);                //newTable[i] 地位上有可能是null，也有可能不为null                //不论是否为null，都作为e这个节点的下一个节点                e.next = newTable[i];                //把e保留在新数组的 i 的地位                newTable[i] = e;                //持续e的下一个节点的同样的解决                e = next;            }        }        //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table        table = newTable;    }    //对hashCode进行运算，JDK中HashMap的实现，间接拷贝过去了    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    //依据 h 求key落在数组的哪个地位    static int indexFor(int h, int length) {        //或者  return h & (length-1) 性能更好        //这里咱们用最容易了解的形式，对length取余数，范畴就是[0,length - 1]        //正好是table数组的所有的索引的范畴        h = h > 0 ? h : -h; //避免正数        return h % length;    }}

下面就是QHashMap的原理。上面咱们写一段测试代码来看下咱们的QHashMap能不能失常运行。测试代码如下：

 public static void main(String[] args) {        QHashMap<String, String> map = new QHashMap<>();        map.put("name", "tom");        map.put("age", "23");        map.put("address", "beijing");        String oldValue = map.put("address", "shanghai"); //key一样，返回旧值，保留新值        System.out.println(map.get("name"));        System.out.println(map.get("age"));        System.out.println("旧值=" + oldValue);        System.out.println("新值=" + map.get("address"));    }

输入如下：

tom23旧值=beijing新值=shanghai

通过下面的简略的实现了QHashMap,还有好多功能没有实现，比拟remove,clear,containsKey()等，还有遍历相干，有趣味的读者能够本人实现

## 手写Java HashMap外围源码
上一章手写LinkedList外围源码，本章咱们来手写Java HashMap的外围源码。
咱们来先理解一下HashMap的原理。HashMap 字面意思 hash + map，map是映射的意思，HashMap就是用hash进行映射的意思。不明确？没关系。咱们来具体解说一下HashMap的原理。

HashMap 应用剖析

//1 存HashMap<String,String> map = new HashMap<>();map.put("name","tom");//2 取System.out.println(map.get("name"));//输入 tom

应用就是这么简略。

HashMap 原理剖析

咱们晓得，Object类有一个hashCode()办法，返回对象的hashCode值，能够了解为返回了对象的内存地址，暂且不论返回的是内存地址或者其它什么也好，先不论，至于hashCode()办法回返的数是怎么算的？咱们也不论

第1 咱们只须要记住：这个函数返回的是一个数就行了。
第2 HashMap外部是用了一个数组来存放数据

1 HashMap是如何把 name,tom寄存的？
上面咱们用一张图来演示

从上图能够看出：
注：上图中数组的大小是7，是多少都行，只是咱们这里就画了7个元素，咱们就以数组大小为7来阐明HashMap的原理。

1. 数组的大小是7，那么数组的索引范畴是[0 , 6]
2. 获得key也就是"name"的hashCode，这是一个数，不论这个数是多少，对7进行取余数，那么范畴必定是 [0 , 6]，正好和数组的索引是一样的。
3. "name".hashCode() % 7 的值如果为2 ，那么value也就是"tom"应该寄存的地位就是2
4. data[2] = "tom" ,存到数组中。是不是很奇妙。

2 上面再来看看如何取？
也用一张图来演示底层原理，如下

由上图可知:

1. 首先也是获取key也就是"name"的hashCode值
2. 用hashCode值对数组的大小 7 进行取余数，和存的时候运行一样，必定也是2
3. 从数组的第 2 个地位把value取出，即: String value = data[2]

注：有几点须要留神

1. 某个对象的hashCode()办法返回的值，在任何时候调用，返回的值都是一样的
2. 对一个数 n 取余数 ,范畴是 [ 0, n - 1 ]

注：有几个问题须要解决

1. 存的时候，如果不同的key的hashCode对数组取余数，都正好雷同了，也就是都映射在了数组的同一地位，怎么办？这就是hash抵触问题

比方 9 % 7 == 2 ， 16 % 7 == 2都等于2
答：数组中寄存的是一个节点的数据结构，节点有next属性，如果hash抵触了，单链表进行寄存，取的时候也是一样，遍历链表

1. 如果数组曾经存满了怎么办？

答：和ArrayList一样，进行扩容，从新映射

1. 间接应用hashCode()值进行映射，产生hash抵触的概论很大，怎么办？

答：参考JDK中HashMap中的实现，有一个hash()函数，再对hashCode()的值进行运行一下，再进行映射

由上可知：HashMap是用一个数组来存放数据，如果遇到映射的地位下面曾经有值了，那么就用链表寄存在以后的后面。数组+链表构造，是HashMap的底层构造
如果咱们的数组外面寄存的元素是QEntry，如下图：

手写 HashMap 外围源码

下面剖析了原理，接下来咱们用起码的代码来提醒HashMap的原理。
咱们就叫QHashMap类，同时数组外面的元素须要也须要定义一个类，咱们定义在QHashMap类的外部。就叫QEntry

QEntry的定义如下：

    //底层数组中寄存的元素类   public static class QEntry<K, V> {        K key;      //寄存key        V value;    //寄存value        int hash;   //key对应的hash值                //hash抵触时，也就是映射的地位上曾经有一个元素了        //那么新加的元素作为链表头，曾经寄存的放在前面        //即保留在next中，一句话：增加新元素时，增加在表头        QEntry<K, V> next;          public QEntry(K key, V value, int hash, QEntry<K, V> next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }    }

QEntry类的定义有了，上面看下QHashMap类中须要哪些属性？
QHashMap类的定义如下图：

public class QHashMap<K, V> {    //默认的数组的大小    private static final int DEFAULT_INITIAL_CAPACITY = 16;    //默认的扩容因子，当数据中元素的个数越多时，hash抵触也容易产生    //所以，须要在数组还没有用完的状况下就开始扩容    //这个 0.75 就是元素的个数达到了数组大小的75%的时候就开始扩容    //比方数组的大小是100，当外面的元素减少到75的时候，就开始扩容    private static final float DEFAULT_LOAD_FACTOR = 0.75f;    //寄存元素的数组    private QEntry[] table;    //数组中元素的个数    private int size;     ......}    

只须要两个常量和两个变量就够了。
上面咱们看下QHashMap的构造函数，为了简略，只实现一个默认的构造函数

  public QHashMap() {        //创立一个数组，默认大小为16        table = new QEntry[DEFAULT_INITIAL_CAPACITY];                //此时元素个数是0        size = 0;    }

咱们来看下QHashMap是如何存放数据的 map.put("name","tom")
put()函数的实现如下：

    /**     * 1 参数key,value很容易了解     * 2 返回V，咱们晓得，HashMap有一个特点，     * 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");     * 前面的值会把后面的笼罩，如果呈现这种状况，返回旧值，在这里返回"tom"     */    public V put(K key, V value) {        //1 为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //不间接用key.hashCode()，咱们对key.hashCode()再作一次运算作为hash值        //这个hash()的办法我是间接从HashMap源码拷贝过去的。能够不必关怀hash()算法自身        //只须要晓得hash()输出一个数，返回一个数就行了。        int hash = hash(key.hashCode());        //用key的hash值和数组的大小，作一次映射，失去应该寄存的地位        int index = indexFor(hash, table.length);        //看看数组中，有没有已存在的元素的key和参数中的key是相等的        //相等则把老的值替换成新的，而后返回旧值        QEntry<K, V> e = table[index];        while (e != null) {            //先比拟hash是否相等，再比拟对象是否相等，或者比拟equals办法            //如果相等了，阐明有一样的key,这时要更新旧值为新的value,同时返回旧的值            if (e.hash == hash && (key == e.key || key.equals(e.key))) {                V oldValue = e.value;                e.value = value;                return oldValue;            }            e = e.next;        }        //如果数组中没有元素的key与传的key相等的话        //把以后地位的元素保留下来        QEntry<K, V> next = table[index];        //next有可能为null，也有可能不为null，不论是否为null        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)        //而后新的元素保留在了index这个地位        table[index] = new QEntry<>(key, value, hash, next);        //如果须要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，教训)        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {            resize();        }        return null;    }

正文很具体，这里有几个函数
hash()函数是间接从HashMap源码中拷贝的，不必纠结这个算法。
indexFor()，传入hash和数组的大小，从而晓得咱们应该去哪个地位查找或保留
这两个函数的源码如下：

   //对hashCode进行运算，JDK中HashMap的实现，间接拷贝过去了    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    //依据 h 求key落在数组的哪个地位    static int indexFor(int h, int length) {        //或者  return h & (length-1) 性能更好        //这里咱们用最容易了解的形式，对length取余数，范畴就是[0,length - 1]        //正好是table数组的所有的索引的范畴        h = h > 0 ? h : -h; //避免正数        return h % length;    }

还有一个扩容函数。当元素的个数大于 table.length * 0.75时，咱们就开始扩容
resize()的源码如下 ：

  //扩容，元素的个数大于 table.length * 0.75    //数组扩容到原来大小的2倍    private void resize() {        //新建一个数组，大小为原来数组大小的2倍        int newCapacity = table.length * 2;        QEntry[] newTable = new QEntry[newCapacity];        QEntry[] src = table;        //遍历旧数组，从新映射到新的数组中        for (int j = 0; j < src.length; j++) {            //获取旧数组元素            QEntry<K, V> e = src[j];            //开释旧数组            src[j] = null;            //因为e是一个链表，有可能有多个节点，循环遍历进行映射            while (e != null) {                //把e的下一个节点保留下来                QEntry<K, V> next = e.next;                //e这个以后节点进行在新的数组中映射                int i = indexFor(e.hash, newCapacity);                //newTable[i] 地位上有可能是null，也有可能不为null                //不论是否为null，都作为e这个节点的下一个节点                e.next = newTable[i];                //把e保留在新数组的 i 的地位                newTable[i] = e;                //持续e的下一个节点的同样的解决                e = next;            }        }        //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table        table = newTable;    }

相比put()函数来说，get()就简略多了。
只须要通过hash值找到相应的数组的地位，再遍历链表，找到一个元素外面的key与传的key相等就行了。
put()办法的源码如下：

    //依据key获取value    public V get(K key) {        //同样为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //对key进行求hash值        int hash = hash(key.hashCode());        //用hash值进行映射，失去应该去数组的哪个地位上取数据        int index = indexFor(hash, table.length);        //把index地位的元素保留下来进行遍历        //因为e是一个链表，咱们要对链表进行遍历        //找到和key相等的那个QEntry，并返回value        QEntry<K, V> e = table[index];        while (e != null) {            //比拟 hash值是否相等            if (hash == e.hash && (key == e.key || key.equals(e.key))) {                return e.value;            }                            //如果不相等，持续找下一个                e = e.next;        }        return null;    }

下面就是QHashMap的外围源码，咱们没有实现删除。
上面是把QHashMap整个类的源码收回来

QHashMap残缺源码如下：

public class QHashMap<K, V> {    //默认的数组的大小    private static final int DEFAULT_INITIAL_CAPACITY = 16;    //默认的扩容因子，当数组的大小大于或者等于以后容量 * 0.75的时候，就开始扩容    private static final float DEFAULT_LOAD_FACTOR = 0.75f;    //底层用一个数组来存放数据    private QEntry[] table;    //数组大小    private int size;    //一个点节，数组中寄存的单位    public static class QEntry<K, V> {        K key;        V value;        int hash;        QEntry<K, V> next;        public QEntry(K key, V value, int hash, QEntry<K, V> next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }    }    public QHashMap() {        table = new QEntry[DEFAULT_INITIAL_CAPACITY];        size = 0;    }    //依据key获取value    public V get(K key) {        //同样为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //对key进行求hash值        int hash = hash(key.hashCode());        //用hash值进行映射，失去应该去数组的哪个地位上取数据        int index = indexFor(hash, table.length);        //把index地位的元素保留下来进行遍历        //因为e是一个链表，咱们要对链表进行遍历        //找到和key相等的那个QEntry，并返回value        QEntry<K, V> e = table[index];        while (e != null) {            //比拟 hash值是否相等            if (hash == e.hash && (key == e.key || key.equals(e.key))) {                return e.value;            }                        //如果不相等，持续找下一个                e = e.next;        }        return null;    }    /**     * 1 参数key,value很容易了解     * 2 返回V，咱们晓得，HashMap有一个特点，     * 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");     * 前面的值会把后面的笼罩，如果呈现这种状况，返回旧值，在这里返回"tom"     */    public V put(K key, V value) {        //1 为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //不间接用key.hashCode()，咱们对key.hashCode()再作一次运算作为hash值        //这个hash()的办法我是间接从HashMap源码拷贝过去的。能够不必关怀hash()算法自身        //只须要晓得hash()输出一个数，返回一个数就行了。        int hash = hash(key.hashCode());        //用key的hash值和数组的大小，作一次映射，失去应该寄存的地位        int index = indexFor(hash, table.length);        //看看数组中，有没有已存在的元素的key和参数中的key是相等的        //相等则把老的值替换成新的，而后返回旧值        QEntry<K, V> e = table[index];        while (e != null) {            //先比拟hash是否相等，再比拟对象是否相等，或者比拟equals办法            //如果相等了，阐明有一样的key,这时要更新旧值为新的value,同时返回旧的值            if (e.hash == hash && (key == e.key || key.equals(e.key))) {                V oldValue = e.value;                e.value = value;                return oldValue;            }            e = e.next;        }        //如果数组中没有元素的key与传的key相等的话        //把以后地位的元素保留下来        QEntry<K, V> next = table[index];        //next有可能为null，也有可能不为null，不论是否为null        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)        //而后新的元素保留在了index这个地位        table[index] = new QEntry<>(key, value, hash, next);        //如果须要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，教训)        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {            resize();        }        return null;    }    //扩容，元素的个数大于 table.length * 0.75    //数组扩容到原来大小的2倍    private void resize() {        //新建一个数组，大小为原来数组大小的2倍        int newCapacity = table.length * 2;        QEntry[] newTable = new QEntry[newCapacity];        QEntry[] src = table;        //遍历旧数组，从新映射到新的数组中        for (int j = 0; j < src.length; j++) {            //获取旧数组元素            QEntry<K, V> e = src[j];            //开释旧数组            src[j] = null;            //因为e是一个链表，有可能有多个节点，循环遍历进行映射            while (e != null) {                //把e的下一个节点保留下来                QEntry<K, V> next = e.next;                //e这个以后节点进行在新的数组中映射                int i = indexFor(e.hash, newCapacity);                //newTable[i] 地位上有可能是null，也有可能不为null                //不论是否为null，都作为e这个节点的下一个节点                e.next = newTable[i];                //把e保留在新数组的 i 的地位                newTable[i] = e;                //持续e的下一个节点的同样的解决                e = next;            }        }        //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table        table = newTable;    }    //对hashCode进行运算，JDK中HashMap的实现，间接拷贝过去了    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    //依据 h 求key落在数组的哪个地位    static int indexFor(int h, int length) {        //或者  return h & (length-1) 性能更好        //这里咱们用最容易了解的形式，对length取余数，范畴就是[0,length - 1]        //正好是table数组的所有的索引的范畴        h = h > 0 ? h : -h; //避免正数        return h % length;    }}

下面就是QHashMap的原理。上面咱们写一段测试代码来看下咱们的QHashMap能不能失常运行。测试代码如下：

 public static void main(String[] args) {        QHashMap<String, String> map = new QHashMap<>();        map.put("name", "tom");        map.put("age", "23");        map.put("address", "beijing");        String oldValue = map.put("address", "shanghai"); //key一样，返回旧值，保留新值        System.out.println(map.get("name"));        System.out.println(map.get("age"));        System.out.println("旧值=" + oldValue);        System.out.println("新值=" + map.get("address"));    }

输入如下：

tom23旧值=beijing新值=shanghai

通过下面的简略的实现了QHashMap,还有好多功能没有实现，比拟remove,clear,containsKey()等，还有遍历相干，有趣味的读者能够本人实现

## 手写Java HashMap外围源码
上一章手写LinkedList外围源码，本章咱们来手写Java HashMap的外围源码。
咱们来先理解一下HashMap的原理。HashMap 字面意思 hash + map，map是映射的意思，HashMap就是用hash进行映射的意思。不明确？没关系。咱们来具体解说一下HashMap的原理。

HashMap 应用剖析

//1 存HashMap<String,String> map = new HashMap<>();map.put("name","tom");//2 取System.out.println(map.get("name"));//输入 tom

应用就是这么简略。

HashMap 原理剖析

咱们晓得，Object类有一个hashCode()办法，返回对象的hashCode值，能够了解为返回了对象的内存地址，暂且不论返回的是内存地址或者其它什么也好，先不论，至于hashCode()办法回返的数是怎么算的？咱们也不论

第1 咱们只须要记住：这个函数返回的是一个数就行了。
第2 HashMap外部是用了一个数组来存放数据

1 HashMap是如何把 name,tom寄存的？
上面咱们用一张图来演示

从上图能够看出：
注：上图中数组的大小是7，是多少都行，只是咱们这里就画了7个元素，咱们就以数组大小为7来阐明HashMap的原理。

1. 数组的大小是7，那么数组的索引范畴是[0 , 6]
2. 获得key也就是"name"的hashCode，这是一个数，不论这个数是多少，对7进行取余数，那么范畴必定是 [0 , 6]，正好和数组的索引是一样的。
3. "name".hashCode() % 7 的值如果为2 ，那么value也就是"tom"应该寄存的地位就是2
4. data[2] = "tom" ,存到数组中。是不是很奇妙。

2 上面再来看看如何取？
也用一张图来演示底层原理，如下

由上图可知:

1. 首先也是获取key也就是"name"的hashCode值
2. 用hashCode值对数组的大小 7 进行取余数，和存的时候运行一样，必定也是2
3. 从数组的第 2 个地位把value取出，即: String value = data[2]

注：有几点须要留神

1. 某个对象的hashCode()办法返回的值，在任何时候调用，返回的值都是一样的
2. 对一个数 n 取余数 ,范畴是 [ 0, n - 1 ]

注：有几个问题须要解决

1. 存的时候，如果不同的key的hashCode对数组取余数，都正好雷同了，也就是都映射在了数组的同一地位，怎么办？这就是hash抵触问题

比方 9 % 7 == 2 ， 16 % 7 == 2都等于2
答：数组中寄存的是一个节点的数据结构，节点有next属性，如果hash抵触了，单链表进行寄存，取的时候也是一样，遍历链表

1. 如果数组曾经存满了怎么办？

答：和ArrayList一样，进行扩容，从新映射

1. 间接应用hashCode()值进行映射，产生hash抵触的概论很大，怎么办？

答：参考JDK中HashMap中的实现，有一个hash()函数，再对hashCode()的值进行运行一下，再进行映射

由上可知：HashMap是用一个数组来存放数据，如果遇到映射的地位下面曾经有值了，那么就用链表寄存在以后的后面。数组+链表构造，是HashMap的底层构造
如果咱们的数组外面寄存的元素是QEntry，如下图：

手写 HashMap 外围源码

下面剖析了原理，接下来咱们用起码的代码来提醒HashMap的原理。
咱们就叫QHashMap类，同时数组外面的元素须要也须要定义一个类，咱们定义在QHashMap类的外部。就叫QEntry

QEntry的定义如下：

    //底层数组中寄存的元素类   public static class QEntry<K, V> {        K key;      //寄存key        V value;    //寄存value        int hash;   //key对应的hash值                //hash抵触时，也就是映射的地位上曾经有一个元素了        //那么新加的元素作为链表头，曾经寄存的放在前面        //即保留在next中，一句话：增加新元素时，增加在表头        QEntry<K, V> next;          public QEntry(K key, V value, int hash, QEntry<K, V> next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }    }

QEntry类的定义有了，上面看下QHashMap类中须要哪些属性？
QHashMap类的定义如下图：

public class QHashMap<K, V> {    //默认的数组的大小    private static final int DEFAULT_INITIAL_CAPACITY = 16;    //默认的扩容因子，当数据中元素的个数越多时，hash抵触也容易产生    //所以，须要在数组还没有用完的状况下就开始扩容    //这个 0.75 就是元素的个数达到了数组大小的75%的时候就开始扩容    //比方数组的大小是100，当外面的元素减少到75的时候，就开始扩容    private static final float DEFAULT_LOAD_FACTOR = 0.75f;    //寄存元素的数组    private QEntry[] table;    //数组中元素的个数    private int size;     ......}    

只须要两个常量和两个变量就够了。
上面咱们看下QHashMap的构造函数，为了简略，只实现一个默认的构造函数

  public QHashMap() {        //创立一个数组，默认大小为16        table = new QEntry[DEFAULT_INITIAL_CAPACITY];                //此时元素个数是0        size = 0;    }

咱们来看下QHashMap是如何存放数据的 map.put("name","tom")
put()函数的实现如下：

    /**     * 1 参数key,value很容易了解     * 2 返回V，咱们晓得，HashMap有一个特点，     * 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");     * 前面的值会把后面的笼罩，如果呈现这种状况，返回旧值，在这里返回"tom"     */    public V put(K key, V value) {        //1 为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //不间接用key.hashCode()，咱们对key.hashCode()再作一次运算作为hash值        //这个hash()的办法我是间接从HashMap源码拷贝过去的。能够不必关怀hash()算法自身        //只须要晓得hash()输出一个数，返回一个数就行了。        int hash = hash(key.hashCode());        //用key的hash值和数组的大小，作一次映射，失去应该寄存的地位        int index = indexFor(hash, table.length);        //看看数组中，有没有已存在的元素的key和参数中的key是相等的        //相等则把老的值替换成新的，而后返回旧值        QEntry<K, V> e = table[index];        while (e != null) {            //先比拟hash是否相等，再比拟对象是否相等，或者比拟equals办法            //如果相等了，阐明有一样的key,这时要更新旧值为新的value,同时返回旧的值            if (e.hash == hash && (key == e.key || key.equals(e.key))) {                V oldValue = e.value;                e.value = value;                return oldValue;            }            e = e.next;        }        //如果数组中没有元素的key与传的key相等的话        //把以后地位的元素保留下来        QEntry<K, V> next = table[index];        //next有可能为null，也有可能不为null，不论是否为null        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)        //而后新的元素保留在了index这个地位        table[index] = new QEntry<>(key, value, hash, next);        //如果须要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，教训)        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {            resize();        }        return null;    }

正文很具体，这里有几个函数
hash()函数是间接从HashMap源码中拷贝的，不必纠结这个算法。
indexFor()，传入hash和数组的大小，从而晓得咱们应该去哪个地位查找或保留
这两个函数的源码如下：

   //对hashCode进行运算，JDK中HashMap的实现，间接拷贝过去了    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    //依据 h 求key落在数组的哪个地位    static int indexFor(int h, int length) {        //或者  return h & (length-1) 性能更好        //这里咱们用最容易了解的形式，对length取余数，范畴就是[0,length - 1]        //正好是table数组的所有的索引的范畴        h = h > 0 ? h : -h; //避免正数        return h % length;    }

还有一个扩容函数。当元素的个数大于 table.length * 0.75时，咱们就开始扩容
resize()的源码如下 ：

  //扩容，元素的个数大于 table.length * 0.75    //数组扩容到原来大小的2倍    private void resize() {        //新建一个数组，大小为原来数组大小的2倍        int newCapacity = table.length * 2;        QEntry[] newTable = new QEntry[newCapacity];        QEntry[] src = table;        //遍历旧数组，从新映射到新的数组中        for (int j = 0; j < src.length; j++) {            //获取旧数组元素            QEntry<K, V> e = src[j];            //开释旧数组            src[j] = null;            //因为e是一个链表，有可能有多个节点，循环遍历进行映射            while (e != null) {                //把e的下一个节点保留下来                QEntry<K, V> next = e.next;                //e这个以后节点进行在新的数组中映射                int i = indexFor(e.hash, newCapacity);                //newTable[i] 地位上有可能是null，也有可能不为null                //不论是否为null，都作为e这个节点的下一个节点                e.next = newTable[i];                //把e保留在新数组的 i 的地位                newTable[i] = e;                //持续e的下一个节点的同样的解决                e = next;            }        }        //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table        table = newTable;    }

相比put()函数来说，get()就简略多了。
只须要通过hash值找到相应的数组的地位，再遍历链表，找到一个元素外面的key与传的key相等就行了。
put()办法的源码如下：

    //依据key获取value    public V get(K key) {        //同样为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //对key进行求hash值        int hash = hash(key.hashCode());        //用hash值进行映射，失去应该去数组的哪个地位上取数据        int index = indexFor(hash, table.length);        //把index地位的元素保留下来进行遍历        //因为e是一个链表，咱们要对链表进行遍历        //找到和key相等的那个QEntry，并返回value        QEntry<K, V> e = table[index];        while (e != null) {            //比拟 hash值是否相等            if (hash == e.hash && (key == e.key || key.equals(e.key))) {                return e.value;            }                            //如果不相等，持续找下一个                e = e.next;        }        return null;    }

下面就是QHashMap的外围源码，咱们没有实现删除。
上面是把QHashMap整个类的源码收回来

QHashMap残缺源码如下：

public class QHashMap<K, V> {    //默认的数组的大小    private static final int DEFAULT_INITIAL_CAPACITY = 16;    //默认的扩容因子，当数组的大小大于或者等于以后容量 * 0.75的时候，就开始扩容    private static final float DEFAULT_LOAD_FACTOR = 0.75f;    //底层用一个数组来存放数据    private QEntry[] table;    //数组大小    private int size;    //一个点节，数组中寄存的单位    public static class QEntry<K, V> {        K key;        V value;        int hash;        QEntry<K, V> next;        public QEntry(K key, V value, int hash, QEntry<K, V> next) {            this.key = key;            this.value = value;            this.hash = hash;            this.next = next;        }    }    public QHashMap() {        table = new QEntry[DEFAULT_INITIAL_CAPACITY];        size = 0;    }    //依据key获取value    public V get(K key) {        //同样为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //对key进行求hash值        int hash = hash(key.hashCode());        //用hash值进行映射，失去应该去数组的哪个地位上取数据        int index = indexFor(hash, table.length);        //把index地位的元素保留下来进行遍历        //因为e是一个链表，咱们要对链表进行遍历        //找到和key相等的那个QEntry，并返回value        QEntry<K, V> e = table[index];        while (e != null) {            //比拟 hash值是否相等            if (hash == e.hash && (key == e.key || key.equals(e.key))) {                return e.value;            }                        //如果不相等，持续找下一个                e = e.next;        }        return null;    }    /**     * 1 参数key,value很容易了解     * 2 返回V，咱们晓得，HashMap有一个特点，     * 如果调用了屡次 map.put("name","tom"); map.put("name","lilei");     * 前面的值会把后面的笼罩，如果呈现这种状况，返回旧值，在这里返回"tom"     */    public V put(K key, V value) {        //1 为了简略，key不反对null        if (key == null) {            throw new RuntimeException("key is null");        }        //不间接用key.hashCode()，咱们对key.hashCode()再作一次运算作为hash值        //这个hash()的办法我是间接从HashMap源码拷贝过去的。能够不必关怀hash()算法自身        //只须要晓得hash()输出一个数，返回一个数就行了。        int hash = hash(key.hashCode());        //用key的hash值和数组的大小，作一次映射，失去应该寄存的地位        int index = indexFor(hash, table.length);        //看看数组中，有没有已存在的元素的key和参数中的key是相等的        //相等则把老的值替换成新的，而后返回旧值        QEntry<K, V> e = table[index];        while (e != null) {            //先比拟hash是否相等，再比拟对象是否相等，或者比拟equals办法            //如果相等了，阐明有一样的key,这时要更新旧值为新的value,同时返回旧的值            if (e.hash == hash && (key == e.key || key.equals(e.key))) {                V oldValue = e.value;                e.value = value;                return oldValue;            }            e = e.next;        }        //如果数组中没有元素的key与传的key相等的话        //把以后地位的元素保留下来        QEntry<K, V> next = table[index];        //next有可能为null，也有可能不为null，不论是否为null        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)        //而后新的元素保留在了index这个地位        table[index] = new QEntry<>(key, value, hash, next);        //如果须要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，教训)        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {            resize();        }        return null;    }    //扩容，元素的个数大于 table.length * 0.75    //数组扩容到原来大小的2倍    private void resize() {        //新建一个数组，大小为原来数组大小的2倍        int newCapacity = table.length * 2;        QEntry[] newTable = new QEntry[newCapacity];        QEntry[] src = table;        //遍历旧数组，从新映射到新的数组中        for (int j = 0; j < src.length; j++) {            //获取旧数组元素            QEntry<K, V> e = src[j];            //开释旧数组            src[j] = null;            //因为e是一个链表，有可能有多个节点，循环遍历进行映射            while (e != null) {                //把e的下一个节点保留下来                QEntry<K, V> next = e.next;                //e这个以后节点进行在新的数组中映射                int i = indexFor(e.hash, newCapacity);                //newTable[i] 地位上有可能是null，也有可能不为null                //不论是否为null，都作为e这个节点的下一个节点                e.next = newTable[i];                //把e保留在新数组的 i 的地位                newTable[i] = e;                //持续e的下一个节点的同样的解决                e = next;            }        }        //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table        table = newTable;    }    //对hashCode进行运算，JDK中HashMap的实现，间接拷贝过去了    static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    }    //依据 h 求key落在数组的哪个地位    static int indexFor(int h, int length) {        //或者  return h & (length-1) 性能更好        //这里咱们用最容易了解的形式，对length取余数，范畴就是[0,length - 1]        //正好是table数组的所有的索引的范畴        h = h > 0 ? h : -h; //避免正数        return h % length;    }}

下面就是QHashMap的原理。上面咱们写一段测试代码来看下咱们的QHashMap能不能失常运行。测试代码如下：

 public static void main(String[] args) {        QHashMap<String, String> map = new QHashMap<>();        map.put("name", "tom");        map.put("age", "23");        map.put("address", "beijing");        String oldValue = map.put("address", "shanghai"); //key一样，返回旧值，保留新值        System.out.println(map.get("name"));        System.out.println(map.get("age"));        System.out.println("旧值=" + oldValue);        System.out.println("新值=" + map.get("address"));    }

输入如下：

tom23旧值=beijing新值=shanghai

通过下面的简略的实现了QHashMap,还有好多功能没有实现，比拟remove,clear,containsKey()等，还有遍历相干，有趣味的读者能够本人实现