集合实际上就是一个容器，可以容纳其他数据类型；数组就是最简单、最初的一个集合。
是一个载体,可以一次容纳多个对象。
在实际开发中，假设数据库中有十条记录，假设把这十条记录查询出来，在java程序中会将10条记录封装成十个java对象，然后将10个java对象存入到集合中，传到java前端，然后遍历取出，展现出来。
集合不能直接存储基本数据类型，另外集合也不能直接存储Java对象；集合中存储的都是对象的内存地址。
或者说集合中存储的是引用。
往不同的集合中存储元素等于将不同的数据放到了不同的数据结构中。
数据结构：数据存储的结构就是数据结构，不同的数据结构，数据存储方式不同。
常见的数据结构：数组、二叉树、链表、哈希表…
往集合c1中放数据，可能是放到了数组上、往c2上放数据可能放到了二叉树上 使用了不同的集合就等于使用了不同的数据结构！
Java已经写好了这些常用的集合类，已经将数据结构实现了，需要掌握怎么用，在什么情况下选择什么样合适的集合。
new ArrayList(); 创建一个集合，底层是数组
new LinkedList(); 底层是链表
new TreeSet(); 底层是二叉树
所有的集合类都在Java.util包下
注意：
在迭代集合元素的过程中，不能调用集合对象的remove（o）方法去删除元素，否则会出现ConcurrentModificationException异常。
若要在迭代集合元素的过程中删除集合元素，应该调用迭代器的remove()方法。
集合状态改变时要重新获取迭代器！迭代器相当于集合的快照，使用集合对象的remove（o）方法时，只删除集合中的元素，不更新迭代器快照中的元素，而使用迭代器的remove（）方法时即会删除集合中的元素也会删除快照中的元素。
ArrayList.java:
public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }contains方法底层使用equals方法来比较是否包含某个元素
若equals方法返回true，则包含某元素，若返回false则不包含某个元素
由于String类重写了equals方法，所以equals方法比较的两个元素的内容是否相等，而不是内存地址
Collection c = new ArrayList(); String s1 = new String("abc"); String s2 = new String("def"); c.add(s1); c.add(s2); String s3 = new String("abc"); System.out.println(c.contains(s3)); //true总结：
使用contains方法时，存放在集合中的类型一定要重写equals方法。
ArrayList.java:
public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } Collection c = new ArrayList(); int i1 = 1; int i2 = 1; c.add(i1); System.out.println(c.remove(i2));//true System.out.println(c.size());//0由于remove方法底层也调用了equals方法， i1就是i2，所以删除i2和删除i1是一样的，都是删除“1”这个内容。删除i2也就是删除i1。
存储特点：有序可重复
有序：List集合中的元素有下标。从0开始，以1递增。
可重复：存储一个1还可以再存储一个1。
List list = new ArrayList(); list.add(1); list.add(2); list.add(3); list.add(1,3); //list接口特有方法 在向集合中添加元素时指定下标索引 for (int i = 0; i <list.size() ; i++) { System.out.println(list.get(i)); //通过下标获取元素 list集合特有的集合元素遍历方式 } System.out.println(list.indexOf(3)); //返回该元素在集合中第一次出现时的索引 1 System.out.println(list.lastIndexOf(3)); //返回该元素在集合中最后一次出现时的索引 3 list.remove(0); //删除指定下标的元素 System.out.println(list.size()); //3 for (Object o : list) { System.out.println(o); //增强for遍历集合中元素 } list.set(1, 111); //修改指定索引处的集合元素内容 for (Object o : list) { System.out.println(o); }ArrayList集合默认初始化容量为10(底层先创建一个长度为0的数组，当添加第一个元素的时候，初始化容量为10)
ArrayList集合底层是Object类型的数组Object[]
ArrayList集合扩容：原容量的1.5倍。（ArrayList.java: grow(): int newCapacity = oldCapacity + (oldCapacity >> 1);）
建议给定一个预估计的集合容量，避免集合扩容；集合扩容比较影响运行效率。
构造方法：
List list = new ArrayList(); List list2 = new ArrayList(20);//指定初始化容量为20优点：检索效率比较高
缺点:随机增删元素效率比较低，另外数组无法存储大数据量，原因是很难找到一块巨大的连续的内存空间。
向数组末尾增加元素，效率很高，不受影响。
对于链表数据结构来说，基本的单元是节点Node.
对于单向链表来说，任何一个节点Node都有两个属性：1.存储的数据 2.下一个节点的内存地址
**优点：**随机增删元素效率较高（因为增删元素不涉及到大量元素位移）
**缺点：**查询效率较低，每一次查找某个元素的时候都需要从头节点开始向下遍历。
双向链表结构图：
LinkedList集合没有初始化容量。
最初这个链表没有任何元素，first和last引用都是null
无序不可重复，但是存储的元素可以自动按照大小顺序排序。称为：可排序集合。
无序：指的是存进去的顺序和取出来的顺序不同，并且没有下标。
TreeSet集合底层实际上是一个TreeMap
TreeSet底层是一个二叉树
放到TreeSet集合中的元素等同于放到TreeMap集合的key部分了
TreeSet无法对自定义类型排序。若要进行排序，需要将自定义类实现comparable<>接口，并重写compareTo方法来自定义排序规则
如果在集合中存放自定义类型时该类不实现comparable<>接口，则程序会抛出Exception in thread “main” java.lang.ClassCastException: CollectionTest.Student cannot be cast to java.lang.Comparable这个异常。
若要对自定义类型进行排序，第二种方式是单独编写一个比较器类，继承Comparator<类型>接口，里面对compare方法进行重写来自定义排序规则。然后在new TreeSet集合时，在TreeSet的构造方法中new这个比较器类即可也可以在new TreeSet集合时，在TreeSet的构造方法中直接new Comparator<类型>（）{重写compare方法}，来实现排序。最终结论：
放到TreeSet或者Tree’Map集合key部分的自定义类型元素要想做到排序，包括两种方式：
放在集合中的自定义类型元素实现java.lang.Comparable接口在构造TreeSet或者TreeMap集合时给它传入一个比较器对象。Comparable和Comparator怎么选择？
当比较规则不会发生变化，或者说当比较规则只有一个的时候，建议实现Comparable接口。
如果比较规则有多个，并且需要多个比较规则之间来回切换，建议使用Comparator接口。
Comparator接口的设计符合OCP原则。
OCP原则： 开闭原则（Open Closed Principle）是Java世界里最基础的设计原则，它指导我们如何建立一个稳定的、灵活的系统。
定义：一个软件实体如类、模块和函数应该对扩展开放，对修改关闭。
TreeSet<Integer> treeSet = new TreeSet<>(); treeSet.add(5); treeSet.add(6); treeSet.add(3); treeSet.add(1); treeSet.add(2); for (Integer tree : treeSet) { System.out.println(tree); } //输出结果： 1 2 3 5 6TreeSet集合存放自定义类测试：
public class TreeSetTest { public static void main(String[] args) { TreeSet<Student> treeSet = new TreeSet<>();//定义一个存放自定义Student类的TreeSet集合 treeSet.add(new Student(11,"ls"));//向集合中添加Student类对象 treeSet.add(new Student(11,"la")); treeSet.add(new Student(13,"aa")); for (Student student : treeSet) {//输出集合内容 System.out.println(student); } } } class Student implements Comparable<Student> {//自定义类来实现Comparable接口 int age; String name; public Student(int age,String name) {//类的构造方法 this.age = age; this.name=name; } @Override public String toString() {//重写toString方法，定义输出格式 return "Student{" + "age=" + age + ", name='" + name + '\'' + '}'; } @Override public int compareTo(Student o) { //重写compareTo方法来自定义排序规则 if (this.age==o.age){ return this.name.compareTo(o.name); }else { return this.age-o.age; } } } //输出结果: Student{age=11, name='la'} Student{age=11, name='ls'} Student{age=13, name='aa'}Map集合的几种遍历形式:
Map<Integer,String> hashMap = new HashMap<>(); hashMap.put(1,"123"); hashMap.put(2,"23"); hashMap.put(3,"3"); hashMap.put(1,"1"); Set<Integer> keys = hashMap.keySet(); Iterator<Integer> iterator = keys.iterator(); while (iterator.hasNext()){ Integer next = iterator.next(); String value = hashMap.get(next); System.out.println(value); } for (Integer key : keys) { //不推荐，因为还需要通过key去集合里找value 效率低 System.out.println(hashMap.get(key)); } Set<Map.Entry<Integer, String>> entries = hashMap.entrySet(); for (Map.Entry<Integer, String> entry : entries) { //建议使用此方式，适合大数据量时 Integer key = entry.getKey(); String value = entry.getValue(); System.out.println(key+"="+value); } Iterator<Map.Entry<Integer, String>> iterator1 = entries.iterator(); while (iterator1.hasNext()){ Map.Entry<Integer, String> entry = iterator1.next(); Integer key = entry.getKey(); String value = entry.getValue(); System.out.println(key+"="+value); }哈希表=数组+单向链表
HashMap集合底层是哈希表。哈希表=数组+单向链表
数组：查询效率高，随机增删效率低
单项链表：随机增删效率高，查询效率低
哈希表将以上两种数据结构融合在一起，充分发挥两种数据结构的优点。
HanshMap底层实际上就是一个一维数组，一维数组里存的是Node节点（单向链表）
HashMap集合底层的源码：
public class HashMap{
//HashMap底层实际上就是一个一维数组 Node<k,v>[] table;
//静态的内部类HashMap.Node
static class Node<k,v>{
final int hash; //哈希值（哈希值是key的hashCode()方法的执行结果，hash值通过哈希函数/算法，可以转换成数组的下标）
final k key；//存储到Map集合中的key
v value;//存储到Map集合中的value
Node<k,v> next;//下一个节点的内存地址
}
}
HashMap集合的key部分的特点:
无序，不可重复。
无序是因为不一定挂载到哪个单向链表上
保证不可重复是因为重写了equals方法
如果key重复，value会覆盖
放在HashMap集合key部分的元素其实就是放到了HashSet集合中。
所以HashSet集合中的元素也需要同时重写hashCode（）+equals（）方法
哈希表HashMap使用不当时无法发挥性能！
假设将所有的hashCode()方法返回值为一个固定的值，那么会导致底层哈希表变成一个纯单向链表。这种情况我们称为**:散列分布不均匀。**
什么是散列分布不均匀?
假设有100个元素，十个单向链表，那么每个单向链表上有10个节点，这样是最好的。是散列分布均匀的。
假设将所有的hashCode()方法的返回值都设置成不一样的值可以吗?有什么问题？
不可以，因为这样的话就导致底层哈希表就变成了一维数组，没有链表的概念了，也是散列分布不均匀。
散列分布均匀，需要重写hashCode（）方法时有一定技巧。
HashMap集合的默认初始化容量为16，默认加载因子是0.75
默认加载因子：当集合底层数组的容量达到75%的时候，数组开始扩容。扩容之后的容量是原容量的2倍。
**重点：**记住：HashMap集合初始化容量必须是2的倍数，这也是官方推荐的！
这是因为达到散列均匀，为了提高HashMap集合的存取效率，所必须的。
**注意：**如果一个类的equals方法重写了，那么hashCode（）方法必须重写。
并且equals方法返回值如果是true，那么hashCode()返回值必定一样。（因为如果equals方法返回为true，说明在同一个链表上，即同一个数组下标，数组下标相同，说明hashCode方法返回的hash值一样）
**终极结论：**放在HashMap集合key部分的，以及放在HashSet集合中的元素，需要同时重写hashCode方法和equals方法。
HashMap集合底层是哈希表数据结构，是非线程安全的。在JDK8之后，如果哈希表单向链表中元素超过8时，单向链表这种数据结构会变成红黑树数据结构。当红黑树上的节点数量小于6时，会重新将红黑树变成单向链表数据结构。
这种方式也是为了提高检索效率，二叉树的检索会再次缩小检索范围，提高效率。初始化容量为16，默认加载因子为.75
哈希碰撞： 如果o1和o2的hash值相同，一定是放在同一个单向链表上。如果o1和o2的hash值不同，但是由于哈希算法执行结束之后转换的数组下标可能相同， 此时会产生“哈希碰撞”。
map集合的key可以为空，但只能有一个。
TreeSet/TreeMap是自平衡二叉树。遵循左小右大存放原则。
存放是要依靠左小右大的原则，所以存放的时候要进行比较。
遍历二叉树的三种方式：
前序遍历：根左右中序遍历：左根右后序遍历：左右根注意：前中后序说的是根的位置，根在前面是前序，根在中间是中序，根在后面是后序
TreeSet/TreeMap集合采用的中序遍历方式。
Iterator采用的中序遍历的方式。即左根右
常用方法：
List<String> list = new ArrayList<>(); //通过synchronizedList方法使该集合变成线程安全的 Collections.synchronizedList(list); list.add("a"); list.add("z"); list.add("c"); list.add("b"); //对集合内元素进行排序 Collections.sort(list);//如果list集合中存放自定义类型元素，则该自定义类型需要实现Comparable接口或在创建该list集合时传入实现comparator接口的自定义排序类 //即：在对list集合中的元素进行排序时，需要保证list集合中的元素实现了Comparable接口。 for (String s : list) { System.out.println(s); //a b c z }Collections.synchronizedList(list); //通过synchronizedList方法使该集合变成线程安全的
Collections.sort(list);//对集合内元素进行排序，如果list集合中存放自定义类型元素，则该自定义类型需要实现Comparable接口或在创建该list集合时传入实现comparator接口的自定义排序类。
该方法只能对list集合进行排序！
若要对set集合进行排序，可先将set集合转换为list集合：List mylist = new ArrayList<>(set);
Collections.sort(list集合，比较器对象)：这种方式来实现使用comparator接口进行排序。
