List
(对付顺序的好帮手): 存储的元素是有序的、可重复的。Set
(注重独一无二的性质): 存储的元素不可重复的。Queue
(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序,存储的元素是有序的、可重复的。Map
(用 key 来搜索的专家): 使用键值对(key-value)存储,类似于数学上的函数 y=f(x),"x" 代表 key,"y" 代表 value,key 是无序的、不可重复的,value 是无序的、可重复的,每个键最多映射到一个值。RandomAccess
是一个标记接口,用来表明实现该接口的类支持随机访问(即可以通过索引快速访问元素)。由于 LinkedList
底层数据结构是链表
ArrayList
和 LinkedList
都是不同步的,也就是不保证线程安全;ArrayList
底层使用的是 Object
数组;LinkedList
底层使用的是 双向链表 数据结构(JDK1.6 之前为循环链表)ArrayList
采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e)
方法的时候, ArrayList
会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element)
),时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。LinkedList
采用链表存储,所以在头尾插入或者删除元素不受元素位置的影响(add(E e)
、addFirst(E e)
、addLast(E e)
、removeFirst()
、 removeLast()
),时间复杂度为 O(1),如果是要在指定位置 i
插入和删除元素的话(add(int index, E element)
,remove(Object o)
,remove(int index)
), 时间复杂度为 O(n) ,因为需要先移动到指定位置再插入和删除。LinkedList
不支持高效的随机元素访问,而 ArrayList
(实现了 RandomAccess
接口) 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)
方法)。ArrayList
的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。我们在项目中一般是不会使用到 LinkedList
的,需要用到 LinkedList
的场景几乎都可以使用 ArrayList
来代替,并且,性能通常会更好!就连 LinkedList
的作者约书亚 · 布洛克(Josh Bloch)自己都说从来不会使用 LinkedList
。
双向链表: 包含两个指针,一个 prev 指向前一个节点,一个 next 指向后一个节点。
双向循环链表: 最后一个节点的 next 指向 head,而 head 的 prev 指向最后一个节点,构成一个环。
public interface RandomAccess {
}
查看源码我们发现实际上 RandomAccess
接口中什么都没有定义。所以,在我看来 RandomAccess
接口不过是一个标识罢了。标识什么? 标识实现这个接口的类具有随机访问功能。
在 binarySearch()
方法中,它要判断传入的 list 是否 RandomAccess
的实例,如果是,调用indexedBinarySearch()
方法,如果不是,那么调用iteratorBinarySearch()
方法
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
ArrayList
实现了 RandomAccess
接口, 而 LinkedList
没有实现。为什么呢?我觉得还是和底层数据结构有关!ArrayList
底层是数组,而 LinkedList
底层是链表。数组天然支持随机访问,时间复杂度为 O(1),所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素,时间复杂度为 O(n),所以不支持快速随机访问。ArrayList
实现了 RandomAccess
接口,就表明了他具有快速随机访问功能。 RandomAccess
接口只是标识,并不是说 ArrayList
实现 RandomAccess
接口才具有快速随机访问功能的!
Comparable 和 Comparator 的区别Comparable 接口和 Comparator 接口都是 Java 中用于排序的接口,它们在实现类对象之间比较大小、排序等方面发挥了重要作用:Comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序Comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序
无序性不等于随机性 ,无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ,而是根据数据的哈希值决定的。
不可重复的数据结构:这意味着数据结构中的元素不允许重复。例如,Java中的Set接口及其实现类(如HashSet、TreeSet等)就是不允许包含重复元素的集合,如果试图向这些集合中添加已经存在的元素,则添加操作将被忽略。
HashSet
、LinkedHashSet
和 TreeSet
都是 Set
接口的实现类,都能保证元素唯一,并且都不是线程安全的。HashSet
、LinkedHashSet
和 TreeSet
的主要区别在于底层数据结构不同。HashSet
的底层数据结构是哈希表(基于 HashMap
实现)。LinkedHashSet
的底层数据结构是链表和哈希表,元素的插入和取出顺序满足 FIFO。TreeSet
底层数据结构是红黑树,元素是有序的,排序的方式有自然排序和定制排序。HashSet
用于不需要保证元素插入和取出顺序的场景,LinkedHashSet
用于保证元素的插入和取出顺序满足FIFO
的场景,TreeSet
用于支持对元素自定义排序规则的场景。Queue
是单端队列,只能从一端插入元素,另一端删除元素,实现上一般遵循 先进先出(FIFO) 规则。
Queue
扩展了 Collection
的接口,根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常,另一种则会返回特殊值。
Queue 接口 |
抛出异常 | 返回特殊值 |
---|---|---|
插入队尾 | add(E e) | offer(E e) |
删除队首 | remove() | poll() |
查询队首元素 | element() | peek() |
Deque
是双端队列,在队列的两端均可以插入或删除元素。
Deque
扩展了 Queue
的接口, 增加了在队首和队尾进行插入和删除的方法,同样根据失败后处理方式的不同分为两类:
Deque 接口 |
抛出异常 | 返回特殊值 |
---|---|---|
插入队首 | addFirst(E e) | offerFirst(E e) |
插入队尾 | addLast(E e) | offerLast(E e) |
删除队首 | removeFirst() | pollFirst() |
删除队尾 | removeLast() | pollLast() |
查询队首元素 | getFirst() | peekFirst() |
查询队尾元素 | getLast() | peekLast() |
事实上,Deque
还提供有 push()
和 pop()
等其他方法,可用于模拟栈。
ArrayDeque
和 LinkedList
都实现了 Deque
接口,两者都具有队列的功能,但两者有什么区别呢?
ArrayDeque
是基于可变长的数组和双指针来实现,而 LinkedList
则通过链表来实现。
ArrayDeque
不支持存储 NULL
数据,但 LinkedList
支持。
ArrayDeque
是在 JDK1.6 才被引入的,而LinkedList
早在 JDK1.2 时就已经存在。
ArrayDeque
插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList
不需要扩容,但是每次插入数据时均需要申请新的堆空间,均摊性能相比更慢。
从性能的角度上,选用 ArrayDeque
来实现队列要比 LinkedList
更好。此外,ArrayDeque
也可以用于实现栈。
PriorityQueue
是在 JDK1.5 中被引入的, 其与 Queue
的区别在于元素出队顺序是与优先级相关的,即总是优先级最高的元素先出队。
这里列举其相关的一些要点:
PriorityQueue
利用了二叉堆的数据结构来实现的,底层使用可变长的数组来存储数据PriorityQueue
通过堆元素的上浮和下沉,实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。PriorityQueue
是非线程安全的,且不支持存储 NULL
和 non-comparable
的对象。PriorityQueue
默认是小顶堆,但可以接收一个 Comparator
作为构造参数,从而来自定义元素优先级的先后。PriorityQueue
在面试中可能更多的会出现在手撕算法的时候,典型例题包括堆排序、求第 K 大的数、带权图的遍历等,所以需要会熟练使用才行。
BlockingQueue
(阻塞队列)是一个接口,继承自 Queue
。BlockingQueue
阻塞的原因是其支持当队列没有元素时一直阻塞,直到有元素;还支持如果队列已满,一直等到队列可以放入新元素时再放入。
BlockingQueue
常用于生产者-消费者模型中,生产者线程会向队列中添加数据,而消费者线程会从队列中取出数据进行处理。
HashMap
是非线程安全的,Hashtable
是线程安全的,因为 Hashtable
内部的方法基本都经过synchronized
修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap
吧!);HashMap
要比 Hashtable
效率高一点。另外,Hashtable
基本被淘汰,不要在代码中使用它;HashMap
可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个;Hashtable 不允许有 null 键和 null 值,否则会抛出 NullPointerException
。Hashtable
默认的初始大小为 11,之后每次扩充,容量变为原来的 2n+1。HashMap
默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。Hashtable
会直接使用你给定的大小,而 HashMap
会将其扩充为 2 的幂次方大小(HashMap
中的tableSizeFor()
方法保证,下面给出了源代码)。也就是说 HashMap
总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。HashMap
在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)时,并且数组的长度大于 64的时候,会将链表转化为红黑树.......
Java 中的 length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性. Java 中的 length() 方法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个方法. Java 中的 size() 方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!hugeCapacity() 方法
LinkedList 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1),其他情况增删元素的平均时间复杂度都是 O(n)
RandomAccess
是一个标记接口,用来表明实现该接口的类支持随机访问(即可以通过索引快速访问元素)。由于 LinkedList
底层数据结构是链表,内存地址不连续,只能通过指针来定位,不支持随机快速访问,所以不能实现 RandomAccess
接口。
是非线程安全的。
可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个
底层是 数组和链表 数组 (链表->红黑树)
JDK1.8 之前 HashMap 由 数组+链表 组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于等于阈值(默认为 8)并且数组的长度大于 64 会将链表转化为红黑树,以减少搜索时间。