Java从入门到精通七（Java数据结构--Collection集合）

兰舟千帆

发布于 2022-07-16 11:03:21

1.1K0

发布于 2022-07-16 11:03:21

Collection集合

一：集合概述

集合和数组的区别是什么？ 数组也是java中的一种数据结构，数据的长度是固定的，存储方式是线性的。并且是可以存储基本的数据类型和对象，基本数据对象可以按照基本类型的装箱处理并存储。而我们的数组是属于引用数据类型的。集合是java中的另外一种数据i结构，相比数组，集合是更加灵活的。从实现方式上，集合的实现方式多样，适用范围比较广，数组采用的是空间连续分配存储的方式。 另外，集合采用了类和接口的形式，具有java面向对象的三大特征，比较数组更加明显地体现了面向对象地逻辑思维。 java中的集合分为单列集合和双列集合，Collection是单列集合的顶层接口，Map是双列集合的顶层接口。从基本的存储上讲，单列存储的数据只包含了数据本身，而双列是包含键和值的，也就是双列不仅存储数据本身，也存储所对应的索引。本文主要介绍单列集合Collection，以及其下面的部分子接口。

一般我们会学习这两种基本的List,Set，但是实际上，还有一种。本文将Collection的三种接口实现类全部说明。

二：Collection集合解析

我们的JDK API是这样对Collection概述的。

Collection 层次结构中的根接口。Collection 表示一组对象，这些对象也称为 collection 的元素。一些 collection 允许有重复的元素，而另一些则不允许。一些 collection 是有序的，而另一些则是无序的。JDK 不提供此接口的任何直接实现：它提供更具体的子接口（如 Set 和 List）实现。此接口通常用来传递 collection，并在需要最大普遍性的地方操作这些 collection。包 (bag) 或多集合 (multiset)（可能包含重复元素的无序 collection）应该直接实现此接口。所有通用的 Collection 实现类（通常通过它的一个子接口间接实现 Collection）应该提供两个“标准”构造方法：一个是 void（无参数）构造方法，用于创建空 collection；另一个是带有 Collection 类型单参数的构造方法，用于创建一个具有与其参数相同元素新的 collection。实际上，后者允许用户复制任何 collection，以生成所需实现类型的一个等效 collection。尽管无法强制执行此约定（因为接口不能包含构造方法），但是 Java 平台库中所有通用的 Collection 实现都遵从它。 **

这里提到了它的具体的实现接口类，Set,List。

另外，文档还很专业的说明了以下需要注意的地方

Collections Framework 接口中的很多方法是根据 equals 方法定义的。例如，contains(Object o) 方法的规范声明：“当且仅当此 collection 包含至少一个满足 (onull ? enull 😮.equals(e)) 的元素 e 时，返回 true。”不应将此规范理解为它暗指调用具有非空参数 o 的 Collection.contains 方法会导致为任意的 e 元素调用 o.equals(e) 方法。可随意对各种实现执行优化，只要避免调用 equals 即可，例如，通过首先比较两个元素的哈希码。（Object.hashCode() 规范保证哈希码不相等的两个对象不会相等）。较为常见的是，各种 Collections Framework 接口的实现可随意利用底层 Object 方法的指定行为，而不管实现程序认为它是否合适。

具体体现在它的实现接口类上，在文章后面详细说明

Collection本身提供了自己的一些方法

摘录常用方法

1. 添加功能
    boolean add(E e) 
        添加一个元素
    boolean addAll(Collection c)  
        添加一批元素
2. 删除功能
   boolean remove(Object o) 
       删除一个元素
3. 判断功能
   boolean contains(Object o) 
       判断集合是否包含指定的元素
   boolean isEmpty()  
       判断集合是否为空(集合中没有元素)
4. 获取功能
   int size()  
      获取集合的长度
5. 转换功能
   Object[] toArray() 
       把集合转换为数组

三：List集合

List集合是单列集合的一种，它所存储的元素是可以重复的。List是直接实现Collection接口类的一种。完整的lIst接口类定义如下。

public interface List<E>extends Collection<E>

E是指代了泛型，泛型说明了类属性。

与 set 不同，列表通常允许重复的元素。更确切地讲，列表通常允许满足 e1.equals(e2) 的元素对 e1 和 e2，并且如果列表本身允许 null 元素的话，通常它们允许多个 null 元素。 List 接口在 iterator、add、remove、equals 和 hashCode 方法的协定上加了一些其他约定，超过了 Collection 接口中指定的约定。为方便起见，这里也包括了其他继承方法的声明。 List 接口提供了 4 种对列表元素进行定位（索引）访问方法。列表（像 Java 数组一样）是基于 0 的。注意，这些操作可能在和某些实现（例如 LinkedList 类）的索引值成比例的时间内执行。因此，如果调用者不知道实现，那么在列表元素上迭代通常优于用索引遍历列表。 List 接口提供了特殊的迭代器，称为 ListIterator，除了允许 Iterator 接口提供的正常操作外，该迭代器还允许元素插入和替换，以及双向访问。还提供了一个方法来获取从列表中指定位置开始的列表迭代器。 List 接口提供了两种在列表的任意位置高效插入和移除多个元素的方法。

既然是接口，那必然需要实现类了。我们通常需要了解两种，那就是ArrayList，LinkedList。

1：实现类ArrayList

<1>方法说明

注意ArrayList只是实现了List，但是并没有继承List接口

public class ArrayList<E>extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, Serializable

可见ArrayList的继承自AbstractList,然后我们查看AbstractList的类定义 查询JDK API说明我们可以看到AbstractList的完整定义

public abstract class AbstractList<E>extends AbstractCollection<E>implements List<E>

溯源

public abstract class AbstractCollection<E>extends Object implements Collection<E>

这些了解就可以，没有什么疑问，Object是根。

ArrayList数据结构为数组，通过数组的特点，我们可以了解到，数组的查询是比较快的，但是增删是比较慢的。

我们来看ArrayList的几个常用的方法。

测试了大部分方法

     //1:将指定的元素添加到此列表的尾部。
        List l = new ArrayList<>();
        //ArrayList L = new ArrayList<>();
        l.add("Hello");//一次只能插入一个元素
        System.out.println(l);
        // 2： add(int index, E element) 
        l.add(0,"jgdabc");
        System.out.println(l);
        ArrayList l1 = new ArrayList<>();
        l1.add("jgdabc01");
        l1.add(20);
        System.out.println(l1);
        //3:add()方法，整个集合添加
        l.add(l1);
        l.addAll(1,l1);
        System.out.println(l);
        //4:addAll(Collection<? extends E> c) 
        l.addAll(l1);
        System.out.println(l);
        //5:addAll(int index, Collection<? extends E> c) 
        //从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。
        l.add(1,l1);
        System.out.println(l);
        //6:clear() 
        //移除此列表中的所有元素。
        l.clear();
        System.out.println(l);
        //7:contains(Object o) 
        //如果此列表中包含指定的元素，则返回 true。
        boolean flag = l1.contains("jgdabc");
        System.out.println(flag);
        //8:get(int index) 
        //返回此列表中指定位置上的元素。如果集合为空，会报异常。
        l.add("jgdabc");
        String s = (String) l.get(0);
        System.out.println(s);
        //9：indexOf(Object o) 
        //返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。
        int x = l.indexOf("jgdabc");
        System.out.println(x);
        //10:isEmpty() 
        //如果此列表中没有元素，则返回 true
        boolean flag_1 = l.isEmpty();
        System.out.println(flag_1);
        //11:lastIndexOf(Object o) 
        //返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。
        int flag_2 = l.lastIndexOf("jgdabc");
        System.out.println(flag_2);
        //12:remove(int index) 
        l.remove(0);
        System.out.println(l);
        //13:removeRange(int fromIndex, int toIndex) 
        //移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。
        // removeRange()方法受保护，只提供子类使用
        l.add("jgdabc");
        l.add("jgdabc01");
        ArrayList ll = new ArrayList<>();
        ArrayList ll2 = ll;
        //14:set(int index, E element) 
        //用指定的元素替代此列表中指定位置上的元素。
        l.set(0, "zhan");
        System.out.println(l);
        // 15:toArray() 
        //按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组
        l.toArray();
        System.out.println(l);
        // 17:trimToSize() 
        //将此 ArrayList 实例的容量调整为列表的当前大小。
        ((ArrayList<Object>) l).trimToSize();
        System.out.println(l.size());

其中需要注意的就是两个方法，一个removeRange()，这个方法虽然在ArrayList中被提供，但是受到保护，只能被子类使用。也就是写一个继承类就好。 还有一个方法，可能并不常用。其实涉及到优化。那就是trimToSize()方法

ArrayList 的内部使用数组存储元素，当数组将被存满，就会创建一个新数组，其容量是当前数组的 1.5 倍。同时，所有元素都将移至新数组，假设内部数组已满，而我们现在又添加了 1 个元素，ArrayList 容量就会以相同的比例扩展（即前一个数组的1.5倍）。在这种情况下，内部数组中将有一些未分配的空间。这时，trimToSize() 方法可以删除未分配的空间并更改 ArrayList 的容量，使其等于 ArrayList 中的元素个数。

<2>并发修改异常

先来看一个代码

package java_practice;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ListDemo {
    public static void main(String args[]) {

        List<String> list = new ArrayList<String>();
        list.add("Hello");
        list.add("world");
        list.add("java");
        Iterator<String> it = list.iterator();
        while(it.hasNext()) {
            String s = it.next();
            if(s.equals("world"))
            {
                list.add("javaee");
            }


           }
//            for(int i=0;i<list.size();i++)
//            {
//                String s = list.get(i);
//                if(s.equals("world"))
//                {
//                    list.add("javaee");
//                }
//
//            }
            System.out.println(list);


    }
}

很显然这里抛出了异常，为什么会这样呢？

下面摘录异常信息

Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:907)
	at java.util.ArrayList$Itr.next(ArrayList.java:857)
	at java_practice.ListDemo.main(ListDemo.java:16)

我们根据checkForComodification步步跟进源码 下面是跟进和溯源处理后的关键源码信息

public interface List<E>{
Iterator<E> iterator();
boolean add(E e)
}

public abstract class AbstractList<E>
{
protected transient int modCount = 0;

}

public class ArrayList<E> extends AbstractList<E>implements List<E>
{
    public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!//每次调用add()会使modCount++
            elementData[size++] = e;
            return true;
        }
    public E get(int index) {
             rangeCheck(index);

            return elementData(index);
            }
    public Iterator<E> iterator() {
            return new Itr();
    }
    private class Itr implements Iterator<E> {

            int expectedModCount = modCount;
            //modCount为实际修改集合的次数
            //expectedModCount为预期修改集合的次数
            public E next() {
                checkForComodification();
                int i = cursor;
                if (i >= size)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i + 1;
                return (E) elementData[lastRet = i];
            }


            final void checkForComodification() {
                if (modCount != expectedModCount)
                //modCount为修改集合的次数，exceptedModCount为预期修改集合的次数
                    throw new ConcurrentModificationException();
            }
        }

        /**
}

源码很清楚了，而且我做了部分注释，可以自己捋一下。原因就是，我们采用迭代器的时候，迭代器会有一个预期的迭代次数，当我们进行在迭代的同时进行添加的时候会调用add()方法的话，就会modCount++（实际迭代次数）,但是expectedModCount（预期迭代次数）没有进行处理同步，造成了数据不一致，源码也说明了，如果不一致，就会抛出异常。 提出一种解决的办法，避免数据不一致，比如for循环。

package java_practice;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ListDemo {
    public static void main(String args[]) {

        List<String> list = new ArrayList<String>();
        list.add("Hello");
        list.add("world");
        list.add("java");
        Iterator<String> it = list.iterator();
//        while(it.hasNext()) {
//            String s = it.next();
//            if(s.equals("world"))
//            {
//                list.add("javaee");
//            }

    //
           //}
            for(int i=0;i<list.size();i++)
            {
                String s = list.get(i);
                if(s.equals("world"))
                {
                    list.add("javaee");
                }

            }
            System.out.println(list);


    }
}

可能在这里你可能有疑问，get()俩面不也有add()吗？为什么不报异常。上面源码也摘录出来了。原因就是我们调用了集合的add()方法，实际上会使实际迭代次数加一的，但是get()函数里面没有进行实际与预期的判断，也自然不会抛出异常，可以参考上诉源码，明明白白。

<3>ListIterator(列表迭代器)

List集合特有的迭代器 接口完整定义

public interface ListIterator<E>extends Iterator<E>

JDK API说明

系列表迭代器，允许程序员按任一方向遍历列表、迭代期间修改列表，并获得迭代器在列表中的当前位置。 演示一个使用

package java_practice;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class ListDemo {
    public static void main(String args[]) {

        List<String> list = new ArrayList<String>();
        list.add("Hello");
        list.add("world");
        list.add("java");
        Iterator<String> it = list.iterator();
//        while(it.hasNext()) {
//            String s = it.next();
//            if(s.equals("world"))
//            {
//                list.add("javaee");
//            }

    //
           //}
//
        ListIterator<String> lit = list.listIterator();
        while(lit.hasNext())
        {
            String s = lit.next();
            if(s.equals("world"))
            {
                lit.add("javaee");
            }
        }

        System.out.println(list);


    }
}

一个疑问就是为什么ListIterator没有报异常？ 我们还是追溯源码，最终整理如下

public interface List<E>{
Iterator<E> iterator();
ListIterator<E> listIterator();
boolean add(E e)
}

public abstract class AbstractList<E>
{
protected transient int modCount = 0;

}

public class ArrayList<E> extends AbstractList<E>implements List<E>
{
    public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!//每次调用add()会使modCount++
            elementData[size++] = e;
            return true;
        }
    public E get(int index) {
             rangeCheck(index);

            return elementData(index);
            }
    public Iterator<E> iterator() {
            return new Itr();
    }
    private class Itr implements Iterator<E> {
    public ListIterator<E> listIterator() {
            return new ListItr(0);
        }
}
private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
}

追诉到根本就是ListItr的add()方法。通过源码分析可以了解到，这里的add()方法在使用后会给预期的变量重新赋值，所以会使预期和实际的统一，这样就不会报异常了。

<4>增强for循环

还是从JDK API查找资料从Collection出发

public interface Collection<E>extends Iterable<E>

追溯Iterable,有理可依。

public interface Iterable<T>实现这个接口允许对象成为 "foreach" 语句的目标。

并且Iterable给出了其可使用的迭代器

Iterator iterator() 返回一个在一组 T 类型的元素上进行迭代的迭代器。

所以可以了解到增强for循环，简化数组和Collection集合的遍历。实现Iterable的类允许其对象成为增强型for循环语句的目标。版本在JDK5之后，内部实现原理是Iterator迭代器。 使用格式如下：

举例示范

int[] arr = {1,2,3,4,5};
        for(int i:arr)
        {
            System.out.println(i);
        }

        List<String> list = new ArrayList<String>();
        list.add("Hello");
        list.add("world");
        list.add("java");
        for(String s :list)
        {
            System.out.println(s);
        }

验证内部实现原理

如何验证内部实现原理是Iterator迭代器，通过Iterator迭代器迭代添加过程中的并发修改异常的特点来验证

   List<String> list = new ArrayList<String>();
        list.add("Hello");
        list.add("world");
        list.add("java");
        for(String s :list)
        {
            if(s.equals("java")){
                list.add("javaee");
            }
            System.out.println(s);
        }

异常信息摘录： Exception in thread “main” java.util.ConcurrentModificationException at java.util.ArrayList

Itr.checkForComodification(ArrayList.java:907) at java.util.ArrayList

Itr.next(ArrayList.java:857) at java_practice.ListDemo.main(ListDemo.java:15)

这里的异常和并发修改的异常一样，所以可以验证出内部实现原理是Iterator迭代器。也可以通过异常追溯源码来验证。

2：实现类LinkedList

基本的继承关系上，同ArrayList一样不是直接继承List接口，是一个实现类。 我们还是明确它的继承以及实现关系

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, Serializable

LinkedList的底层实现是链表，并且是双向链表。

与ArrayList相比，ArrayList的基本实现是数组，数组是便于进行查找的，而LinkedList的基本是实现双向链表是方便去进行增删改，但是不是很适合去随机查询。当然是和数组相比较。这个双向链表的顺序查找效率还是比较高的，因为是双向链表嘛！每个节点都有一个直接前驱和直接后继。前驱和后继可以认为是指针(C语言中的灵魂)。

<方法说明>

我们来看方法说明，其实很多方法还是和ArrayList的方法一样的。 add() addAll,clear(),clone(),contains(),get(),indexof(),lastIndexof(),remove(),set(),toArray()。基本上这几个方法都和ArrayList的方法使是一样的。 具体的看一些新的方法。我们分开说明

1：removeLastOccurrence(Object o) 从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时）。

 LinkedList link = new LinkedList<>();
        link.add("jgdabc");
        link.add("jink");
        link.add("jgdabc");
        System.out.println(link);
        link.removeLastOccurrence("jgdabc");
        System.out.println(link);

相应的一样道理 2：removeFirstOccurrence(Object o) 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。

 LinkedList link = new LinkedList<>();
        link.add("jgdabc");
        link.add("jink");
        link.add("jgdabc");
        System.out.println(link);
        link.removeFirstOccurrence("jgdabc");
        System.out.println(link);

3：removeLast() 移除并返回此列表的最后一个元素。改方法在移除的同时会返回移除的元素。

  link.removeFirstOccurrence("jgdabc");
        System.out.println(link);
        String s_s = (String) link.removeLast();
        System.out.println("移除元素后的集合："+link);
        System.out.println("被移除的元素:"+s_s);

同样， 4：removeFirst() 移除并返回此列表的第一个元素。不再举例 5：push(E e) 将元素推入此列表所表示的堆栈。此方法就是压栈的操作。 该方法的效果等同于addFirst() 对应还有 6:pop(E e) 出栈，此方法等效于removeFirst()

  link.push("jgdabc");
        System.out.println(link);
        link.pop();
        System.out.println(link);

7:pollLast() 获取并移除此列表的最后一个元素；如果此列表为空，则返回 null 8:pollFirst() 获取并移除此列表的第一个元素；如果此列表为空，则返回 null。 9：poll() 获取并移除此列表的头（第一个元素）

  String s_  = (String) link.pollLast();
        System.out.println(s);
        String s_1 = (String) link.pollFirst();
        System.out.println(s_1);
        String s_2 = (String) link.poll();
        System.out.print(s_2);

10：peekLast() 获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。 11：peekFirst() 获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。 12:peek() 获取但不移除此列表的头（第一个元素）。

String s_3 = (String) link.peekFirst();
        System.out.println(s_3);
        String s_4 = (String) link.peekLast();
        System.out.println(s_4);
        String s_5 = (String) link.peek();
        System.out.println(s_5);

13:offerLast(E e) 在此列表末尾插入指定的元素。 14:offerFirst(E e) 在此列表的开头插入指定的元素。 15:offer(E e) 将指定元素添加到此列表的末尾（最后一个元素）。

 boolean flag_f= link.offerFirst("jgdabc");
        System.out.println(flag_f);
        System.out.println(link);
        boolean baby = link.offerLast("baby");
        System.out.println(baby);
        System.out.println(link);
        boolean come_on = link.offer("come on");
        System.out.println(come_on);
        System.out.println(link);

14: Iterator descendingIterator() 返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。 具体的我们举个例子，看看这个逆向迭代器的使用，后面还会总结迭代方法

Iterator iterator = link.descendingIterator();
        while(iterator.hasNext())
        {
            System.out.println(iterator.next());

        }

vector已经废弃，不再叙述。至于为什么现在基本不用了，之后会写一篇专门详细介绍

四：Set集合

我们来看jdk API对Set集合的概述

一个不包含重复元素的 collection。更确切地讲，set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2，并且最多包含一个 null 元素。在所有构造方法以及 add、equals 和 hashCode 方法的协定上，Set 接口还加入了其他规定，这些规定超出了从 Collection 接口所继承的内容。出于方便考虑，它还包括了其他继承方法的声明（这些声明的规范已经专门针对 Set 接口进行了修改，但是没有包含任何其他的规定）。对这些构造方法的其他规定是（不要奇怪），所有构造方法必须创建一个不包含重复元素的 set（正如上面所定义的）。

Set集合完整定义 public interface Set extends Collection

Set集合是不允许重复元素的，并且是不保证存取顺序一致的。

1:实现类HashSet

哈希值浅说

哈希值是Jdk根据对象的地址或者字符串或者数字计算出来的int类型的数值。 Object类有方法可以获取到对象的哈希值 还是重JDK API去查找

int hashCode() 返回该对象的哈希码值。
代码举例

 TreeSet<Student> ts = new TreeSet<Student>();
        Student s1 = new Student(29, "西施");
        Student s2 = new Student(28, "王昭君");
        Student s3 = new Student(30, "貂蝉");
        Student s4 = new Student(33, "杨玉环");
        ts.add(s1);
        ts.add(s2);
        ts.add(s3);
        ts.add(s4);

        System.out.println("s1的哈希值:"+s1.hashCode());
        System.out.println("s2的哈希值:"+s2.hashCode());
        System.out.println("world的哈希值："+"world".hashCode());
        System.out.println("hello哈希值:"+"hello".hashCode());

<1 HashSet的数据结构

HashSet的数据结构实现在jdk1.8之前，哈希表=数组+链表，jdk1.8之后加入了红黑树。关于红黑树，后面再另起一篇文章叙述。 我们来看HashSet完整的类定义

public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, Serializable

我们具体看JDK API对该类的说明

此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。此类为基本操作提供了稳定性能，这些基本操作包括 add、remove、contains 和 size，假定哈希函数将这些元素正确地分布在桶中。对此 set 进行迭代所需的时间与 HashSet 实例的大小（元素的数量）和底层 HashMap 实例（桶的数量）的“容量”的和成比例。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

HashSet底层的实现 看了一下源码，原来底层的实现竟然是Map

public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * the specified initial capacity and the specified load factor.
     *
     * @param      initialCapacity   the initial capacity of the hash map
     * @param      loadFactor        the load factor of the hash map
     * @throws     IllegalArgumentException if the initial capacity is less
     *             than zero, or if the load factor is nonpositive
     */
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * the specified initial capacity and default load factor (0.75).
     *
     * @param      initialCapacity   the initial capacity of the hash table
     * @throws     IllegalArgumentException if the initial capacity is less
     *             than zero
     */
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

    /**

HashSet要保证没有重复元素，可能是这样的特性才要从Map那里分点基因吧。。

<2>方法说明

API给出了摘要的几个方法 add(),clear(),clone(),contains(),isEmpty(),iterator(),remove()这些方法的使用与上一样。

<1存储不重复

简要演示，来看一段代码

     HashSet s = new HashSet();
        s.add("jgdabc");
        s.add("hello");
        s.add("jgdabc");
        System.out.println(s);

可以看得出是保证了元素的不重复。 但是很多时候我们是操作对象的，如果我们把new()出来的对象添加进去，对象内部的属性还具有一样的值，那么HashSet能保证它的不重复性吗？示例验证一下

package java_practice;

import java.util.HashSet;

public class HashSetDemo2 {
    private String name;
    private int age;


    public void setName(String name) {
        this.name = name;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }


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

    public static void main(String args[])
    {
        HashSet<HashSetDemo2> s = new HashSet<HashSetDemo2>();
        HashSetDemo2  ha = new HashSetDemo2("jgdabc",19);
        HashSetDemo2 ha1 = new HashSetDemo2("jgdabc",19);
        HashSetDemo2 ha2 = new HashSetDemo2("li",20);
        s.add(ha);
        s.add(ha1);
        s.add(ha2);
        for(HashSetDemo2 ss : s )
        {
            System.out.println(ss.getName()+ss.getAge());
        }
//        s.add("jgdabc");
//        s.add("hello");
//        s.add("jgdabc");
//        System.out.println(s);


    }
}

可以看到虽然姓名和年龄都一样，但是都添加进去了。为什么？ 原因是因为我们添加的是对象，而对象的地址是不一样的。这里我们就可以引出HashSet如何判断元素唯一性的源码分析

很简单，那就从add()方法一路溯源

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

add这边又调用了put，所以我们去看put(HashMap的put) 好，找到了

   */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

put调用的是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;
    }

需要注意到的是，首先是比较hashcode值，进行一个判断，然后比较的是equals()方法。 具体比较流程

其实比较的首先是地址，我们上面每个new的对象的地址是不一样的，所以就直接存储进去了。不再比较值。那么如何根据值，来确保不存储同样的学生呢？这样做，重写HashCode和equals()方法。那我们现在修改上面的代码，保证存储的唯一性。

package java_practice;

import java.util.HashSet;
import java.util.Objects;

public class HashSetDemo2 {
    private String name;
    private int age;


    public void setName(String name) {
        this.name = name;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }


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

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        HashSetDemo2 that = (HashSetDemo2) o;
        return age == that.age &&
                Objects.equals(name, that.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    public static void main(String args[])
    {
        HashSet<HashSetDemo2> s = new HashSet<HashSetDemo2>();
        HashSetDemo2  ha = new HashSetDemo2("jgdabc",19);
        HashSetDemo2 ha1 = new HashSetDemo2("jgdabc",19);
        HashSetDemo2 ha2 = new HashSetDemo2("li",20);
        s.add(ha);
        s.add(ha1);
        s.add(ha2);
        for(HashSetDemo2 ss : s )
        {
            System.out.println(ss.getName()+ss.getAge());
        }
//        s.add("jgdabc");
//        s.add("hello");
//        s.add("jgdabc");
//        System.out.println(s);


    }
}

<2输出不保证无序

不一定任何情况输出都是无序的没我们可以参考这篇大佬的文章，很详细了。 深入分析——HashSet是否真的无序？（JDK8）说实话，这篇文章的探究性比较强，我在写本文这里取看这篇文章没有看到底。目前看的东西太多了，有点烦躁。其实当我们深入探究的化话，就会到内存，数据的位运算，与运算这些，以及优化原理，甚至还有一些函数，还要考虑内存的存放机制。 Hashset其它的方法没有什么特殊的。

<3> 哈希表浅说

我们从逻辑上最简单的理解这种存储结构 HashSet是通过链表加数组实现的。 那么我们给出16个位置，索引为 0-15。每次通过计算得出的哈希值是比较大的，我们不可能让哈希值作为索引下标。于是采用了取模也就是对16取余数，余数是多少就会存储到那个位置。不过在存储之前也就会进行判断，判断方法已经说明，不再赘述。如果存储到数组的同一个位置，后面就会采用在该位置进行链式存储。如上图。 HashSet的默认构造方法HashSet的默认初始容量为16

构造方法摘要 HashSet() 构造一个新的空 set，其底层 HashMap 实例的默认初始容量是 16，加载因子是 0.75

2:实现类LinkedHashSet

完整类定义 public class LinkedHashSetextends HashSetimplements Set, Cloneable, Serializable 通过类定义我们可以发现，LinkedHashSet是HashSet的继承类。并且实现了Set类。 LinkedHashSet是通过双向链表实现的。我们知道HashSet存取元素是无序的，LinkedHashSet采用双向链表，双向链表在逻辑存储上是连续的，所以LinkedHashSet是有序存储的。 JDKAPI 也有详细的说明 我们来看部分说明

具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现。此实现与 HashSet 的不同之外在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，即按照将元素插入到 set 中的顺序（插入顺序）进行迭代。注意，插入顺序不受在 set 中重新插入的元素的影响。（如果在 s.contains(e) 返回 true 后立即调用 s.add(e)，则元素 e 会被重新插入到 set s 中。）

<1>方法说明

JDK API给出了具体的继承的方法

从类 java.util.HashSet 继承的方法 add, clear, clone, contains, isEmpty, iterator, remove, size 从类 java.util.AbstractSet 继承的方法 equals, hashCode, removeAll 从类 java.util.AbstractCollection 继承的方法 addAll, containsAll, retainAll, toArray, toArray, toString 从类 java.lang.Object 继承的方法 finalize, getClass, notify, notifyAll, wait, wait, wait 从接口 java.util.Set 继承的方法 add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray

验证元素输出是否有序和唯一

package java_practice;

import java.util.LinkedHashSet;

public class LinkedHashSet_Demo {
    public static void main(String args[]){
        LinkedHashSet<String> lhs  = new LinkedHashSet<String>();
        lhs.add("Hello");
        lhs.add("world");
        lhs.add("Hello");
        lhs.add("every body");
        System.out.println(lhs);

    }
}

注：常用的方法，已经说过了。比较深入的，会在后面用到的时候说，比如finalize()还是有很大的学问的。

3:实现类TreeSet

在类的定义中尽管没有点出实现Set集合，但是直接溯源还是可以认为其是Set集合的一种 我们来看完整的类定义

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

//从AbstractSet溯源
public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {

所以我们也可以认为TreeSet实现了Set集合 JDK API 给出了TreeSet的部分说明

基于 TreeMap 的 NavigableSet 实现。使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的 Comparator 进行排序，具体取决于使用的构造方法。

当然还有其它的内容，但是文字凝聚太强，难以理解。 底层数据结构实现是红黑树，所以TreeSet存储的数据是有顺序的。 TreeSet集合的元素有序，按照一定的规则进行排序，具体的排序方式取决于采用的构造器，并且数还是不允许重复的。

<1>方法说明

<1>默认的自然排序方式（默认调用无参构造器）

举例直接上代码

   TreeSet<Integer> in = new TreeSet<>();
        in.add(10);
        in.add(20);
        in.add(30);
        in.add(5);
        in.add(4);
        //遍历集合
        for(Integer i :in)
        {
            System.out.println(i);
        }

<2>自然排序Comparable的使用

现在我要采用TreeSet对我设计的一个学生类进行一个自然排序，看看是否可以成功？

package java_practice;

import java.util.TreeSet;

public class TreeSetDemo {
    public static void main(String args[])
    {
        TreeSet<Student> ts = new TreeSet<Student>();
        Student s1 = new Student(29, "西施");
        Student s2 = new Student(28, "王昭君");
        Student s3 = new Student(30, "貂蝉");
        Student s4 = new Student(33, "杨玉环");
        ts.add(s1);
        ts.add(s2);
        ts.add(s3);
        ts.add(s4);
        for(Student s : ts)
        {
            System.out.println(s.getName()+""+s.getAge());
        }




    }
}

写代码感觉没问题，但是运行就出问题了

摘录出来

Exception in thread "main" java.lang.ClassCastException: java_practice.Student cannot be cast to java.lang.Comparable
	at java.util.TreeMap.compare(TreeMap.java:1294)
	at java.util.TreeMap.put(TreeMap.java:538)
	at java.util.TreeSet.add(TreeSet.java:255)
	at java_practice.TreeSetDemo.main(TreeSetDemo.java:13)

关键的一句

Exception in thread "main" java.lang.ClassCastException: java_practice.Student cannot be cast to java.lang.Comparable

说明了学生类是不能够转为Comparable这个接口的。为什么不可以？ 我们再去查看Comparable这个接口的说明

public interface Comparable此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，类的 compareTo 方法被称为它的自然比较方法。

那么我们的Student类需要去实现它

//Student 类
package java_practice;

public class Student implements Comparable<Student>{
    private int age;
    private String name;

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

    public void setAge(int age) {
        this.age = age;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public String getName() {
        return name;
    }

    @Override
    public int compareTo(Student s) {
        int num = this.age -s.age;
        return num;
        //return 0;
    }
}
//测试类
package java_practice;

import java.util.TreeSet;

public class TreeSetDemo {
    public static void main(String args[])
    {
        TreeSet<Student> ts = new TreeSet<Student>();
        Student s1 = new Student(29, "西施");
        Student s2 = new Student(28, "王昭君");
        Student s3 = new Student(30, "貂蝉");
        Student s4 = new Student(33, "杨玉环");
        ts.add(s1);
        ts.add(s2);
        ts.add(s3);
        ts.add(s4);
        for(Student s : ts)
        {
            System.out.println(s.getName()+""+s.getAge());
        }




    }
}

 public int compareTo(Student s) {
        int num = this.age -s.age;
        return num;
        //return 0;
    }

返回值，this放在前面就是升序排列，放在后面就是降序。如果你直接返回数字1的话，那么就顺序输出了。返回0的话，就只能输出一个元素。可以自己进行测试。

但是还有一个问题就是如果年龄相同的话，那么如果还要向集合中添加元素的话，那么是不会输出输出与前面对象年龄数据相同的后续对象的，那么我们可以添加条件。 具体还是操作CompareTo方法，稍微改一下。

 public int compareTo(Student s) {
        int num = this.age -s.age;
        int num2 = num == 0?this.name.compareTo(s.name):num;
        return num2;
}

这样就可以了。 那么你可能会有疑惑，为什么上面的Integer类型可以实现比较呢?因为Integer本身就实现了CompareTo方法，另外字符串也实现了这个方法。

<3>比较器Comparator的使用

我们可以使用比较器实现与自然排序一样的效果。 参考来源：JDK API

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

具体通过代码举例

//Student类
package java_practice;

public class Student {
    private int age;
    private String name;

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

    public void setAge(int age) {
        this.age = age;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public String getName() {
        return name;
    }

//    @Override
//    public int compareTo(Student s) {
//        int num = this.age -s.age;
//        int num2 = num == 0?this.name.compareTo(s.name):num;
//        return num2;
}
//测试类
package java_practice;

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetDemo1 {
    public static void main(String args[]) {
        TreeSet<Student> ts = new TreeSet<>(new Comparator<Student>() {
            @Override
            public int compare(Student s1, Student s2) {
                int num = s1.getAge() - s2.getAge();
                int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num;
                return num2;
            }
        });

        Student s1 = new Student(29, "西施");
        Student s2 = new Student(28, "王昭君");
        Student s3 = new Student(30, "貂蝉");
        Student s4 = new Student(33, "杨玉环");
        ts.add(s1);
        ts.add(s2);
        ts.add(s3);
        ts.add(s4);
        for (Student s : ts) {
            System.out.println(s.getName() + "" + s.getAge());
        }

    }
}

这里实现比较器，是通过匿名内部类实现了。 TreeSet的好多常规方法上面集合中都有包含，所以不再赘述。

后记：单列集合的相关总结一部分来自自己的查阅API方法尝试，一部分是课程笔记。基础比较多，作为学习记录。还有很多没有写进来的知识，如果想起。会添加进来。

文章三万字，内容可能比较杂乱，有不对的地方希望指正。文章一直更新，动态变换。记录的意义在于思维总结，后续的查看，同样为了分享，仅此而已。

访问主页

五：小应用

1：输入字符串统计其中各个字符出现的次数

package java_practice;

import java.util.HashMap;
import java.util.Scanner;
import java.util.Set;

//实现一个统计输入字符串中出现某字符的个数
public class HashMapDemo2 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入字符串");
        String line = sc.nextLine();
        //创建HashMap集合
        HashMap<Character, Integer> hm = new HashMap<>();
        for (int i = 0; i < line.length(); i++) {
            char key = line.charAt(i);
            Integer value = hm.get(key);
            if (value == null) {
                hm.put(key, 1);
            } else {
                value++;
                hm.put(key, value);
            }
        }
        StringBuilder sb = new StringBuilder();
        Set<Character> keyset = hm.keySet();
        for(Character  key:keyset)
        {
            Integer value = hm.get(key);
            sb.append(key).append("(").append(value).append(")");


        }
        String result = sb.toString();
        System.out.println(result);

    }
}

2：模拟斗地主发牌洗牌

–jgdabc(兰舟千帆)

版本一

package demo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class PokerDemo {
    public static void main(String[] args) {
        ArrayList<String> array = new ArrayList<>();
        //创建HashMap,键是编号，值是牌
        HashMap<Integer, String> hm = new HashMap<>();
        //创建ArrayList,存储编号

        //定义花色数组
        String[] colors = {"♦", "♥", "♣", "♠"};
        String[] numbers = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A"};
        //
        for (String color : colors)
            for (String number : numbers) {
                array.add(color + number);
    }
        array.add("小王");
        array.add("大王");
        //System.out.println(array);
        //进行洗牌
        Collections.shuffle(array);
        // System.out.println(array);
        //创建三个玩家
        ArrayList<String> lqx = new ArrayList<String>();
        ArrayList<String> ly = new ArrayList<>();
        ArrayList<String> fqy = new ArrayList<>();
        //创建底牌
        ArrayList<String> dp = new ArrayList<>();
        //进行发牌
        for (int i = 0; i < array.size(); i++) {
            String s = array.get(i);
            if (i >= array.size() - 3) {
                dp.add(s);
            } else if (i % 3 == 0) {
                lqx.add(s);

            } else if (i % 3 == 1) {
                ly.add(s);
            } else if (i % 3 == 2) {
                fqy.add(s);
            }
        }
        lookPoker("林青霞",lqx);
        lookPoker("柳岩",ly);
        lookPoker("风清扬",fqy);
        lookPoker("底牌",dp);
    }

        //看牌的方法
        public static void lookPoker(String name,ArrayList<String> array)
        {
            System.out.print(name + "的牌是:");
            for(String poker:array)
            {
                System.out.print(poker+" ");
            }
            System.out.println();
        }
        //存储编号

      
    //
    }

版本二

package demo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.TreeSet;

public class PokerDemo1 {
    public static void main(String args[]) {
        //创建HashMap,键是编号，值是牌
        HashMap<Integer, String> hm = new HashMap<Integer, String>();
        //创建ArrayList。存储编号
        ArrayList<Integer> array = new ArrayList<>();
        //创建花色数组和点数数组
        String[] colors = {"♦", "♥", "♣", "♠"};
        String[] numbers = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A"};
        //从零开始往HashMap中存储编号，并存储对应的牌，同时在ArrayList里面存储编号
        int index = 0;
        for (String number : numbers) {
            for (String color : colors) {
                hm.put(index, color + number);
                array.add(index);
                index++;
            }
        }
        hm.put(index, "小王");
        array.add(index);
        index++;
        hm.put(index, "大王");
        array.add(index);
        Collections.shuffle(array);
        //发牌，发的也是编号，为了保证编号是排序的，创建TreeSet集合接收
        TreeSet<Integer> lqx = new TreeSet<Integer>();
        TreeSet<Integer> ly = new TreeSet<Integer>();
        TreeSet<Integer> fqy = new TreeSet<Integer>();
        TreeSet<Integer> dp = new TreeSet<Integer>();
        for (int i = 0; i < array.size(); i++) {
            int x = array.get(i);
            if (i >= array.size() - 3) {
                dp.add(x);
            } else if (i % 3 == 0) {
                lqx.add(x);
            } else if (i % 3 == 1) {
                ly.add(x);

            } else if (i % 3 == 2) {
                fqy.add(x);
            }
        }

        lookPoker("林青霞", lqx, hm);
        lookPoker("柳岩", ly, hm);
        lookPoker("风清扬",fqy,hm);
        lookPoker("底牌",dp,hm);
    }

    //定义方法看牌（遍历TreeSet集合，获取编号，到HashMap找到对应的牌）
    public static void lookPoker(String name, TreeSet<Integer> ts, HashMap<Integer, String> hm) {
        System.out.println(name + "的牌是：");
        for (Integer key : ts) {
            String poker = hm.get(key);
            System.out.print(poker + " ");
        }
        System.out.println();
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-03-21，如有侵权请联系 cloudcommunity@tencent.com 删除

网站