Java 基础篇学习 集合框架List与Set

List与Set

• • List
  • • List简介
    • ArrayList 初始化源码简要分析
    • LinkedList 初始化源码简要分析
    • List接口中的常用方法
  • Set
  • • Set简介

List

List简介

    |-- Collection接口：单列集合，用了存储一个一个的对象
        |— List接口：存储有序的、可重复的数据，–>“动态数组”，替换原有数组
            |------ArrayList 作为List接口的主要实现类;线程不安全，效率高;底层使用的是 Object[] elementData
            |------LinkedList 对于频繁的插入、删除操作，使用LinkedList的效率比ArrayList高;底层使用的是双向链表
            |------Vector 作为List接口的古老实现类，比List出现早;线程安全的，效率低;底层使用的是 Object[] elementData
     ArrayList、LinkedList、Vector 的相同点：三个类都实现了List接口，存储数据的特点相同：存储有序的，可重复的数据，不同点见上，还有一点不同 扩容时，ArrayList扩容为原来容量的1.5倍，Vector扩容为原来的两倍

// Vector 的初始化默认长度为10的数组
public Vector() {
        this(10);
    }
public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
// Vector 的扩容
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 默认情况下 扩容为原来的2倍
        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);
    }
// ArrayList 的扩容
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 这行代码是往右移一位 比如 二进制 10101 变为 1010 效率高于  x/2
        // 从这里也证明了若是大致知道ArrayList的长度应该在初始化直接给定ArrayList的长度
        // 每次扩容都会Arrays.copyOf()效率会受到一点影响
        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 初始化源码简要分析

    JDK7 中的 ArrayList
    ArrayList list = new ArrayList<>(); 调用空参构造器，初始化一个长度为 10 的Object类型的数组 this.elementData = new Object[initialCapacity]，list.add(1); elementData[0] = new Integer(11);…list.add(11);// 如果此次的添加导致底层elementData数组容量不够，则扩容。默认情况下，扩容为原来容量的1.5倍，同时需要将原有数组中的数组copy到新的数组中。(抛弃旧的创建新的)。结论：建议使用带参数的初始化构造器时，如果大致确定数组长度 public ArrayList(int initialCapacity) ，给定list的长度，避免多次扩容
    JDK8 中的 ArrayList
    ArrayList list = new ArrayList<>();调用空参构造器，的Object类型的数组 Object [] elementData 初始化为{} 并没有创建长度为10的数组，list.add(1);第一次调用add方法，此时底层才创建了长度为10的数组，并将元素添加到elementData数组，后续操作与JDK7基本相似。
    总结：JDK7中的ArrayList的对象的创建 类似于单列模式中的饿汉式，而JDK8中的ArrayList的对象的创建，类似于单例模式中的懒汉式，延迟了数组的创建，一定程度上节省内存。

LinkedList 初始化源码简要分析

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;
    // LinkedList 数据存储的基本单位是 Node
    transient Node<E> first; // LinkedList的第一个元素 内部声明 默认指为null
    
    transient Node<E> last;// LinkedList的当前最后一个元素
    public LinkedList() {
    }
    // LinkedList add 方法 添加元素 不涉及数组 无需扩容
	public boolean add(E e) {
        linkLast(e);
        return true;
    }
    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last; // LinkedList当前最后一个元素 首次调用时 为 null
        final Node<E> newNode = new Node<>(l, e, null); // 新建一个 node
        last = newNode; // newNode赋值给当前类的最后一个元素
        if (l == null) // 如果l是null 当前元素就是第一个元素 也是最后一个元素
            first = newNode;
        else	// 否则 l 指向的下一个元素 就是当前元素
            l.next = newNode;
        size++; // 长度 ++ 
        modCount++;
    }
    // LinkedList的内部类 Node<E> 的定义 可以说明LinkedList 是双向链表 指向上一个还指向下一个
	private static class Node<E> {
        E item;		// 当前元素核心数据
        Node<E> next; // 指向下一个元素
        Node<E> prev; // 指向上一个元素
		// 初始化Node时的参数  前一个元素 当前数据 后一个元素
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

List接口中的常用方法

	@Test
    public void test1(){
        ArrayList<String> list = new ArrayList<String>(){{
            add("123");
            add("test");
            add("456");
            add("123");
            add("Tom");
        }};
        System.out.println(list);
        // 在index位置插入元素
        list.add(1,"Jerry");
        System.out.println(list);
        // 从 index 位置开始，将Collection 中所有的元素插入进去
        Collection<String> coll = new HashSet<String>(){{
            add("TXT");
            add("IMG");
        }};
        list.addAll(1,coll);
        System.out.println(list);
        System.out.println(list.size());
        // 获取指定index位置的元素
        System.out.println(list.get(1));
        // 获取元素在集合中首次出现的位置
        System.out.println(list.indexOf("123"));
        System.out.println(list.indexOf("1234"));// 不存在返回 -1
        // 获取元素在集合中最后一次出现的位置
        System.out.println(list.lastIndexOf("123"));
        // 移除指定index位置的元素，并将此元素返回
        System.out.println(list.remove(1)); // 本身重载的方法
        // 按照对象去移除 
        boolean tom = list.remove("TOM"); // 重写的 Collection 中的remove() 方法
        System.out.println(tom);
        // 设置index位置为指定元素
        System.out.println(list.set(1,"PUBLIC"));
        // subList(int fromIndex,int toIndex) 获取fromIndex 到 toIndex 位置的子集合
        List<String> subList = list.subList(1, 4);
        System.out.println(subList);
    }
    /**
     * 总结常用方法
     * 增：boolean add(E e) 末尾增加
     * 删：boolean remove(Object o) / E remove(int index)
     * 改：E set(int index, E element)
     * 查：E get(int index)
     * 插入：void add(int index, E element)
     * 长度：int size()
     * 遍历：1、Iterator 迭代器 2、forech 3、fori
     */
    @Test
    public void test2() {
        ArrayList<String> list = new ArrayList<String>() {{
            add("123");
            add("test");
            add("456");
            add("123");
            add("Tom");
        }};
        // iterator 迭代器方式遍历
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        System.out.println("---------------------");
        // foreach 遍历
        for (String str : list) {
            System.out.println(str);
        }
        System.out.println("---------------------");
        list.forEach(System.out::println);
        // list.forEach(item-> System.out.println(item));
        System.out.println("---------------------");
        // 普通for 循环遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }

Set

Set简介

    Set接口是Collection的子接口，Set接口没有提供额外的方法。
    Set集合不允许包含相同的元素，如果尝试两个相同的元素加入同一个Set集合中，添加操作失败。
    Set判断两个对象是否相同使用的不是==运算符，而是equals()方法。
    HashSet

/**
 * 1、Set接口框架
 *      ｜-- Collection接口：单列集合，用来存储一个一个的对象
 *          ｜---Set 接口：存储无序的、不可重复的数据
 *              ｜----HashSet：作为Set接口的主要实现类；线程不安全的；可以存储null值
 *                  ｜-----LinkedHashSet：HashSet的子类；遍历内部数据时，可以按照添加的顺序遍历
 *              ｜----TreeSet：可以按照添加对象的指定属性进行排序
 * 2、Set接口没有额外定义的新方法，使用的都是Collection中声明过的方法
 * 3、理解 无序和不可重复
 *      以HashSet为例
 *      3.1 无序性：不等于随机性；无序性是对比List的有序性；
 *          3.1.1 存储的数据在底层数组中，并非按照数组索引的顺序添加，而是根据数据的哈希值决定的
 *      3.2 不可重复性：
 *          3.2.1 本质上还是拿equals() 方法比较，也就是保证添加的元素根据equals()方法判断时 
 * 				不能返回 true
 *
 *
 * 4、Set中添加元素的简要过程->以HashSet为例
 *     4.1 向HashSet中添加元素a，首先调用元素a所在类的HashCode,计算元素a的哈希值。
 *     4.2 此哈希值通过散列算法计算出在HashSet底层数组中的存放位置(即为索引位置)
 *     4.3 判断数组此位置上是否已经有元素：
 *      4.3.1 如果此位置上没有其他元素，元素a添加成功                      --->成功情况1
 *      4.3.2 如果此位置上已经有元素b(或者以链表形式存在的多个元素),比较元素a与元素b的哈希值
 *            4.3.2.1 如果哈希值不同，元素a添加成功                       --->成功情况2
 *            4.3.2.2 如果哈希值相同 调用元素a所在类的equals()方法
 *              4.3.2.2.1 equals()方法返回true 元素a添加失败
 *              4.3.2.2.2 equals()方法返回false 元素a添加成功             --->成功情况3
 *       对于添加成功的情况2和成功情况3：元素a 与已经存在指定索引位置上的数据以链表的方式存储
 * 	(JDK8中链表长度大于8将会转换为红黑树结构存储)
 *       JDK7中：元素a放到数组中指向原来的元素
 *       JDK8中：原来的元素还在数组中，指向元素a
 */

     重写hashCode() 和 equals() 方法

@Getter
@Setter
@ToString
@NoArgsConstructor
@AllArgsConstructor
class Student {

    private Integer no;

    private String name;
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Student student = (Student) o;

        if (!no.equals(student.no)) return false;
        return name.equals(student.name);
    }

    /**
     * 重写hashCode()方法 会有31数字出现，原因有：
     * 1、选择系数的时候，需要选择尽量大的系数。因为计算出来的hash地址值越大，
     		所谓的"冲突"就会越小，查找起来的效率会提高。(减少冲突)
     * 2、31只占用了5bits，相乘计算出结果数据溢出的概率降低
     * 3、a*31可以等同于 (a<<5)-a来表示，也就是a*31 == ((a<<5)-a) 
     	     现在很多虚拟机里面都有相关优化(提高算法效率)
     * 4、31是一个素数，素数与另外一个数字相乘，那么最终结果只能被这个素数本身和被乘数还有1整除
     	   ，目的也是减少冲突
     */
    @Override
    public int hashCode() {
        int result = no.hashCode();
        result = 31 * result + name.hashCode();
        return result;
    }
}

    建议：向Set添加数据是，数据所在的类一定要重写hashCode() 和 equals() 方法，重写的hashCode() 和 equals() 方法尽可能保持一致性：相等的对象必须具有相等的散列码。
    重写hashCode()方法的基本原则
    1、在程序运行时，同一个对象多次调用hashCode()方法，应该返回相同的值。
    2、当两个对象equals()方法比较返回true时，这两个对象的hashCode()方法返回值必须相等。
    3、对象中用于equals()方法比较的Field(属性)，都应该用来计算hashCode值。
    LinkedHashSet

/**
     * LinkedHashSet 是 hashSet的子类，在添加数据的同时，每个数据还维护了两个引用，
     * 记录此数据 前一个数据和后一个数据。
     * 优点，对于频繁的遍历操作，LinkedHashSet效率高于hashSet。
     */
    @Test
    public void test1() {
        LinkedHashSet<String> hashSet = new LinkedHashSet<String>() {{
            add("123");
            add("789");
            add("456");
            add("123");
        }};
        System.out.println(hashSet);
    }

    TreeSet

    /**
     * 1、向TreeSet中添加数据，要求是相同类的对象 采用的是红黑树的存储结构 特点是有序，查询速度比List快
     * 2、两种排序方式 自然排序和定制排序
     * 2.1 自然排序中，比较两个对象是否相同的标准为compareTo() 方法返回值是不是 0 不再是equals()方法
     * 2.2 定制排序 比较两个对象是否相同的标准为compare() 方法返回值是不是 0 不再是equals()方法
     */
    @Test
    public void testTreeSet() {
        // TreeSet添加元素 调用  Integer.compare() 方法
        TreeSet<Integer> set = new TreeSet<Integer>() {{
            add(3);
            add(9);
            add(8);
            add(1);
            add(2);
        }};
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        System.out.println("-----------------------");
        // 自然排序 自定义类Y需要实现Comparable接口 并重写 compareTo()方法
        TreeSet<Y> treeSet = new TreeSet<Y>() {{
            add(new Y("Tom", 12));
            add(new Y("Jerry", 5));
            add(new Y("Sandy", 33));
            add(new Y("Mack", 22));
            add(new Y("Tom", 32));
        }};
        treeSet.forEach(System.out::println);
        System.out.println("-----------------------");
        // 定制排序
        // 原始写法
//        Comparator<Y> comparator = new Comparator<Y>() {
//            @Override
//            // 按照年龄从小到大排序 年龄一致 舍弃该元素
//            public int compare(Y y1, Y y2) {
//                return Integer.compare(y1.age, y2.age);
//            }
//        };
        // Java 8 写法
        Comparator<Y> comparator = Comparator.comparingInt(y -> y.age);
        TreeSet<Y> yTreeSet = new TreeSet<Y>(comparator) {{
            add(new Y("Tom", 12));
            add(new Y("Sandy", 32));
            add(new Y("Mack", 22));
            add(new Y("Jerry", 5));
            add(new Y("Tom", 32)); // Tom将会被舍弃
        }};
        yTreeSet.forEach(System.out::println);

    }

    @Getter
    @Setter
    @NoArgsConstructor
    @AllArgsConstructor
    @EqualsAndHashCode
    @ToString
    static class Y implements Comparable<Object> {

        private String name;

        private Integer age;


        @Override
        public int compareTo(Object o) {
            if (o instanceof Y) {
                Y y = (Y) o;
                // 仅按照姓名从小到达排序 出现一样的姓名仅能出现一次，
                // TreeSet判断两个元素是否一致的标准是 根据compareTo()方法返回的值是不是0
                //return this.name.compareTo(y.name);
                // 先根据姓名从小到达排序，然后根据 年龄从小到大排序
                int compare = this.name.compareTo(y.name);
                if (compare != 0) {
                    return compare;
                } else {
                    return Integer.compare(this.age, y.age);
                }
            } else {
                throw new RuntimeException("类型转换异常");
            }
        }
    }

本文地址：https://blog.csdn.net/GayFei/article/details/109572085