阿里P8深入讲解Java集合

阿里P8深入讲解Java集合

Collection（集合)

常用方法：

增

add(E e)//添加单一对象
addAll(Collection<? extends E> c)//添加一个集合

删

remove(Object o)//删除一个对象
removeAll(Collection<?> c)//删除一个集合

判空

isEmpty()//判断集合是否为为空

清除

clear()//将集合元素清空

判断是否包含

contains(Object o)//判断集合中是否存在改元素
containsAll(Collection<?> c)//判断集合是否存在子集合

长度

size()//获取集合元素个数

遍历

iterator()//获取一个迭代器对象用来遍历集合
迭代器

获取迭代器对象

使用Iterator类的hasNext遍历集合

使用Iterator类的next获取数据

迭代器执行原理

foreach遍历集合元素

规则：for(数据类型 变量名：遍历集合)

List（存储重复有序的数据）
List的实现类的对比

不同

ArrayList：底层实现为数组，做查改操作时效率较高，做增删效率较低(底层数组拷贝比较消耗资源和时间)，线程不安全，每次扩容为原来的1.5倍

LinkedList：底层为双向链表结构，做增删时效率较高，查改时，效率较低

Vector：底层实现为数组，线程安全，但效率较低，每次扩容为原来的2倍

相同

都是实现了LIst接口，都是存储有序可重复的数据

常用方法

增

add(E e)//添加元素在最后
add(int index, E element);//在指定位置添加数据
删

remove(int index)//移除指定位置数据
remove(Object o)//移除指定数据
改

set(int index, E element)//修改指定位置的数据
查

get(int index)//获取指定位置的数据

ArrayList
jdk1.7中(饿汉式)

在初始化ArrayList时会创建一个长度为10的数组

每次进行数组扩容时，扩容为原来的1.5倍

源码如下：

private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = pyOf(elementData, newCapacity);}//加入Java开发交流君样：756584822一起吹水聊天

jdk1.8中(懒汉式–节省内存)

在初始化ArrayList时，不会创建数组

在第一次进行数据添加时才会创建一个长度为10的数组

LinkedList
底层为双向链表

源码如下

 private static class Node<E> {E item;Node<E> next;Node<E> prev;
​Node(Node<E> prev, E element, Node<E> next) {this.item =  = next;this.prev = prev;}}//加入Java开发交流君样：756584822一起吹水聊天

所有的数据都被封装为一个节点，链接前一个后一个数据，所以底层是一个双向

链表

Vector

初始长度为10

每次扩容为原来长度的2倍

源码如下

 private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = pyOf(elementData, newCapacity);}//加入Java开发交流君样：756584822一起吹水聊天

Set(存储不重复无序的数据)
Set的实现类对比

不同

HashSet：线程不安全，可以存储null值

LinkedHashSet：可以按照添加顺序进行遍历，进行增删操作时效率较高

TreeSet：能够按照添加数据的属性进行排序

相同

都是实现了Set接口，存储不可重复没有顺序的数据

无序性：HashSet在存储数据时，通过计算添加数据的hash值进行存放数据，并不是按照数组的索引顺序进行数据存放

不可重复性：不能存放equals()返回为true的值

HashSet(数组+链表)
底层实现：

HashSet底层其实是使用的HashMap，在HashMap中说明，实际是将数据作为HashMap的key值存储

添加过程：

通过计算添加数据的hash值获取存放位置

若位置上没有数据，则直接存放-----第一种情况

若存在数据

通过遍历存放位置上的链表，判断是否存在与添加数据相同的hash值

若没有相同hash值数据，则直接添加数据----第二种情况

若存在相同hash值数据

进行equals()方法比较

返回值为false，则可以添加数据----第三种情况

返回值为true，则添加失败

注意：

jdk1.7中，添加数据是将新数据放在起始位置，将旧的数据挂在新的数据上

jdk1.8中，添加数据是将新的数据挂在旧的数据上

关于equals()和hashCode()方法：

使用HashSet集合时，存储的数据类要进行equals和hashCode方法的重写

LinkedHashSet
在HashSet的前提下，定义了两个前后的引用，形成链表结构

在进行频繁的增删操作时效率较高

TreeSet(判断对象是否相同不在时equals方法，而是compareTo或者compare方法)
自然排序

实现Compable接口

重写 compareTo方法，定义排序方式

定制排序

初始化一个Comparator接口的实例化对象，定义排序方式

初始化TreeSet集合，将Comparator对象作为参数放入集合中

Map(以键值对方式存储数据)
Map接口的多个实现类对比

不同

HashMap：效率高，可以存储null的key或value，线程不安全

LInkedHashMap：在HashMap的基础上添加了前后两个引用，形成链表结构，增删较多时，效率较高，能够按照添加顺序进行遍历

Hashtable：效率低，不能存储空key或value，线程安全

TreeMap：能够通过对key值的定制排序或者自然排序对键值对进行排序(CompableComparator),底层使用红黑树

相同

都是实现了Map结构

Map的常用方法：

增

put(K key, V value)//添加一个键值对
putAll(Map<? extends K,? extends V> m)//添加一个Map集合
删

remove(Object key)//删除指定key值的键值对
remove(Object key, Object value)//删除指定key值，指定value的键值对
清空

clear()//清空map集合数据
查

get(Object key)//获取指定key值的value
判空

isEmpty()//判断map集合是否为空
判断是否存在

containsKey(Object key)//判断是否存在指定key值
containsValue(Object value)//判断是否存在指定value值
大小

size()//获得map集合数据个数
遍历

keySet()//获取map集合所有数据的key值的集合，再通过get方法获取value值
values()//获取map集合中所有value值的集合
entrySet()//获取map中所有的entry键值对，通过getKey，getValue获取键与值

键值对数据的特点

key：不可重复，无序，key所在的类要重写equals和hashCode方法

value：无序，可重复

entry：一个key-value构成一个entry对象，无序，不可重复

HashMap
HashMap的底层

jdk1.7：底层是数组+链表

jdk1.8：底层是数组+链表+红黑树

底层实现原理

jdk1.7中：

默认初始数组长度为16，每次扩容为原来的2倍，数组类型(Entry)，扩容要求(已有数据长度大于临界值，并且插入位置为空)

加载因子为0.75

临界值=数组长度*加载因子，默认为12

添加数据过程：

通过某种算法计算key的hash值也就是键值对存放位置，并判断该位置是否存在哈希碰撞

未发生碰撞，直接将数据添加—情况1

发生碰撞时，采用链式处理，即将数据形成链表

将待插入数据的key值的hash值与链表上的所有元素的key的hash值作比较

没有相同的hash值存在，直接添加数据–情况2

存在相同的hash值

将相同hash值的key和待插入数据的key值做equals比较

返回flase，添加数据–情况3

返回true，将新的value替换旧的value

jdk1.8中(只说不同)：

数组类型为Node类型

初始化时并不进行数据的初始化，在第一次进行数据添加时才进行底层数组的初始化

源码如下：
初始化：

public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}
添加数据：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;
数组初始化：
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead =  = e;loTail = e;}else {if (hiTail == null)hiHead =  = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) { = null;newTab[j] = loHead;}if (hiTail != null) { = null;newTab[j + oldCap] = hiHead;}}}}//加入Java开发交流君样：756584822一起吹水聊天}return newTab;}

当链表长度大于8并且数组长度大于64时，链表形式改为红黑树

数组初始长度为16的原因：

源码如下：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
设置数组初始长度为2的幂，的时候n-1的2进制为11111这种，在进行&运算时，才能够利用所有位数进行索引值的运算，若不是2的幂，例如15，结果为14参与&运算，14的2进制为1110，最后一位为0，&运算后结果都是0，则最后一位是1的位置hash值都被浪费了，例如0001，0011等等，容易造成哈希碰撞。

至于采用16而不是4，8等，64，初始数组过小，会导致扩容减缓效率，过大会造成空间浪费，所以采用折中的大小。

总结：

减少哈希碰撞

增加查询效率

防止太小频繁扩容浪费时间

防止过大浪费空间

加载因子大小为0.75的原因：

加载因子过大例如1，则会造成数组长度过长，链表长度过长，导致效率低下，增加碰撞几率

加载因子过小例如0.5，则会频繁的进行数组扩容，浪费时间

所以取了折中的方案

HashMap源码中关于负载因子0.75的注释(在负载因子为0.75时，每个链表的长度超过8的概率时非常小的)

* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006
* //加入Java开发交流君样：756584822一起吹水聊天

LinkedHashMap

在HashMap的基础上将newNode方法重写，使用自己的LinkedHashMap.Entry对象，使得存在链表结构

 static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}//加入Java开发交流君样：756584822一起吹水聊天}

TreeMap

要求:添加同一类的对象

能够按照添加元素的key值进行排序

自然排序

实现Compable接口

重写 compareTo方法，定义排序方式

定制排序

初始化一个Comparator接口的实例化对象，定义排序方式

初始化TreeMap集合，将Comparator对象作为参数放入集合中

Hashtable
有个实现类Properties多用于资源文件的加载

Collections工具类
常用方法：

reverse(List<?> list)//反转List集合
shuffle(List<?> list)//打乱List集合
sort(List<T> list)//按照默认排序方式升序排序List集合
sort(List<T> list, Comparator<? super T> c)//按照指定排序方式排序
swap(List<?> list, int i, int j)//交换List集合中两个位置的数据
frequency(Collection<?> c, Object o)//返回一个集合中一个对象出现次数
copy(List<? super T> dest, List<? extends T> src)//将一个List的数据拷贝到另一个List集合
replaceAll(List<T> list, T oldVal, T newVal)//使用新值替换旧值

最新2020整理收集的一些高频面试题（都整理成文档），有很多干货，包含mysql，netty，spring，线程，spring cloud、jvm、源码、算法等详细讲解，也有详细的学习规划图，面试题整理等，需要获取这些内容的朋友请加Q君样：756584822