昨天学习了几种简单数据结构，为何要了解数据结构？一方面的原因是因为集合的底层就是与其息息相关的。
ArrayList的底层数据结构：数组。
LinkedList的底层数据结构：链表。
TreeSet的底层数据结构：红黑树。
HashSet的底层数据结构：哈希表。
前天学习了Collection集合，其继承体系图如下：
今天就来了解Collection的子接口List，Set，以及它们各自的实现类。
一、List接口
List，翻译就是列表的意思，列表有何特点？
它的元素是有序的。
它是有索引的（Collection没索引）。
它的元素是可以重复的。
Collection是List的父接口，那么Collection中的所有方法，List都能直接拿来用。
List因为带索引，所以它相对于Collection的特有方法基本都是索引相关的。
集合中有四类方法是最常见的：也就是增加元素，删除元素，修改元素，查询元素，简称就是增删改查。
①增：add方法
可以直接添加元素，也可以根据索引添加元素。
②删：remove方法
Collection中的remove方法是删除对应的元素，List中可以根据索引来删除元素。
③改：set方法
修改对应索引位的元素。
④查：get方法
得到对应索引位的元素。
1.ArrayList
这个集合很早前就学习过了，因为太常见了。
ArrayList是List的实现类，看名字就能看出来，其中Array就是数组的意思，显而易见，ArrayList的底层就是数组。数组查询快，故ArrayList常用来查询数据。
那么问题来了，数组长度不可变，ArrayList怎么又可变了呢？
ArrayList默认是长度为10的数组，如果超过了，就会扩容。
如何扩容?
创建一个新的数组，再将旧数组复制进去，这样长度就增加了。
所以本质上ArrayList长度可变是因为底层换了数组。
2.LinkedList
和ArrayList一样，LinkedLIst也是List的实现类，其底层是链表。链表增删快，故LinkedList常用来增删数据。
集合中重要的是增删改查四种方法，linkedList有几种特殊的方法：
①addFirst方法：将元素添加到开头。
其中push方法和addFirst方法一样。
②addLast方法：将元素添加到结尾。
③removeFirst方法：将开头元素移除并返回。
其中pop方法和removeFirst方法一样。
④removeLast方法：将结尾元素移除并返回。
⑤getFirst方法：查询获取开头元素。
⑥getLast方法：查询获取结尾元素。
这几个方法都非常简单，理解其中文意思也就知道其作用了。
其中有两个方法比较特殊，官方解释如下：
pop方法：从此列表所表示的堆栈处弹出一个元素。
push方法：将元素推入此列表所表示的堆栈。
不要看它解释的这么复杂，其实就是堆栈结构，堆栈有什么特点？
先进先出，所以无论是增加还是删除，都是最上面的元素。
二、Set接口
Set和List一样，都是Collection的子接口。
特点和List刚好相反：
它的元素是无序的。
它是没有索引的。
它的元素是不能重复的。
集合有没有索引的依据是什么?
如果元素可以重复，比如说一个集合存了两个元素，都是“刘小爱”，系统要如何判断它们？所以就需要索引，这样就能区分开：1索引位的刘小爱和2索引位的刘小爱，就算元素一样，索引也不一样。
故：元素可以重复，就有索引；元素不可以重复，就不需要索引。
Set因为没有索引，所以和父接口Collection的方法一样，没有特殊方法。
那如何保证元素不重复？这就得依赖于hashCode和equals方法。
1.Object类的hashCode(哈希值)
Object类有一个toString方法，代码如下：
toHexString：是转换成十六进制的意思。
也就是说，我们直接打印Object对象得到的一串地址值就是hashCode的十六进制。
但是一个对象它真正的地址值，Java是不会轻易告诉我们的，一是我们知道了也没啥用；二是黑客会拿它做坏事。于是Java就想了个办法，对真正的地址进行加密，也就是hashCode的由来。
所以什么叫hashCode?
hashCode是对真正的地址进行一种加密手段而得到的一串数字（什么手段也不用去了解，除非你要去做黑客)。
那么现在问题来了，有没有可能存在多个对象地址，对应同一个hashCode呢？
答案是有的，只不过这种情况非常少见。也就是说：
不同的对象的真正地址是不可能相同的，
不同对象的hashCode是有可能相同的。
如何理解这句话呢？
就是我们理论上是可以创建无数多个对象的，可以不停地在电脑上new对象，但是hashCode值是有限的，它是一个int类型的数据，最多也只有42亿（2的32次方）多种可能。
所以不同的对象是有可能出现同一hashCode的，这种情况就叫哈希碰撞，只不过遇到这种情况概率微乎其微。
Object有一个方法就是hashCode，按照继承的原则，所有类都有这个方法。
2.String的hashCode
String的hashCode方法是重写过了的，跟真正的地址其实是没关系的。
为何要这么做？为了保证Set的元素不可重复。
hashCode值若是不相等，那这两个元素必定不重复。
hashCode值若是相等，这两个元素大概率是重复的，但也有例外。
如下图几种情况：
三、哈希表
Set的元素不可重复，这个问题该如何解决？
若是我的话，我肯定会想：将新的元素和Set中的每一个元素比较一遍不就可以了？如果有相等的，就不添加；如果有不相等的，就添加。
这样做有问题么，理论上是没问题的，但是效率太低太低了，每次添加一个元素就要将元素遍历一遍。
那些程序员大神为了解决这个问题，就弄出了哈希表。
所以什么叫哈希表？
哈希表可以用来高效率解决元素不可重复这个问题，其本质就是：数组+链表+红黑树。
①哈希值就有点类似于数组中的索引****，因为哈希值不同其元素必定不同。
数组查询快，如果现在添加进来了一个元素，我根本不用遍历，我就看有没有相同的哈希值（相当于索引），直接就可以定位：
如果没有相同的哈希值，直接添加进集合。
如果有相同的哈希值，我再比较内容是否一样。
数组有一个问题，就是长度是一定的，所以若是元素过多时，需要扩容。但是哈希表数据结构比较复杂，还要提前扩容：哈希表中数组默认长度16，如果数组中的元素超过了75%就开始扩容。
②虽然哈希值一样，但我还会比较它们的内容是否一样，用equals方法比较内容是否一样。
如果内容也一样，重复元素，不添加进集合。
如果内容不一样，不是重复元素，添加进集合。
③如果链表元素数量超过8，就将链表重构成红黑树。
链表查询是很慢的，所以为了查询效率，链表元素数量过多，就会重构成红黑树，红黑树查询效率比链表要快。
这里面涉及就到了两个方法：hashCode方法和equals方法，它们一起能很好地判断元素是否重复。
所以如果新建了一个对象，需要重写hashCode方法和equals方法，这个在开发工具中直接使用Alt+Insert自动重写方法。
HashSet的底层原理就是哈希表。
其中LinkedHashSet又是HashSet的一个子类，其特点主要是有序的Set集合，存储和取出的顺序一致。 总结
