Java容器原理+高频面试题
集合概述
Java 集合, 也叫作容器,主要是由两大接口派生而来:一个是 Collection
接口,主要用于存放单一元素;另一个是 Map
接口,主要用于存放键值对。对于Collection
接口,下面又有三个主要的子接口:List
、Set
和 Queue
。
Java 集合框架如下图所示:
Collection接口
单列集合,用来存储一个一个的对象
List
接口:存储有序的、可重复的数据。 (对付顺序的好帮手)ArrayList:线程不安全,效率高;底层采用Object[] 数组存储
LinkedList:对于频繁的插入删除操作,使用此类效率比ArrayList效率高底层采用双向链表存储 (JDK1.6 之前为循环链表,JDK1.7 取消了循环)
Vector:作为List的古老实现类,线程安全,效率低;底层采用Object[]数组存储
Set
接口:存储无序的、不可重复的数据 –>(注重独一无二的性质)HashSet:作为Set接口主要实现类;线程不安全;可以存null值
- LinkedHashSet:作为HashSet的子类;遍历其内部数据时,可以按照添加顺序遍历;对于频繁的遍历操作,LinkedHashSet效率高于HashSet.
TreeSet:可以按照添加对象的指定属性,进行排序。
Queue
接口: 按特定的排队规则来确定先后顺序,存储的元素是有序的、可重复的。(实现排队功能的叫号机)PriorityQueue:
Object[]
数组来实现二叉堆ArrayQueue
: Object[]
数组 + 双指针
Map接口
双列数据,存储key-value对的数据
HashMap:作为Map的主要实现类;线程不安全的,效率高;存储null的key和value
- LinkedHashMap:保证在遍历map元素时,可以照添加的顺序实现遍历。
原因:在原的HashMap底层结构基础上,添加了一对指针,指向前一个和后一个元素。
对于频繁的遍历操作,此类执行效率高于HashMap。
- LinkedHashMap:保证在遍历map元素时,可以照添加的顺序实现遍历。
TreeMap:保证照添加的key-value对进行排序,实现排序遍历。此时考虑key的自然排序或定制排序底层使用红黑树
Hashtable:作为古老的实现类;线程安全的,效率低;不能存储null的key和value
- Properties:常用来处理配置文件。key和value都是String类型
List接口
List通用方法
- 增:
add(Object obj)
- 删:
remove(int index)
/remove(Object obj)
- 改:
set(int index, Object ele)
- 查:
get(int index)
- 插:
add(int index, Object ele)
- 长度:
size()
- 遍历: ① Iterator迭代器方式 ② foreach(增强for循环) ③ 普通的循环
Arraylist
- ArrayList是List接口的典型实现类、主要实现类
- 本质上,ArrayList是对象引用的一个”变长”数组
- Array Listi的JDK 1.8之前与之后的实现区别?
- JDK 1.7:ArrayList像饿汉式,直接创建一个初始容量为10的数组
- JDK 1.8:ArrayList像懒汉式,一开始创建一个长度为0的数组,当添加第一个元素时再创建一个始容量为10的数组
Arrays.asList(...)
方法返回的List集合,既不是 ArrayList实例,也不是Vector实例。Arrays.asList(...)
返回值是一个固定长度的List集合
扩容策略:
JDK7.0情况下:
首先创建一个长度为10的Object[]数组elementData
添加数据
如果此次的添加导致底层elementData数组容量不够,则扩容。
默认情况下,扩容为原来的容量的1.5倍,同时需要将原有数组中的数据复制到新的数组中。
JDK 8.0中ArrayList的变化:
底层Object[] elementData初始化为{}.并没创建长度为10的数组
第一次调用add()时,底层才创建了长度10的数组,并将数据添加到elementData
后续的添加和扩容操作与JDK 7.0 无异。
结论:
JDK 7.0中的ArrayList的对象的创建类似于单例的饿汉式,而JDK 8.0中的ArrayList的对象的创建类似于单例的懒汉式,延迟了数组的创建,节省内存。
建议开发中使用带参的构造器:
ArrayList list = new ArrayList(int capacity)
避免出现扩容。
Linklist
新增方法:实际上是Deque接口提供的
void addFirst(Object obj)
void addLast(Object obj)
Object getFirst()
Object getlast)()
Object removeFirst()
Object removeLast()
最好不要用
我们在项目中一般是不会使用到
LinkedList
的,需要用到LinkedList
的场景几乎都可以使用ArrayList
来代替,并且,性能通常会更好!就连LinkedList
的作者约书亚 · 布洛克(Josh Bloch)自己都说从来不会使用LinkedList
。
最好不要用,空间占用太大!
另外,不要下意识地认为
LinkedList
作为链表就最适合元素增删的场景。我在上面也说了,LinkedList
仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1),其他情况增删元素的时间复杂度都是 O(n) 。
最好不要用,没有比arraylist快多少
Vector
几乎与Arraylist相同,唯一的区别在于Vector是同步类(synchronized)、
开销就比 ArrayList要大,访问要慢。
Vector每次扩容请求其大小的2倍空间,而ArrayList是1.5倍。
Vector还有一个子类Stack.
Set接口
特点:
Set接口是Collection的子接口,set接口没有提供额外的方法
存放无序的、不可重复的元素
无序性:不等于随机性。存储的数据在底层数组中并非照数组索引的顺序添加,而是根据数据的哈希值决定的。
不可重复性:保证添加的元素照equals()判断时,不能返回true.即:相同的元素只能添加一个。
元素是如何添加的?(以HashSet为例)
我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法,计算元素a的哈希值,此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置(即为:索引位置),判断数组此位置上是否已经有元素:
- 如果此位置上没有其他元素,则元素a添加成功。 —>情况1
- 如果此位置上有其他元素b(或以链表形式存在的多个元素),则比较元素a与元素b的hash值:
- 如果hash值不相同,则元素a添加成功。**—>情况2**
- 如果hash值相同,进而需要调用元素a所在类的equals()方法:
- equals()返回true,元素a添加失败
- equals()返回false,则元素a添加成功。**—>情况3**
对于添加成功的情况2和情况3而言:元素a 与已经存在指定索引位置上数据以链表的方式存储。
JDK 7.0 :元素a放到数组中,指向原来的元素。
JDK 8.0 :原来的元素在数组中,指向元素a
总结:七上八下
HashSet底层:数组+链表的结构。(JDK 7.0以前)
涉及到的常用方法
重写hashCode()方法
在程序运行时,同一个对象多次调用
hashCode()
方法应该返回相同的值。当两个对象的
equals()
方法比较返回true时,这两个对象的hashCode()
方法的返回值也应相等。对象中用作
equals()
方法比较的Field,都应该用来计算hashCode值。
理解:要让对象中所有元素尽可能地参与hashcode的计算,减少碰撞
重写
equals()
方法以自定义的 Customer类为例,何时需要重写
equals()
?当一个类有自己特有的“逻辑相等”概念,当改写equals()的时候,总是要改写
hash Code()
,根据一个类的 equals方法(改写后),两个截然不同的实例有可能在逻辑上是相等的,但是,根据Object.hashCode()
方法,它们仅仅是两个对象。因此,违反了相等的对象必须具有相等的散列码.
结论:复写equals方法的时候一般都需要同时复写 hashCode 方法。通常参与计算 hashCode的对象的属性也应该参与到
equals()
中进行计算。
Eclipse/IDEA工具里hashCode()重写
以Eclipse/DEA为例,在自定义类中可以调用工具自动重写 equals()
和 hashCode()
问题:为什么用 Eclipse/IDEA复写 hash Code方法,有31这个数字?
选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大,所谓的“冲突”就越少,查找起来效率也会提高。(减少冲突)
并且31只占用5bits,相乘造成数据溢出的概率较小。
31可以由i*31==(<<5)-1来表示,现在很多虚拟机里面都有做相关优化。(提高算法效率)
31是一个素数,素数作用就是如果我用一个数字来乘以这个素数,那么最终出来的结果只能被素数本身和被乘数还有1来整除!(减少冲突)
示例:
|
HashSet
- Hashset是Set接口的典型实现,大多数时候使用Set集合时都使用这个实现类。
- HashSet按Hash算法来存储集合中的元素,因此具有很好的存取、查找、删除性能。
- HashSet具有以下特点:
- 不能保证元素的排列顺序
- HashSet不是线程安全的
- 集合元素可以是nul
- 对于存放在Set容器中的对象,对应的类一定要重写equals()和hashCode(Object obj)方法,以实现对象相等规则。即:“相等的对象必须具有相等的散列码”
LinkHashSet
LinkedhashSet是HashSet的子类
LinkedhashSet根据元素的hashCode值来决定元素的存储位置但它同时使用双向链表维护元素的次序,这使得元素看起来是以插入顺序保存的。
LinkedhashSet插入性能略低于HashSet,但在迭代访问Set里的全部元素时有很好的性能。
LinkedhashSet不允许集合元素重复。
TreeSet
Treeset是SortedSet接口的实现类,TreeSet可以确保集合元素处于排序状态。
TreeSet底层使用红黑树结构存储数据
新增的方法如下:(了解)
Comparator comparator()
Object first()
Object last()
Object lower(object e)
Object higher(object e)
SortedSet subSet(fromElement, toElement)
SortedSet headSet(toElement)
SortedSet tailSet(fromElement)
TreeSet两种排序方法:自然排序和定制排序。默认情况下,TreeSet采用自然排序
红黑树的特点:有序,查询效率比List快
详细介绍:www.cnblogs.com/LiaHon/p/11…
排序的使用说明
comparable 和 Comparator 的区别
comparable
接口实际上是出自java.lang
包 它有一个compareTo(Object obj)
方法用来排序comparator
接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)
方法用来排序
方式一:自然排序->comparable
自然排序:TreeSet会调用集合元素的
compareTo(object obj)
方法来比较元素之间的大小关系,然后将集合元素按升序(默认情况)排列如果试图把一个对象添加到Treeset时,则该对象的类必须实现Comparable接口。
- 实现Comparable的类必须实现
compareTo(Object obj)
方法,两个对象即通过compareTo(Object obj)
方法的返回值来比较大小
- 实现Comparable的类必须实现
Comparable的典型实现:
BigDecimal、BigInteger以及所有的数值型对应的包装类:按它们对应的数值大小进行比较
Character:按字符的unic!ode值来进行比较
Boolean:true对应的包装类实例大于fase对应的包装类实例
String:按字符串中字符的unicode值进行比较
Date、Time:后边的时间、日期比前面的时间、日期大
向TreeSet中添加元素时,只有第一个元素无须比较
compareTo()
方法,后面添加的所有元素都会调用compareTo()
方法进行比较。因为只有相同类的两个实例才会比较大小,所以向 TreeSet中添加的应该是同一个类的对象。 对于TreeSet集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过
compareTo(Object obj)
方法比较返回值。当需要把一个对象放入TreeSet中,重写该对象对应的equals()方法时,应保证该方法与
compareTo(Object obj)
方法有一致的结果:如果两个对象通过equals()方法比较返回true,则通过compareTo(object ob)
方法比较应返回0。否则,让人难以理解。
|
方式二:定制排序->Comparator
TreeSet的自然排序要求元素所属的类实现Comparable接口,如果元素所属的类没有实现 Comparable接口,或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序,则考虑使用定制排序。定制排序,通过 Comparator接口来实现。需要重写 compare(T o1,T o2)方法。
利用
int compare(T o1,T o2)
方法,比较o1和o2的大小:如果方法返回正整数,则表示o1大于o2;如果返回0,表示相等;返回负整数,表示o1小于o2。要实现定制排序,需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。
此时,仍然只能向Treeset中添加类型相同的对象。否则发生
ClassCastException
异常使用定制排序判断两个元素相等的标准是:通过 Comparator比较两个元素返回了0
|
比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同
HashSet
、LinkedHashSet
和TreeSet
都是Set
接口的实现类,都能保证元素唯一,并且都不是线程安全的。HashSet
、LinkedHashSet
和TreeSet
的主要区别在于底层数据结构不同。HashSet
的底层数据结构是哈希表(基于HashMap
实现)。LinkedHashSet
的底层数据结构是链表和哈希表,元素的插入和取出顺序满足 FIFO。TreeSet
底层数据结构是红黑树,元素是有序的,排序的方式有自然排序和定制排序。- 底层数据结构不同又导致这三者的应用场景不同。
HashSet
用于不需要保证元素插入和取出顺序的场景,LinkedHashSet
用于保证元素的插入和取出顺序满足 FIFO 的场景,TreeSet
用于支持对元素自定义排序规则的场景。
Queue接口
LinkedList类实现了Queue接口,因此我们可以把LinkedList当成Queue来用。
Queue 与Deque的区别
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()
等其他方法,可用于模拟栈。
Map接口
- Map与Collection并列存在。用于保存具有映射关系的数据:key-value
- Map中的key和value都可以是任何引用类型的数据
- Map中的key用set来存放,不允许重复,即同一个Map对象所对应的类,须重写
hashCode()
和equals()
方法 - 常用 String类作为Map的“键”
- key和value之间存在单向一对一关系,即通过指定的key总能找到唯一的、确定的value
- Map接口的常用实现类:HashMap、TreeMap、LinkedHashMap和Properties。其中,HashMap是Map接口使用频率最高的实现类
常用方法
- 添加:
put(Object key,Object value)
- 删除:
remove(Object key)
- 修改:
put(Object key,Object value)
- 查询:
get(Object key)
- 长度:
size()
- 遍历:
keySet()
/values()
/entrySet()
HashMap
HashMap是Map接口使用频率最高的实现类。
允许使用null键和null值,与 HashSet一样,不保证映射的顺序。
所有的key构成的集合是set:无序的、不可重复的。所以,key所在的类要重写equals()和 hashCode()
所有的value构成的集合是Collection:无序的、可以重复的。所以,value所在的类要重写:equals()
一个key-value构成一个entry
所有的entry构成的集合是Set:无序的、不可重复的
HashMap判断两个key相等的标准是:两个key通过
equals()
方法返回true,hashCode值也相等。HashMap判断两个value相等的标准是:两个value通过
equals()
方法返回true.
LinkedHashMap
- LinkedHashMap底层使用的结构与HashMap相同,因为LinkedHashMap继承于HashMap.
- 区别就在于:LinkedHashMap内部提供了Entry,替换HashMap中的Node.
- 与Linkedhash Set类似,LinkedHashMap可以维护Map的迭代顺序:迭代顺序与Key-value对的插入顺序一致
Hashtable
(基本被淘汰,不要使用它!)
并发状态下使用ConcurrentHashMap!!
Hashtable是个古老的Map实现类,JDK1.0就提供了。不同于 HashMap,Hashtable是线程安全的.
Hashtable实现原理和HashMap相同,功能相同。底层都使用哈希表结构,查询速度快,很多情况下可以互用
与HashMap.不同,Hashtable不允许使用null作为key和value.
与HashMap一样,Hashtable也不能保证其中Key-value对的顺序.
Hashtable判断两个key相等、两个value相等的标准,与HashMap-致.
Properties
加载xml用
Properties类是Hashtable的子类,该对象用于处理属性文件
由于属性文件里的key、value都是字符串类型,所以Properties里的key和value都是字符串类型
存取数据时,建议使用
setProperty(String key,String value)
方法和getProperty(String key)
方法
存储结构的理解
- Map中的key:无序的、不可重复的,使用Set存储所的key —> key所在的类要重写equals()和hashCode() (以HashMap为例)
- Map中的value:无序的、可重复的,使用Collection存储所的value —>value所在的类要重写equals()
- 一个键值对:key-value构成了一个Entry对象。
- Map中的entry:无序的、不可重复的,使用Set存储所有的entry
内存结构的理解(难点)
JDK 7.0及以前的版本:HashMap是数组+链表结构(地址链表法)(拉链法)
JDK 8.0版本以后:HashMap是数组+链表+红黑树实现
HashMap实现原理
JDK1.8之前
- 创建与添加
HashMap map = new HashMap()
:
在实例化以后,底层创建了长度是16的一维数组 Entry[] table
。
…可能已经执行过多次put…
map.put(key1,value1)
:
- 首先,调用key1所在类的
hashCode()
计算key1哈希值,此哈希值经过(n - 1) & hash
计算以后,得到在Entry数组中的存放位置。 - 如果此位置上的数据为空,此时的key1-value1添加成功。 —-情况1
- 如果此位置上的数据不为空,(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据的哈希值:
- 如果key1的哈希值与已经存在的数据的哈希值都不相同,此时key1-value1添加成功。—-情况2
- 如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同,继续比较:调用key1所在类的equals(key2)方法,比较:
- 如果
equals()
返回false:此时key1-value1添加成功。—-情况3 - 如果
equals()
返回true:使用value1替换value2。
- 如果
补充:关于情况2和情况3:此时key1-value1和原来的数据以链表的方式存储。
在不断的添加过程中,会涉及到扩容问题,当超出临界值(且要存放的位置非空)时,扩容。默认的扩容方式:扩容为原来容量的2倍,并将原有的数据复制过来。
- HashMap的扩容
当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对 HashMap的数组进行扩容,而在HashMap数组扩容之后,原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是 resize。
- 扩容时机
当HashMap中的元素个数超过数组大小(数组总大小 length,不是数组中个数)* loadFactor时,就会进行数组扩容,loadFactor的默认值(DEFAULT_LOAD_ FACTOR
)为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小(DEFAULT INITIAL CAPACITY
)为16,那么当 HashMap中元素个数超过16 * 0.75=12(这个值就是代码中的 threshold值,也叫做临界值)的时候,就把数组的大小扩展为2 * 16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知 HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。
JDK1.8
相比于之前的版本, JDK1.8 之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。
HashMap散列算法是如何设计的
为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。我们上面也讲到了过了,Hash 值的范围值-2147483648 到 2147483647,前后加起来大概 40 亿的映射空间,只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组,内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash
”。(n 代表数组长度)。这也就解释了 HashMap 的长度为什么是 2 的幂次方。
为什么是(n - 1) & hash????
“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方;)。” 并且 采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是 2 的幂次方。
Collections工具类
Collections 工具类常用方法:
- 排序
- 查找,替换操作
- 同步控制(不推荐,需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)
排序操作
void reverse(List list)//反转 |
查找,替换操作
int binarySearch(List list, Object key)//对List进行二分查找,返回索引,注意List必须是有序的 |
同步控制
不建议使用
最好不要用下面这些方法,效率非常低,需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。
/*
省略
*//
面试题相关
- HashMap的底层实现原理?
- HashMap 和 Hashtable的异同?
- CurrentHashMap 与 Hashtable的异同?
- 负载因子值的大小,对HashMap的影响?
- 负载因子的大小决定了HashMap的数据密度。
- 负载因子越大密度越大,发生碰撞的几率越高,数组中的链表越容易长,造成査询或插入时的比较次数增多,性能会下降
- 负载因子越小,就越容易触发扩容,数据密度也越小,意味着发生碰撞的几率越小,数组中的链表也就越短,查询和插入时比较的次数也越小,性能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能,建议初始化预设大一点的空间
- 按照其他语言的参考及研究经验,会考虑将负载因子设置为0.7~0.75,此时平均检索长度接近于常数。
总结自