HashMap

Java中的HashMap是哈希表（散列表）的实现。哈希表存储的数据是键值对，它能实现快速的查找和存储数据。为了快速的存取数据，哈希表用散列函数将键值映射到表里（通常是一个数组）。

通常情况下散列函数会产生冲突，这里的冲突是指将多个键值映射到表里的同一个位置。如果不解决散列函数产生的冲突，哈希表就无法正常工作。

目前，解决冲突的方法主要有四种：

• 开放寻址法：当前位置发生冲突后，按一定方法找下一个位置。例如线性探测法:产生冲突时，查看当前位置的下一个，直到没有冲突位置。
• 拉链法（hashMap解决冲突的方式）
• 再Hash法:产生冲突时,计算另一个Hash函数，直到没有冲突位置
• 建立公共溢出区：把冲突的元素都放在同一个地方,不在表里面。

HashMap采用的是拉链法解决冲突。拉链法是在表中的每个位置挂一个链表，当发生冲突时，将冲突的元素放到链表上。
如果链表过长的话，HashMap的效率会大大降低,甚至会退化成链表。为了解决这个问题，java 8中的HashMap做了优化，就是当链表长度大于8的时候，将链表转为一个红黑树。

HashMap常用的函数就是put和get，放入元素和读取元素。通过这两个方法能大致的了解HashMap的结构。

        //放入元素
        map.put(4, "barry");
        //获取元素
        map.get(1);
        //获取元素，没有的话返回""
        map.getOrDefault(0,"");
        ...

put方法

/**
     * 在map中放入特定的键值对（key-value）
     * 如果map中存在key，那原来的value值会被取代.
     *
     * @param key 
     * @param value 
     * @return 返回<tt>key</tt>对应的旧值, 如果map中原来没有这个<tt>key</tt>值，
     *          就返回<tt>null</tt>.
     *         (不过返回 <tt>null</tt> ，也可能是
     *          <tt>key</tt>对应的旧值是
     *         <tt>null</tt>，不一定是没有key值)
     */
    public V put(K key, V value) {
        //key可以是null        
        if (key == null)
            //处理key值是null的情况
            return putForNullKey(value);
        
        //计算key值的hash值
        int hash = hash(key);

        //找到key在表中的位置
        int i = indexFor(hash, table.length);
        
        //遍历链表(table中的每个位置是一个Entry<K,V>链表),如果找到key值，就替换原来的元素。
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //根据hash，引用，Equals方法判断是否相等
            //加入引用判断提升效率
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                //记录旧值被取代了。LinkedHashMap会用到这个值
                e.recordAccess(this);
                return oldValue;
            }
        }

        //如果key不在map中，创建一个Entry项
        
        //modCount用于记录HashMap被修改的次数，用于快速失败
        modCount++;
        
        //添加一个Entry项
        addEntry(hash, key, value, i);
        return null;
    }

HashMap的底层结构是数组 + Entry链表。put方法是key,value放入对应的位置。首先计算出key值对应的Hash值；然后根据hash值，找到表中对应的位置（也称桶，槽等）；如果原先有key对应的Entry项（根据hash、引用和Equals方法判断key值是否相等。），就替换旧值，并返回旧值；如果表中原先没有该key值的Entry项，就新建一个Entry,并返回null。

put方法中涉及了putForNullKey，addEntry方法。往下看看者这些方法。

    private V putForNullKey(V value) {
        //tabel[0]的位置遍历，如果map中存在key = null的entry，就用value替换原先的值。
        //能这样做是因为key为null值时，一直存放在table[0]中。
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;                
                e.recordAccess(this);
                return oldValue;
            }
        }
        //如果key不在map中

        modCount++;
        //在table[0]的位置添加entry;
        addEntry(0, null, value, 0);
        return null;
    }

/**
     * 在特定的槽里添加entry<k,v>。
     * 如果map，这个方法会resize table.     
     *
     * 子类覆盖这个方法能重新定义map的put行为.
     */

    void addEntry(int hash, K key, V value, int bucketIndex) {
        //如果size大于等于阈值，并且要添加的槽的位置不为空，就resize。说明添加的元素之前会检查是否要resize.
        if ((size >= threshold) && (null != table[bucketIndex])) {
            //resize为原来的两倍
            resize(2 * table.length);
            //重新计算hash值，如果为null，直接是0
            hash = (null != key) ? hash(key) : 0;
            //重新计算槽的位置
            bucketIndex = indexFor(hash, table.length);
        }

        //添加entry
        createEntry(hash, key, value, bucketIndex);
    }

    void createEntry(int hash, K key, V value, int bucketIndex) {
        //找到对应的位置
        Entry<K,V> e = table[bucketIndex];
        //看起来有点奇怪。直接new的entry,那原先槽里的Entry链表怎么办？实际上new Entry的时候做了一些事。
        //Entry是一个链表的节点，肯定存放着下一个节点的引用。
        //将原先的链表传入构造函数，将新生成的Entry的next指向原来的链表。o(1)时间完成了元素的插入。
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        //大小加1，加入下一个元素的时候判断是否超过了阈值
        size++;
    }

到这已经把put方法大致过了一遍。还想说一下IndexFor方法.就是根据key找到桶的位置.这个方法比较巧妙.

    /**
     * 通过位运算计算桶的位置。之所以能用位运算计算桶的位置,是由于length的大小是2的整数倍（初始值时16，每次resize,map大小乘2）,那么length-1是全1的二进制数,起到了类似掩码的作用.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

看了put方法，那get方法就简单多了。

get方法

     /**
     * 返回Key对应的Value,
     * 如果map中没有key对应的映射，就返回{@code null} 
     *
     * <p>如果map中含有key
     * {@code k} 到 value {@code v} 的映射， 使得 {@code (key==null ? k==null :
     * key.equals(k))}, 那么这个方法就返回 {@code v}; 否则
     * 它就返回 {@code null}.  (最多只有一个这样的映射.)
     *
     * <p>返回值是 {@code null} 不足以说明map不包含key; 也有可能是 key 映射到 {@code null}.
     * {@link #containsKey containsKey} 方法能区别这两种情况.
     *
     * @see #put(Object, Object)
     */
     public V get(Object key) {
         //key等于null就去Table[0]的位置找,和put对应.找不到就返回null
        if (key == null)            
            return getForNullKey();

        //根据key找entry
        Entry<K,V> entry = getEntry(key);

        //如果有nullable类型,这里可能写的好看一些.
        return null == entry ? null : entry.getValue();
    }

 /**
     * Returns the entry associated with the specified key in the
     * HashMap.  Returns null if the HashMap contains no mapping
     * for the key.
     */
    final Entry<K,V> getEntry(Object key) {
        //计算hash值.重新判断null
        int hash = (key == null) ? 0 : hash(key);

        //找到桶的位置,遍历链表
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            //判断相等性
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

JDK的代码中，每个方法都有大量的注释。其实看注释就能很清楚的明白方法的作用了。