HashMap常考面试题

HashMap概述

HashMap的底层使用数据+链表+红黑树的数据结构，数组部分主要是用来方便查找，时间复杂度为O（1），默认大小是16，数组的下标索引是通过key的hashCode计算得到的，当多个key的hashCode值相同时，但Key值不同时，单个Node就会转换为链表。链表的查询复杂度为O(n)，当链表的长度大于等于8并且数组的长度超过64时，链表就会转化为红黑树，红黑树的查询复杂度为O(log(n))

一图胜千言,还是图上说话吧

 //初始容量为 16
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

 //最大容量
 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;

 //记录迭代过程中 HashMap 结构是否发生变化，如果有变化，迭代时会 fail-fast
 transient int modCount;

 //HashMap 的实际大小，可能不准(因为当你拿到这个值的时候，可能又发生了变化)
 transient int size;

 //存放数据的数组
 transient Node<K,V>[] table;

 // 扩容的门槛，有两种情况
 // 如果初始化时，给定数组大小的话，通过 tableSizeFor 方法计算，数组大小永远接近于 2 的幂次方，比如你给定初始化大小 19，实际上初始化大小为 32，为 2 的 5 次方。
 // 如果是通过 resize 方法进行扩容，大小 = 数组容量 * 0.75
 int threshold;

 //链表的节点
 static class Node<K,V> implements Map.Entry<K,V> {
 
 //红黑树的节点
 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

HashMap存储数据的过程是什么样的？

不同的JDK版本中存储过程略有差异，以JDK1.8为例，存储数据的过程可以分为以下几步：

如果当前数组为null,进行容量的初始化，初始化容量为16
对Key进行hashCode(),进行hash后计算数组获得下标index
如果hash计算后没有发生碰撞，直接放到对应数组下标里
如果hash计算后发生碰撞且节点已经存在，则替换掉原来的对象
如果hash计算后发生碰撞且节点已经是树结构，则挂载到树上
如果hash计算后发生碰撞且节点是链表结构，则添加到链表尾部，并且判断链表是否需要转成树结构（默认大于8的情况会转成树结构）
完成put后，是否需要resize()操作，(数组量超过threshold,threshold为初始容量和负载因子之积，默认为12)

而在jdk1.7的版本中，5、6步骤是合在一起的，即如果发生哈希碰撞且节点是链表结构，则放在链表头。

未命名文件

// 参数onlyIfAbsent表示是否替换原值
// 参数evict我们可以忽略它，它主要用来区别通过put添加还是创建时初始化数据的
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 空表，需要初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        // resize()不仅用来调整大小，还用来进行初始化配置
        n = (tab = resize()).length;
    // (n - 1) & hash这种方式也熟悉了吧？都在分析ArrayDeque中有体现
    //这里就是看下在hash位置有没有元素，实际位置是hash % (length-1)
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 将元素直接插进去
        tab[i] = newNode(hash, key, value, null);
    else {
        //这时就需要链表或红黑树了
        // e是用来查看是不是待插入的元素已经有了，有就替换
        Node<K,V> e; K k;
        // p是存储在当前位置的元素
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; //要插入的元素就是p，这说明目的是修改值
        // p是一个树节点
        else if (p instanceof TreeNode)
            // 把节点添加到树中
            e = ((TreeNode<K,V>)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);
                    // 链表比较长，需要树化，
                    // 由于初始即为p.next，所以当插入第8个元素才会树化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到了对应元素，就可以停止了
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 继续向后
                p = e;
            }
        }
        // e就是被替换出来的元素，这时候就是修改元素值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 默认为空实现，允许我们修改完成后做一些操作
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // size太大，达到了capacity的0.75，需要扩容
    if (++size > threshold)
        resize();
    // 默认也是空实现，允许我们插入完成后做一些操作
    afterNodeInsertion(evict);
    return null;
}

如果hashcode值相同，如何获取对象？

hashCode相同，说明这些对着对象都在同一个数组下标对应的链表或者树上。get方法的签名是V get(Object key),入参只有一个key，因此通过遍历链表或者树，取出每一个节点对比hash值是否相等且Key是否相等（==或者equals）

final Node<K,V> getNode(int hash, Object key) {
 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
 if ((tab = table) != null && (n = tab.length) > 0 &&
     (first = tab[(n - 1) & hash]) != null) {
     // 数组该位置的第一个对象是目标对象的条件：hash值相等且key相等（=或者equals)
     if (first.hash == hash && // always check first node
         ((k = first.key) == key || (key != null && key.equals(k))))
         return first;
     //数组该位置的第一个对象不是目标对象，则遍历链表或者树
     if ((e = first.next) != null) {
           xxx;
         } while ((e = e.next) != null);
     }
 }
 return null;
}

HashMap和HashTable的区别？

HashMap是线程不安全的，HashTable是线程安全的
HashMap的键需要重新计算对象的hash值，而hashTable只是使用对象的hash值
HashMap的键和值都可以是null,HashTable的键和值都不可以是null,
HashMap的数组初始化容量是16，HashTable的初始化容量是11，HashMap扩容是原来的2倍，HashTable扩容原来的两倍+1

JDK1.8中HashMap的hashCode计算方式

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

源码中就是通过以上代码来计算 hash 的，首先计算出 key 的 hashcode，因为 key 是 Object，所以会根据 key 的不同类型进行 hashcode 的计算，接着计算 h ^ (h >>> 16) ，这么做的好处是使大多数场景下，算出来的 hash 值比较分散。