理解HashMap，实现基础的hashMap

HashMap的原理

HashMap的原理是存储数据到内部的数组中，最简单的原理是把每个key的hash值当做脚标，类似tab【hash(key)】 = value,但是hash值过于庞大，会造成内存溢出，所以需要一个算法indexFor（）来替代hash(key)，把这个范围计算在先前预定的数组长度范围内，但是这个indexFor方法会造成不同的hash值算出来相同的脚标，这个就是所谓的hash碰撞，那么重复的脚标就交由链式结构来处理，在相同的位置用链式结构去存储这些相同的indexFor()算出来的脚标，这也就是原来的hashMap链式存储结构了。

JDK1.7到1.8中HashMap的变化

1.8中主要的变化是原来的链式结构如果到达长度8之后变成红黑树结构存储数据，1.7中如果在hash碰撞之后会在原来的节点生成一个链式结构，过长会导致查询效率变低，1.8中优化了这块。

模拟HashMap基础功能代码

package com.example.qianfei.map;

/**
 * Created by qf on 2018/10/24
 * 描述: MyHashMap
 */
public class MyHashMap<K, V> {

    //默认的数组长度
    private int defulLen = 16;

    //主要用于存储数据的数组
    private EntryBean<K,V>[] table = new EntryBean[defulLen];

    public V put(K key, V value) {
        EntryBean<K, V> kvEntryBean = table[indexFor(hash(key), defulLen)];

        //key等于null先不处理

        if (null == kvEntryBean) {
            //相同脚标处没有出现过hash碰撞，需要new一个EntryBean 存上数据到这个位置
            table[indexFor(hash(key), defulLen)] = new EntryBean<>(key, value, null, hash(key));
            return value;
        } else {
            //kvEntryBean 不是空的说明在这个脚标下有存储数据，需要判断是否有存储过之前的key，
            // 如果没有需要链式存储一下,新的数据作为新的链式头部
            // 如果有需要替换下

            //判断这个链上是否有存储过相同的key
            for (EntryBean<K, V> e = kvEntryBean; null != e.getNextBean(); e = e.getNextBean()) {
                if (e.getHashCode() == hash(key) && (e.getKey() == key || key.equals(e.getKey()))) {
                    //有相同的 需要替换掉
                    V oldVlue = e.getValue();
                    e.setValue(value);
                    return oldVlue;
                }
            }

            //没有相同的需要链式存储一下,新的数据作为新的链式头部
            table[indexFor(hash(key), defulLen)]  = new EntryBean(key,value, kvEntryBean, hash(key));

            return value;
        }

    }


    public V get(K key) {
        //通过二次 hash 获得脚标
        int i = indexFor(hash(key), defulLen);
        //获得这个脚标所在的链式的头对象
        EntryBean<K, V> kvEntryBean = table[i];

        //遍历链表 查找符合的key对应的value
        for (EntryBean<K, V> e = kvEntryBean; null != e; e = e.getNextBean()) {
            if (e.getHashCode() == hash(key) && (e.getKey() == key || key.equals(e.getKey()))) {
                return e.getValue();
            }
        }
        return null;
    }

    public static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h =key.hashCode()) ^ (h >>> 16);
    }

    public static int indexFor(int hashcode, int length) {
        return hashcode & (length-1);
    }

    public static class EntryBean<K, V>{
        K key;
        V value;
        EntryBean nextBean;
        int hashCode;

        public EntryBean(K key, V value, EntryBean bean, int code) {
            this.key = key;
            this.value = value;
            this.nextBean = bean;
            this.hashCode = code;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }

        public EntryBean getNextBean() {
            return nextBean;
        }

        public void setNextBean(EntryBean nextBean) {
            this.nextBean = nextBean;
        }

        public int getHashCode() {
            return hashCode;
        }

        public void setHashCode(int hashCode) {
            this.hashCode = hashCode;
        }
    }
}

几个疑问
hash碰撞
在HashMap中内部存储是通过数组存储的，脚标是通过key的二次hash计算算出来的，二次计算中会导致不同的key算出相同的脚标，把这理解为hash碰撞

resize()
一般内部的数组有个默认的存储大小16个长度，但是不断存储数据时数组需要不断扩大，这个在什么时候扩大数组是通过一个阀门值控制的，如果存储的数据长度到达了当前长度的0.75是会去扩大数组长度，扩大一倍。
原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize
hashMap扩容之后位置重新排版，重新计算tab脚标位置

为什么hashMap长度都是2的次幂
hashMap内部的存储是数组，脚标是通过key的hash值与(&)上长度-1 的来计算的，2^n-1 算出的二进制末尾都是1，不同的key算得得index相同的几率较小，方便脚标的平均分布，减少碰撞的几率，提高查询效率

concurrentHashMap的分步锁
HashMap不支持异步操作，推荐concurrentHashMap

HashMap为什么是线程不安全的
resize()之后会把旧的tab的数据重新排版到新的tab上，多线程情况下有可能会导致同一个tab位置的链接首尾的对象互相成为next对象，在get的时候就会出现死循环

学习自一处大神博客，详细学习jdk1.8和1.7中HashMap变化的去看看JDK1.7&1.8源码对比分析【集合】HashMap
这块Hashmap的扩容机制以及一些细节讲得很棒HashMap的扩容机制—resize()