集合概述

• 是一个对象。
• 集合在java中本身是一个容器（来容纳其它类型的数据）。
• 集合中任何时候存储的都是“引用”。
• 集合不能直接存储基本数据类型，另外集合也不能直接存储java对象。例如：list.add(100); //自动装箱Integer，存储该对象的引用地址
• 在java中每一个不同的集合，底层会对应不同的数据结构。
• 往不同的集合中存储元素，等于将数据放到了不同的数据结构当中。
• 所有的集合类和集合接口都在java.util包下。
• 在java中集合分为两大类：

一、Collection

• java.util.Collection

Collection 是 List 和 Set 的父接口，在 Collection 中定义了一些主要方法

Iterator 接口

关于 Iterator 接口说明，Iterator 称为迭代接口，通过此接口可以遍历集合中的数据，

• 集合结构改变，必须要重新获取迭代器
• 此接口主要方法为：

迭代器迭代元素的过程中不能使用集合对象的remove方法删除元素，
要使用迭代器Iterator的remove方法来删除元素，防止出现异常：
ConcurrentModificationException

• ArrayList类 内部实现 Iterator接口的Itr内部类：源码如下

//获得Iterator的方法
    public Iterator<E> iterator() {
        return new Itr();
    }
//Iterator接口的实现类
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        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];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

（一）List接口

• 是一个有序集合，可以放重复的数据，有下标

• List 接口下面主要有两个实现 ArrayList 和 LinkedList，都是有顺序的，也就是放进去是什么顺序，取出来还是什么顺序，也就是基于线性存储，可以看作是一个可变数组

• List接口中有一些特有的方法。

1. ArrayList：

查询数据比较快，添加和删除数据比较慢(基于可变数组)

• ArrayList集合初始化容量10（JDK8中的注释：We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added.）
• 扩容为原容量 1.5 倍。
• 底层是数组。
• ArrayList集合末尾增删元素效率还是可以的。

2. LinkedList：

查询数据比较慢，添加和删除数据比较快（基于双向链表数据结构）

3. Vector:

Vector 已经不建议使用，Vector 中的方法都是同步的，效率慢，已经被 ArrayList取代

• Vector初始化容量是10.
• 扩容为原容量的 2 倍。
• 底层是数组。
• Vector底层是线程安全的。
• 得到一个线程安全的List： Collections.synchronizedList(list);

4. Stack

是继承 Vector 实现了一个栈，栈结构是后进先出，目前已经被 LinkedList 取代

（二）Set接口

• 是一个无序集合，不允许放重复的数据

1. 哈希表

• 哈希表是一种数据结构，哈希表能够提供快速存取操作。哈希表是基于数组，数组内存放单向链表的
• 缺点，数组一旦创建将不能扩展。

2. HashSet

• 底层是HashMap
• HashSet 中的数据是无序的不可重复的。HashSet 按照哈希算法存取数据的，具有非常好性能
• 它的工作原理是这样的，当向 HashSet 中插入数据的时候，他会调用对象hashCode 得到该对象的哈希码，然后根据哈希码计算出该对象插入到集合中（数组）的位置。
• 重点：特别是向 HashSet 或 HashMap 中加入数据时必须同时覆盖 equals 和 hashCode 方法，应该养成一种习惯覆盖 equals 的同时最好同时覆盖 hashCode

对象间的比较要求

• 两个对象 equals 相等，那么它的 hashcode 相等
• 两个对象 equals 不相等，那么它的 hashcode 并不要求它不相等，但一般建议不相等
• hashcode 相等不代表两个对象相等（采用 equals 比较）

3. TreeSet 实现SortedSet接口

• 底层是TreeMap
• TreeSet 可以对 Set 集合进行排序，默认自然排序（即升序），但也可以做自定义的排序

Comparable 接口

• 放到 TreeSet 中的对象， TreeSet 会对其进行排序，那么该对象必须必须实现 Comparable 接口，基本类型的包装类和 String 他们都是可以排序的，都实现了 Comparable 接口，重写compareTo() 方法，自定义比较规则

Comparable 和 Comparator 的区别

• 一个类实现了 Camparable 接口则表明这个类的对象之间是可以相互比较的，这个类对象组成的集合就可以直接使用 sort 方法排序。
• Comparator 可以看成一种算法的实现，将算法和数据分离（OOP原则），Comparator 也可以在下面两种环境下使用：
  1、类的没有考虑到比较问题而没有实现 Comparable，可以通过 Comparator 来实现排序而不必改变对象本身
  2、可以使用多种排序标准，比如升序、降序等

二、Map

• java.util.Map;

是一个无序集合，集合中包含一个键对象，一个值对象，键对象不允许重复，值对象可以重复（身份证号—姓名）

• Map 中可以放置键值对，也就是每一个元素都包含键对象和值对象
• Map 实现较常用的为HashMap，HashMap 对键对象的存取和 HashSet 一样
• 采用的是哈希算法，所以如果使用自定类作为 Map 的键对象，必须复写 equals 和hashCode 方法。
• Map接口中常用方法：

• 遍历Map集合的两种方式

  • 第一种：获取所有key，遍历每个key，通过key获取value.
  • 第二种：获取Set即可，遍历Set集合中的Entry，调用entry.getKey() entry.getValue()

• put方法和get方法原理
  存放的数据结构是哈希表：一个结点数组，数组里面是单向链表

  
  
  • 可以得出，
    • 向Map集合中存，以及从Map集合中取，都是先调用key的hashCode方法，然后再调用equals方法
    • key会被调用hashCode方法和equals方法
    • 同一个单向链表上所有节点的hash相同，因为是同一个数组小标，但同一个链表上的key之间的equals方法 返回值都是false

（一）HashMap类

• 放在HashMap集合key部分的，以及放在HashSet集合中的元素，因为 HashMap 的底层实现采用的是 hash 表，所以 Map 的 key 必须覆盖hashCode 和 equals 方法
• JDK8之后的特点：如果哈希表单向链表中元素超过8个，单向链表这种数据结构会变成红黑树数据结构；当红黑树上的节点数量小于6时，会把红黑树变成单向链表数据结构

（二）Hashtable类

• HashMap和Hashtable的区别

（三）TreeMap类 实现了SortedMap接口

• 底层是二叉树
• treeMap 可以对 Map 中的 key 进行排序，如果 map 中的 key 采用的是自定类那么需要实现Comaprable 或 Comparator 接口完成排序
  • 第一种：实现java.lang.Comparable接口。
  • 第二种：单独编写一个比较器Comparator接口。

• 自平衡二叉树

  
  
  自平衡二叉树

（四）Properties类

• 是Map集合，继承Hashtable
• key和value都是string类型
• 常用两个方法
  • setProperty
  • getProperty
• 被称为属性类对象
• 是线程安全的

三、Collections 工具类

Collections 位于 java.util 包中，提供了一系列实用的方法，如：对集合排序，对集合中的内容查找等

• synchronizedList方法：获得线程安全的集合
• sort方法（要求集合中元素实现Comparable接口。或者传入一个比较器）