Java中常用的集合工具类

文章目录

• • • 一、Java中类集结构图
    • 二、List接口：
    • • 2.1 ArrayList
      • 2.2 Vector
      • 2.3 LinkedList
      • 2.4 Iterator与ListIterator
    • 三、Set接口：
    • • 3.1 HashSet
      • 3.2 TreeSet
      • 3.3 Comparable与Comparator(比较器)
      • 3.4 Collections集合工具类
    • 四、Map接口：
    • • 4.1 Hash表与HashMap
      • 4.2. TreeMap

一、Java中类集结构图

Map大佬是和Collection一个元老级别的，不是List、set一级的

1.1 Collection接口

Collection是所有单列集合的父接口，因此在Collection中定义了单列集合(List和Set)通用的一些方法，这些方法可用于操作所有的单列集合。常用方法如下：

• 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(): 把集合中的元素，存储到数组中。

1.2 Map接口

Map是双值存储结构。常用方法如下：

• public V put(K key, V value): 把指定的键与指定的值添加到Map集合中。
• public V remove(Object key): 把指定的键 所对应的键值对元素 在Map集合中删除，返回被删除元素的值。
• public V get(Object key) 根据指定的键，在Map集合中获取对应的值。
• boolean containsKey(Object key) 判断集合中是否包含指定的键。
• public Set keySet(): 获取Map集合中所有的键，存储到Set集合中。
• public Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的键值对对象的集合(Set集合)。

二、List接口：

2.1 ArrayList

2.1.1 概述

ArrayList： 使用的是数组结构，对于插入和删除慢，查找快。

• 此类的iterator和listIterator方法返回的迭代器是快速失败的 ：如果在创建迭代器之后的任何时候对列表进行结构修改，除了通过迭代器自己的remove或add方法之外，迭代器将抛出ConcurrentModificationException

• 此类是线程不同步的(不是线程安全的)

2.2.2 操作

三种构造方法：

• ArrayList() 构造一个初始容量为10的空列表。

  • 其实初始容量为0，只是在第一次扩容时把容量改为了10。第一次之后的每次扩容为原来的1.5倍。

• ArrayList(int initialCapacity)构造具有指定初始容量的空列表。

  • 如果我们一开始就要存一个容量很大的数据，此时用无参数构造器就会很浪费空间，因为要不断扩容。

• ArrayList(Collection<? extends E> c) 按照集合的迭代器返回的顺序构造一个包含指定集合元素的列表。

  常用方法：

• public void add(int index, E element): 将指定的元素，添加到该集合中的指定位置上。

  • 指定的下标不能大于列表的长度(即：list.size())，否则抛出

• public E get(int index):返回集合中指定位置的元素。

• public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素。

• public E remove(Object o): 移除列表中指定值元素的一项

• public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回值的更新前的元素。

• public Iterator<E> iterator():得到一个迭代器对象

• public int siz():获得元素的个数

2.2 Vector

2.2.1 概述

Vector： 类实现了可增长的对象数组。 像数组一样，它包含可以使用整数索引访问的组件。 但是， Vector的大小可以根据需要增大或缩小，以便在创建Vector后添加和删除项目。

• 它的操作和ArrayList类似，它也不能用除了迭代器自己的remove或add方法之外的方法去修改迭代器。
• 与新的集合实现不同， Vector是同步的。
• 如果不需要线程安全实现，建议使用ArrayList代替Vector 。

2.2.2 操作

四种构造器方法：

• Vector() 构造一个空向量，使其内部数据数组的大小为 10 ，其标准容量增量为零。
• Vector(int initialCapacity)构造一个具有指定初始容量且容量增量等于零的空向量。
• Vector(int initialCapacity, int capacityIncrement)构造具有指定初始容量和容量增量的空向量。
• Vector(Collection<? extends E> c) 按照集合的迭代器返回的顺序构造一个包含指定集合元素的向量。

常用方法：

​ 见ArrayList

2.3 LinkedList

2.3.1 概述

LinkedList：使用的是双向链表，对于增加删除快，查找慢

• 可以用{addFirst(E e)、removeFirst()|getFirst()}或直接用{push、pop}把它当做一个栈来使用
• 可以用addFirst(E e)、removeLast()|getLast()把它当做一个队列来使用

2.3.2 操作

• public void addFirst(E e):将指定元素插入此列表的开头。
• public void addLast(E e):将指定元素添加到此列表的结尾。
• public E getFirst():返回此列表的第一个元素。
• public E getLast():返回此列表的最后一个元素。
• public E removeFirst():移除并返回此列表的第一个元素。
• public E removeLast():移除并返回此列表的最后一个元素。
• public E pop():从此列表所表示的堆栈处弹出一个元素。
• public void push(E e):将元素推入此列表所表示的堆栈。
• public boolean isEmpty()：如果列表不包含元素，则返回true。

LinkedList是List的子类，List中的方法LinkedList都是可以使用

2.4 Iterator与ListIterator

2.4.1 Iterator

**迭代器：**它是用来Java中用来遍历元素的工具类

迭代：即Collection集合元素的通用获取方式。在取元素之前先要判断集合中有没有元素，如果有，就把这个元素取出来，继续在判断，如果还有就再取出出来。一直把集合中的所有元素全部取出。这种取出方式专业术语称为迭代。

常用方法：

• public E next():返回迭代的下一个元素。
• public boolean hasNext():向后如果仍有元素可以迭代，则返回 true。
• public void remove( ):删除迭代器指针所指向的集合元素

2.4.2 ListIterator

它与Iterator是一样的用法，只不过它是专门用来迭代List集合用的

常用方法：

• public E next():返回迭代的下一个元素。
• public boolean hasPrevious():向前如果仍有元素可以迭代，则返回 true。
• public E previous():返回迭代的上一个元素。
• public boolean hasNext():向后如果仍有元素可以迭代，则返回 true。
• public void remove( ):删除迭代器指针所指向的集合元素

三、Set接口：

3.1 HashSet

3.1.1 概述

Set: 不包含重复元素的集合。 更正式地说，集合不包含元素e1和e2 ，使得e1.equals(e2)为true且最多一个存入null元素(利用Comparator比较器)。
HashSet: 散列存放，底层用HashMap实现（哈希表实现），将自己的值作为键存入一个HashMap中，故性质与HashMap相似。

3.1.2 操作

构造方法：

HashSet()：返回一个默认容量为16和默认加载因子为0.75的对象

HashSet(int initialCapacity)：返回一个指定容量和默认加载因子为0.75的对象

HashSet(int initialCapacity,float loadFactor)：返回一个指定容量和指定加载因子的对象

HashSet(Collection<? extends E> c)：返回一个指定集合元素的对象

常用方法：

• public Iterator<E> iterator():得到一个迭代器对象

• public boolean add(E e)：如果该元素不存在，则添加到此集合中

• public void clear() ：移除所有元素

• public boolean contains(Object o) ：如果此 set 包含指定元素，则返回 true。

• public int size()：获得set中元素的个数

• public boolean remove(Object o)：如果指定元素存在于此 set 中，则将其移除

• public int size()：获得set中元素的个数

3.2 TreeSet

3.2.1 概述

TreeSet: 跟HashSet一样，内部也是用Map集合实现（TreeMap）

• HashSet是无序的，而它是有序的（自然顺序）
• 自定义类型要存入TreeSet要实现Comparable接口

3.2.2 操作

构造方法：

public TreeSet():构造一个新的空 set，该 set 根据其元素的自然顺序进行排序。

public TreeSet(Comparator<? super E> comparator):构造一个新的空 TreeSet，它根据指定比较器进行排序。

public TreeSet(Collection<? extends E> c):构造一个包含指定 collection 元素的新 TreeSet，它按照其元素的自然顺序进行排序。

public TreeSet(SortedSet<E> s):构造一个与指定有序 set 具有相同映射关系和相同排序的新 TreeSet。

常用方法：

• public boolean add(E e):将指定的元素添加到此 set（如果该元素尚未存在于 set 中）。
• public boolean remove(Object o):将指定的元素从 set 中移除（如果该元素存在于此 set 中）。
• public void clear():移除此 set 中的所有元素。
• public E first():返回此 set 中当前第一个（最低）元素。
• public E last():返回此 set 中当前最后一个（最高）元素。
• public E pollFirst():获取并移除第一个（最低）元素；如果此 set 为空，则返回 null。
• public E pollLast():获取并移除最后一个（最高）元素；如果此 set 为空，则返回 null。
• public Iterator<E> iterator():返回在此 set 中的元素上按升序进行迭代的迭代器。
• public int size():返回 set 中的元素数（set 的容量）。

3.3 Comparable与Comparator(比较器)

3.3.1 概述

Comparable 简介
Comparable 是排序接口。

​ 若一个类实现了Comparable接口，就意味着“该类支持排序”。此外，“实现Comparable接口的类的对象”可以用作“有序映射(如TreeMap)”中的键或“有序集合(TreeSet)”中的元素，而不需要指定比较器。
接口中通过x.compareTo(y)来比较x和y的大小。若返回负数，意味着x比y小；返回零，意味着x等于y；返回正数，意味着x大于y。

Comparator 简介
Comparator 是比较器接口。

​ 我们若需要控制某个类的次序，而该类本身不支持排序(即没有实现Comparable接口)；那么，我们可以建立一个“该类的比较器”来进行排序。这个“比较器”只需要实现Comparator接口即可。也就是说，我们可以通过“实现Comparator类来新建一个比较器”，然后通过该比较器对类进行排序。

int compare(T o1, T o2)和上面的x.compareTo(y)类似。

​ 排序规则(升序):大于—>返回1，等于—>返回0，小于—>-1，

Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。

3.3.2 操作

public static void main(String[] args) {
        TreeSet<Person> data = new TreeSet<>();
        Person p1 = new Person("张三",18);
        Person p2 = new Person("李四",19);
        //当Person里没有实现Comparable接口时会报错：TreeSetDemo2$Person cannot be cast to class java.lang.Comparable，
        //自定义类型要存入TreeSet要实现Comparable接口
        //String类也是实现了这个接口的，所以我们使用String类型时它能直接进行比较
        Person p3 = new Person("王二",19);//把Person实现了Comparable接口，并且重新定义了用age比较的规则，让此时的p3与p2年龄相同则存不进去
        data.add(p1);
        data.add(p2);
        for (Person p:data){
            System.out.println(p);
        }
        System.out.println("---------测试comparator------------");
        //不能用来测试TreeSet，因为comparator接口使用来外排序的。
        List<Student> list = new ArrayList<>();
        list.add(new Student("张三",18));
        list.add(new Student("李四",19));
        list.add(new Student("王二",17));
        for (Student s:list){
            System.out.println(s);
        }
        Collections.sort(list,new ComparatorDemo());
        System.out.println("-------comparator后------");
        for (Student s:list){
            System.out.println(s);
        }
    }
	//定义一个比较器   
    static class ComparatorDemo implements Comparator<Student>{
        //升序排列
        @Override
        public int compare(Student o1, Student o2) {
            if(o1.age>o2.age){
                return 1;
            }else if(o1.age==o2.age){
                return 0;
            }else{
                return -1;
            }
        }
    //把自定义类实现Comparable接口    
    static class Person implements Comparable<Person>{
        private String name;
        private int age;
        @Override
        public int compareTo(Person o) {
            //this 与 o 比较
            //返回的数据： 负数小/零一样大/正数大
            if(this.age > o.age){
                return 1;
            }else if(this.age == o.age){
                return 0;
            }else {
                return -1;
            }
        }
        public Person() {
        }

        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }

        @Override
        public String toString() {
            return "Person{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }

    }
    static class Student{
        private String name;
        private int age;

        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }

        public Student(String name, int age) {
            this.name = name;
            this.age = age;
        }
    }

    }

3.4 Collections集合工具类

3.4.1 概述

Collection与Collections的区别：
Collection：是集合类的上级接口，继承与他有关的接口主要有List和Set
**Collections：**是针对集合类的一个帮助类，他提供一系列静态方法实现对各种集合的搜索、排序、线程安全等操作

3.4.2 操作

常用方法：

public static <T> int binarySearch(List<? extends Comparable<? super T>> list,T key):使用二分搜索法搜索指定列表，以获得指定对象。在进行此调用之前，必须根据列表元素的自然顺序对列表进行升序排序（通过 sort(List) 方法）。返回要查找的元素的的下标，没找到返回-1。

public static <T extends Comparable<? super T>> void sort(List<T> list):根据元素的自然顺序 对指定列表按升序进行排序。

public static <T> void sort(List<T> list,Comparator<? super T> c):根据指定比较器产生的顺序对指定列表进行排序。

四、Map接口：

4.1 Hash表与HashMap

4.1.1 HashMap内部实现的Hash表结构图

4.1.2 概述

Hash表(散列表)：是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

• 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

HashMap：是Java中用对象数组加链表实现的一种数据类型（结构类型），它通过代码实现了Hash表 这种数据结构，并在此结构上定义了一系列操作。

• 桶的初始数量为16个(对应0~15的下标)。
• 在存值时利用hashCode( )得到的一个int类型的key，然后将key与桶个数进行取余运算得到key在数组中的下标位置，然后就可将key对应的value存入该下标对应的桶(链表)中。

【注意】：

1. 在jdk8之后，为了提高HashMap的性能，在哈希桶(链表)中数据量大于8时，会将链表转换为红黑树(目的在于数据量大时将查询的时间复杂度从n降为log(n)),而当数据量从大于8降为小于6时又会转为链表(数据量小时查询效率差不太多，反而会增加空间复杂度)。

   i. 为什么不一开始就用红黑树的？

   ​ 答：因为二叉树(红黑树其实是一种二叉树)虽然查询效率高，但是空间开销非常大，单个 TreeNode 需要占用的空间大约是普通 Node 的两倍，而在数据量很小时，红黑树与链表的查询效率不会差太多，所以一开始用链表结构的桶是比较划算的。

   ii. 为什么转换阀值是8？

   ​ 答：①从分布规律解释：根据理想状态下的泊松分布规律桶长度超过8的概率非常小，约为6乘以10的负8次方，这是一个小于千万分之一的概率，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。

   ​ ②从数学计算来解释：红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，查询长度已经多出1个了，这样就有了转换成树的必要。

   iii.在转换回来的时候，为什么不是小于8(即7)时就立即将红黑树转为链表？

   答：中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

2. HashMap默认的散列因子(负载因子)是0.75。

   i. 什么是散列因子？

   ​ 答：负载因子是哈希表容量自动增加之前允许哈希表获得的满度的度量。当哈希表中的桶的数量超过负载因子和当前容量的乘积时，哈希表将被重新哈希。

   ii. 为什么散列因子是0.75？

   ​ 答：当负载因子是0.5的时候，这也就意味着，当数组中的元素达到了一半就开始扩容，既然填充的元素少了，Hash冲突也会减少，那么桶中的链表长度或者是红黑树的高度就会降低。查询效率就会增加。但是，这时候空间利用率就会大大的降低，原本存储1M的数据，现在就意味着需要2M的空间。一句话总结就是负载因子太小，虽然时间效率提升了，但是空间利用率降低了。而当负载因子为1的时候，此时空间利用率确实高，但是链表或红黑树的高度也剧增了，此时的查询效率就大打折扣了。为了达到时间和空间上的权衡，最终选择了0.75作为负载因子。

HashMap里调用put方法的调用过程

HashMap存值过程（put方法）

• 第一步：当往调用put方法向HashMap里增加一个键值对时，会先调用键的hashcode方法，来得到一个hashcode值，然后根据这个值来计算出这个键值对在map中数组对应的下标，及定位到HashMap中的具体的某一个桶。
• 第二步：判断这个桶是否为空，如果是，直接把对象存到数组里，存储结束；如果不是，转到第三步
• 第三步：判断已存在对象的key的equals方法，跟需要添加的对象的key对比，是否为true，如果是，覆盖这个key所对应的value，存储结束；如果不为true，转到第四步
• 第四步：判断这个对象它指向下一个对象的next指针的是不是为空，如果不为空，重复（3）的过程；如果为空，则把该对象的next指针指向要增加的对象，存储结束。

HashMap取值过程（get方法）

• 第一步：调用key的hashcode方法，得到一个返回值，通过返回值定位到map中数组对应的下标，就是定位到HashMap中的具体的某一个桶。
• 第二步：判断这个桶是否为空，如果是，就结束判断，返回null；如果不是空，就转到第三步。
• 第三步：判断桶中对象的key值与传入的key值是否相等并且用equals方法判断他们是否为同一个对象，如果判断结果为真，就返回这个对象的value值；如果为假，就转到第四步。
• 第四步：判断这个对象它指向下一个对象的next指针的是不是为空，如果是空，就结束判断，返回null；如果next指针不是空，就取出它所指对象，重复上面第三步的判断操作，直到取出对应的value值，或者直到桶中的对象被遍历完，返回一个null值。

4.1.3 操作

构造方法：

HashMap(): 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。

public HashMap(int initialCapacity): 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。

public HashMap(int initialCapacity,float loadFactor):构造一个带指定初始容量和加载因子的空 HashMap。

public HashMap(Map<? extends K,? extends V> m):构造一个映射关系与指定 Map 相同的新 HashMap。所创建的 HashMap 具有默认加载因子(0.75) 和足以容纳指定 Map 中映射关系的初始容量。

常用方法：

• public V put(K key,V value):存入键值对，如果该键对应的旧值存在，则替换掉旧值，并返回旧值。
• public V remove(Object key):删除某键值对。
• public int size():得到键值对的个数。
• public V get(Object key):返回指定键所映射的值。
• public Set<K> keySet():返回一个包含所有键的Set集合。
• public void clear():删除所有映射关系。

4.2. TreeMap

4.2.1 概述

TreeMap: 跟TreeSet一样，如果（key!!!）是存自定义类型的数据的话，自定义数据要求实现Comparable接口。也能明显的能知道它与HashMap的不同，它是能够排序的。

4.2.2 操作

构造方法：

public TreeMap():使用键的自然顺序构造一个新的、空的树映射。

public TreeMap(Comparator<? super K> comparator):构造一个新的、空的树映射，该映射根据给定比较器进行排序。

public TreeMap(Map<? extends K,? extends V> m):构造一个与给定映射具有相同映射关系的新的树映射，该映射根据其键的自然顺序进行排序。

public TreeMap(SortedMap<K,? extends V> m):构造一个与指定有序映射具有相同映射关系和相同排序顺序的新的树映射。

常用方法：

• public void clear():删除所有映射关系。
• public K firstKey():返回此映射中当前第一个（最低）键。
• public K lastKey():返回此映射中当前第一个（最低）键。
• public V get(Object key):返回指定键所映射的值。
• public Set<K> keySet():返回一个包含所有键的Set集合。
• public V put(K key,V value):存入键值对，如果该键对应的旧值存在，则替换掉旧值，并返回旧值。
• public V remove(Object key):删除某键值对。
• public int size():得到键值对的个数。
• public Collection<V> values():返回此映射包含的值的 Collection 视图。

public void clear():删除所有映射关系。

• public K firstKey():返回此映射中当前第一个（最低）键。
• public K lastKey():返回此映射中当前第一个（最低）键。
• public V get(Object key):返回指定键所映射的值。
• public Set<K> keySet():返回一个包含所有键的Set集合。
• public V put(K key,V value):存入键值对，如果该键对应的旧值存在，则替换掉旧值，并返回旧值。
• public V remove(Object key):删除某键值对。
• public int size():得到键值对的个数。
• public Collection<V> values():返回此映射包含的值的 Collection 视图。

本文地址：https://blog.csdn.net/weixin_44398687/article/details/109822795