HashMap面试题总结

文章目录

由于HashMap在面试中是一个重点，内容十分多，需要单独写一篇文章总结

HashMap在Jdk1.7与1.8之中有很大区别！！

HashMap简介

HashMap 是用来存储数据的，它底层在JDK 1.7是数组+链表实现的，而JDK 1.8是使用数组+链表+红黑树实现，通过对 key 进行哈希计算等操作后得到数组下标，把 value 等信息存放在链表或红黑树存在此位置。

如果两个不同的 key 运算后获取的数组下标一致，就出现了哈希冲突。数组默认长度是16，如果实际数组长度超过一定的值，就会进行扩容。

问题集合

问点一：你了解HashMap的底层数据结构吗？

在JDK1.7使用的是数组+链表的实现，在JDK1.8中使用的是数组+链表+红黑树

img img

问点二：为什么JDK 7使用数组+链表？JDK8中为什么要使用红黑树？哈希冲突是怎么回事？HashMap又是怎么解决的？

  • JDK 7使用数组+链表，是因为HashMap是根据Key计算Hash值，从而得到哈希表的索引下标，而哈希表本质是数组实现。当出现Hash冲突时，则一个桶可能需要存放多个数据。HashMap将会根据equals()方法，判断Hash冲突的Key是否是同一个值，此时如果仍然不相同，就会利用头插法，将出现Hash冲突的Key+Value存放在链表上。
  • 但是如果一个链表比较长，那么查询的效率将会降低，所以JDK8中又使用了红黑树来解决链表过长导致查询效率变差的问题，会在一个桶上链表长度为8时，进行树化。但是树化的时候，会判断当前的长度是否小于64，如果小于，则不进行树化，而是选择进行一次扩容，因为扩容的时候会使哈希表长度增加，hash值会重新计算，将重新打乱当前的元素排列，分配到新的空间上，这样也避免了链表过长。

对于HashMap中的每个key，根据一个Hash函数，计算出一个Hash值，对应就是桶的编号，桶实际上是用数组实现的。

//key 进行哈希计算
int hash = hash(key);
//获取数组下标
int i = indexFor(hash, table.length);

通过计算后的下标，从而得到数组的对应下标的位置，最后把k，v值存进去，同样的当再次第二次存值的时候，同样把k，v传进来，当k再次进行计算出数组下标index，有可能和第一次计算的index的值相同。

但是，两次的需要存进去的value值是不同的，这就出现了同一个数组后面有一条链表，会比较链表上的每一个value值与当前的value是否相同，若是不相同，通过头插法，将数值插入链表中。如下图所示：

img

接下来通通过源码进行分析，在jdk 7插入的put 方法源码如下：

public V put(K key, V value) {
　　　　　//数组为空就进行初始化
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
　　　　　//key 进行哈希计算
        int hash = hash(key);
　　　　　//获取数组下标
        int i = indexFor(hash, table.length);
　　　　　//如果此下标有值，遍历链表上的元素，key 一致的话就替换 value 的值
        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++;
　　　　　//新增一个key
        addEntry(hash, key, value, i);
        return null;
    }

put方法中主要做了以下几件事：

  1. 判断table数组是否为空，若为空进行初始化table数组。
  2. 判断key值是否为null，将null是作为key存进去。
  3. 若key不为空，通过key计算出数组下标，判断table[i]是否为空。
  4. 若是不为空通过链表循环，判断在链表中是否存在与该key相等，若是存在，直接将value替换成新的value。若是table[i]为空或者链表中不存在与之相同的key，就addEntry(hash, key, value, i)新增一个节点。

接下来看看addEntry(hash, key, value, i)新增节点的源码如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
//数组长度大于阈值且存在哈希冲突（即当前数组下标有元素），就将数组扩容至2倍
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

这个方法很简单，直接就是判断当前数组的大小是否>=threshold并且table[bucketIndex]是否为null。若成立扩容，然后rehash，重新得到新数组的下标值，最后 createEntry(hash, key, value, bucketIndex)创建新节点。

最后来看一下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++;
    }

在JDK 7中，链表存储有一个缺点，就是当数据很多的时候，链表就会很长，每次查询都会遍历很长的链表。

因此在JDK 8中为了优化HashMap的查询效率，将内部的结构改为数组+链表+和红黑树，当一个哈希桶后面的链表长度>8的时候，就会将链表转化为红黑树，红黑树是二分查找，提高了查询的效率。接下来通过JDK 8的put源码分析如下：

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;
　　　　　//数组为空就初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
　　　　　//当前下标为空，就直接插入
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
　　　　　　　//key 相同就覆盖原来的值
            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 {
                for (int binCount = 0; ; ++binCount) {
　　　　　　　　　　　　//链表，尾插法插入数据
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
　　　　　　　　　　　　　　//链表长度超过8，就把链表转为红黑树
                        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;
                }
            }
            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;
    }

通过分析源码，上面的方法主要做了以下几件事：

  1. 判断当前桶是否为空，空的就需要初始化（resize 中会判断是否进行初始化）。
  2. 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。
  3. 如果当前桶有值（ Hash 冲突），那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key是否相等，相等就赋值给 e。
  4. 如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
  5. 如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面（形成链表）。
  6. 接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。
  7. 如果在遍历过程中找到 key 相同时直接退出遍历。
  8. 如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。
  9. 最后判断是否需要进行扩容。

继续看下 treeifyBin 的源码：

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
　　　　　//链表转为红黑树时，若此时数组长度小于64，扩容数组
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
　　　　　　　//链表转为树结构
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

由此可以看到1.8中，数组有两种情况会发生扩容：

  1. 一是超过阈值
  2. 二是链表转为红黑树且数组元素小于64时

由此在jdk1.8中，默认长度为16情况下，要么元素一直放在同一下标，链表转为红黑树且数组元素小于64时就会扩容，要么超过阈值12时才会扩容。

依据上面的源码分析，在JDK 1.8中put方法的执行的原理图如下

image-20200702094441458

问点三：HashMap的扩容机制是怎么样的？JDK7与JDK8有什么不同吗？

JDK 1.7的扩容条件是数组长度大于阈值且存在哈希冲突，而JDK 1.8扩容条件是数组长度大于阈值或链表转为红黑树且数组元素小于64时，源码中的体现如下所示：

JDK1.7扩容源码：

void addEntry(int hash, K key, V value, int bucketIndex) {
　　　　　//数组长度大于阈值且存在哈希冲突（即当前数组下标有元素），就将数组扩容至2倍
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

JDK1.8扩容源码：

//数组长度大于阈值，就扩容
if (++size > threshold)
      resize();

//链表转为红黑树时，若此时数组长度小于64，扩容数组
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
      resize();

问点四：HashMap中的键值可以为Null吗？能简单说一下原理吗？

JDK两个版本都可以。JDK1.7和1.8本质都是去寻找Hash值为0的那个桶，然后如果key为null，则直接替换值

问点五：HashMap中能put两个相同的Key吗？为什么能或为什么不能？

在JDK7和JDK8中的做法是一样的，若是存入的key值一样，就会将原来的key所对应的value值直接替换掉

问点六：聊一聊JDK 7的HashMap中的“死锁”是怎么回事？

首先JDK7采用的头插法，会有链表成环的问题，JDK采用的尾插法，不会有循环链表的问题。

HashMap是线程不安全的，在HashMap的源码中并未对其操作进行同步执行，所以在并发访问的时候就会出现线程安全的问题。

JDK 7死锁出现在高并发的时候，此时两个线程都将对数据进行扩容，每次扩容的时候，会让链表翻转。

transfer函数源码（transfer函数是resize扩容方法中调用的另一个方法）：

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; ---------------------(1)
        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;
    } // while
    }
}

假设一个链表，A.next = B , B.next = null：

  • 正常情况下，新扩容的数组应该是位null，然后A.next = newTable[i]，则A.next = null，newTable[i] = A ，B.next = newTable[i]，则B.next = A，newTable[i] = B
  • 如果两个线程同时转换，此时已然会执行 A.next = newTable[i] , 则将A.next = null变成A.next = B，剩下过程一致，出现循环链表

问点七：HashMap是线程安全的吗？为什么安全或者不安全？

不是线程安全的，比如会在扩容的时候产生循环链表；在put的时候会覆盖别的线程的值

问点八：什么 HashMap 的加载因子是0.75？为什么是超过“8”才用红黑树？

因为HashMap底层的数据结构是哈希表，在插入数据的时候会出现hash冲突，而HashMap的解决方式是使用拉链法，即采用额外的空间来解决冲突。

而选择加载因子是0.75主要跟数学上泊松分布有关系，选择的参数平均为0.5的泊松分布，计算出来当前加载因子是0.75，这更是空间与时间的一种选择折中。

而超过8才使用红黑树，源于该泊松分布计算出来的，一个节点哈希冲突8次的概率极为的小，几乎为不可能时间，这也是一次空间与时间的折中。

​

//1个节点哈希冲突n次的概率
0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006

问点九：HashMap、HashTable、ConcurrentHashMap的区别

HashMap是线程不安全的，在jdk1.7高并发的时候，可能会在扩容的时候，产生循环链表，所以在高并发的时候，不去使用。

HashTable是一个线程安全的，采用的是synchronize的方式，关键字加在方法上，即对当前HashTable对象加锁，会导致所有的数据加上锁。

ConcurrentHashMap在JDK1.7的时候使用的是Segment分段锁的思想，将数据分成段，每个段都有个可重入锁，则多线程的时候不会影响到其他线程访问其他段的数据。

ConcurrentHashMap在JDK1.8的时候使用的是CAS+synchronized方式，抛弃了Segment分段锁的思想，CAS是一个乐观锁，则在不加锁情况下实现赋值，在当前节点为空的时候，会采用CAS的方式添加节点；而用synchronized而不用是可重入锁的原因是因为官方对synchronized做了很多优化。

HashTable其中使用synchronize来保证线程安全，即当有一个线程拥有锁的时候，其他的线程都会进入阻塞或者轮询状态,这样会使得效率越来越低。

而ConcurrentHashMapMap的锁分段技术可以有效的提高并发访问率，HashTable访问效率低下的原因，就是因为所有的线程在竞争同一把锁。

如果容器中有多把锁，不同的锁锁定不同的位置，这样线程间就不会存在锁的竞争，这样就可以有效的提高并发访问效率,这就是ConcurrentHashMap所使用的锁分段技术将数据一段一段的存储，为每一段都配一把锁，当一个线程只是占用其中的一个数据段时,其他段的数据也能被其他线程访问。

在JDK1.7中currentHashMap采用的是Segment分段锁的思想方式实现：

  • Segment是将数据分成段，默认是16，每个段都有一把锁，则理论最高支持16个线程并发

image-20200703093226831

JDK1.8的currentHashMap采用的是**数组+链表+红黑树，抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized **方式实现：

  • CAS，是一个乐观锁，他主要思想是比较然后再执行操作，比较的是内存的值和预期的原值是否一致，如果不一致，则需要自旋获取新值，但是CAS的最大问题就是可能出现ABA的问题。

  • 在no lock when adding to empty bin ，也就是桶为空的时候采用CAS方式添加数据，而不为空的时候采用synchronized 的方式

    image-20200703093803430

问点十：谈谈你理解的 HashMap，讲讲其中的 get和put 过程

put方法：

  • 考虑是否要初始化
  • 根据key计算哈希值，找到hash表对应的索引
  • 然后判断是否出现的hash冲突，如果没有则直接插入，查看是否需要扩容
  • JDK1.7出现hash冲突直接插入链表中即可
  • JDK1.8出现hash冲突，需要先判断当前是红黑树还是链表，对于链表可能会有一个树化的过程

get方法：

  • 思路与上面一致，只是少了一个扩容和树化的过程

image-20200702094441458