java校招面试题:常见集合有哪些?HashMap 和 Hashtable 区别有哪些?

2021年3月5日15:13:09 发表评论 96 views

集合这方面的考察相当多,这部分是面试中必考的知识点。

1)说说常见的集合有哪些吧?

答:Map 接口和 Collection 接口是所有集合框架的父接口:

Collection 接口的子接口包括:Set 接口和 List 接口;
Map 接口的实现类主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap 以及 Properties 等;
Set 接口的实现类主要有:HashSet、TreeSet、LinkedHashSet 等;
List 接口的实现类主要有:ArrayList、LinkedList、Stack 以及 Vector 等。

2)HashMap 和 Hashtable 的区别有哪些?(必问)

答:
HashMap 没有考虑同步,是线程不安全的;Hashtable 使用了 synchronized 关键字,是线程安全的;
前者允许 null 作为 Key;后者不允许 null 作为 Key。

3)HashMap 的底层实现你知道吗?

答:在 Java8 之前,其底层实现是数组 + 链表实现,Java8 使用了数组 + 链表 + 红黑树实现。此时你可以简单的在纸上画图分析:
java校招面试题:常见集合有哪些?HashMap 和 Hashtable 区别有哪些?

4)ConcurrentHashMap 和 Hashtable 的区别?(必问)

答:ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步,hashtable 考虑了同步的问题。但是 hashtable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。 ConcurrentHashMap 将 hash 表分为 16 个桶(默认值),诸如 get,put,remove 等常用操作只锁当前需要用到的桶。

面试官:ConcurrentHashMap 的具体实现知道吗?
答:
该类包含两个静态内部类 HashEntry 和 Segment;前者用来封装映射表的键值对,后者用来充当锁的角色;
Segment 是一种可重入的锁 ReentrantLock,每个 Segment 守护一个 HashEntry 数组里得元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 锁。

5)HashMap 的长度为什么是 2 的幂次方?

答:
通过将 Key 的 hash 值与 length-1 进行 & 运算,实现了当前 Key 的定位,2 的幂次方可以减少冲突(碰撞)的次数,提高 HashMap 查询效率;
如果 length 为 2 的次幂 则 length-1 转化为二进制必定是 11111……的形式,在于 h 的二进制与操作效率会非常的快,而且空间不浪费;
如果 length 不是 2 的次幂,比如 length 为 15,则 length-1 为 14,对应的二进制为 1110,在于 h 与操作,最后一位都为 0,而 0001,0011,0101,1001,1011,0111,1101 这几个位置永远都不能存放元素了,空间浪费相当大。
更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!这样就会造成空间的浪费。

6)List 和 Set 的区别是啥?

答:List 元素是有序的,可以重复;Set 元素是无序的,不可以重复。

7)List、Set 和 Map 的初始容量和加载因子

答:

  1. List
    ArrayList 的初始容量是 10;加载因子为 ; 扩容增量:原容量的 倍 +1;一次扩容后长度为 16。
    Vector 初始容量为 10,加载因子是 1。扩容增量:原容量的 1 倍,如 Vector 的容量为 10,一次扩容后是容量为 20。
  2. Set
    HashSet,初始容量为 16,加载因子为 ; 扩容增量:原容量的 1 倍; 如 HashSet 的容量为 16,一次扩容后容量为 32
  3. Map
    HashMap,初始容量 16,加载因子为 ; 扩容增量:原容量的 1 倍; 如 HashMap 的容量为 16,一次扩容后容量为 32

8)Comparable 接口和 Comparator 接口有什么区别?

答:
前者简单,但是如果需要重新定义比较类型时,需要修改源代码。
后者不需要修改源代码,自定义一个比较器,实现自定义的比较方法。

9)Java 集合的快速失败机制 “fail-fast”

答:它是 java 集合的一种错误检测机制,当多个线程对集合进行结构上的改变的操作时,有可能会产生 fail-fast 机制。
例如 :假设存在两个线程(线程 1、线程 2),线程 1 通过 Iterator 在遍历集合 A 中的元素,在某个时候线程 2 修改了集合 A 的结构(是结构上面的修改,而不是简单的修改集合元素的内容),那么这个时候程序就会抛出 ConcurrentModificationException 异常,从而产生 fail-fast 机制。

原因: 迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化,就会改变 modCount 的值。

每当迭代器使用 hashNext()/next() 遍历下一个元素之前,都会检测 modCount 变量是否为 expectedmodCount 值,是的话就返回遍历;否则抛出异常,终止遍历。

解决办法:

在遍历过程中,所有涉及到改变 modCount 值得地方全部加上 synchronized;
使用 CopyOnWriteArrayList 来替换 ArrayList。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: