【JavaGuide笔记】2.2 Java 集合

2020-03-31 本文已影响0人 linyk3

2.2 Java 集合

1.List、Set、Map 三者的区别

List：有序、不唯一
Set: 不允许重复，无序
Map：K-V键值对，Key不能重复

2.ArrayList VS LinkedList

特性	ArrayList	LinkedList
是否线程安全	线程不安全	线程不安全
底层数据结构	Object数组	双向链表
插入和删除是否受元素位置影响	add(E e) : O(1), add(int index, E e): O(n-i)	add(E d): O(1) add(int index, E e): O(n)
是否支持快速随机访问	支持随机访问	不支持随机访问：get(int index)
内存空间占用	空间浪费主要在列表结尾预留一定的容量空间	空间花费主要在每个元素需要额外的空间来维持双向链表

补充： RandomAccess 接口是一个标识接口。标识实现这个接口的类具有随机访问的功能。

list 遍历方式选择：

实现了RandomAccess 接口的list，优先选择普通for循环，其次是foreach.
未实现RandomAccess 接口的list，优先选择iterator 遍历。大size的数据，千万不要使用普通的for循环。（foreach 遍历底层也是通过iterator实现的）

补充：双向链表 VS 双向循环链表

双向链表：包含两个指针，prev 指向前一个节点，next指针指向后一个节点

image.png
双向循环链表：在双向链表的基础上，最后一个节点的next指向head，而head的prev指向最后一个节点，构成一个环。

image.png

3.ArrayList VS Vector，为什么要用ArrayList 取代 Vector

Vector 类的所有方法都是同步的，线程安全但是不高效。
ArrayList 不是同步的，不需要保证线程安全的时候建议使用ArrayList。

4. ArrayList 的扩容机制

ArrayList 三种初始化方式：

   /**
     * 默认初始容量大小
     */
    private static final int DEFAULT_CAPACITY = 10;
    

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     *默认构造函数，使用初始容量10构造一个空列表(无参数构造)
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * 带初始容量参数的构造函数。（用户自己指定容量）
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//初始容量大于0
            //创建initialCapacity大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//初始容量等于0
            //创建空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//初始容量小于0，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }


   /**
    *构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
    *如果指定的集合为null，throws NullPointerException。 
    */
     public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

调用无参构造方法来创建ArrayList时，实际上初始化赋值的是一个空数组。当真正往数组添加元素时，才真正分配容量，扩展为10.

ArrayList 扩容机制

1.add 方法

    /**
     * 将指定的元素追加到此列表的末尾。 
     */
    public boolean add(E e) {
   //添加元素之前，先调用ensureCapacityInternal方法
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //这里看到ArrayList添加元素的实质就相当于为数组赋值
        elementData[size++] = e;
        return true;
    }

2. ensureCapacityInternal() 方法

   //得到最小扩容量
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
              // 获取默认的容量和传入参数的较大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

当要 add 第1个元素时，minCapacity为1，在Math.max()方法比较后，minCapacity 为10。

3.ensureExplicitCapacity() 方法

  //判断是否需要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //调用grow方法进行扩容，调用此方法代表已经开始扩容了
            grow(minCapacity);
    }

我们来仔细分析一下：

当我们要 add 进第1个元素到 ArrayList 时，elementData.length 为0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal() 方法，所以 minCapacity 此时为10。此时，minCapacity - elementData.length > 0 成立，所以会进入 grow(minCapacity) 方法。
当add第2个元素时，minCapacity 为2，此时e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入（执行）grow(minCapacity) 方法。
添加第3、4···到第10个元素时，依然不会执行grow方法，数组容量都为10。
直到添加第11个元素，minCapacity(为11)比elementData.length（为10）要大。进入grow方法进行扩容。

4.grow()

    /**
     * 要分配的最大数组大小
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * ArrayList扩容的核心方法。
     */
    private void grow(int minCapacity) {
        // oldCapacity为旧容量，newCapacity为新容量
        int oldCapacity = elementData.length;
        //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
        //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
       // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
       //如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
        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);
    }

int newCapacity = oldCapacity + (oldCapacity >> 1),
所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity为偶数就是1.5倍，否则是1.5倍左右）！奇偶不同，比如：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.

5.hugeCapacity() 方法。

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //对minCapacity和MAX_ARRAY_SIZE进行比较
        //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
        //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
        //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

补充

这里补充一点比较重要，但是容易被忽视掉的知识点：

java 中的 length 属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性.
java 中的 length() 方法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个方法.
java 中的 size() 方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!

System.arraycopy() 和 Arrays.copyOf()方法

add(int index, E element)用到了System.arraycopy()方法

    /**
     * 在此列表中的指定位置插入指定的元素。 
     *先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大；
     *再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //arraycopy()方法实现数组自己复制自己
        //elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index + 1：目标数组中的起始位置； size - index：要复制的数组元素的数量；
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

toArray() 方法用到了 Arrays.copyOf()

/**
     以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; 返回的数组的运行时类型是指定数组的运行时类型。 
     */
    public Object[] toArray() {
    //elementData：要复制的数组；size：要复制的长度
        return Arrays.copyOf(elementData, size);
    }

ArrayList.copyOf() 内部实际调用的也是 System.arraycopy() 方法。

ensureCapacity方法

ensureCapacity方法没有在ArrayList 内部调用过，是提供给用户调用的，这样就可以提前根据用户所需数组的大小初始化，以减少增量重新分配的次数。

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        list = new ArrayList<Object>();
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(N);
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法后："+(endTime1 - startTime1));
    }
}

向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法，以减少增量重新分配的次数。

5. HashMap VS HashTable

特性	HashMap	HashTable
是否安全	非线程安全	线程安全(synchronized)
效率	比HashTable 高	慢，基本被淘汰了，不推荐使用HashTable
Null key Null value	允许一个键为null，允许多个值为 null	不允许key或value为null，否则会抛出 NullPointerException
初始容量/每次扩充容量	默认是16，扩充为2n，如果指定容量，会将其扩充为2的幂次大小	默认是11，扩充为2n+1，如果指定容量直接使用
底层数据结构	数组+链表（1.8后红黑树）	数组+链表

6. HashMap VS HashSet

HashSet 底层是基于HashMap实现的。

HashMap	HashSet
实现了Map接口	实现了Set接口
存储键值对	仅存储对象
put() 添加元素	add() 添加元素
使用Key计算hashcode	使用成员对象来计算hashcode，如果hashcode相同，再用equals() 方法来判断对象的相等性

7. HashSet 如何检查重复

当把对象加入HashSet时，会先计算对象的hashcode来判断对象加入的位置，同时也会和其他已加入的对象的hashcode做比较，如果没有相符的hashcode，则说明没有重复对象。如果发现相同的hashcode，就会调用equals()判断对象是否真的相等。

hashCode() 和 equals() 的规定：

1.如果两个对象相等，则hashcode一定也是相同的；
2.如果两个对象相等，则equals() 比较结果为true；
3.如果两个对象的hashcode相等，但这两个对象不一定是相等的；
4.综上，equals() 方法被重写，则 hashCode() 也必须被重写；
1. hashCode() 默认是对堆上的对象产生独特值。如果没有重写hashCode(), 即使两个对象的内容一样，也不会相等。

8. HashMap 底层实现

JDK 1.8 之前

JDK1.8之前，HashMap的底层是数组+链表，也就是链表散列。HashMap通过key的hashcode 经过扰动函数处理过后得到hash值，然后通过(n-1)&hash判断当前元素存放的位置。如果当前位置存在元素，就比较hash值和key是否相同，如果相同，直接覆盖；如果不相同，通过拉链法解决冲突。
扰动函数可以减少冲突的发生。
JDK1.8 的hash方法：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h == key.hashcode()) ^ (h >>> 16);
}

JDK1.7 的hash方法：

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) & (h >>> 4);
}

相比于JDK1.8的hash方法，JDK1.7的hash方法性能稍差一点，毕竟扰动了4次。

JDK 1.8 之后

当链表长度大于阈值（默认是8）时，将链表转化为红黑树，以减少搜索时间。

image.png

TreeMap、TreeSet 以及 JDK1.8 之后的HashMap 底层都用到了红黑树。主要是为了解决二叉查找树某些情况会退化成一个线性结构。

9. HashMap 的长度为什么是 2 的幂次方

让HashMap 存取高效，尽量减少碰撞，把数据分配均匀。
Hash 值的范围是 -2147483684~2147483647，总共40亿个映射空间。内存是放不下一个40亿长度的数组的，所有需要对长度取模运算。取模的% 方法太慢，并且当除数是2的幂次方时，满足 hash%length==hash&(length-1)，所以快速方法是：(n - 1) & hash,所以长度要求是2的幂次方。

10. HashMap 多线程操作导致死循环

主要原因是并发下 ReHash 会造成元素之间形成一个循环链表。JDK1.8 已修复，但并发下还是会存在其他问题，例如数据丢失，所以并发环境下推荐使用 ConcurrentHashMap。
参考:https://coolshell.cn/articles/9606.html

11. ConcurrentHashMap VS HashTable

ConcurrentHashMap 和 HashTable 的区别主要体现在实现线程安全的方式上不同。

底层数据结构：JDK1.7的ConcurrentHashMap 底层采用分段的数组+链表。 JDK1.8 采用数组+链表/红黑树。
实现线程安全的方式：JDK1.7 ConcurrentHashMap（分段锁）对整个桶数组进行了分割分段，每一把锁只锁容器中其中一部分数据。多线程访问容器里不同数据段就不会产生锁竞争，提高并发访问率。 JDK1.7 时ConcurrentHashMap 摒弃分段锁Segment概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用synchronized和 CAS 来操作。（JDK1.6 以后对 synchronized锁做了很多优化）整个看起来就像是优化过且线程安全的HashMap，虽然在JDK1.8 还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本。 HashTable(同一把锁)：使用synchronized来保证线程安全，效率非常低下。但多个线程访问同步方法时，会进入阻塞或轮询状态，如果一个线程使用put添加元素，另一个线程不能使用put，也不能使用get。

参考:ConcurrentHashMap实现原理及源码分析

image.png

JDK1.7�ConcurrentHashMapήA

12. ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

JDK1.7 ConcurrentHashMap
首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

static class Segment<K,V> extends ReentrantLock implements Serializable {
        private static final long serialVersionUID = 2249069246763182397L;
        static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
        // 数据节点存储在这里(基础单元是数组)
        transient volatile HashEntry<K,V>[] table;
        transient int count;
        transient int modCount;
        transient int threshold;
        final float loadFactor;
}

static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;
}

image.png

JDK1.8 ConcurrentHashMap
ConcurrentHashMap 取消了分段锁 Segment，采用了CAS 和 synchronized 来保证并发安全。数据结构与HashMap 1.8 结构类似，数组+链表/红黑树。 Java 8 在链表长度超过一定阈值（8）时，将链表(寻址时间复杂度O(N))转换为红黑树(O(log(N))）
synchronized 只锁定当前链表或红黑树的首节点，这样只要hash不冲突，就不会阻塞，效率提高N倍。

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {
    private static final long serialVersionUID = 7249069246763182397L;

//...

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
        // ...
    }

    static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
    }

    static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }

    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }

 public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        int h = spread(key.hashCode());
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

/** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }
}

13. comparable VS comparator

comparable：接口实际上是出自java.lang包，它有一个compareTo(Object obj) 的方法用来排序
comparator：接口实际是出自java.util包，它有一个compare(Object obj1, Object obj2) 方法用来排序。

Collections.sort(arrayList, new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
          return o2.compareTo(o1);
      }
});


public class Person implements Comparable<Person> {
      // ...
     @Override
     public int compareTo(Person o) {
          if(this.age > o.getAge()) {
              return 1;
          } else if (this.age < o.getAge()) {
              return -1;
          }
          return age;
     } 
}

14. 集合框架底层数据结构总结

Collection

1.List

ArrayList：Object 数组
Vector： Object 数组
LinkedList：双向链表（JDK1.6为循环链表，JDK1.7取消循环）

2.Set

HashSet（无序，唯一）：基于HashMap 实现，底层采用HashMap来保存元素
LinkedHashSet： LinkedHashSet 继承于HashSet，内部是通过LinkedHashMap来实现的。
TreeSet（有序，唯一）：红黑树

3.Map

HashMap：JDK1.7 数组+链表， JDK1.8 数组+链表/红黑树(8)
LinkedHashMap：LinkedHashMap 继承自HashMap，在数组+链表/红黑树的基础上，增加了一条双向链表。
HashTable：数组+链表
TreeMap：红黑树

15. 如何选用集合

键值对 => Map 接口
- 排序 => TreeMap
- 不需要排序 => HashMap
- 线程安全 => ConcurrentHashMap
存放 => Collection
- 唯一 => Set(TreeSet/HashSet)
- 不唯一 => ArrayList/LinkedList

16. 补充：Collection 和 Collections 的区别

Collection 接口

java.util.Colletion
是集合框架的父接口，提供了集合对象基本操作的通用接口方法。Collection 存在的意义就是为各种具体的集合提供了最大化的统一操作方式。

public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    boolean retainAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
}

Collections 工具类

java.util.Collections
是一个包装类，包含各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于Java的Colletion 框架。提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。

1. 排序 Collections.sort(list)

        Integer nums[] = {1,4,5,7,3,6,3,4,544,33};
        List list = Arrays.asList(nums);
        Collections.sort(list);
        // [1, 3, 3, 4, 4, 5, 6, 7, 33, 544]
        System.out.println(list.toString());

2.随机排序 Collections.shuffle(list)

    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,3,4,544,33};
        List list = Arrays.asList(nums);
        Collections.shuffle(list);
        // [6, 3, 3, 7, 4, 5, 544, 1, 4, 33]
        System.out.println(list.toString());
    }

1. 反转 Collections.reverse(list)

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,3,4,544,33};
        List list = Arrays.asList(nums);
        Collections.sort(list);
        // [1, 3, 3, 4, 4, 5, 6, 7, 33, 544]
        System.out.println(list.toString());
        Collections.reverse(list);
        [544, 33, 7, 6, 5, 4, 4, 3, 3, 1]
        System.out.println(list.toString());
    }
}

1. 替换所有元素 Collections.fill(list, 0)

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,3,4,544,33};
        List list = Arrays.asList(nums);
        Collections.fill(list, 3);
        // [3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
        System.out.println(list.toString());
    }
}

1. 拷贝 Collections.copy(newList, list)

public class Test {
    public static void main(String[] args) {
        List<Integer> list =  new ArrayList();
        list.add(1);
        list.add(3);
        List<Integer> newList = new ArrayList();
        newList.add(4);
        newList.add(5);
        //newList 长度要求大于等于 list
        Collections.copy(newList, list);
        System.out.println(list.toString());  //[1, 3]
        System.out.println(newList.toString()); //[1, 3]
    }
}

1. 最大/小元素 Collections.min(list) / Collections.max(list)

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,3,4,544,33};
        List<Integer> list =  Arrays.asList(nums);
        System.out.println(Collections.min(list));  // 1
        System.out.println(Collections.max(list)); // 544
    }
}

1. 源列表中第一次/最后一次出现目标列表的起始位置

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,3,4,3,6,544,33};
        Integer temp[] = {3,6};
        List<Integer> list = Arrays.asList(nums);
        List<Integer> dest = Arrays.asList(temp);
        System.out.println(Collections.indexOfSubList(list,dest));  // 4
        System.out.println(Collections.lastIndexOfSubList(list, dest)); // 8
    }
}

1. 循环移动列表中的元素 Collections.rotate(list,4)

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,3,4,3,6,544,33};
        List<Integer> list = Arrays.asList(nums);
        Collections.rotate(list,4); // 右移 4 位
        System.out.println(list.toString()); // [3, 6, 544, 33, 1, 4, 5, 7, 3, 6, 3, 4]
        Collections.rotate(list,-2); // 左移 2 位
        System.out.println(list.toString()); // [544, 33, 1, 4, 5, 7, 3, 6, 3, 4, 3, 6]
    }
}

17. 补充：5 种方法输出 List

1. 直接输出list（要求是Java 已有的类）

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,544,33};
        List list = Arrays.asList(nums);
        System.out.println(list.toString()); // [1, 4, 5, 7, 3, 6, 544, 33]
    }
}

1. 增强for循环

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,544,33};
        List<Integer> list = Arrays.asList(nums);
        for(Integer i : list) {
            System.out.println(i);
        }
    }
}

1. 下标for 循环

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,544,33};
        List<Integer> list = Arrays.asList(nums);
        for(int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

1. iterator 遍历

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,544,33};
        List<Integer> list = Arrays.asList(nums);
        Iterator iterator = list.iterator();
        while(iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

1. Java 8 Lambda 表达式

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,544,33};
        List<Integer> list = Arrays.asList(nums);
        list.forEach(item -> System.out.println(item));
    }
}

1. Java 8 ForEach

public class Test {
    public static void main(String[] args) {
        Integer nums[] = {1,4,5,7,3,6,544,33};
        List<Integer> list = Arrays.asList(nums);
        list.forEach(new Consumer<Integer>() {
            @Override
            public void accept(Integer integer) {
                System.out.println(integer);
            }
        });
    }
}

18. 补充：3种方法打印一维数组

定义一个数组：

int[] nums = {1,2,3,4}

1. 下标for循环

for(int i = 0; i < nums.length; i++) {
    System.out.println(nums[i]);
}

1. 增强for循环

for(int a : nums){
    System.out.println(a);
}

1. Arrays.toString(int[] nums)

System.out.println(Arrays.toString(nums)); // [1,2,3,4]
System.out.println(nums); // 这样打印出来的是数组的首地址

19. 补充：3种方法打印二维数组

Java 实际没有二维数组的概念，只有一维数组。多维数组被解读为“数组的数组”。所以对二维数组的操作也是将多维拆解为一维数组，然后进行操作。

int[][] matrix = {
  {1,2,3},
  {4,5,6}
};

这里 matrix.length = 2; matrix[0].length = 3;

1.下标for循环

for(int i =0; i < matrix.length; i++) {
    for(int j = 0; j < matrix[i].length; j++) {
        System.out.print(matrix[i][j] + " ");
    }
    System.out.println();
}

2.增强for循环

for(int[] arr : matrix) {
    for(int num : arr) {
        System.out.print(num + " ");
    }
    System.out.println();
}

3.Arrays.toString()

for(int i = 0; i < matrix.length; i++) {
    Systen.out.println(Arrays.toString(matrix[i]));
}

【JavaGuide笔记】2.2 Java 集合

2.2 Java 集合

1.List、Set、Map 三者的区别

2.ArrayList VS LinkedList

3.ArrayList VS Vector， 为什么要用ArrayList 取代 Vector

4. ArrayList 的扩容机制

ArrayList 三种初始化方式：

ArrayList 扩容机制

1.add 方法

2. ensureCapacityInternal() 方法

3.ensureExplicitCapacity() 方法

4.grow()

5.hugeCapacity() 方法。

补充

System.arraycopy() 和 Arrays.copyOf()方法

ensureCapacity方法

5. HashMap VS HashTable

6. HashMap VS HashSet

7. HashSet 如何检查重复

hashCode() 和 equals() 的规定：

8. HashMap 底层实现

JDK 1.8 之前

JDK 1.8 之后

9. HashMap 的长度为什么是 2 的幂次方

10. HashMap 多线程操作导致死循环

11. ConcurrentHashMap VS HashTable

12. ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

13. comparable VS comparator

14. 集合框架底层数据结构总结

Collection

1.List

2.Set

3.Map

15. 如何选用集合

16. 补充：Collection 和 Collections 的区别

Collection 接口

Collections 工具类

17. 补充：5 种方法输出 List

18. 补充：3种方法打印一维数组

19. 补充：3种方法打印二维数组

猜你喜欢

热点阅读

3.ArrayList VS Vector，为什么要用ArrayList 取代 Vector