Java的集合学习

路要慢慢走，有些事情必须要做。静心，沉住气。

前言

安全中代码审计其实也是有很多漏洞是从集合的这些数据结构的底层，由于开发者忽视了底层代码，一些类搭配使用的时候造成了漏洞。

所以分析学习类的底层代码对于发现漏洞以及提升审计能力都十分有帮助。

在编程中，集合是用于存储和操作一组对象的数据结构。Java 的集合框架提供了一组接口和类，用于处理各种类型的集合。集合框架的主要目标是提供一种通用的方式来管理对象，使我们能够更轻松地添加、删除、搜索和遍历元素。

集合框架有助于我们处理复杂的数据，例如列表、集合、映射等。它提供了一些常见的数据结构，如数组、链表、栈、队列等，以及各种实现这些数据结构的类。

Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection 接口又有 3 种子类型，List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

Java 的集合框架是由一组接口和类组成的，这些接口和类之间形成了一个层次结构。以下是集合框架的一些关键接口：

1. Collection 接口：Collection 接口是所有集合类的根接口，它定义了一组通用的方法，如添加、删除、遍历元素等。它有两个主要子接口：List 和 Set。
2. List 接口：List 接口表示有序的集合，允许重复的元素。它的一些常见实现类包括 ArrayList、LinkedList 和 Vector。
3. Set 接口：Set 接口表示不允许重复元素的集合。它的一些实现类包括 HashSet、LinkedHashSet 和 TreeSet。
4. Map 接口：Map 接口表示键值对的集合，每个键对应一个值。它的一些实现类包括 HashMap、LinkedHashMap 和 TreeMap。

集合实现类（集合类）

标准集合类汇总于下表：

序号	类描述
1	AbstractCollection 实现了大部分的集合接口。
2	AbstractList 继承于AbstractCollection 并且实现了大部分List接口。
3	AbstractSequentialList 继承于 AbstractList ，提供了对数据元素的链式访问而不是随机访问。
4	LinkedList 该类实现了List接口，允许有null（空）元素。主要用于创建链表数据结构，该类没有同步方法，如果多个线程同时访问一个List，则必须自己实现访问同步，解决方法就是在创建List时候构造一个同步的List。例如：List list=Collections.synchronizedList(newLinkedList(...));LinkedList 查找效率低。
5	ArrayList 该类也是实现了List的接口，实现了可变大小的数组，随机访问和遍历元素时，提供更好的性能。该类也是非同步的,在多线程的情况下不要使用。ArrayList 增长当前长度的50%，插入删除效率低。
6	AbstractSet 继承于AbstractCollection 并且实现了大部分Set接口。
7	HashSet 该类实现了Set接口，不允许出现重复元素，不保证集合中元素的顺序，允许包含值为null的元素，但最多只能一个。
8	LinkedHashSet 具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现。
9	TreeSet 该类实现了Set接口，可以实现排序等功能。
10	AbstractMap 实现了大部分的Map接口。
11	HashMap HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。 该类实现了Map接口，根据键的HashCode值存储数据，具有很快的访问速度，最多允许一条记录的键为null，不支持线程同步。
12	TreeMap 继承了AbstractMap，并且使用一颗树。
13	WeakHashMap 继承AbstractMap类，使用弱密钥的哈希表。
14	LinkedHashMap 继承于HashMap，使用元素的自然顺序对元素进行排序.
15	IdentityHashMap 继承AbstractMap类，比较文档时使用引用相等。

集合算法

集合框架定义了几种算法，可用于集合和映射。这些算法被定义为集合类的静态方法。

在尝试比较不兼容的类型时，一些方法能够抛出 ClassCastException异常。当试图修改一个不可修改的集合时，抛出UnsupportedOperationException异常。

集合定义三个静态的变量：EMPTY_SET，EMPTY_LIST，EMPTY_MAP的。这些变量都不可改变。

如何使用迭代器

通常情况下，你会希望遍历一个集合中的元素。例如，显示集合中的每个元素。

一般遍历数组都是采用for循环或者增强for，这两个方法也可以用在集合框架，但是还有一种方法是采用迭代器遍历集合框架，它是一个对象，实现了Iterator 接口或 ListIterator接口。

迭代器，使你能够通过循环来得到或删除集合的元素。ListIterator 继承了 Iterator，以允许双向遍历列表和修改元素。

Collection接口

Collection 接口中定义了一些单列集合通用的方法：

public boolean add(E e); // 把给定的对象添加到当前集合中
public void clear(); // 清空集合中所有的元素
public boolean remove(E e); // 把给定的对象在当前集合中删除
public boolean contains(E e); // 判断当前集合中是否包含给定的对象
public boolean isEmpty(); // 判断当前集合是否为空
public int size(); // 返回集合中元素的个数
public Object[] toArray(); // 把集合中的元素，存储到数组中

List

List接口扩展自Collection，它可以定义一个允许重复的有序集合，从List接口中的方法来看，List接口主要是增加了面向位置的操作，允许在指定位置上操作元素，同时增加了一个能够双向遍历线性表的新列表迭代器ListIterator。AbstractList类提供了List接口的部分实现，AbstractSequentialList扩展自AbstractList，主要是提供对链表的支持。

ArrayList

ArrayList 类位于 java.util 包中，使用前需要引入它，语法格式如下：

import java.util.ArrayList; // 引入 ArrayList 类

ArrayList<E> objectName =new ArrayList<>();　 // 初始化

• E: 泛型数据类型，用于设置 objectName 的数据类型，只能为引用数据类型。
• objectName: 对象名。

ArrayList 是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。

用数组存储元素的，这个数组可以动态创建，如果元素个数超过了数组的容量，那么就创建一个更大的新数组，并将当前数组中的所有元素都复制到新数组中。

ArrayList是一个动态数组，当你使用无参构造方法去创建时，它会创建一个空数组，既然是空数组，那怎么加进去的元素，我们来看看 add方法

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

调用了一个 ensureCapacityInternal 方法

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

又调用了另一个方法 calculateCapacity ，用来计算容量。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

注意到方法 calculateCapacity有一个常量 DEFAULT_CAPACITY

private static final int DEFAULT_CAPACITY = 10;

如果你通过无参构造方法创建一个ArrayList，经过这个容量计算，它会返回10，接着看方法ensureExplicitCapacity

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

如果大于当前数组的长度，那就扩容！！！ 我们来看看扩容方法

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);
    }

当你看到了扩容方法最后一行，是不是明白了，扩容其实就是创建一个新数组，将老数组的数据放进去，也并没有加锁什么的，所以说，不管是出于效率还是出于安全什么，插入操作多的话，不推荐用底层为数组的ArrayList。

LinkedList

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的地址。

LinkedList 类位于 java.util 包中，使用前需要引入它，语法格式如下：

// 引入 LinkedList 类
import java.util.LinkedList; 

LinkedList<E> list = new LinkedList<E>();   // 普通创建方法
或者
LinkedList<E> list = new LinkedList(Collection<? extends E> c); // 使用集合创建链表

transient关键字的主要作用就是让某些被transient关键字修饰的成员属性变量不被序列化

二者比较

链表和数组的最大区别在于它们对元素的存储方式的不同导致它们在对数据进行不同操作时的效率不同，同样，ArrayList与LinkedList也是如此，实际使用中我们需要根据特定的需求选用合适的类，如果除了在末尾外不能在其他位置插入或者删除元素，那么ArrayList效率更高，如果需要经常插入或者删除元素，就选择LinkedList。

以下情况使用 ArrayList :

• 频繁访问列表中的某一个元素。
• 只需要在列表末尾进行添加和删除元素操作。

以下情况使用 LinkedList :

• 你需要通过循环迭代来访问列表中的某些元素。
• 需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作。

Set

接口在方法签名上与 Collection 接口其实是完全一样的，只不过在方法的说明上有更严格的定义，最重要的特点是他「拒绝添加重复元素，不能通过整数索引来访问」，并且「元素无序」。所谓无序也就是元素的存入顺序和取出顺序不一致。其常用实现类有：

• 「HashSet」：底层基于 HashMap 实现，采用 HashMap 来保存元素
• 「LinkedHashSet」：LinkedHashSet 是 HashSet 的子类，并且其底层是通过 LinkedHashMap 来实现的。

HashSet

散列集HashSet是一个用于实现Set接口的具体类，可以使用它的无参构造方法来创建空的散列集，也可以由一个现有的集合创建散列集。在散列集中，有两个名词需要关注，初始容量和客座率。客座率是确定在增加规则集之前，该规则集的饱满程度，当元素个数超过了容量与客座率的乘积时，容量就会自动翻倍。

HashSet底层采用哈希表实现，元素对象的HashCode值决定了在哈希表中存储的位置，当往HashSet中添加新元素的时候，先会判断该位置是否有元素：

1. 如果没有，直接把该新的对象存储到hashCode指定的位置
2. 如果有，再继续判断新对象和集合对象的equals作比较：

• • 若equals为true，则视为同一个对象，不保存，add()方法返回false
  • 如果equals为false，则存储在之前的对象的同一个位置上开辟一个链表进行存储

每一个存储到哈希表中的对象，都得重写hashCode和equals方法来判断是否是同一个对象，在一般情况下，equals为true的时候，hashCode应该也相等，Idea可以自动生成这些方法

HashSet 中的元素实际上是对象，一些常见的基本类型可以使用它的包装类。

基本类型对应的包装类表如下：

基本类型	引用类型
boolean	Boolean
byte	Byte
short	Short
int	Integer
long	Long
float	Float
double	Double
char	Character

HashSet 类位于 java.util 包中，使用前需要引入它，语法格式如下：

import java.util.HashSet; // 引入 HashSet 类

以下实例我们创建一个 HashSet 对象 sites，用于保存字符串元素：

HashSet<String> sites = new HashSet<String>();

LinkedHashSet

LinkedHashSet是用一个链表实现来扩展HashSet类，它支持对规则集内的元素排序。HashSet中的元素是没有被排序的，而LinkedHashSet中的元素可以按照它们插入规则集的顺序提取。

TreeSet

TreeSet扩展自AbstractSet，并实现了NavigableSet，AbstractSet扩展自AbstractCollection，树形集是一个有序的Set，其底层是一颗树，这样就能从Set里面提取一个有序序列了。在实例化TreeSet时，我们可以给TreeSet指定一个比较器Comparator来指定树形集中的元素顺序。树形集中提供了很多便捷的方法。

Queue

队列是一种先进先出的数据结构，元素在队列末尾添加，在队列头部删除。Queue接口扩展自Collection，并提供插入、提取、检验等操作。

Map

Map并不是集合，而是类似两个集合的映射关系，所以Map中没有实现Collection接口

在Map中，要求A集合的每一个元素（key）都可以在B集合中找到唯一的值（value）与之对应，意味着A集合中的元素是不可以重复的而B集合中的元素却可以重复，所以A集合应该是一个Set集合，而B集合是一个List集合

HashMap

JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间（注意：将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）。

数组+单/双向链表+红黑树

实现链表

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

生成key的hashcode

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//如果不为0，hashcode与右移16位的hashcode进行异或运算得到值作为key的hashcode
    }

扩容方法resize,返回了一个新的数组。

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;
                        }
                    }
                }
            }
        }
        return newTab;
    }

putval，添加新数据

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;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            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;
    }

构造红黑树

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//如果小于64则继续扩容，而不是生成红黑树
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

常量

static final int MIN_TREEIFY_CAPACITY = 64;

LinkedHashMap

HashMap 的子类，可以保证元素的存取顺序一致（存进去时候的顺序是多少，取出来的顺序就是多少，不会因为 key 的大小而改变）。

LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构，即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

TreeMap

TreeMap底层的key是基于红黑树，因为Map中的key也是一个Set集合，所以不能保证添加的先后顺序，且也不允许重复，因为Map中存储的key会默认使用自然排序（从小到大），和TreeSet一样，除了可以使用自然排序也可以自定义自己的排序。

参考：

Java 集合框架 | 菜鸟教程 (runoob.com)

详解java集合，Collection，list，set，map汇总 - 知乎 (zhihu.com)

常用的几种java集合类总结_java集合分为哪几大类-CSDN博客

你真的了解集合吗，来给我说一下集合的底层数据结构！（上）-阿里云开发者社区 (aliyun.com)

你真的了解集合吗，来给我说一下集合的底层数据结构！（中）-阿里云开发者社区 (aliyun.com)

你真的了解集合吗，来给我说一下集合的底层数据结构！（下）-阿里云开发者社区 (aliyun.com)

Java 集合框架_w3cschool

2024吃透JDK8中HashMap的底层源码，你的Java面试水平就真的牛了！！_哔哩哔哩_bilibili