Java的第十二篇文章——JAVA集合（上）-阿里云开发者社区

第十二章集合

学习目标

认识集合框架
List集合的结构
ArrayList集合使用
ArrayList源码解析
LinkedList集合使用
LinkedList源码解析
对象的哈希值
哈希表数据结构
Collections工具类
了解泛型及其定义
哈希表确定对象唯一性
HashSet源码解析
红黑树结构Red/Black Tree Visualization
对象的自然顺序与比较器

1. 集合框架的由来

JDK1.2版本后，出现这个集合框架，到JDK1.5后，大幅度优化。

集合本质上是存储对象的容器
数组也能存储对象，数组弊端就是定长
解决数组的问题,开发出来集合框架，集合框架无需考虑长度
集合和数组的区别与共同点

集合，数组都是容器，都可以存储数据
集合只存储引用数据类型，不存储基本数据类型（如int，就会换成包装类Integer）
数组可以存储基本类型，也可以存储引用类型
数组定长，集合容器变长

牢记：数据多了存数组，对象多了存集合

集合学习的关键点

怎么存储数据
怎么取出数据
选择哪种容器

2. 集合框架的继承体系

3. Collection接口

是所有单列集合的顶级接口，任何单列集合都是他的子接口，或者是实现类，该接口中定义的方法，是所有单列集合的共性方法。

Collection<E> 尖括号就是泛型，E我们要写,集合存储的数据类型

3.1 Collection接口的常用方法

方法的定义	方法作用
boolean add(E)	元素添加到集合
void clear()	清空集合容器中的元素
boolean contains(E)	判断元素是否在集合中
boolean isEmpty()	判断集合的长度是不是0,是0返回true
int size()	返回集合的长度,集合中元素的个数
boolean remove(E)	移除集合中指定的元素,移除成功返回true
T[] toArray(T[] a)	集合转成数组

（1） boolean add(E)

/**
*  boolean add(E) 元素添加到集合中
*  返回值,目前都是true
*/
public static void collectionAdd(){
    //接口多态创建集合容器对象,存储的数据类型是字符串
    Collection<String> coll = new ArrayList<>();
    //集合对象的方法add添加元素
    coll.add("hello");
    coll.add("world");
    coll.add("java");
    coll.add("money");
    coll.add("wife");
    /**
    *  输出语句中,输出集合对象,调用的是方法toString()
    *  看到的内容是一个完整的字符串, 不叫遍历
    *  遍历时一个个过，一个个输出
    */
    System.out.println(coll);
}

（2）void clear()，int size()，boolean isEmpty()

/**
     *  void clear() 清空集合中的所有元素
     *  int size() 集合的长度
     */
    public static void collectionClear(){
        Collection<Integer> coll = new ArrayList<>();
        coll.add(1);
        coll.add(2);
        coll.add(3);
        System.out.println(coll);
        System.out.println("集合的长度::"+ coll.size());//长度
        coll.clear();
        System.out.println(coll);
        System.out.println("集合的长度::"+ coll.size());
        System.out.println("集合是空吗?" + coll.isEmpty());//长度=0,isEmpty()返回true
    }

（3）boolean contains()，boolean remove()

/**
     *  boolean contains(E) 判断是否包含
     *  boolean remove(E) 移除元素
     */
public static void collectionContains(){
    //接口多态创建集合容器对象,存储的数据类型是字符串
    Collection<String> coll = new ArrayList<>();
    //集合对象的方法add添加元素
    coll.add("hello");
    coll.add("wife");
    coll.add("world");
    coll.add("java");
    coll.add("money");
    coll.add("wife");
    //判断集合中是否包含某个元素
    boolean b = coll.contains("world");
    System.out.println("b = " + b);
    //移除集合中的元素
    //删除成功返回true,如果有多个相同的对象,删除最先遇到的那个
    boolean b1 = coll.remove("wife");
    System.out.println("b1 = " + b1);
    System.out.println(coll);
}

4. Iterator接口

迭代器接口 Iterator，为集合进行遍历的。迭代器技术是所有Collection集合的通用遍历形式。

4.1 Iterator接口的抽象方法

boolean hasNext() 判断集合中是否有下一个可以遍历的元素，如果有返回true
E next() 获取集合中下一个元素
void remove() 移除遍历到的元素

4.2 获取迭代器接口实现类

迭代器就是为了遍历集合而产生。集合的顶层接口Collection中定义了方法：方法的名字就是 iterator()，返回值是Iterator接口类型, 返回的是Iterator接口实现类的对象

Collection接口中的方法摘要 :
  public Iterator iterator() ; 返回迭代器接口实现类的对象
使用的对象ArrayList,实现接口Collection,重写方法iterator();

public static void main(String[] args) {
    //迭代器遍历集合
    //接口多态创建集合容器对象,存储的数据类型是字符串
    Collection<String> coll = new ArrayList<>();
    //集合对象的方法add添加元素
    coll.add("hello");
    coll.add("world");
    coll.add("java");
    coll.add("money");
    coll.add("wife");
    //1 遍历 集合对象,调用方法iterator() 获取迭代器接口的实现类对象
    Iterator<String> it = coll.iterator();
    //2 迭代器对象的方法,判断集合是否有下元素
    //boolean b = it.hasNext();
    //System.out.println(b);
    //3 迭代器对象的方法,取出元素
    //String str = it.next();
    //System.out.println(str);
    //条件,集合中有下一个元素就可以
    while ( it.hasNext() ){
        String str =  it.next();
        System.out.println(str);
    }
}

4.3 迭代器的实现原理

每个集合容器，内部结构不同，但是迭代器都可以进行统一的遍历实现

结论：迭代器是隐藏在集合的内部的（即为成员内部类），提供公共的访问方式。

//Iterator接口的源码和ArrayList中的iterator的源码
interface Iterator{
    boolean hasNext();
    E next();
    void remove();
}
public class ArrayList {
    public Iterator iterator(){
        return  new Itr();
    }
    private class Itr implements Iterator{
         boolean hasNext(); //重写
       E next(); //重写
         void remove(); //重写
    }
}

图1：ArrayList的内部类实现接口Iterator的源码图片

4.4 并发修改异常

如何不发生这个异常

异常的产生原因：在迭代器遍历集合的过程中，使用了集合的功能，改变了集合的长度造成。

public static void main(String[] args) {
    //迭代器遍历集合
    //接口多态创建集合容器对象,存储的数据类型是字符串
    Collection<String> coll = new ArrayList<>();
    //集合对象的方法add添加元素
    coll.add("hello");
    coll.add("world");
    coll.add("java");
    coll.add("money");
    coll.add("wife");
    //迭代器遍历集合
    Iterator<String> it = coll.iterator();
    while ( it.hasNext() ){
        String str = it.next();
        //判断,遍历到的集合元素是不是java
        if (str.equals("java")){
            //添加元素 出现并发修改异常
            coll.add("add");
        }
        System.out.println(str);
    }
}

4.5 集合存储自定义对象并迭代

public static void main(String[] args) {
    //创建集合,存储自定义的对象
    Collection<Person> coll = new ArrayList<>();
    //集合的方法add存储Person对象
    coll.add( new Person("张三",21) );
    coll.add( new Person("李四",22) );
    coll.add( new Person("王五",23) );
    //迭代器遍历集合
    Iterator<Person> iterator = coll.iterator();
    while (iterator.hasNext()){
        Person person = iterator.next();
        System.out.println(person);
        System.out.println(person.getName());
    }
}

/**
 *  定义私有成员
 *  get set方法
 *  无参数构造方法
 *
 *  满足以上的三个条件 ,这个类,换一个名字,叫JavaBean
 */
public class Person   {
    private String name;
    private int age;
    public Person(){}
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

5. List接口

List接口，继承Collection接口，是单列集合。

5.1 List接口的特点

这个接口的集合都具有索引
这个接口中的元素允许重复
这个接口中的元素是有序的

元素不会排序 ,有序指的是 ,元素存储和取出的顺序是一致的

List接口的所有实现类，都具有以上三个特征

5.2 List接口自己的方法（带有索引）

（1）void add(int index ,E e);

/**
* List接口的方法 add(int index, E e)
* 指定的索引位置,添加元素
*
*   IndexOutOfBoundsException 集合越界异常  长度是size()
*     StringIndexOutOfBoundsException 字符串越界异常  长度是 length()
*     ArrayIndexOutOfBoundsException 数组越界异常  长度是 length
*/
public static void listAdd(){
    List<String> list = new ArrayList<>();
    list.add("a") ;//集合的尾部添加
    list.add("b");
    list.add("c");
    list.add("d");
    list.add("e");
    System.out.println(list);
    //指定的索引上,添加元素 ,3索引添加元素
    list.add(3,"QQ");
    System.out.println(list);
}

（2）E get(int index);

/**
     *  List接口的方法 E get(int index)
     *  返回指定索引上的元素
     *  List集合可以使用for循环像数组一样的方式遍历
     */
    public static void listGet(){
        List<String> list = new ArrayList<>();
        list.add("a") ;//集合的尾部添加
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        //List接口方法get取出元素
        //String s = list.get(3);
        //System.out.println(s);
        for(int i = 0 ; i < list.size() ; i++){
            System.out.println(list.get(i));
        }
    }

（3）E set(int index,E e); E remove(int index);

/**
     * List接口方法
     *  E set (int index , E e) 修改指定索引上的元素,返回被修改之前的元素
     *  E remove(int index) 移除指定索引上的元素, 返回被移除之前的元素
     */
    public static void listSetRemove(){
        List<String> list = new ArrayList<>();
        list.add("a") ;//集合的尾部添加
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        System.out.println(list);
        //修改指定索引上的元素,3索引
        String str = list.set(3,"https://www.baidu.com");
        System.out.println(list);
        System.out.println(str);
        //删除指定索引上的元素,删除3索引
        str = list.remove(3);
        System.out.println(list);
        System.out.println(str);
    }

5.3 List集合的特有迭代器

List接口中的方法 listIterator() 返回迭代器，迭代器的接口是ListIterator，List集合的专用迭代器。

ListIterator迭代器接口的方法

boolean hasNext()
E next()
boolean hasPrevious() 判断集合中是否有上一个元素,反向遍历
E previous() 取出集合的上一个元素

/**
     * List接口的方法:
     *   listIterator() List集合的特有迭代器
     *   反向遍历
     */
    public static void iterator(){
        List<String> list = new ArrayList<>();
        list.add("a") ;//集合的尾部添加
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        //获取特有迭代器接口实现类对象
        ListIterator<String> lit = list.listIterator();
        //先要正向遍历
        while (lit.hasNext()){
            String s = lit.next();
            System.out.println(s);
        }
        System.out.println("=============");
        //判断上一个元素
        while (lit.hasPrevious()){
            //取出元素
            String s = lit.previous();
            System.out.println(s);
        }
    }

5.4 List接口的实现类的数据结构

LinkedList（链表）

数组 :

有索引，数组中元素的地址是连续，查询速度快
数组的长度为固定，新数组创建,数组元素的复制，增删的效率慢

链表

链表没有索引，采用对象之间内存地址记录的方式存储
查询元素,必须通过第一个节点依次查询，查询性能慢
增删元素，不会改变原有链表的结构,速度比较快

6. ArrayList实现类

6.1 ArrayList集合的特点

ArrayList类实现接口ListArrayList具备了List接口的特性 (有序，重复，索引)

ArrayList集合底层的实现原理是数组,大小可变 (存储对象的时候长度无需考虑)。
数组的特点：查询速度快，增删慢。
数组的默认长度是10个，每次的扩容是原来长度的1.5倍。
ArrayList是线程不安全的集合，运行速度快。

6.2 ArrayList源码解析

6.2.1 ArrayList类的成员变量

private static final int DEFAULT_CAPACITY = 10; //默认容量

private static final Object[] EMPTY_ELEMENTDATA = {};//空数组

transient Object[] elementData; //ArrayList集合中的核心数组
private int size; //记录数组中存储个数

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //数组扩容的最大值

6.2.2 ArrayList集合类的构造方法

//无参数构造方法
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //数组没有长度

//有参数的构造方法
public ArrayList(int 10) {
    if (initialCapacity > 0) {
        //创建了10个长度的数组
      this.elementData = new Object[10];
    } else if (initialCapacity == 0) {
      this.elementData = EMPTY_ELEMENTDATA;
    } else {
      throw new IllegalArgumentException("Illegal Capacity: "+
    initialCapacity);
    }
}

6.2.3 ArrayList集合类的方法add()

new ArrayList<>().add("abc"); //集合中添加元素
public boolean add("abc") {
    //检查容量  (1)
    ensureCapacityInternal(size + 1); 
    //abc存储到数组中,存储数组0索引,size计数器++
    elementData[size++] = "abc";//数组扩容为10
    return true;
}

//检查集合中数组的容量, 参数是1
private void ensureCapacityInternal(int minCapacity = 1) {
    //calculateCapacity 计算容量,方法的参是数组 , 1
    // ensureExplicitCapacity (10) 扩容的
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//计算容量方法, 返回10
private static int calculateCapacity(Object[] elementData, int minCapacity = 1) {
    //存储元素的数组 == 默认的空的数组  构造方法中有赋值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //返回最大值   max(10,1)
      return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

//扩容 
private void ensureExplicitCapacity(int minCapacity = 10) {
    modCount++;
   // 10 - 数组的长度0 > 0
    if (minCapacity - elementData.length > 0)
        //grow方法(10) 数组增长的
      grow(minCapacity);
}

//增长的方法,参数是(10)
 private void grow(int minCapacity = 10) {
     //变量oldCapacity保存,原有数组的长度  = 0
     int oldCapacity = elementData.length; // 0
     //新的容量 = 老 + (老的 / 2)
     int newCapacity = oldCapacity + (oldCapacity >> 1);// 0
     // 0 - 10 < 0 新容量-计算出的容量
     if (newCapacity - minCapacity < 0)
      newCapacity = minCapacity; //新容量 = 10
     //判断是否超过最大容量
     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);
 }

7. LinkedList实现类

7.1 LinkedList集合的特点

LinkedList类实现接口List，LinkedList具备了List接口的特性 (有序，重复，索引)

LinkedList底层实现原理是链表，双向链表
LinkedList增删速度快
LinkedList查询慢
LinkedList是线程不安全的集合，运行速度快

7.2 LinkedList集合特有方法

集合是链表实现，可以单独操作链表的开头元素和结尾元素

void addFirst(E e) 元素插入到链表开头
void addLast(E e) 元素插入到链表结尾
E getFirst() 获取链表开头的元素
E getLast() 获取链表结尾的元素
E removeFirst() 移除链表开头的元素
E removeLast() 移除链表结尾的元素
void push(E e)元素推入堆栈中
E pop()元素从堆栈中弹出

public static void main(String[] args) {
  linkedPushPop();
}
//- void push(E e)元素推入堆栈中
//- E pop()元素从堆栈中弹出
public static void linkedPushPop(){
    LinkedList<String> linkedList = new LinkedList<String>();
    //元素推入堆栈中
    linkedList.push("a"); //本质就是addFirst() 开头添加
    linkedList.push("b");
    linkedList.push("c");
    System.out.println("linkedList = " + linkedList);
    String pop = linkedList.pop(); // removeFirst()移除开头
    System.out.println(pop);
    System.out.println("linkedList = " + linkedList);
}
//- E removeFirst() 移除链表开头的元素
//- E removeLast() 移除链表结尾的元素
public static void linkedRemove(){
    LinkedList<String> linkedList = new LinkedList<String>();
    linkedList.add("a"); //结尾添加
    linkedList.add("b"); //结尾添加
    linkedList.add("c"); //结尾添加
    linkedList.add("d"); //结尾添加
    System.out.println("linkedList = " + linkedList);
    //移除开头元素,返回被移除之前
    String first = linkedList.removeFirst();
    //移除结尾元素,返回被移除之前的
    String last = linkedList.removeLast();
    System.out.println("first = " + first);
    System.out.println("last = " + last);
    System.out.println("linkedList = " + linkedList);
}
//- E getFirst() 获取链表开头的元素
//- E getLast() 获取链表结尾的元素
public static void linkedGet(){
    LinkedList<String> linkedList = new LinkedList<String>();
    linkedList.add("a"); //结尾添加
    linkedList.add("b"); //结尾添加
    linkedList.add("c"); //结尾添加
    linkedList.add("d"); //结尾添加
    System.out.println("linkedList = " + linkedList);
    //获取开头元素
    String first = linkedList.getFirst();
    //获取结尾元素
    String last = linkedList.getLast();
    System.out.println("first = " + first);
    System.out.println("last = " + last);
    System.out.println("linkedList = " + linkedList);
}
// void addFirst(E e) 元素插入到链表开头
// void addLast(E e) 元素插入到链表结尾
public static void linkedAdd(){
    LinkedList<String> linkedList = new LinkedList<String>();
    linkedList.add("a"); //结尾添加
    linkedList.add("b"); //结尾添加
    linkedList.add("c"); //结尾添加
    linkedList.add("d"); //结尾添加
    System.out.println("linkedList = " + linkedList);
    //结尾添加
    linkedList.addLast("f");
    linkedList.add("g");
    //开头添加
    linkedList.addFirst("e");
    System.out.println("linkedList = " + linkedList);
}

7.3 LinkedList源码解析

7.3.1 LinkedList集合的成员变量

transient int size = 0; //集合中存储元素个数计数器

transient Node<E> first; //第一个元素是谁

transient Node<E> last; //最后一个元素是谁

7.3.2 LinkedList集合的成员内部类Node（结点）

//链表中,每个结点对象
private static class Node<E> {
        E item; //我们存储的元素
        Node<E> next; // 下一个结点对象
        Node<E> prev; // 上一个结点对象
    //构造方法,创建对象,传递上一个,下一个,存储的元素
    Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
}

7.3.4 LinkedList集合的方法add()添加元素

//添加元素 e 存储元素 abc
//再次添加元素 e
void linkLast(E "abc") {
    //声明新的节点对象 = last
    final Node<E> l = last; // l = null  l "abc"节点
    //创建新的节点对象,三个参数, 最后一个对象,"abc", 上一个对象null
    final Node<E> newNode = new Node<>(l, e, null);
    //新节点赋值给最后一个节点
    last = newNode;
    if (l == null)
        //新存储的几点赋值给第一个节点
      first = newNode;
    else
      l.next = newNode;
    size++;
    modCount++;
}

7.3.5 LinkedList集合的方法get()获取元素

//集合的获取的方法
//index是索引, size 长度计数器
Node<E> node(int index) {
    //索引是否小于长度的一半,折半思想
    if (index < (size >> 1)) {
      Node<E> x = first;
      for (int i = 0; i < index; i++)
        x = x.next;
     return x;
    } else {
       Node<E> x = last;
      for (int i = size - 1; i > index; i--)
      x = x.prev;
      return x;
    }
}

8. Set接口

Set集合，是接口Set，继承Collection接口。Set集合不存储重复元素。

Set集合存储的数据是无序、不重复、无索引。

无序指的是存储和取出的顺序不一样，但是由于使用迭代器遍历，Set集合的输出会根据自然顺序输出，例如“a”自然排序在“b”之前，所以先输出“a”。

Set接口下的所有实现类，都会具有这个特性。

Set接口的方法，和父接口Collection中的方法完全一样。

8.1 Set集合存储和遍历

public static void main(String[] args) {
        //Set集合存储并迭代
        Set<String> set = new HashSet<String>();
        //存储元素方法 add
        set.add("b");
        set.add("a");
        set.add("c");
        set.add("d");
        set.add("d");
        System.out.println("set = " + set);
        Iterator<String> it = set.iterator();
        while (it.hasNext()){
            System.out.println(it.next());
        }
    }

8.2 Set接口实现类HashSet类

HashSet集合类的特点 :

实现Set接口，底层调用的是HashMap集合
HashSet的底层实现原理是哈希表
HashSet不保证迭代顺序，元素存储和取出的顺序不一定
线程不安全，运行速度快

图二：创建HashSet其实就是创建HashMap

8.3 对象的哈希值

每个类继承Object类，Object类定义方法：

public native int hashCode(); // C++语言编写,不开源

方法使用没有区别：方法返回int类型的值,就称为哈希值

哈希值的结果不知道是怎么计算的，调用toString()方法的时候，返回的十六进制数和哈希值是一样的，@1b6d3586叫哈希值 (根本和内存地址是无关的)

public static void main(String[] args) {
    Person p = new Person();
    int code = p.hashCode();
    // int 变量 460141958 (是什么,无所谓, 数字就是对象的哈希值)
    System.out.println(code);
    // com.atguigu.hash.Person@1b6d3586
    System.out.println(p.toString());
 }

可以重写父类的hashCode()方法，再输出该哈希值或toString()方法

/**
     * 重写父类的方法
     * 返回int值
     */
    public int hashCode(){
        return 9527;
    }

Java的第十二篇文章——JAVA集合（上）

第十二章集合

学习目标

1. 集合框架的由来

2. 集合框架的继承体系

3. Collection接口

3.1 Collection接口的常用方法

4. Iterator接口

4.1 Iterator接口的抽象方法

4.2 获取迭代器接口实现类

4.3 迭代器的实现原理

4.4 并发修改异常

4.5 集合存储自定义对象并迭代

5. List接口

5.1 List接口的特点

5.2 List接口自己的方法（带有索引）

5.3 List集合的特有迭代器

5.4 List接口的实现类的数据结构

6. ArrayList实现类

6.1 ArrayList集合的特点

6.2 ArrayList源码解析

7. LinkedList实现类

7.1 LinkedList集合的特点

7.2 LinkedList集合特有方法

7.3 LinkedList源码解析

8. Set接口

8.1 Set集合存储和遍历

8.2 Set接口实现类HashSet类

8.3 对象的哈希值

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

Java的第十二篇文章——JAVA集合（上）

第十二章 集合

学习目标

1. 集合框架的由来

2. 集合框架的继承体系

3. Collection接口

3.1 Collection接口的常用方法

4. Iterator接口

4.1 Iterator接口的抽象方法

4.2 获取迭代器接口实现类

4.3 迭代器的实现原理

4.4 并发修改异常

4.5 集合存储自定义对象并迭代

5. List接口

5.1 List接口的特点

5.2 List接口自己的方法（带有索引）

5.3 List集合的特有迭代器

5.4 List接口的实现类的数据结构

6. ArrayList实现类

6.1 ArrayList集合的特点

6.2 ArrayList源码解析

7. LinkedList实现类

7.1 LinkedList集合的特点

7.2 LinkedList集合特有方法

7.3 LinkedList源码解析

8. Set接口

8.1 Set集合存储和遍历

8.2 Set接口实现类HashSet类

8.3 对象的哈希值

热门文章

最新文章

相关课程

相关电子书

相关实验场景

第十二章集合