集合关系图

简略图

完整关系图

集合的概念

在Java程序中可以通过数组来保存对象，但是某些情况下不确定到底需要保存多少个对象，此时数组将不再适用，因为数组的长度不可变，为了保存这些数目不确定的对象，jdk提供了集合类
集合的存储结构
1.顺序存储（ArrayList，Vector）
元素在内存中连续的存储在一起，查找快，但是增加删除慢
2.链式存储（LinkedList,LinkedHashMap）
元素一般右data和指针next域构成，元素在内存中不需要是连续的（也可以是连续的），通过next可获得下一个元素的位置，增删快，查找慢
3.散列存储(HashSet,Hashtable,)
元素值（唯一）通过一种散列技术决定了对象在内存中的存储位置
4.映射存储(Map)
每个元素由key-value组成，根据key以及相应的散列算法计算出元素存储地址

集合大致分为两大类，单列集合Collection和双列集合Map

（1）Collection
单列集合的根接口，用于存储符合某种规则的一系列元素，它有两个重要的子接口，分别是List和Set，query很少用，List的特点是有序并且可重复，Set特点是无序并且不重复
（2）Map
双列集合的根接口，用于存储具有键值映射关系的元素，每个元素都包含一对键值，在使用Map集合时可根据指定的key找到对应的值

Collection 集合

Collection接口常用方法，Collection中的方法对List和Set都适用，但是List和Set都有一些专属方法

List集合

List集合元素有序可重复，继承了Collection接口中的全部方法，并且增加了一些根据元素索引来操作集合的特有方法

*ArrayList
ArrayList是一个动态数组，ArrayList内部封装了一个长度可变的数组对象

当ArrayList初始化没有存入元素时，长度为0
当ArrayList存入元素后，长度默认为10
当ArrayList存入元素个数大于10，每次增长50%

ArrayList数组是不安全的，内部没有用synchronized上锁

底层用数组实现，所以查找快，增删操作慢

*LindedList
LinkedList有一些自已专属的方法

LinkedList列表底层使用双向链表实现，增删快，但查找慢

LinkedList也是不安全的

*Vector
Vector数组与ArrayList的用法一样，底层也是使用数组实现
区别是Vector内部方法都是synchronized上锁的，是一个安全的数组
但是Vector由于是线程同步的，所以它的效率比ArrayList慢
当Vector数组中元素数目>数组长度时，增长率为100%

*Stack
stack 继承自 Vector
Stack也是线程安全的，底层用栈数据结构实现
特有方法

Set集合

Set集合继承自Collection接口，但是并没有对Collection接口进行功能进行扩充，只是更加严格了，Set集合只允许包含一个null元素

*HashSet
HashSet扩展AbstractSet并且实现Set接口，它创建一个2集合，该集合使用散列表进行存储，而散列表通过使用称之为散列法的机制来存储信息，在散列集合中，一个关键字的信息内容被用来确定唯一的一个值，称为散列码，而散列码被用来当作与关键字相连的数据的存储下标。关键字到散列码的转换是自动执行的（看不到散列码本身，程序代码也不能直接索引散列表。）散列法的优点在于即使对于很大的集合，它的add().contains(),remove(),size()方法的运行时间不变

HashSet构造方法的四种形式
1.HashSet()
构造一个默认的散列集合
2.HashSet(Collection c)
用c中的元素初始化散列集合
3.HashSet(int capacity)
用capacity初始化散列集合的容量
4.HashSet(int capacity,float fillRatio)
用它的参数初始化散列集合的容量和填充比（也成为加载因子）
填充比必须介于0.0-1.0之间,就是当元素个数大于散列集合容量*填充比时，散列集合将被扩大，填充比默认0.75

HashSet如何确保不出现重复的元素？
当调用HashSet的add()方法存入元素时，首先调用当前存入对象的hashCode()方法获得对象的哈希值，然后根据对象的哈希值计算出一个存储位置。入股哦该位置上没有元素，则直接将元素存入；如果该位置上有元素存在，则会调用equals()方法让当前存入的元素依次和该位置上的元素进行比较，如果返回的结果为false就将该元素存入集合，返回的结果为true就说明有重复元素，则将该元素舍弃，所以为了保证HashSet正常工作，要求在存入对象时，重写该类的hashCode()和equals()方法

*LinkedHashSet
LinkedHashSet是HashSet集合的一个实现，具有set集合不重复的特点，同时具有可预测的迭代顺序，也就是我们插入的顺序与迭代顺序一致。

并且linkedHashSet是一个非线程安全的集合。

*TreeSet
TreeSet是Set的另一个实现类，它内部采用自平衡的排序二叉树来存储元素
排序二叉树：左节点<根节点<右节点
Tree由于使用了排序二叉树来存储数据，所以内部是有顺序的
那么它是如何使元素有序的呢？
在向TreeSet集合中依次存入元素时，首先将第一个元素放在二叉树的顶端，之后存入的元素与第一个元素比较，如果比它大，就放右子树，比它小，就放左子树，以此类推
集合中的元素在进行比较时，都会调用conpareTo()方法，该方法是在Comparable接口中定义的，所以想要对集合中的元素进行排序，就必须实现Compareable接口，JDK大部分的类型都实现了Compareable接口，都有接口中的compareTo方法，如Integer,String,Double等

Map集合

Map集合采用键值对方式存储，键不能重复，且键相同值覆盖

Map集合常用方法

*HashMap
HashMap是无序的，存入顺序与迭代顺序不一致，如果想一致，可以用HashMap的子类LinkedHashMap，也是双向链表维护内部元素关系
HashMap的三种遍历方式
方式一：keySet()

public static void main(String[] args) {
        Map map = new HashMap();
        map.put("1","Jack");
        map.put("2","Rose");
        map.put("3","Lucy");
        Set keySet = map.keySet();//得到map集合中的所有键的集合keySet
        Iterator iterator = keySet.iterator();//迭代keySet
        while(iterator.hasNext()){
            Object key = iterator.next();
            Object value = map.get(key);
            System.out.println(key+":"+value);
        }
    }

方式二：entrySet()

public static void main(String[] args) {
        Map map = new HashMap();
        map.put("1","Jack");
        map.put("2","Rose");
        map.put("3","Lucy");
        Set entrySet = map.entrySet();//得到map集合中的所有键值对的集合entrySet
        Iterator iterator = entrySet.iterator();//迭代entrySet
        while(iterator.hasNext()){
            Map.Entry entry = (Map.Entry)(iterator.next());//获取entrySet集合中键值对的映射关系
            //entry相当于一个只有一个键值对的map集合
            Object key = entry.getKey();
            Object value = entry.getValue();
            System.out.println(key+":"+value);
        }
    }

方式三：values()获取所有值的集合

public static void main(String[] args) {
        Map map = new HashMap();
        map.put("1","Jack");
        map.put("2","Rose");
        map.put("3","Lucy");
        Collection values = map.values();//获取所有值的集合
        Iterator iterator = values.iterator();
        while(iterator.hasNext()){
            Object value = iterator.next();
            System.out.println(value);
        }
    }

*Hashtable
Hashtable的用法与HashMap的用法基本一致，
不过Hashtable内部方法用synchronized上锁，因此Hashtable是线程安全的
Hashtable线程安全，但是效率比HashMap低

*Properties
Properties类继承自Hashtable，主要用来读取配置文件
也是线程安全的

*TreeMap
也是用自平衡的排序二叉树来存储，内部存储的数据按照key的类型进行排序
key为整形，从小到大排序
key为String，由于String实现了Comparable接口，因此也会按照默认升序排列

Collection和Collections的区别

Collection是一个集合接口，List和Set的父类
Collections是一个工具类，专门提供了一些对集合的操作
Arrays也是一个针对于数组Array的工具类

Collections的常用方法

同步控制
Collections几乎对每一个集合都定义了同步控制的方法，来将集合包装为线程安全的集合

Collection c = Collections.synchronizedCollection(new ArrayList<>());
Collection list = Collections.synchronizedList(new ArrayList<>());
Set s = Collections.synchronizedSet(new HashSet<>());
Map m = Collections.synchronizedMap(new HashMap<>());

设置不可变（只读）集合
unmodifiableXXX():返回指定集合的只读视图

Map readOnlyMap = Collections.unmodifiableMap(map);