Java中的集合

1. 所有集合都在java.util包下
2. Collection和Map是Java集合框架的根接口
3. Collections,集合工具类，用来对集合进行操作

Collection

• 继承Iterable

  
  继承Iterable

Iterable是一个顶级接口，共有三个方法

public interface Iterable<T> {

    Iterator<T> iterator();

    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

• 接口和实现类

  
  子接口和实现类

List

元素有序可重复

list接口和实现类

• ArrayList

1. 底层基于数组
2. 元素增删慢, 查找块

实现原理

1. 默认初始化大小为10的数组
2. 增加元素大于当前数组长度, 则进行扩容, 将数组长度增加原来数组的一半

ArrayList源码

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

//定义
List list1 = new ArrayList();

//添加元素
list1.add("张三");
list1.add(12);

System.out.println(list1.get(0)); //张三  取下标为0的元素
System.out.println(list1.size()); //2  集合长度
System.out.println(list1.contains(12));//true  是否包含

//删除下标为1的元素
System.out.println(list1); //[张三, 12]
list1.remove(1);
System.out.println(list1); //[张三]

//两个集合合并
List list2 = new ArrayList();
list2.add("lisi");
list2.add(13);
list1.addAll(list2);
System.out.println(list1); //[张三, lisi, 13]
list1.addAll(0, list2);
System.out.println(list1); //[lisi, 13, 张三, lisi, 13]

方法还有很多, 自己去试吧.....

• Vector

1. 线程安全
2. 性能比ArrayList低

实现原理
添加元素大于当前数组长度， 则进行扩容， 将数组的长度增加原来数组的1倍

• LinkedList

1. 基于链
2. 方便元素添加、删除, 提供了大量首尾操作的方法

Set

元素无序不可重复

子接口及实现类

• HashSet

1. 不可重复
2. 无序
3. 根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能

数据结构
在JDK1.8之前

1. 哈希表底层采用数组+链表实现
2. 同一hash值的链表都存储在一个链表里， 当hash值相等的元素较多时，通过key值依次查找的效率较低

在JDK1.8

1. 数组+链表+红黑树实现
2. 当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找 时间

• LinkedSet
  HashSet保证了数据唯一, 但元素存放进去是没有顺序的, 那么我们怎么保证顺序?使用LinkedSet
  链表 + 哈希表实现

Map

1. 基于数组 + 链表
2. 紫色, Hash数组, 数组元素是每个链表的头节点
3. 绿色, 链表, 解决hash冲突, 不同的key映射到了数组的同一索引处, 则形成链表

Map的数据结构

• HashMap

1. 哈希表结构
2. 元素的存取顺序不能保证一致
3. 由于要保证键的唯一、不重复，需要重写键的hashCode()方法、equals()方法

• LinkedHashMap

1. 哈希表结构+链表结构
2. 通过链表结构可以保证元素的存取顺序一致
3. 通过哈希结构保证键的唯一不重复, 需要重写键的 hashCode()方法、equals()方法