Java面试题总结-Day4
Table of Contents
- 1. ArrayList和LinkedList区别
- 1.1. 是否线程安全
- 1.2. 底层数据结构
- 1.3. 插入和删除是否受元素位置的影响
- 1.4. 是否支持快速随机访问
- 1.5. 内存空间占用
- 2. ArrayList和Vector的区别
- 3. HashMap的底层实现
- 3.1. JDK1.8之前的实现方法
- 3.2. JDK1.8以后的实现方法
- 4. HashMap和HashTable的区别
- 4.1. 是否线程安全
- 4.2. 效率
- 4.3. 对Null key和Null value的支持
- 4.4. 初始容量大小和每次扩容大小的不同
- 4.5. HashMap的长度为什么是2的幂次方
- 4.5.1. 该算法的设计
1 ArrayList和LinkedList区别
1.1 是否线程安全
- ArrayList和LinkedList都是不同步的,也就是不保证线程安全.
1.2 底层数据结构
- ArrayList底层使用的是Object数组.
- LinkedList底层使用的是双向循环链表数据结构.
1.3 插入和删除是否受元素位置的影响
- ArrayList采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响.
- 执行
add(E e)方法的时候,ArrayList会默认在将指定的元素追加到此列表的末尾,这种情况下时间复杂度就是 \(O(1)\) - 如果要在指定位置i插入和删除元素的话
add(intindex, E element),时间复杂度就是 \(O(n-i)\).因为在进行上述操作时候集合中第i和第i个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作.
- 执行
- LinkedList采用链表存储,所以插入,删除元素时间复杂度不受元素位置的影响,都是近似 \(O(1)\) ,而数组近似为 \(O(n)\)
1.4 是否支持快速随机访问
- 快速随机访问就是通过元素的序号快速获得元素对象(对应于
get(intIndex)方法) - LinkeList不支持高效的随机元素访问,而ArrayList实现了RandomAccess接口,所以有随机访问的能力.
1.5 内存空间占用
- ArrayList的空间浪费主要体现在list列表的结尾会预留一定的容量空间.
- LinkedList的空间话费则体现在它每一个元素都需要消耗比ArrayList更多的空间(因为要存放直接后继和直接前驱以及数据).
2 ArrayList和Vector的区别
- Vector类的所有方法都是同步的.可以由两个线程安全地访问同一个Vector对象,但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间.
- ArrayList不是同步的,在不需要保证线程安全时建议使用ArrayList
3 HashMap的底层实现
3.1 JDK1.8之前的实现方法
- JDK1.8之前HashMap由
数组+链表组成的("链表散列"即数组和链表的组合体). - 数组是HashMap的主体,链表则是为了解决哈希冲突而存在的.(HashMap采用拉链法"链地址法"解决冲突)
- 如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找,添加等操作很快,仅需一次寻址即可.
- 如果定位的数组包含链表,对于添加操作,其时间复杂度依然为 \(O(1)\) ,因为最新的Entry会插入链表头部,即需要简单改变引用链即可以.
- 对于查找操作来讲,就需要遍历链表,然后通过key对象equals方法逐一对比查找.
3.2 JDK1.8以后的实现方法
- JDK1.8之后在解决哈希冲突时有了较大的变化,当链表长度大于阀值(默认是8)时,将链表转化为红黑树,以减少搜索时间.
- TreeMap,TreeSet以及JDK1.8知乎的HashMap底层都用了红黑树.红黑树就是为了接二觉二叉查找树的缺陷,因为二叉查找树在某些情况下会退化为一个线性结构
4 HashMap和HashTable的区别
4.1 是否线程安全
- HashMap是非线程安全的.
- HashTable是线程安全的.
4.2 效率
- 因为线程安全的问题,HashMap要比HashTable效率高一些.
- 另外,HashTable基本被淘汰,不要在代码中使用它.
4.3 对Null key和Null value的支持
- HashMap中,null可以作为键,这样的键只有一个,可以由一个或多个键所对应的值为null.
- HashTable中put进的键值只要有一个null,直接抛出NullPointeerException.
4.4 初始容量大小和每次扩容大小的不同
- 创建时不指定初值,HashTable默认的初始大小为11,之后每次扩充,容量会变为原来的2n+1.
- HashMap默认的初始大小为16.之后每次扩充,容量变为原来的2倍.
- 创建时候如果给定了容量初始值,那么HashTable会直接使用你给定的大小,而HashMap会将其扩充为2的幂次方大小.
4.5 HashMap的长度为什么是2的幂次方
- 为了能让HashMap存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同.这个实现就是把数据存到哪个链表/红黑树中的算法.
4.5.1 该算法的设计
- 位运算操作比取余操作更快.
- 取余操作中如果除数是2的幂次则等价于其除数-1的与操作,也就是说 \(hash % length == hash & (length - 1)\) 的前提是length是2的n次方.
- 所以HashMap的长度是2的幂次方.
Date: 2018-11-03 09:42
Created: 2018-11-03 六 09:42
Validate
