Java HashMap原理以及常见的面试题

叙述 HashMap 原理这里以代码为例,本文还回分析一些HashMap在面试中遇到的一些问题以及解答。

1. 先了解几点重要知识

1.1. HashMap的组成

JDK1.7 数组+列表（Entry）分散存储在一个数组。
JDK1.8 数组+列表+红黑树,（Entry）分散存储在一个数组。JDK1.8中在 HashMap 中引入了红黑树的概念。

1.2. 扩容因子：0.75

加载因子是表示Hash表中元素的填满的程度。加载因子越大,填满的元素越多,空间利用率越高，但冲突的机会加大了。
反之,加载因子越小,填满的元素越少,冲突的机会减小,但空间浪费多了。
因此,必须在 “冲突的机会”与”空间利用率”之间寻找一种平衡与折衷。
HashMap负载因子为 0.75 (百分之75) 是空间和时间成本的一种折中。

1.3. 初始容量：2的幂次方

在初始化时 HashMap 会计算当前容量是否为2的幂次方,如果不是将补足。

如：new HashMap<>(10) 假设我们初始化数组容量为10,在初始化会计算为2的幂次方也就是16。

如下代码：

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

1.4. Hash槽定位

样例代码：

HashMap map = new HashMap<>();
map.put(20,"定位Hash槽");

以上给 HashMap 中添加了一个key为20的元素：

1.在put元素时会将当前key计算hash值,通过现有的key计算确认hashCode为20,下面看看 Hash槽是如何定位到数组里的。
2.用Hash值定位数组:

hashCode 20转为二进制位为10100,(默认的长度容量为16,是下面代码 n 的值）length-1=15 = 01111 (n - 1),用2进制算法的与进行计算 10100 & 01111 = 00100 = 4
说说与符号计算,二进制为 10100 跟 01111 相比都为1的输出 1 所以计算后为 00100 = 4 最后N位刚好就是十进制的取余运算的结果 20 % 16 = 4
为什么要用二进制算,不用 % 求模算,因为二进制算的速度比求模快10倍

if ((p = tab[i = (n - 1) & hash]) == null)
   tab[i] = newNode(hash, key, value, null);

1.5. 源码解析 get：获取元素

'以下操作牵扯到数组,链表以及红黑树本文章不做讲解'
public V get(Object key) {
        Node e; '一.查询到的元素'
        return (e = getNode(hash(key), key)) == null ? null : e.value;
}
'二.获取Node方法'
'1).hash 为key的hash值;'
'2).key 为键;'
'3).Node[] tab;为数组'
'4).Node first;(链表或红黑树)'
'5).Node e;子节点'
'5).int n 数组长度'
'5).K k 存储在节点中的Key元素'
final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    '将成员变量tab赋给局部变量tab,并且当前数组的长度大于0,并且定位到hash槽中的节点不为空,将数组里的节点获取出来'
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) { '//first = tab[(n - 1) & hash])定位hash槽获取元素'
        '判断根节点的hash以及key是否完全相等。链表以及红黑树的根节点的操作复杂度为0(1)'
        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)
                '如果是转换为红黑树,调用getTreeNode查找元素,并返回'
                return ((TreeNode)first).getTreeNode(hash, key);
            '不为红黑树,就是链表循环遍历查找元素'
            do {
                '如链表中hash以及key是否完全相等'
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    '相等就返回元素'
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

1.6. 源码解析 put：添加元素

'1).Node[] tab;为数组'
'2).Node p;为节点(链表或红黑树)'
'5).int n 数组长度'
'5).i 为定位hash槽的下标(数组下标)'
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node[] tab; Node p; int n, i;
    '判断当前数组是否为空'
    if ((tab = table) == null || (n = tab.length) == 0)
        '等于空就调整大小'
        n = (tab = resize()).length;
    '定位hash槽获取元素(Node 节点)'
    if ((p = tab[i = (n - 1) & hash]) == null)
        '为空创建一个新的链表'
        tab[i] = newNode(hash, key, value, null);
    else {
        '判断根节点的hash以及key是否完全相等。链表以及红黑树的根节点的操作复杂度为0(1)'
        Node e; K k;
        if (p.hash == hash &&
            '如果根节点key相等'
            ((k = p.key) == key || (key != null && key.equals(k))))
            '相等就替换'
            e = p;
        '判断是否为红黑树'
        else if (p instanceof TreeNode)
            '是就转换到红黑树中进行添加元素操作'
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        '根节点不相等进行下面代码'
        else {
            '循环操作(无条件操作,直到成功时停止循环)'
            for (int binCount = 0; ; ++binCount) {
                '判断子节点是否为空'
                if ((e = p.next) == null) {
                    '为空就创建一个新的节点,并且赋值给当前节点'
                    p.next = newNode(hash, key, value, null);
                    '判断循环次数是否大于等于 8 - 1 的长度'
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        '是就将当前链表转换为红黑树继续操作'
                        treeifyBin(tab, hash);
                    break;
                }
                '子节点不为空,判断子节点的hash以及key相等,是就停止循环。e 为HashMap里有的值,需要将value替换'
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                '将节点值赋值给局部变量,进行下一次修改'
                p = e;
            }
        }
        '如果e元素存在声明,之前HashMap节点中有这个key根value,value的值需要'
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            '替换值 !onlyIfAbsent 为 true'
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            '将当前节点移动到链表最后'
            afterNodeAccess(e);
            return oldValue;
        }
    }
    '如果代码进入这说明,是新添加了一个元素'
    ++modCount;
    '判断当前tab数组是否要扩容'
    if (++size > threshold)
        '调整数组大小'
        resize();
    afterNodeInsertion(evict);
    return null;
}

1.7. 源码解析 resize: 扩容

当容量大于 0.75 负载因子进行扩。即默认情况下数组长度是16*0.75=12时，触发扩容操作。
创建一个原来的2倍数组,将原数组值复制进去,这里需要重新计算位置,我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

2. HashMap 面试题

2.1. HashMap1.7跟1.8的HashMap的区别

HashMap1.7 是由数组+链接组成
HashMap1.8 是由数组+链接+红黑树组成

2.2. HashMap1.8 为什么要引入红黑树,有那些好处

首先红黑树是一个绝对平衡二叉树 ,操作级别在O(logN),链接的插入节点操作是O(1)级别,查询为O(n)级别的。
HashMap的Hash冲突如果链表来存储,如果链接很长,需要从头节点查询到尾节点查询开销太大,查询速度慢。
引用红黑树是,当链表长度为8的时候会将链表转换为红黑树进行存储,红黑树的查询是通过左右子树查询的。(这里不做过多的解释了,有兴趣可以去看看红黑树或平衡二叉树)

2.3. HashMap1.7用的是链表头节点插入,HashMap1.8是用尾节点插入的有什么区别,会发生什么问题

1.7 头节点插入数据,主要是考虑热点数据的原因, 而 1.8 引入了红黑树不需要考虑热点数据。
1.7 头节点插入,在resize()扩容会使链表形成倒序,(形成倒序之后会发生死循环,当多线程处理的时候，此时如果存在a->b->c链表，当我们rehash以后，有可能变为b->a，然而其他的线程处理完之后，结果可能会造成b->a->b，造成loop成环。一旦寻找数据会造成死循环。)
1.8 为了解决 1.7 中的一些问题,采用了尾部插入的方式,源码中使用了一个高位来识别之前的数据和插入的新数据，保持了之前的顺序，解决了1.7中可能造成成环的问题。具体的实现是扩容只有最高位会多出一个1，如果之前的数据一旦e & oldCapacity = 0，表明是原来的数据，保持就好，如果是为1，表明是即将插入的新数据，此时保持插入高位，这样就避免了成环的问题。

Java技术知识

Java HashMap

Jvm 配置及优化上一篇

Java OOM定位处理下一篇