校招面试之Java集合常见面试题

2021/9/25 17:13:51

编程Tag： 面试题 hash return key Java null int hashmap 校招

本文主要是介绍校招面试之Java集合常见面试题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

面试总结
问题汇总与答案整理（仅供参考）
- 1. ArrayList和LinkedList的区别（都是线程不安全的）
- 2. ArrayList相关知识
- 3. HashMap，HashTable，ConcurrentHashMap
- - 3.1 HashMap和HashTable的区别
  - 3.2 HashMap的底层实现
  - 3.3 HashMap的扩容机制
  - 3.4 HashMap为什么是线程不安全的
  - 3.5 HashMap为什么要用红黑树，为什么不用其他平衡树
  - 3.6 HashMap的负载因子为什么默认取0.75
  - 3.7 HashMap的哈希过程为什么要高16位与低16位异或
  - 3.8 HashMap和ConcurrentHashMap区别
  - 3.9 ConcurrentHashMap 1.7和1.8的区别与源码，怎么实现线程安全的

面试总结

这一块问来问去主要还是ArrayList和HashMap。HashMap这一块源码是必须要懂的。在有的面试官眼里是必备的基础。

问题汇总与答案整理（仅供参考）

1. ArrayList和LinkedList的区别（都是线程不安全的）

ArrayList是基于Object数组实现的，而LinkedList是基于双向链表实现的
ArrayList支持随机访问，查询速度比LinkedList更快，但进行增加和删除操作的时候，LinkedList不需要向ArrayList一样不断地进行移位操作
内存空间的开销不一样：ArrayList的空间浪费在需要预留一定的容量空间，而LinkedList的空间主要花费在其要存放前驱节点和后继节点的指针信息上

2. ArrayList相关知识

ArrayList继承自AbstractList，初始默认容量为10（private static final int DEFAULT_CAPACITY = 10）

ArrayList有三个构造函数，一个不传参默认生成一个初始容量为10的elementData数组，另一个传入一个初始容量参数，小于0会抛出异常，最后一个是传入一个指定的集合

传入初始容量的构造函数如下：

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        }
    }

ArrayList使用add添加元素的时候会调用grow(size+1)方法来增加容量

private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
 }
 private int newCapacity(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0)
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity: hugeCapacity(minCapacity);
 }

上述代码中ArrayList的MAX_ARRAY_SIZE为Integer.MAX_VALUE-8

3. HashMap，HashTable，ConcurrentHashMap

3.1 HashMap和HashTable的区别

HashMap是线程不安全的，而HashTable是线程安全的，原因是其加了synchronized锁。
HashMap的初始容量默认为16，每次扩容都是2的幂次方倍，而HashTable初始容量是11，扩容是2n+1。
HashMap可以插入null作为键，而HashTable不行，会抛出NullPointerException异常。
在Java1.8之后HashMap在解决哈希冲突时，当链表长度大于8时会将链表转为红黑树，而HashTable不会且因为效率问题基本被弃用了

3.2 HashMap的底层实现

HashMap的数据结构为：

JDK1.7及之前：数组+链表；JDK1.8：数组+链表+红黑树

静态常量（常用）

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;  //负载因子

哈希桶数组中的存储数据结构

//这个是HashMap的一个内部类，实现了Map.Entry接口，其构造方法包含四个参数：hash,key,value,next。
//然后这里面还定义了一些其他方法，如getKey(),getValue(),toString(),setValue(),还重写了equals方法。
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

构造方法（4个）

//第一个传入初始容量和负载因子
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;
    this.threshold = tableSizeFor(initialCapacity);
}
//第二个传入初始容量
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//第三个不传入任何值
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//第四个传入一个指定的Map
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

hash函数

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

put源码

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
//参数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;
    //首先判断table是否为空或者长度是否为0，如果是则需要调用resize()扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //根据hash值计算在哈希桶中的索引，如果当前索引的位置没有节点，直接新建节点添加
    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);
        //如果不是则开始遍历链表准备插入，如果链表长度大于8则转换成红黑树插入，否则链表插入，若key存在直接覆盖
        else {
            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;
                }
                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;
    //插入成功后，判断键值对数量size是否超过了最大容量threshold，超过则扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

get源码

public V get(Object key) {
    Node<K,V> e;
    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;
    //首先判断table是否为空，其长度是否大于0，以及当前位置是否为空，如果有一个是则返回null，不是继续判断
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
    //判断当前位置的首节点是否等于key，是则返回，不是则遍历下一节点，然后判断是否为树节点，如果是转为树查找，不是则遍历链表查找。
        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;
}

3.3 HashMap的扩容机制

下述代码为Java1.7的源代码

void resize(int newCapacity) {   //传入新的容量
     Entry[] oldTable = table;    //引用扩容前的Entry数组
     int oldCapacity = oldTable.length;         
     if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
         threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
         return;
     }   
    Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
    transfer(newTable);                         //将数据转移到新的Entry数组里
    table = newTable;                           //HashMap的table属性引用新的Entry数组
    threshold = (int)(newCapacity * loadFactor);//修改阈值
}

Java1.8对扩容做了哪些优化？

在java1.7版本的时候，扩容的时候每次都需要重新计算hash值，但是因为HashMap使用的是2的幂次方扩展，所以可以发现每次扩容，
元素的位置要么在原位置，要么在原位置上移动新扩容的大小所处的位置。而元素在哈希桶上的位置是由（length-1）& hash得到的，
所以并不需要每次都重新计算hash值，只要看之前hash新增的那个比特是1还是0即可。

HashMap扩容为什么要取2的幂次方？

因为只有在length为2的幂次方的时候hash%length==（length-1）& hash，使用位运算符能够大大提高计算效率

3.4 HashMap为什么是线程不安全的

HashMap在并发时可能出现的问题主要是以下两方面：

put的时候导致的多线程数据不一致

比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的 hash桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的 hash桶索引和线程B要插入的记录计算出来的 hash桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。

resize而引起死循环（JDK1.8已经不会出现该问题）

这种情况发生在JDK1.7 中HashMap自动扩容时，当2个线程同时检测到元素个数超过数组大小 × 负载因子。此时2个线程会在put()方法中调用了resize()，两个线程同时修改一个链表结构会产生一个循环链表（JDK1.7中，会出现resize前后元素顺序倒置的情况）。接下来再想通过get()获取某一个元素，就会出现死循环

3.5 HashMap为什么要用红黑树，为什么不用其他平衡树

因为红黑树和其他平衡树的查找时间复杂度都是O(log(n))，但是红黑树的插入和删除最多两次旋转即可实现平衡，而其他平衡树的旋转比红黑树的旋转要复杂许多

HashMap的链表结构什么时候会转化成红黑树

长度为8时

为什么选长度为8时转换

这个严格意义上来说是由概率决定的，因为链表长度大于等于8时转成红黑树正是遵循泊松分布

3.6 HashMap的负载因子为什么默认取0.75

加载因子如果定的太大，比如1，这就意味着数组的每个空位都需要填满，但如果一直等数组填满才扩容，虽然达到了最大的数组空间利用率，但会产生大量的哈希碰撞，同时产生更多的链表。如果设置的过小，比如0.5，这样一来保证了数组空间很充足，减少了哈希碰撞，这种情况下查询效率很高，但消耗了大量空间。

因此，我们就需要在时间和空间上做一个折中，选择最合适的负载因子以保证最优化，取到了0.75

3.7 HashMap的哈希过程为什么要高16位与低16位异或

这个与HashMap中table下标的计算有关。

n = table.length;
index = （n-1） & hash;

因为，table的长度都是2的幂，因此index仅与hash值的低n位有关，hash值的高位都被与操作置为0了。假设table.length=2⁴=16

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bitejTv7-1632552369746)(C:\Users\MiracleWK\AppData\Roaming\Typora\typora-user-images\image-20210706101655387.png)]

由上图可以看到，只有hash值的低4位参与了运算。这样做很容易产生碰撞。设计者权衡了speed, utility, and quality，将高16位与低16位异或来减少这种影响。

3.8 HashMap和ConcurrentHashMap区别

3.9 ConcurrentHashMap 1.7和1.8的区别与源码，怎么实现线程安全的

3.8和3.9推荐大家看博客ConcurrentHashMap实现原理与分析

这篇关于校招面试之Java集合常见面试题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！