阿里P8深入讲解Java集合

- 日理万妓 2021-07-24 21:05 394阅读 0赞

## 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获取数据

## 迭代器执行原理 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70]

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)//获取指定位置的数据

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 1]

ArrayList  
jdk1.7中(饿汉式)

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

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

源码如下：

private void grow(int minCapacity) { 
           // overflow-conscious code
           int 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 = Arrays.copyOf(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 = element;
                this.next = next;
                this.prev = prev;
            }
        }//加入Java开发交流君样：756584822一起吹水聊天

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

## 链表 ##

## Vector ##

初始长度为10

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

源码如下

private void grow(int minCapacity) { 
            // overflow-conscious code
            int 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 = Arrays.copyOf(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值的定制排序或者自然排序对键值对进行排序(Compable\\Comparator),底层使用红黑树

相同

都是实现了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 threshold
                newCap = oldThr;
            else {                // zero initial threshold signifies using defaults
                newCap = 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 order
                            Node<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;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else { 
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            if (loTail != null) { 
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) { 
                                hiTail.next = 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)//使用新值替换旧值

![image][]

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70]: /images/20210724/80f6bcc380eb47a7bbad1e31ef4d4681.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 1]: /images/20210724/8679dd5294c14e91b4926d5db7519957.png
[image]: /images/20210724/f60b706337054432a183ccd654390c4e.png
[2020_mysql_netty_spring_spring cloud_jvm_Q_756584822]: https://jq.qq.com/?_wv=1027&k=0IsBuUb0