0
0

Java集合专题（超级详细）

Java集合专题（超级详细）

文章目录

前言

一、集合是什么？

集合是一个用来存放对象的容器，它只能存放对象（实际上是对象名，即指向地址的指针），在没有集合前，我们是用数组来储存对象的。下面介绍一下集合和数组之间都有哪些不同。

1.集合和数组的区别

区别数组集合长度固定可变存放类型基本类型/引用类型引用类型存储元素同一种类型不同类型操作上添加/删除元素比较麻烦提供add/remove/set/get 比较方便

2.Collection体系的继承树

在这里插入图片描述

2.1 Collection接口常用方法

  1. add:添加单个元素
  2. remove：删除指定元素
  3. contains：查找元素是否为空
  4. size：获取元素个数
  5. isEmpty：判断元素是否为空
  6. clear：清空
  7. addAll：添加多个元素
  8. containsAll：查找多个元素是否都存在
  9. removeAll：删除多个元素

2.2 Collection常用遍历方式

2.2.1 迭代器Iterator使用

Collection接口遍历元素使用Iterator(称为迭代器)，所有实现Collection接口的集合类都有一个Iterator（）方法，只能用于遍历集合。

        List list =newArrayList<>();
        Iterator iterator = list.iterator();//获取迭代器while(iterator.hasNext()){//判断是否还有下一个，如果不用hasNext()会报NoSuchElementException
            Object next =  iterator.next();
            System.out.println(next);}

2.2.2 增强for循环遍历

底层也是采用了 Iterator 的方式实现，可以理解为简化版本的Iterator

        List lists =newArrayList<>();//增强for循环同样可以用在数组上面//使用foreach增强for循环for(Object list:lists){
            System.out.println(list);}

2.3 List常用遍历方式(3种)

1. 使用迭代器（Iterator）
2. 使用增强for循环
3. 使用普通for循环

2.4 Set常用遍历方式(2种)

1. 使用迭代器（Iterator）
2. 使用增强for循环
3. 不能使用普通for循环（因为没有提供get方法）

3.Map体系的继承树

在这里插入图片描述
Map与Collection并列存在。用于保存具有映射关系的数据：Key-Value（双列元素）
Key-Value为了方便遍历，还会创建EntrySet集合，该集合存放元素的类型Entry，而一个Entry对象就有Key，Value。
当HashMap $ Node对象存放到EntrySet就会方便我们遍历，因为Map.Entry<K, V>提供了重要的方法，如下：

 Set<Map.Entry<K, V>>entrySet();interfaceEntry<K,V>{
        K getKey();

        V getValue();...}

3.1 Map接口常用方法

  1. put:添加
  2. remove：根据键删除映射关系
  3. get：根据键获取值
  4. size：获取元素个数
  5. isEmpty：判断元素是否为空
  6. clear：清空
  7. containsKey：查找键是否存在

3.2 Map常用遍历方式（6种）

第一组：先取出所有的key，在通过Key获取对应的Values

  1. 增强for循环
//先取出所有的key，在通过Key获取对应的Values
        Set keyset = map.keySet();for(Object key:keyset){
            System.out.println(key+"__"+map.get(key));}
  1. 迭代器
//先取出所有的key，在通过Key获取对应的Values
        Set keyset = map.keySet();
        Iterator iterator = keyset.iterator();while(iterator.hasNext()){
            Object key = iterator.next();
            System.out.println(map.get(key));}

第二组：取出所有的Values
3. 增强for循环

//把所有的Values值取出
    Collection values = map.values();for(Object value:values){
            System.out.println(value);}
  1. 迭代器
//把所有的Values值取出
        Collection values = map.values();
        Iterator iterator = values.iterator();while(iterator.hasNext()){
            Object value = iterator.next();
            System.out.println(value);}

第三组：通过EntrySet来获取key-value
5. 增强for循环

//通过EntrySet来获取key-value
    Set entrySet = map.entrySet();for(Object entry:entrySet){
          Map.Entry entrys =(Map.Entry) entry;
          System.out.println(entrys.getKey()+" "+entrys.getValue());}
  1. 迭代器
通过EntrySet来获取key-value
        Set entrySet = map.entrySet();
        Iterator iterator = entrySet.iterator();while(iterator.hasNext()){
            Object value = iterator.next();
            Map.Entry entrys =(Map.Entry) value;
            System.out.println(entrys.getKey()+" "+entrys.getValue());}

4.List，Set，Map三者的区别

Collection集合主要有List和Set两大接口
接口有序性重复性索引List有序可重复有Set无序不可重复无
Map是一个键值对集合，存储键、值和之间的映射。 Key无序，唯一；value 不要求有序，允许重复。

5.开发中如何选择集合

其实开发中如何选择集合，主要是取决于业务操作特点，然后根据集合实现类特性进行选择，分析如下：
1.先判断存储类型（是单列还是双列）
单列：Collection接口

  • 允许重复：List- 增删多：LinkedList（底层维护了双向链表）- 改查多：ArrayList（底层维护了Object类型的可变数组）
  • 不允许重复：Set- 无序：HashSet（底层维护了HashMap）- 排序：TreeSet- 插入取出顺序一致：LinkedHashSet（底层维护了数组+双向链表）

双列：Map接口

  • 键无序：HashMap
  • 键有序：TreeMap
  • 读取文件：Properties
  • 插入取出顺序一致：LikendHashMap

二、List源码分析

1.ArrayList源码分析

ArrayList是线程不安全的，从源码中可以看出，没有添加synchronized

publicbooleanadd(E e){ensureCapacityInternal(size +1);// Increments modCount!!
        elementData[size++]= e;returntrue;}

ArrayList (线程不安全），在多线程的情况下不建议使用ArrayList，可以考虑Vector(线程安全)。ArrayList 和Vector基本一样，除了在线程上面不同。
ArrayList底层操作机制源码分析：

  1. ArrayList中维护了一个Object类型的数组（transient Object[] elementData）transient 表示该属性不会被序列化。 为什么要使用transient呢？因为lementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。
  2. 当创建ArrayList对象时，如果使用的是无参构造器，则初始化elementData容量为0 ，如果第一次添加，则扩容elementData为10，如果需要再次扩容，则扩容elementData为1.5倍
  3. 如果使用指定大小的容量capacity构造器，则初始化elementData容量为指定大小的capacity，如果需要扩容，则直接扩容elementData为1.5倍
  4. 当添加元素时，先判断是否需要扩容，如果需要则调用grow()方法，否则直接添加元素到合适的位置
privatevoidgrow(int minCapacity){// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity +(oldCapacity >>1);//位移1位 相当于原来的oldCapacity 除于2if(newCapacity - minCapacity <0)//第一次扩容因为oldCapacity为0，所以默认elementData为10
            newCapacity = minCapacity;if(newCapacity - MAX_ARRAY_SIZE >0)
            newCapacity =hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);//Arrays.copyOf保证原先的数组不变的情况下，进行扩容}

2.Vector源码分析

Vector底层也是一个对象数组，protected Object[] elementData，它是线程安全的，操作方法基本都带有synchronized，在开发中需要线程同步安全时，可以考虑Vector

publicsynchronizedbooleanadd(E e){
        modCount++;ensureCapacityHelper(elementCount +1);
        elementData[elementCount++]= e;returntrue;}publicsynchronized E get(int index){if(index >= elementCount)thrownewArrayIndexOutOfBoundsException(index);returnelementData(index);}publicsynchronized E set(int index, E element){if(index >= elementCount)thrownewArrayIndexOutOfBoundsException(index);
        E oldValue =elementData(index);
        elementData[index]= element;return oldValue;......}
  1. 如果是无参构造，默认Capacity为10，当Capacity超出10后就按2倍进行扩容
//无参构造，默认Capacity为10publicVector(){this(10);}publicVector(int initialCapacity){this(initialCapacity,0);}publicVector(int initialCapacity,int capacityIncrement){super();if(initialCapacity <0)thrownewIllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);this.elementData =newObject[initialCapacity];this.capacityIncrement = capacityIncrement;}

//确定是否需要扩容privatevoidensureCapacityHelper(int minCapacity){if(minCapacity - elementData.length >0)grow(minCapacity);}privatevoidgrow(int minCapacity){int oldCapacity = elementData.length;//capacityIncrement在创建Vector时默认就是0int 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);}
  1. 如果是有参构造，指定大小，则每次直接按2倍扩容
  2. 如果指定大小Capacity和capacityIncrement（自定义扩容大小），则按照自定义扩容大小进行扩容
//也可以进行指定capacityIncrement，不用默认的0publicVector(int initialCapacity,int capacityIncrement){super();if(initialCapacity <0)thrownewIllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);this.elementData =newObject[initialCapacity];this.capacityIncrement = capacityIncrement;}//扩容核心代码int newCapacity = oldCapacity +((capacityIncrement >0)?
                                         capacityIncrement : oldCapacity);

3.ArrayList与Vector的区别

集合底层结构效率扩容机制版本ArrayList可变数组线程不安全，效率高有参构造 1.5倍，无参第一次10，第二次按1.5倍扩容jdk1.2Vector可变数组线程安全效率低无参默认10，按2倍扩容，指定大小，每次也按2倍，通过有参构造修改capacityIncrement ，可以按照capacityIncrement 的值扩容jdk1.0

4.LinkedList源码分析

  1. LinkedList底层实现了双向链表，维护了两个属性first（首节点）和last（尾结点），每个节点中维护了prev,item,next三个属性。通过prev自行前一个节点和next指向后一个节点，最终实现双向链表。
transient Node<E> first;transient Node<E> last;//node节点（有三个属性）privatestaticclassNode<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;}}

4.1 LinkedList添加操作底层分析

1.执行添加操作，在添加第一个元素时，从源码中可以看出 first、last和都指向同一个节点，并且两头为空。

publicbooleanadd(E e){linkLast(e);returntrue;}voidlinkLast(E e){final Node<E> l = last;// 第一次添加 last为nullfinal Node<E> newNode =newNode<>(l, e, null);// l==null//将新的节点，加入到双向链表的最后
        last = newNode;//last 指向newNodeif(l == null)//执行这条语句
            first = newNode;//first 指向newNodeelse
            l.next = newNode;
        size++;//链表元素个数
        modCount++;//修改次数}

参考下图更容易理解：
在这里插入图片描述

2.执行添加操作，在添加第二个元素时，从源码中可以看出 first、last和都指向同一个节点，并且两头为空。

publicbooleanadd(E e){linkLast(e);returntrue;}voidlinkLast(E e){final Node<E> l = last;// 第二次添加 l指向lastfinal Node<E> newNode =newNode<>(l, e, null);// l==last,这里相当于把新节点 的pre指向last(前一个节点)//将新的节点，加入到双向链表的最后
        last = newNode;//last 指向新的节点newNode（原来的旧节点就断开了）if(l == null)
            first = newNode;else//l这个时候不为null 执行这条语句
            l.next = newNode;//l.next 指向newNode
        size++;//链表元素个数
        modCount++;//修改次数}

参考下图更容易理解：
在这里插入图片描述

  1. 可以添加任意元素（元素可以重复），包括null，添加和删除是通过修改节点指向，不是由数组完成的，所以效率较高。
  2. 线程不安全，没有实现同步

5.ArrayList与LinkedList的区别

集合底层结构效率ArrayList可变数组增删效率较低（数组扩容）/改查效率较高LinkedList双向链表增删效率较高（链表）/改查效率较低

5.1 如何选择ArrayList和LinkedList

1.修改和查找操作多时，我们选择ArrayList，
2.增加和删除操作多时，我们选择LinkedList

注意：这两个集合都是线程不安全的，所以适合在单线程的情况下使用

三、Set源码分析

1.HashSet源码分析

1.1 HashSet添加操作底层分析

1.HashSet底层是HashMap，HashMap底层是（数组+链表+红黑树）

publicHashSet(){
        map =newHashMap<>();}

2.添加一个元素时，先得到hash值（hash值是通过(h = key.hashCode()) ^ (h >>> 16)算法计算得出），在转成索引值

privatestaticfinal Object PRESENT =newObject();//PRESENT 占位用 没有实际意义publicbooleanadd(E e){return map.put(e, PRESENT)==null;}//这里主要用到key;  value=PRESENT 是static共享的public V put(K key, V value){returnputVal(hash(key), key, value,false,true);}//得到hash值，这里的hash是通过算法计算得到的 staticfinalinthash(Object key){int h;return(key == null)?0:(h = key.hashCode())^(h >>>16);}//核心方法（难点）final V putVal(int hash, K key, V value,boolean onlyIfAbsent,boolean evict){
        Node<K,V>[] tab; Node<K,V> p;int n, i;//table就是HashMap的一个数组，类型是Node[]//table是null或0,就是第一次扩容到16个空间if((tab = table)== null ||(n = tab.length)==0)//resize()执行返回Node<K,V>[]有16个大小的
            n =(tab =resize()).length;//根据key得到的hash，去计算key应该放在table表的哪个索引位置，并把这个位置赋值给p//如果p为null:表示还未存放元素，就创建一个Node，然后放进去tab[i] = newNode(hash, key, value, null);if((p = tab[i =(n -1)& hash])== null)
            tab[i]=newNode(hash, key, value, null);//如果p不为null:else{
            Node<K,V> e; K k;//定义了辅助变量,在需要的时候在创建//如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样//并且满足下面两个条件之一：//1、准备加入的key和p指向Node结点的key是同一个对象（地址相同）//2、准备加入的key和p指向Node结点的key是同一个值（值相同）if(p.hash == hash &&((k = p.key)== key ||(key != null && key.equals(k))))//这里可以重写equals方法 比如new Person("小明");new Person("小明");//通过重写equals方法可以让他们按照equals去比较是否相等
                e = p;//判断p是不是红黑树,如果是调用putTreeVal方法elseif(p instanceofTreeNode)
                e =((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else{//如果table对应索引位置，已经是一个链表，就可以使用for循环比较//依次和该链表的每一个元素比较后，都不相同，则加入到该链表的最后，添加后立即判断该链表是否已经达到8个节点，如果达到就调用treeifyBin（tab, hash）方法（树化）转成红黑树。//在转成红黑树时,要进行判断，如果该table数组size小于64（TREEIFY_CAPACITY），不会马上树化，会先扩容table。//如果发现相同的情况，就直接breakfor(int binCount =0;;++binCount){if((e = p.next)== null){
                        p.next =newNode(hash, key, value, null);if(binCount >= TREEIFY_THRESHOLD -1)// -1 for 1sttreeifyBin(tab, hash);break;}if(e.hash == hash &&((k = e.key)== key ||(key != null && key.equals(k))))break;
                    p = e;}}//这里指的是当用HashMap时，key一致，value不可重复（替换原来的value）if(e != null){// existing mapping for key
                V oldValue = e.value;if(!onlyIfAbsent || oldValue == null)
                    e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if(++size > threshold)resize();afterNodeInsertion(evict);return null;}

3.找到存储数据表table，看这个索引位置是否已经存放有元素
4.如果没有，直接加入
5.如果有，就调用equals比较，如果相同，就放弃添加，如果不同，则添加到最后
6.在java8中，如果一条链表的元素个数达到TREEIFY_THRESHOLD（默认是8）,并且table的大小>=TREEIFY_CAPACITY（默认64），就会进行树化（红黑树）

1.2 HashSet的扩容和转红黑树机制

  1. HashSet底层是HashMap，第一次添加时，table数组扩容到16，临界值（threshold）是16*加载因子（loadFactor）0.75=12
  2. 如果table数组使用到了临界值12，就会扩容到162=32，新的临界值就是320.75=24，以此类推
  3. 在Java8中，如果一条链表的元素个数达到TREEIFY_THRESHOLD（默认是8）,并且table的大小>= TREEIFY_CAPACITY（默认64），就会进行树化（红黑树），否则仍然采用数组扩容机制

2.LinkedHashSet源码分析

LinkedHashSet底层是一个LinkedHashMap,底层维护了一个数组+双向链表。添加数据和取出元素的顺序一致

2.1 LinkedHashSet添加操作底层分析

1.第一次添加时，直接将数值table扩容到16，存放节点(数据)的类型是LinkedHashMap $ Entry，数组类型是HashMap $ Node[]

作为HashSet的子类，只是比它多了一条链表，这条链表用来记录元素顺序，因此LinkedHashSet其中的元素有序。

staticclassEntry<K,V>extendsHashMap.Node<K,V>{
        Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next){super(hash, key, value, next);}}

添加方法和前面描述的HashSet添加操作底层分析一样的，这里就不再重复介绍。

publicbooleanadd(E e){return map.put(e, PRESENT)==null;}

四、Map源码分析

1.HashMap源码分析

在上面的HashSet中已经讲过了，这里就简单讲解一下

HashMap是最经典的Map实现，下面以它的视角介绍put的过程：

1.首次扩容：

  • 先判断数组是否为空，若数组为空则进行第一次扩容（resize）；

2.计算索引：

  • 通过hash算法，计算键值对在数组中的索引；

3.插入数据：

  • 如果当前位置元素为空，则直接插入数据；
  • 如果当前位置元素非空，且key已存在，则直接覆盖其value；
  • 如果当前位置元素非空，且key不存在，则将数据链到链表末端；
  • 若链表长度达到8，则将链表转换成红黑树，并将数据插入树中；

4.再次扩容

如果数组中元素个数（size）超过threshold，则再次进行扩容操作。
在这里插入图片描述

2.HashTable源码分析

HashTable（线程安全）使用方法基本和HashMap（线程不安全）一致，HashTable的键和值都不能为空
底层用Hashtable $ Entry[] 初始化大小为11。临界值threshold为8 = 11 * loadFactor（0.75）

privatetransient Entry<?,?>[] table;publicsynchronized V put(K key, V value){// Make sure the value is not nullif(value == null){thrownewNullPointerException();}
         Entry<?,?> tab[]= table;int hash = key.hashCode();int index =(hash &0x7FFFFFFF)% tab.length;@SuppressWarnings("unchecked")
        Entry<K,V> entry =(Entry<K,V>)tab[index];for(; entry != null ; entry = entry.next){if((entry.hash == hash)&& entry.key.equals(key)){
                V old = entry.value;
                entry.value = value;return old;}}//添加方法addEntry(hash, key, value, index);return null;}privatevoidaddEntry(int hash, K key, V value,int index){
            modCount++;
    
            Entry<?,?> tab[]= table;if(count >= threshold){// 扩容方法rehash();
    
                tab = table;
                hash = key.hashCode();
                index =(hash &0x7FFFFFFF)% tab.length;}// Creates the new entry.@SuppressWarnings("unchecked")
            Entry<K,V> e =(Entry<K,V>) tab[index];
            tab[index]=newEntry<>(hash, key, value, e);
            count++;}

3.TreeMap源码分析

TreeMap基于红黑树（Red-Black tree）实现。映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。TreeMap的基本操作containsKey、get、put、remove方法，它的**时间复杂度是log(N)**。

TreeMap包含几个重要的成员变量：root、size、comparator。其中root是红黑树的根节点。它是Entry类型，Entry是红黑树的节点，它包含了红黑树的6个基本组成：key、value、left、right、parent和color。Entry节点根据根据Key排序，包含的内容是value。Entry中key比较大小是根据比较器comparator来进行判断的。size是红黑树的节点个数。

标签： java 开发语言
本文转载自: https://blog.csdn.net/weixin_46015018/article/details/123190875
版权归原作者 大雄有哆啦梦 所有， 如有侵权，请联系我们删除。
登录后发布评论

“Java集合专题（超级详细）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

前端点击预览图片：Viewer.js 使用方法

一键将CentOs的yum源更换为国内阿里yum源

Ubuntu 16.04 更换国内源及相关设置

day05-Hive语法补充

2024年阿里最新软件测试面试题：Web 测试+接口测试+App 测试

owasp-top10（2024）

什么是“蜜罐”

文章导航