JAVA基础之集合篇

36人浏览 / 0人评论
1. ArrayList和LinkedList的区别是什么(面试)?
答案: ①是否保证线程安全: ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全;
② 底层数据结构: Arraylist 底层使用的是Object数组;LinkedList 底层使用的是双向循环链表数据结构;
③ 插入和删除是否受元素位置的影响:  ① ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element))时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储,所以插入,删除元素时间复杂度不受元素位置的影响,都是近似 O(1)而数组为近似 O(n)。
④是否支持快速随机访问:  LinkedList 不支持高效的随机元素访问,而ArrayList 实现了RandmoAccess 接口,所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
⑤内存空间占用:  ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为要存放直接后继和直接前驱以及数据)。
 
2. 什么是 List 接口
答: ①是元素有序并且可以重复的集合,被称为序列,
②List可以精准的控制每个元素的插入位置,或者删除某个位置元素
③List接口的常用子类有ArrayList,LinkedList,Vector(已经过时)
 
3.什么是HashMap(重点)
答案: ①HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,即null  value和null key
②本质为无序散列,Hash算法来决定存储位置.
③HashMap的数据结构和底层实现(面试重点)
 JDk1.8之前的HashMap由数组+链表组成的,即”链表散列”,数组是HashMap的主题,链表则是主要是为了解决哈希冲突而存在的(“拉链法”),如果定位到的数组位置不含链表(entry的next指向null),那么对于查找,添加等操作很快,仅需要一次就能寻找到地址;如果定位到数组包含链表,对于添加操作,其时间复杂度依然为O(1),因为最新的Entry会插入链表头部,急需要简单改变引用链即可,而对于查找操作来讲,此时就需要遍历链表,然后通过key对象的equals方法逐一对比.   
④HashMap不是线程安全的,当迭代其中有其他的线程改变了HashMap中的值将会抛出ConcurrentModifcationException.
关于 HashMap的扩容机制
Threshold(开始扩容的临界点)=Size(HashMap的容量)*Load_Factor(负载因子);】
 
4.什么时候开始扩容?
答:当 HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中元素个数超过16*0.75=12(这个值就是代码中的threshold值,也叫做临界值)的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置。
为什么是 0.75,大量实验得出的结果
如果取 0.5,超过一般就扩容,造成资源的浪费.
如果取 1,到临界值才扩容,会增加哈希碰撞的几率.
 
5.扩容的方法是?
调用 resize方法
 
6.Hashmap 为什么大小是 2 的幂次?
答案:为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。
 
7.HashMap线程安全问题,对应的线程安全Map是什么?
答:①对应的的是ConCurrentHashMap支持高并发的访问和更新,它是线程安全的.
②ConCurrentHashMap在JDK1.8中和HashMap的底层相同都是散列表+红黑树
③通过部分锁定+CAs算法来进行实现线程安全的.
④ConCurrentHashMap的key和Value都不能为null.
 
8. 什么是 CAs 算法 ?
答:Compare and swap是一种有名的无锁算法,当多个线程尝试使用CAS同时更新同一个变量时,只有其中一个线程能更新变量的值,而其他线程都失败,失败的线程并不会被挂起,而是被告知这次竞争中失败,并可以再次尝试.
总结:先比较是否 相等,如果相当则 替换 .

全部评论

i