JAVA基础之集合篇

Maybe

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同时更新同一个变量时,只有其中一个线程能更新变量的值,而其他线程都失败,失败的线程并不会被挂起,而是被告知这次竞争中失败,并可以再次尝试.
总结:先比较是否相等,如果相当则替换.