一、HashMap学习笔记

HashMap采用数组+链表的数据结构，只是在jdk1.7和1.8的实现上有所不同，下面，简单的分析一下，方便自己更加深刻的理解这种典型的key-value的数据结构。

1.1.jdk1.7实现原理简单分析

1.7的HashMap数据结构图

WX20181201-102134@2x

也可以这么理解

在jdk1.8之前，HashMap由数组 + 链表组成，也就是链表散列，数组是HashMap的主体，链表实则是为了解决哈希冲突而存在的，（拉链法解决哈希冲突）。

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法换句话说使用扰动函数之后可以减少碰撞。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

1.7的HashMap类中的常量

/** 初始化桶大小，HashMap底层是数组，这个是数组默认的大小 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**  桶的最大值 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/** 默认的负载因子 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

static final Entry<?,?>[] EMPTY_TABLE = {};

/** table真正存放数据的数组 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

/** map中存放数据的大小 */
transient int size;

/** 桶大小。可以在初始化的时候显示指定 */
int threshold;

/** 负载因子，可以在初始化的时候显示指定 */
final float loadFactor;

loadFactor负载因子

默认的HashMap的容量是16，负载因子是0.75，当我们在使用HashMap的时候，随着我们不断的put数据，当数量达到16 * 0.75 = 12的时候，就需要将当前的16进行扩容，而扩容就涉及到数据的复制，rehash等，就消耗性能，所谓的负载因子，也可以叫加载因子，用来控制数组存放数据的疏密程度，loadFactor越趋紧与1，说明数组中存放的entry越多，链表的长度就越长。所以，建议当我们知道HashMap的使用大小时，应该在初始化的时候指定大小，减少扩容带来的性能消耗。

loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。

threshold桶大小

threshold桶大小，也叫临界值，threshold = capacity \* loadFactor，当HashMap的Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 threshold是衡量数组是否需要扩增的一个标准。

table存放数据的数组

table数组中存放的是Entry类型的数据，下面我们简单看看Entry的定义。

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    /** 创建一个新的Entry */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}

Entry是一个内部类，其中的key就是写入的键，value就是写入的值，由于HashMap由数组+链表的形式，这里的next就是用于实现链表结构。hash存放的事当前key的hashcode值。

put()方法

public V put(K key, V value) {
    /** 判断当前数组是否需要初始化 */
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    /** 如果key为空，则put一个空值进去 */
    if (key == null)
        return putForNullKey(value);
    /** 根据key计算出hashcode值 */
    int hash = hash(key);
    /** 根据计算的hashcode值定位所在的桶 */
    int i = indexFor(hash, table.length);
    /** 如果桶是一个链表则需要遍历判断里面的 hashcode、key 是否和传入 key 相等， */
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        /** 如果相等则进行覆盖，并返回原来的值 */
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    /** 如果桶是空的，说明当前位置没有数据存入；新增一个 Entry 对象写入当前位置 */
    addEntry(hash, key, value, i);
    return null;
}

新增一个Entry

void addEntry(int hash, K key, V value, int bucketIndex) {
    /** 判断当前HashMap的size与临界值的大小，判断是否需要扩容操作 */
    if ((size >= threshold) && (null != table[bucketIndex])) {
        /** 如果需要扩容，就进行2倍扩容 */
        resize(2 * table.length);
        /** 将当前的key重新hash并定位 */
        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];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

put()方法简单将如下：

get()方法

public V get(Object key) {
    /** 如果key为null,就去数组[0]的位置找 */
    if (key == null)
        return getForNullKey();
    /** 根据key获取Entry */
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
    /** 如果当前HashMap的size都为0，那就直接返回null */
    if (size == 0) {
        return null;
    }
    /** 根据key计算hashcode值,然后定位到具体的桶中 */
    int hash = (key == null) ? 0 : hash(key);
    /** 判断是否是链表，为链表则需要遍历直到 key 及 hashcode 相等时候就返回值*/
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        /** 不是链表就根据 key、key 的 hashcode 是否相等来返回值*/
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    /** 啥都没取到就直接返回 null */
    return null;
}

1.2.jdk1.8实现原理简单分析

在jdk1.7中HashMap实现原理分析，我们知道当hash冲突很严重的时候，链表的长度就会很长，我们也知道数组和链表的优缺点，简单总结一下：

数组：数据存储是连续的，占用内存很大，所以空间复杂度较高，但是二分查找的时间复杂度为O(1)，简单讲就是，数组寻址容易，插入和删除较为困难。

链表：存储区间零散，所以内存较为宽松，故空间复杂度较低，但是时间复杂的高，为O(n)，简单讲就是，链表寻址困难，插入和删除较为容易。

所以，在jdk1.8中，对HashMap的实现做了相应的修改，jdk1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。

1.8的HashMap的数据结构图

1.8的HashMap类的常量

/** 默认的初始容量16 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/** 最大的容量 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/** 默认的填充因子 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/** 当桶上的节点数量大于8时，会将链表转为红黑树 */
static final int TREEIFY_THRESHOLD = 8;

/** 当桶上的节点数量小于6时，会将红黑树转为链表 */
static final int UNTREEIFY_THRESHOLD = 6;

/**桶中的结构转为红黑树对应的最小数组大小为64 */
static final int MIN_TREEIFY_CAPACITY = 64;

/** 存储元素的数组，总是2的幂次倍 */
transient Node<K,V>[] table;

/** 存放具体元素的集合 */
transient Set<Map.Entry<K,V>> entrySet;

/** 存放元素的个数，注意的是这个值不等于数组的长度 */
transient int size;

/** 每次扩容或者更改map结构的计数器 */
transient int modCount;

/** 临界值，当实际大小（容量 * 负载因子）超过临界值的时候，就会进行扩容操作 */
int threshold;

/** 负载因子 */
final float loadFactor;

对比1.7中的常量，我们就会发现1.8中做了如下的改变。

增加了TREEIFY_THRESHOLD，当链表的长度超过这个值的时候，就会将链表转换红黑树。
Entry修改为Node，虽然Node的核心也是key、value、next。

Node类

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // 哈希值
    final K key; // key
    V value; // value
    Node<K,V> next; // 指向下一个节点
}

树节点类

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // 父
    TreeNode<K,V> left;    // 左
    TreeNode<K,V> right;   // 右
    TreeNode<K,V> prev;    
    boolean red;           // 判断颜色
}

put()方法

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    /** 判断当前桶是否为空，空的就需要初始化（resize 中会判断是否进行初始化） */
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    /** 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空，
     * 为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。
     */
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        /** 如果当前桶有值（ Hash 冲突），
         * 那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等，相等就赋值给 e
         */
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;     
        /** 如果当前桶为红黑树，那就要按照红黑树的方式写入数据*/
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            /** 如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面（形成链表）*/
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    /** 接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树 */
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                /** 如果在遍历过程中找到 key 相同时直接退出遍历 */  
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        /** 如果 e != null 就相当于存在相同的 key,那就需要将值覆盖 */
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    /** 最后判断是否需要进行扩容 */
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

put方法图解

get()方法

public V get(Object key) {
    Node<K,V> e;
    /** 首先将 key hash 之后取得所定位的桶 */
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    /** 如果桶为空则直接返回 null  */
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        /** 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key，是就直接返回 value */
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        /** 如果第一个不匹配，则判断它的下一个是红黑树还是链表 */
        if ((e = first.next) != null) {
            /** 红黑树就按照树的查找方式返回值 */
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            /** 链表就遍历匹配返回值 */
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

小结

从上面的简单分析中，我们可以知道在jdk1.8之后，对HashMap的实现做了改变，主要在于将链表的长度超过临界值的时候，就将链表转为红黑树，利用红黑树的优点，可以更好的查找元素，使得查询的时间复杂度变为O(logn)

但是，jdk1.8并未有修改HashMap之前的线程安全问题，我们都知道HashMap是线程不安全的，涉及到线程安全的时候，我们应该使用ConcurrentHashMap，有关ConcurrentHashMap的知识将在下一片博客中学习，这里简单的分析一下，为什么HashMap会造成线程不安全尼？

1.3.HashMap线程不安全的原因

resize造成死循环

在1.7中，当数据put进HashMap的时候，都会比较和thredhold的大小，当超过临界值的时候，就会进行扩容操作，就会调用resize()方法。而resize()中调用了transfer方法。下面简单的看看transfer方法。

但是在1.8中，resize()方法的实现和1.7有一些不一样，没有使用transfer方法，可以说1.8中hashmap不会因为多线程put导致死循环，但是依然有其他的弊端，比如数据丢失等。因此多线程情况下还是建议使用concurrenthashma,

Jdk1.7中transfer方法如下：

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> 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;
        }
    }
}

transfer方法的的作用就是：

对索引数组中的元素遍历
对链表上的每一个节点遍历：用 next 取得要转移那个元素的下一个，将 e 转移到新 Hash 表的头部，使用头插法插入节点。
循环2，直到链表节点全部转移
循环1，直到所有索引数组全部转移

转移的时候是逆序的。假如转移前链表顺序是1->2->3，那么转移后就会变成3->2->1。死锁问题不就是因为1->2的同时2->1造成的吗？所以，HashMap 的死锁问题就出在这个transfer()函数上。

隐士，一枚88年的java程序员，好奇心比较强，目前是一个码农，从事Java方向的研究和开发。-- hins

JavaEE基础知识学习-----HashMap学习笔记

一、HashMap学习笔记

1.1.jdk1.7实现原理简单分析

1.7的HashMap数据结构图

1.7的HashMap类中的常量

loadFactor负载因子

threshold桶大小

table存放数据的数组

put()方法

新增一个Entry

get()方法

1.2.jdk1.8实现原理简单分析

1.8的HashMap的数据结构图

1.8的HashMap类的常量

Node类

树节点类

put()方法

put方法图解

get()方法

小结

1.3.HashMap线程不安全的原因

resize造成死循环