02Java容器模块面试题

1、Java容器有哪些

Java容器分别为Collection和Map两大类，其下右分为很多子类

2、Collection和Collections有什么区别

Collection是一个集合接口，它提供了对集合对象进行基本操作的通用接口方法，所有集合都是它的子类，比如List、Set

Collections是一个包装类，包含了很多静态方法，不能被实例化，就像工具类

3、List、Set、Map之间的区别

List、Set、Map之间的区别主要体现在两个方面：元素是否有序、是否允许重复元素

4、HashMap与HashTable的区别

HashMap是继承自AbstractMap类，而HashTable继承自Dictionary类。不过它们都桶实现了map,clonaeable,Serializable(可序列化)这三个接口

HashMap的key可以是null;HashMap的key可以是null

线程安全性:HashMap的方法没有使用sychronized关键字修饰；都是非线程安全的；；

​ HashTable的方法都是被synchronized修饰的，是线程安全的

​ 可以使用Collections.synchronized(hashMap)或者使用ConcurrentHashMMap

初始容量大小和每次扩容容量大小的不同:HashTable默认的初始大小为11,之后每次扩充，容量变为原来的2n+1

​ HashMap的默认初始化大小为16,之后每次扩充，容量变为原来的2倍

计算hash值的方法不同:HashTable直接使用对象的hashCode；HashMap是根据对象的地址或者字符串或者数字计算出来的int类型的数值

int hash = key.hashCode(); //HashTable return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//HashMap 12345

5、说说如何决定使用HashMap还是TreeMap

对Key有序遍历选择TreeMap

6、说一下HashMap的实现原理

HashMap基于hash算法实现的，我们通过put(key,value)存储，get(key)来获取。

当传入key，HashMap会根据key.hashCode（）计算出hash值，根据hash值将value保存在bucket里

当计算出的hash值相同时，我们称为hash冲突,HashMap的做法使用链表和红黑树存储想用值的valye

当hash冲突个数少时，使用链表否则使用红黑树

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 123456

7、说一下HashSet的实现原理?

HashSet是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet的实现比较简单，相关HashSet的操作，基本上都是底层直接调用HashMap的相关方法来完成

8、ArrayList和LinkedList的区别是什么?

9、如何实现数组和List之间的转换

数组转List:使用Arrays.asList(array)进行转换

List转换数组:使用List自带的toArray方法

10、ArrayList和Vector的区别是什么

线程安全:Vector使用了synchronized来实现线程同步，是线程安全的，而ArrayList是非线程安全的

性能:ArrayList在性能方面优于Vector

扩容:ArrayList和Vector都会根据实际情况需要动态的调整容量，只不过在Vector扩容每次会增加1倍，而ArrayList只会增加50%

11、Array和ArrayList有喝区别

Array可以存储基本数据类型和对象，ArrayList只能存储对象

Array是指定固定大小的，而ArrayList大小是自动扩展的

Array内置方法没有ArrayList多，比如addAll，removeAll,iteration等方法只有ArrayList有

12、在Queue中poll()和remove()有什么区别//element()和peek()的区别

相同点:都是返回第一个元素，并在队列中删除返回的对象

不同点:如果没有元素remove()会直接抛出NoSuchElementException异常，而poll会返回异常

13、哪些集合是线程安全的?

Vector、HashTable、Stack都是线程安全的，而像HashMap则是线程不安全的；

不过在JDK 1.5以后随着java.util.concurrent并发包的出现，他们也有了自己对应的线程安全类，比如HashMap对应的线程安全类就是ConcurrentHashMap

14、迭代器Iterator是什么??

Iterator接口提供遍历任何Collection的接口；

我们可以从Collection中使用迭代器方法来获取迭代器实例；

迭代器取代了Java集合框架中的Enumeration，迭代器运行调用者在迭代过程中移除元素

15、Iterator和ListIterator有什么区别？

public interface ListIterator<E> extends Iterator<E> {

Iterator可以遍历Set和List集合；而ListIterator只能遍历ListIterator只能单向遍历，而ListIterator可以双向遍历（向前/后遍历)ListIterator从Iterator接口继承，然后添加了一些额外的功能，比如添加一个元素，替换一个元素，获取前面或后面元素的索引位置

16、怎么确保一个集合不被修改，

可以使用Collections.unmodifiableCollection(Collection c)方法来创建一个只读集合，这样改变集合的任何操作都会抛出UnsupportedOperationException异常****

17、怎样确保一个集合成为线程安全的集合

可以使用Collections.synchronizedList(Collection c)方法来创键一个线程安全的集合

18、HashMap原理，内部数据结构?

HashMap的内部存储结构其实是对数组+链表的结合（1.8后加入红黑树，O(n)到O(logn)的时间开销）。

当实例化一个HashMap的时候，系统会创建一个长度为Capacity的Entry数组，这个长度称为容量(Capacity),这个数组可以存放元素的位置我们诚挚为“桶（bucket)"",每个bucket有自己的索引，系统可以根据索引快速的查找bucket中的元素，每个bucket中存储一个元素，即一个Entry对象，但每一个Entry对象可以带有一个引用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一条Entry链

19、讲一下HashMap中的put方法？（如何存储，发生Hash冲突怎么办?)

对key求hash值然后计算下标如果没有哈希碰撞则直接放入槽中如果碰撞以后以链表的形式连接到后面如果链表长度超过阈值（默认阈值为8），就把链表转为红黑树如果节点已存在旧的值，就替换如果槽满了（容量*加载因子），就需要resize

20、HashMap中哈希函数是怎么样实现的？还有哪些hash实现方法?

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

高16bit不变，低16bit和高16位做异或获得hash值，然后(n-1)&hash获得下标

直接地址发：直接以关键字k或者k加上某个常数(k+c)作为hash地址

数字分析法：提取关键字中取值比较均匀的数字作为哈希地址

21、为什么HashMap中的&位必须为奇数（为什么数组容量为2的幂次）？

长度是16或者其他2的幂次，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HasCode后几位的值。只要输入的HashCode本身分布均匀，HASH算法的结果就是均匀的。然后使用(length-1)&hashCde相当于求出余数，比%快，确定在桶中的位置tab[i=(n-1)&hash]&

22、如何解决hash冲突(什么叫hash冲突)

两个key值计算的hash值一样 -----> 发生hash冲突如何解决

Hash冲突：hASHcODE值一样，但key不一样，就导致哦了冲突（如果Key一样，就是相同的值覆盖了）

HashMap的冲突处理是用的是链表地址发，将所有哈希地址相同的记录都连接在同一个链表中（同一个桶的链表中）。

当然：还有其他解决hash冲突的方法，例如：开放地址（外加增量d)、再哈希（hash函数不同）、链地址发、建立公共溢出区

23、HashMap线程并发安全性问题

HashMap在并发时可能常出现的问题主要是两方面?

如果在多线程同时使用put方法添加元素，而假设正好存在两个put的key发生了碰撞，那么根据hashMao的实现，这两个key会添加到数组的同一个位置，这样最终就会发生其中一个线程put的数据被覆盖**

如果多个线程同时检测到元素个数超过数组大小* loadFactor，这样就会发生多个线程同时对Node数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋值给table,也就是说其他线程都会全丢失

如何实现一个并发安全的HashMap?参考ConncurrentHashMap底层原理

25、HashMap的扩容优化,是否会重算hash值?

jdk1.7扩容就是 当size>threesold=length*loadFactor时，将HashmAP的数组扩大两倍，所有元素再次进行Hash放入到新的HashMap中JDK1.8扩容 当位桶中为链表时， 它会将原来的链表同过计算e.hash&oldCap==0分成两条链表,再将两条链表散列到新数组的不同位置上

1.7扩容后会重新计算hash值，这个key值(key%新的长度)在新桶的什么位置，这样就会有大量的重复计算

1.8中进行优化。桶中的链表不需要向JDK1.7中实现的那样重新计算hash值，只需要将原来的hash值新增的那个bithi1还是0.是0的话索引没变，是1的话索引编程元索引+oldCap

jdk1.7扩容代码

//调用resize方法对table进行扩展，扩展策略是乘2 resize(2 * table.length); //resize该方法/// void resize(int newCapacity) { //记录旧的表 Entry[] oldTable = table; //旧的表的长度 int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; //调用transfer方法将原来的键值对移植过来 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; //计算新的阈值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } //这段代码遍历原来的每个键值对，计算新位置，并保存到新位置 //注意对源hAshMap中的每个元素再次进行hash，然后放入x 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; 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; } }

123456789101112131415161718192021222324252627282930313233343536373839404142434445

JDK1.8扩容

final Node<K,V>[] resize() { Node<K, V>[] oldTab = table;//首次初始化后table为Null int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold;//默认构造器的情况下为0 int newCap, newThr = 0; if (oldCap > 0) {//table扩容过 //当前table容量大于最大值得时候返回当前table if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //table的容量乘以2，threshold的值也乘以2 newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold //使用带有初始容量的构造器时，table容量为初始化得到的threshold newCap = oldThr; else{ //默认构造器下进行扩容 // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { //使用带有初始容量的构造器在此处进行扩容 float ft = (float) newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes", "unchecked"}) Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap]; table = newTab; if (oldTab != null) { //对新扩容后的table进行赋值，条件中的代码删减 } return newTab; } /// if (oldTab != null) { //对新扩容后的table进行赋值，条件中的代码删减 //oldCap为原数组的长度 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { //将原数组位置置为空，应该是便于垃圾回收吧 oldTab[j] = null; //如果数组中只存放了一个元素，即不是红黑树 //结构也不是链表结构 if (e.next == null) //直接通过&算法找到数组中的位置 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) //如果是红黑树结构，就调用split ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order //如果数组中存放的是链表，会将原来的链分成两条链表 Node<K,V> loHead =null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; //通过计算e.hash&oldCap==0构造一条链 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } //通过e.hash&oldCap!=0构造另外一条链 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); //遍历结束以后，将tail指针指向null //e.hash&oldCap==0构造而来的链的位置不变 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //e.hash&oldCap!=0构造而来的链的位置在数 //组j+oldCap位置处 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } ———————————————— 版权声明：本文为CSDN博主「alex-zhou96」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/ZHOUJIAN_TANK/article/details/104463188

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105

相关知识

借花献佛！朋友干了5年整的Java面试官，给我分享了一份面试官最爱问的Java面试题
2024年前端框架：第二章：Layui(类UI ) 框架：关于2，2024年最新初级Web前端开发面试题
插花艺术模块二商业插花模块二商业插花（63页）
制造模块论文范文9篇(全文)
光照强度传感器模块
模块式植物墙与布袋式植物墙比较
宿舍智能管理模块DDEb2
【模块式屋顶绿化】
Kubernetes集群管理：农场主女儿的三个容器编排技巧
模块5

网址: 02Java容器模块面试题 https://www.huajiangbk.com/newsview1178999.html

上一篇: 有两只密闭容器A和B，A能保持恒

下一篇: 甲、乙两个圆柱形容器盛有相同深度