HashMap 1.7基于数组+链表实现,1.8基于数组+链表+红黑树。链表则是主要为了解决哈希冲突
而存在的(“拉链法”解决冲突)。JDK1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于
阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先
进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。
HashTable 和 HashMap 类似,但它是线程安全的,这意味着同一时刻多个线程可以同时写入
HashTable 并且不会导致数据不一致。它是遗留类,不应该去使用它。(现在可以使用
ConcurrentHashMap 来支持线程安全,并且 ConcurrentHashMap 的效率会更高(1.7
ConcurrentHashMap 引入了分段锁, 1.8 引入了红黑树)。)
LinkedHashMap 继承自 HashMap。使用双向链表来维护元素的顺序,顺序为插入顺序或者最近
最少使用(LRU)顺序。
2.详细说说 Arraylist 和 LinkedList的区别?
ArrayList :底层是基于数组实现的,查找快,增删较慢。LinkedList 不支持高效的随机元素访
问,而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int
index)方法)。
LinkedList :底层是基于链表实现的。确切的说是循环双向链表(JDK1.6之前是双向循环链表、
JDK1.7之后取消了循环),查找慢、增删快。LinkedList链表由一系列表项连接而成,一个表项包
含3个部分︰元素内容、前驱表和后驱表。因此内存空间占用比ArrayList 更多。
面试官追问:ArrayList的增删一定比LinkedList要慢吗?
答:
不一定的
1. 如果增删都是在末尾来操作(每次调用的都是 remove() 和 add() ),此时 ArrayList就不需要
移动和复制数组来进行操作了。如果数据量有百万级的时,速度是会比 LinkedList 要快的。
2. 如果删除操作的位置是在中间。由于LinkedList的消耗主要是在遍历上,ArrayList的消耗主要是在
移动和复制上(底层调用的是 arrayCopy() 方法,是native方法)。LinkedList 的遍历速度是要慢于
ArrayList的复制移动速度的。如果数据量有百万级的时,还是ArrayList要快。
3.ArrayList实现 RandomAccess接口有何作用?
查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。
从源码可以看出RandomAccess 接口只是一个标志接口,只要List集合实现这个接口,就能支持快速随
机访问。通过查看 Collections 类中的 binarySearch() 方法,可以看出,判断List是否实现
RandomAccess接口来实行 indexedBinarySerach(list, key) 或 iteratorBinarySerach(list,
key) 方法。再通过查看这两个方法的源码发现:实现RandomAccess接口的List集合采用一般的 for
循环遍历,而未实现这接口则采用迭代器,即ArrayList 一般采用for循环遍历,而 LinkedList 一般采用
迭代器遍历: