Java集合——HashMap（一）

Java集合三大体系——List、Set、Map，而Set是基于Map实现的.在Map中HashMap作为其中常用类，面试中的常客.记得之前有次面试回答，HashMap是链表散列的数据结构，其容量是16，负载因子0.75，当大于容量*负载因子会进行2倍扩容，put操作是将key的hashcode值进行一次hash计算，key的equals方法找到键值对进行替换返回被旧数据，若没有找到会插入到链表中，HashMap线程不安全.当面试官听到这些以后第一个问题为什么容量是16，15、14不行吗？为什么2倍扩容？为什么HashMap建议不可变对象用Key？自己当时思考得不够深入，还没问到ConcurrentHashMap我就已经心慌了...下面我来聊一聊我对HashMap的看法

HashMap简述

继承关系

先看下HashMap的继承关系:

从图中可以看到HashMap实现了Map、Serializable、Cloneable接口，继承了AbstractMap抽象类.那么既然已经继承了AbstractMap，而AbstractMap实现了Map接口，这相当于hashmap已经实现了map接口，可为什么Hashmap还要去实现Map接口，在集合中有很多这样的情况，网上找了下结构大致有以下答案:

①.添加Map接口声明是为了Class类的getInterfaces这个方法能够直接获取到Map接口

②.mistake是一个错误

③.为了java api的文档生成工具而优化，产生更精确的类型的文档

HashMap数据结构

1.7的HashMap采用数组+单链表实现，虽然HashMap定义了hash函数来避免冲突，但还是会出现两个不同的Key经过计算后桶的位置一样，HashMap采用了链表来解决，可如果位于链表中的结点过多，1.7的HashMap通过key值依次查找效率太低，所以在1.8中HashMap进行了改良，采用数组+链表+红黑树来实现，当链表长度超过阈值8时，将链表转换为红黑树.

再来看看Entry中有哪些属性，在1.8中Entry改名为Node，属性不变，1.8改动后面会说，主讲1.7

static class Entry implements Map.Entry {
        /** 贱对象*/
        final K key;
        /** 值对象*/
        V value;
        /** 指向下一个Entry对象*/
        Entry next;
        /** 键对象哈希值*/
        int hash;
    }

1.7 HashMap源码分析

HashMap关键属性

/**
     * 默认初始容量16——必须是2的幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    
    /**
     * HashMap存储的键值对数量
     */
    transient int size;
    
    /**
     * 默认负载因子0.75
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    /**
     * 扩容阈值，当size大于等于其值，会执行resize操作
     * 一般情况下threshold=capacity*loadFactor
     */
    int threshold;
    
    /**
     * Entry数组
     */
    transient Entry[] table = (Entry[]) EMPTY_TABLE;
    
    /**
     * 记录HashMap修改次数，fail-fast机制
     */
    transient int modCount;
    
    /**
     * hashSeed用于计算key的hash值，它与key的hashCode进行按位异或运算
     * hashSeed是一个与实例相关的随机值，用于解决hash冲突
     * 如果为0则禁用备用哈希算法
     */
     transient int hashSeed = 0;

HashMap构造方法

/**
     * 指定容量及负载因子构造方法
     */
    public HashMap(int initialCapacity, float loadFactor) {
        //校验初始容量
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity:" +
                                               initialCapacity);
        //当初始容量超过最大容量，初始容量为最大容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //校验初始负载因子    
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        //设置负载因子
        this.loadFactor = loadFactor;
        //设置扩容阈值
        threshold = initialCapacity;
        //空方法，让其子类重写例如LinkedHashMap
        init();
    }
    
    /**
     * 默认构造方法，采用默认容量16，默认负载因子0.75
     */
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    
    /**
     * 指定容量构造方法，负载因子默认0.75
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

从这3个构造方法中我们可以发现虽然指定了初始化容量大小，但此时的table还是空，是一个空数组，且扩容阈值为初始容量.在其put操作前，会创建数组.

/**
     * 根据已有Map构造新HashMap的构造方法
     * 初始容量:参数map大小除以默认负载因子+1与默认容量的最大值
     * 初始负载因子:默认负载因子0.75
     */
    public HashMap(Map m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        inflateTable(threshold);
        //把传入的map里的所有元素放入当前已构造的HashMap中
        putAllForCreate(m);
    }

这个构造方法便是在put操作前调用inflateTable方法，inflate意为膨胀，这个方法我们来看下，注意刚也提到了此时的threshold扩容阈值是初始容量

private void inflateTable(int toSize) {
        //返回不小于number的最小的2的幂数，最大为MAXIMUM_CAPACITY
        int capacity = roundUpToPowerOf2(toSize);
        //设置扩容阈值，值为容量*负载因子与最大容量+1的较小值
        threshold = (int) Math.min(capacity * loadFactor,
                 MAXIMUM_CAPACITY + 1);
        //创建数组
        table = new Entry[capacity];
        //初始化HashSeed值
        initHashSeedAsNeeded(capacity);
    }
    
    /**
     * 返回不小于number的最小的2的幂数，最大为MAXIMUM_CAPACITY
     */
    private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        /**
         * 若number不小于最大容量则为最大容量
         * 若number小于最大容量大于1，则为不小于number的最小的2的幂数
         * 若都不是则为1
         */
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }

从这里我们可以到HashMap创建了一个2的幂数容量的数组，那为什么一定要这样设计？后面我会介绍.

put方法

我往HashMap中添加元素调用最多就是这个put方法

public V put(K key, V value)

我们来看下其代码实现:

public V put(K key, V value) {
        //若数组为空时创建数组
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        //若key为null
        if (key == null)
            return putForNullKey(value);
        //对key进行hash计算，获取hash值    
        int hash = hash(key);
        //根据刚得到的hash值与数组长度计算桶位置
        int i = indexFor(hash, table.length);
        //遍历桶中链表
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            //key值与hash值都相同的话进行替换
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                //空方法，让其子类重写例如LinkedHashMap
                e.recordAccess(this);
                //返回旧值
                return oldValue;
            }
        }
        //记录修改
        modCount++;
        //链表中不存在此键，则调用addEntry方法向链表中添加新结点
        addEntry(hash, key, value, i);
        return null;
    }

从上面的源码我们可以看到:

①HashMap首先判断数组是否为空，若为空调用inflateTable进行扩容.

②接着判断key是否为null，若为null就调用putForNullKey方法进行put.所以HashMap允许Key为null

③再将key进行一次哈希计算，得到的哈希值和当前数组长度计算得到数组中的索引

④然后遍历该数组索引下的链表，若key的hash和传入key的hash相同且key的equals放回true，那么直接覆盖 value

⑤最后若不存在，那么在此链表中头插创建新结点

逐步来介绍(第一步就不说了上文已阐述过)，第二步最主要就是putForNullKey方法，从中我们可以发现若key为null会先从0位置桶上链表遍历，若找到结点key为null的进行替换，不存在则添加结点.方法内的addEntry后续讲

private V putForNullKey(V value) {
        //遍历0位置桶上的链表，若存在结点Entry的key为null替换value，返回旧值
        for (Entry e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        //若不存在，0位置桶上的链表中添加新结点
        addEntry(0, null, value, 0);
        return null;
    }

第三步中先看下HashMap的hash算法，获取键对象哈希值并将补充哈希函数应用于该对象结果哈希，防止质量差的哈希函数，注意：空键总是映射到散列0，因此索引为0，1.8的hash方法已进行过优化，

final int hash(Object k) {
        // 当h不为0且键对象类型为String用此算法，1.8已删除
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();
        //此函数确保在每个比特位置上仅以恒定倍数不同的hashCode具有有限的碰撞数量（在默认负载因子下约为8）
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

根据所计算的值与数组长度计算桶位置:

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

此方法对数组的长度取模运算，得到的余数进行下表访问，那么既然是取模运算为什么不直接h%length，因为其效率很低，所以采用位运算.从中我们可以看出，假设length为16，当我们h为1，17时算出桶的索引都为1这种情况就称为冲突(k1≠k2，而f(k1)=f(k2)).当有冲突时HashMap采用链地址法(把所有的同义词用单链表连接起来的方法)处理冲突

其次假设length分别为16，15，14时，他们的冲突次数:

从中我们就可以知道为什么不是15，14而必须要是2的幂数，length为16时在[0,15]区间内冲突为0，且雨露均沾分布均匀每个桶都可能会存放数据，而为15，14时不仅有冲突而且有些空间永远不会存放数据这就导致了资源浪费.

那么初始容量为什么要为16，而不是8，32呢？我认为若是8的话扩容阈值为6，没放几个就会扩容;而32的话又不会放那么多，资源浪费.

第四步中若key的hash和传入key的hash相同且key的equals放回true，那么直接覆盖value.key的hash值是根据其hashcode值进行hash哈希计算得到的，那么当我们用可变对象时其hashcode值很容易会变化，那么就会带来风险找不到原来的value，所以HashMap建议使用不可变对象作为Key

最后一步addEntry方法创建新结点，代码如下

void addEntry(int hash, K key, V value, int bucketIndex) {
        //当前hashmap中的键值对数量超过扩容阈值，进行2倍扩容
        if ((size >= threshold) && (null != table[bucketIndex])) {
            //2倍扩容
            resize(2 * table.length);
            //扩容后，桶的数量增加了，重新对键进行哈希码的计算
            hash = (null != key) ? hash(key) : 0;
            //根据键的新哈希码和新的桶数量重新计算桶索引值
            bucketIndex = indexFor(hash, table.length);
        }
        //创建结点
        createEntry(hash, key, value, bucketIndex);
    }
    
    /**
     * 头插结点
     * 将原本在数组中存放的链表头置入到新的Entry之后，将新的Entry放入数组中
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

先不看扩容情况，当不需要扩容时，hashmap采用头插法插入结点，为什么要头插而不是尾插，因为后插入的数据被使用的频次更高，而单链表无法随机访问只能从头开始遍历查询，所以采用头插.突然又想为什么不采用二维数组的形式利用线性探查法来处理冲突，数组末尾插入也是O(1)，可数组其最大缺陷就是在于若不是末尾插入删除效率很低，其次若添加的数据分布均匀那么每个桶上的数组都需要预留内存.

再来看看扩容:

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        //创建新的数组
        Entry[] newTable = new Entry[newCapacity];
        //将旧Entry数组转移到新Entry数组中去
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        //重新设置扩容阈值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

transfer方法遍历旧数组所有Entry，根据新的容量逐个重新计算索引头插保存在新数组中，扩容相当麻烦，所以如果当我们知道需要添加多少数据时最好指定容量初始化.

/**
     * 将旧Entry数组转移到新Entry数组中去
     */
    void transfer(Entry[] newTable, boolean rehash) {
        //获取新数组的长度
        int newCapacity = newTable.length;
        for (Entry e : table) {
            while(null != e) {
                Entry next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //重新计算索引
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

在这里可能会出现环形链表导致死循环.先假设容量为4，负载因子默认0.75，扩容阈值3，HashMap当前存储如下:

单线程情况下若再添加一个元素，HashMap会扩容重新布局可能如下:

那当我们多线程操作HashMap呢？

假定有两个线程同时要添加数据到此HashMap，在扩容时 Thread1正准备处理Entry1，执行完Entry<K,V> next = e.next挂起执行Thread2，此时E为Entry1，next为Entry2

Thread2执行完transfer方法

此时Thread1恢复执行，

将Entry1插入到新数组中去，然后e为Entry2，轮到下次循环时next由于Thread2的操作变为了Entry1

因为Thread2执行过整个transfer方法所以Entry2和Entry1在新散列表中一定会再次冲突，然后将Entry2头插链表，再次e为Entry1，next为null

由于头插Entry1插入链表，将Entry1指向了Entry2，此时环形链表出现了，当我们操作环形链表的桶就会gg.也因为HashMap本就线程不安全，所以sun不认为这是个问题，若有并发场景就用ConcurrentHashMap

get方法

知道了put原理，get操作就很好理解了，先看下代码:

/**
     * 返回到指定键所映射的值，若不存在返回null
     */
    public V get(Object key) {
        //与put一样单独处理
        if (key == null)
            return getForNullKey();
        Entry entry = getEntry(key);
        return null == entry ? null : entry.getValue();
    }

与存null key一样，从0位置上的桶上获取

private V getForNullKey() {
        if (size == 0) {
            return null;
        }
        for (Entry e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

getEntry

final Entry getEntry(Object key) {
        //size为0，即hashmap为空，返回null
        if (size == 0) {
            return null;
        }
        //对key进行hash计算，获取hash值
        int hash = (key == null) ? 0 : hash(key);
        //根据hash值与数组长度获取桶位置，遍历对应桶上链表
        for (Entry e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            //key值与hash值都相同的话返回结点
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        //若不存在返回null
        return null;
    }