首页>Java>正文

关于Java集合中一些常考的重点知识点总结

时间:2019-02-27 11:41:49   来源: 帅地 苦逼的码农   阅读:

1、集合

Java的集合框架中可以分为两大类:第一类是按照单个元素存储的 Collection 集合,其中 Set, List, Queue 都实现了 Collection 接口。第二类是按照 Key-Value 存储的 Map 集合。
 

2、List

List常量的两个子类分别是 ArrayList 和 LinkedList 这两个集合。

(1)、ArrayList 的特点

A. ArrayList 底层数据结构是数组,数组的特点就是可以快速随机访问,直接根据下标定位,缺点是插入和删除速度比较慢,需要移动元素。

B. ArrayList 每次扩容之后的大小为之前的 1.5 倍。默认初始容量大小为 10。
 

(2)、LinkedList 的特点

LinkedList 底层数据结构是双向链表,链表的特点就是随机访问速度慢,必须一个一个遍历,不能直接通过下标定位,不过在插入、删除方面速度就比较快。不过由于链表是内存分配不要求连续,内存的利用率比较高。

LinkedList 还实现了另外一个接口Deque,即 double-ended queue,使得 LinkedList 同时具有队列和栈的特性。
 

(3)、vector 的特点

vector 和 ArrayList 基本一样,不过 Vector 是线程安全的,而 ArrayList 是线程不安全的,

ArrayList 和 LinkedList 都是线程不安全的集合。

 

3、Map

Map 是一种 key-value 的集合,其常用的集合实现类有 HashMap, HashTable, TreeMap。

(1)、HashMap(重重点)

HashMap 的底层数据结构是 链表 + 数组,如果对他的底层结构不大懂的可以看上海尚学堂之前的文章:【上海Java培训】Java集合框架之HashMap
【上海Java培训】HashMap的工作原理
Java中最常用的集合类框架之 HashMap


HashMap 在进行 put 操作时,允许 key 和 value 为 null,且是线程不安全的,所以 HashMap 的性能非常好,只不过在多线程的环境下使用,需要给他加上对应的锁。
 

重点数据:HashMap 的默认容量为 capacity = 16, 默认扩容因子 loadFactor = 0.75,至于扩容因子有什么用,下面会涉及到。
 

不过需要注意的是,HashMap 内部用变量 threshold 变量来表示 HashMap 中能放入的元素个数,且在 threshold 不超过最大值前提下, threshold = loadFactor * capacity。
 

也就是说,当元素的个数达到 threshold 之后,就会触发 HashMap 的扩容,而不是达到 capacity 才触发扩容。每次扩容之后的容量为之前的 2 倍。而 ArrayList 则是元素达到 capacity 时才触发扩容。
 

还有一个需要注意的是,HashMap 容量并不会在 new 的时候分配,而是在第一次 put 的时候才完成创建的。

public V put(K key, V value){
    if(table == EMPTY_TABLE){
        // 初始化
        inflateTable(threshold);
    }
}

默认初始化容量大小 capacity = 16,如果我们在初始化的时候指定了容量的大小 initialCapacity,则会先计算出比 initialCapacity 大的 2 的幂存入 threshold,并且也会把初始化容量置为 capacity = threshold。例如当我们指定初始容量 initialCapacity = 26 的话,则 threshold = 32, capacity = 32。
 

(2)、HashTable的特点

a. HashTable 和 HashMap 在工作原理上几乎一样,不过 HashTable 是线程安全的,如图

不过锁是直接加在方法外面,所以在多线程环境下,性能极差。
 

不过在多线程的环境下,我们优先使用 ConcurrentHashMap 集合,这个集合在工作原理上也几乎和前面两个一样,但它是线程安全的,并且不像 HashTable 那样,把整个方法都给加锁了,而是把方法里面的关键代码加锁了,如图:

所以在处理速度上比较快。
 

b. HashTable 不允许 key 和 value 为 null。

c. HashMap 的迭代器是 fail-fast 机制(快速失败机制), 而 HashTable 则是 fail-safe 机制(快速安全)。

 

(3)、LinkedHashMap 的特点

LinkedHashMap 是 HashMap 的一个子类,我们知道 HashMap是在插入的时候是根据哈希码来选择位置的,是无序的,而 LinkedHashMap 在插入的时候具有双向链表的特性,内部使用链表维护了插入的顺序,能够保证输出的顺序和输入时的相同。
 

LinkedHashMap 也是线程不安全的,并且允许 key-value 为 null。
 

(4)、TreeMap

TreesMap 的底层数据结构是红黑树,和 HashMap 不同,它的 get, put, remove 操作都是 O(logn) 的时间复杂度,并且元素是有序的。

同样,TreeMap 也是线程不安全的。
 

4、Set

Set 是一种不允许出现重复元素的集合类型,常用的三个实现类是 HashSet、TreeSet 和 LinkedHashSet。

(1)、HashSet

HashSet 实际上是用 HashMap 来实现的,如图

只是 Value 被固定为一个静态对象

使用 Key 来保证集合元素的唯一性,不过它不保证集合元素的顺序。
 

(2)、TreeSet

TreeSet 也是用 TreeMap 来实现的,底层为树结构,TreeSet 则能够保证集合元素是有序的。
 

(3)、LinkedHashSet

LinkedHashSet 继承 HashSet,具有 HashSet 优点,不过与 HashSet 不同的是,LinkedHashSet 内部使用了链表来维护元素的插入顺序。


这些知识点如果都能自己打开源码配合看一下,很多有关集合的面试题就可以应付了。
(帅地,来自公众号:苦逼的码农)

想要更全详细的Java面试题集和Java程序员成长秘籍,可以联系客服小姐姐获取哦!

分享:0

电话咨询

客服热线服务时间

周一至周五 9:00-21:00

周六至周日 9:00-18:00

咨询电话

021-67690939
15201841284

微信扫一扫