第1章 第8节 集合(二)

2020-10-17   95 次阅读


● 请解释为什么集合类没有实现Cloneable和Serializable接口?

考察点:JAVA集合

参考回答:

克隆(cloning)或者是序列化(serialization)的语义和含义是跟具体的实现相关的。因此,应该由集合类的具体实现来决定如何被克隆或者是序列化。
实现Serializable序列化的作用:将对象的状态保存在存储媒体中以便可以在以后重写创建出完全相同的副本;按值将对象从一个从一个应用程序域发向另一个应用程序域。
实现 Serializable接口的作用就是可以把对象存到字节流,然后可以恢复。所以你想如果你的对象没有序列化,怎么才能进行网络传输呢?要网络传输就得转为字节流,所以在分布式应用中,你就得实现序列化。如果你不需要分布式应用,那就没必要实现实现序列化。

● 请说明Java集合类框架的基本接口有哪些?

考察点:JAVA集合

参考回答:

集合类接口指定了一组叫做元素的对象。集合类接口的每一种具体的实现类都可以选择以它自己的方式对元素进行保存和排序。有的集合类允许重复的键,有些不允许。
Java集合类提供了一套设计良好的支持对一组对象进行操作的接口和类。Java集合类里面最基本的接口有:
Collection:代表一组对象,每一个对象都是它的子元素。
Set:不包含重复元素的Collection。
List:有顺序的collection,并且可以包含重复元素。
Map:可以把键(key)映射到值(value)的对象,键不能重复。

● 请你说明一下ConcurrentHashMap的原理?

考察点:JAVA内存模型

参考回答:

ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEntry 用来封装映射表的键 / 值对;Segment 用来充当锁的角色,每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。HashEntry 用来封装散列映射表中的键值对。在 HashEntry 类中,key,hash 和 next 域都被声明为 final 型,value 域被声明为 volatile 型。

static final class HashEntry<K,V> {
       final K key;                       // 声明 key 为 final 型
       final int hash;                   // 声明 hash 值为 final 型
       volatile V value;                 // 声明 value 为 volatile 型
       final HashEntry<K,V> next;      // 声明 next 为 final 型
 
       HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
           this.key = key;
           this.hash = hash;
           this.next = next;
           this.value = value;
       }
}

在ConcurrentHashMap 中,在散列时如果产生“碰撞”,将采用“分离链接法”来处理“碰撞”:把“碰撞”的 HashEntry 对象链接成一个链表。由于 HashEntry 的 next 域为 final 型,所以新节点只能在链表的表头处插入。 下图是在一个空桶中依次插入 A,B,C 三个 HashEntry 对象后的结构图:

图1. 插入三个节点后桶的结构示意图:

注意:由于只能在表头插入,所以链表中节点的顺序和插入的顺序相反。

Segment 类继承于 ReentrantLock 类,从而使得 Segment 对象能充当锁的角色。每个 Segment 对象用来守护其(成员对象 table 中)包含的若干个桶。

● 请解释一下TreeMap?

考察点:key-value集合

参考回答:

TreeMap是一个有序的key-value集合,基于红黑树(Red-Black tree)的 NavigableMap实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator进行排序,具体取决于使用的构造方法。
TreeMap的特性:
根节点是黑色
每个节点都只能是红色或者黑色
每个叶节点(NIL节点,空节点)是黑色的。
如果一个节点是红色的,则它两个子节点都是黑色的,也就是说在一条路径上不能出现两个红色的节点。
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

● 请说明ArrayList是否会越界?

考点:集合

参考回答:

ArrayList是实现了基于动态数组的数据结构,而LinkedList是基于链表的数据结构2. 对于随机访问get和set,ArrayList要优于LinkedList,因为LinkedList要移动指针;ArrayList并发add()可能出现数组下标越界异常。

● 请你说明concurrenthashmap有什么优势以及1.7和1.8区别?

考点:集合

参考回答:

Concurrenthashmap线程安全的,1.7是在jdk1.7中采用Segment + HashEntry的方式进行实现的,lock加在Segment上面。1.7size计算是先采用不加锁的方式,连续计算元素的个数,最多计算3次:1、如果前后两次计算结果相同,则说明计算出来的元素个数是准确的;2、如果前后两次计算结果都不同,则给每个Segment进行加锁,再计算一次元素的个数;

1.8中放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,1.8中使用一个volatile类型的变量baseCount记录元素的个数,当插入新数据或则删除数据时,会通过addCount()方法更新baseCount,通过累加baseCount和CounterCell数组中的数量,即可得到元素的总个数;

● 请你说明一下TreeMap的底层实现?

考点:集合

参考回答:

TreeMap 的实现就是红黑树数据结构,也就说是一棵自平衡的排序二叉树,这样就可以保证当需要快速检索指定节点。

红黑树的插入、删除、遍历时间复杂度都为O(lgN),所以性能上低于哈希表。但是哈希表无法提供键值对的有序输出,红黑树因为是排序插入的,可以按照键的值的大小有序输出。红黑树性质:

性质1:每个节点要么是红色,要么是黑色。

性质2:根节点永远是黑色的。

性质3:所有的叶节点都是空节点(即 null),并且是黑色的。

性质4:每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点)

性质5:从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

● 请你说明ConcurrentHashMap锁加在了哪些地方?

考点:集合

参考回答:

加在每个Segment 上面。

● 请你解释HashMap的容量为什么是2的n次幂?

考点:集合

参考回答:

负载因子默认是0.75, 2^n是为了让散列更加均匀,例如出现极端情况都散列在数组中的一个下标,那么hashmap会由O(1)复杂退化为O(n)的。

● 请你简单介绍一下ArrayList和LinkedList的区别,并说明如果一直在list的尾部添加元素,用哪种方式的效率高?

考点:集合

参考回答:

ArrayList采用数组数组实现的,查找效率比LinkedList高。LinkedList采用双向链表实现的,插入和删除的效率比ArrayList要高。一直在list的尾部添加元素,LinkedList效率要高。

● 如果hashMap的key是一个自定义的类,怎么办?

考点:集合

参考回答:

使用HashMap,如果key是自定义的类,就必须重写hashcode()和equals()。

● 请你解释一下hashMap具体如何实现的?

考点:集合

参考回答:

Hashmap基于数组实现的,通过对key的hashcode & 数组的长度得到在数组中位置,如当前数组有元素,则数组当前元素next指向要插入的元素,这样来解决hash冲突的,形成了拉链式的结构。put时在多线程情况下,会形成环从而导致死循环。数组长度一般是2n,从0开始编号,所以hashcode & (2n-1),(2n-1)每一位都是1,这样会让散列均匀。需要注意的是,HashMap在JDK1.8的版本中引入了红黑树结构做优化,当链表元素个数大于等于8时,链表转换成树结构;若桶中链表元素个数小于等于6时,树结构还原成链表。因为红黑树的平均查找长度是log(n),长度为8的时候,平均查找长度为3,如果继续使用链表,平均查找长度为8/2=4,这才有转换为树的必要。链表长度如果是小于等于6,6/2=3,虽然速度也很快的,但是转化为树结构和生成树的时间并不会太短。还有选择6和8,中间有个差值7可以有效防止链表和树频繁转换。假设一下,如果设计成链表个数超过8则链表转换成树结构,链表个数小于8则树结构转换成链表,如果一个HashMap不停的插入、删除元素,链表个数在8左右徘徊,就会频繁的发生树转链表、链表转树,效率会很低。

● 请你说明一下Map和ConcurrentHashMap的区别?

考点:集合

参考回答:

hashmap是线程不安全的,put时在多线程情况下,会形成环从而导致死循环。CoucurrentHashMap是线程安全的,采用分段锁机制,减少锁的粒度。

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

毕生所求无它,爱与自由而已