基础_List和Set
在Collection接口的下面有2个直接的子接口，分别是Set和List
1.List
介绍:
1.是Collection接口的子接口，继承了Collection接口中的所有方法；
2.List接口定义的所有集合中的元素都可以重复，并且还可以保证存取的顺序一致(存储和取出的顺序一致的)；
3.List接口下的所有集合全部拥有下标，List接口更像数组；
4.由于List接口规定自己的真实实现类（集合）都拥有下标，因此我们在操作List接口下的所有集合容器的时候，都可以通过下标操作；
5.因此在List接口中它不仅仅继承到Collection接口中的所有函数，同时java 还根据List的下标的特性，定义了适合List接口的特有函数；
1.2 LinkedList
LinkedList集合：它也是List接口的实现类，它的底层使用的链接列表（链表）数据结构。
链表结构的特点：有头有尾。
链表结构：由一个链子把多个节点连接起来的数据结构。
节点：在链表结构中每个可以保存数据的空间称为节点，而一个链表结构是由多个节点组成的。
也就是说链表结构使用节点来存储数据。
每个节点(存储数据的空间)可以分成若*分，其中有一部分存储数据，另外一部分存储的是其他节点的地址。
特点:
1、它的底层使用的链表结构；
2、有头有尾，其中的方法都是围绕头和尾设计的；
3、LinkedList集合可以根据头尾进行各种操作，但它的增删效率高，查询效率低；
LinkedList集合增删效率高是因为底层是链表结构，如果增加或者删除只需要在增加或者删除节点的位置上记住新的节点的地址即可，而其他节点不需要移动，所以速度会快。
而查询遍历由于链表结构的特点，查询只能从头一直遍历到链表的结尾，所以速度会慢。
4、LinkedList集合底层也是线程不安全。效率高；
5、也可以存储null元素；
2.Set
不能保存重复元素，没有下标。可以存储null但只能有一个。并且不保证存取的顺序，也就是说对于集合set进行存取操作的时候都没有任何顺序，没有任何规律而言。
2.1 HashSet集合
说明：
1）实现了Set接口，具备了Set集合的特性；
2）不保证集合中的迭代顺序（不保证元素存取一致），允许存储null元素；
底层使用哈希表结构；
2.2 哈希表介绍(掌握)
哈希表：
它是一个数据结构，底层依赖的是数组，只是不按照数组的下标操作数组中的元素。需要根据数组中存储的元素的哈希值进行元素操作。
哈希表的存储过程：
1）哈希表底层是一个数组，我们必须知道集合中的一个对象元素到底要存储到哈希表中的数组的哪个位置，也就是需要一个下标。
2）哈希表会根据集合中的每个对象元素的内容计算得出一个整数值。由于集合中的对象元素类型是任意的，而现在这里使用的算法必须是任意类型的元素都可以使用的算法。能够让任意类型的对象元素都可以使用的算法肯定在任意类型的对象所属类的父类中，即上帝类Object中，这个算法就是Object类中的hashCode()函数。
结论：要给HashSet集合中保存对象，需要调用对象的hashCode函数。
3）hashCode算法，得到一个整数，但是这个整数太大了，这个值不能直接作为数组下标的。所以底层还会对这个值结合数组的长度继续计算运行，得到一个在0~数组长度-1之间的整数，这样就可以作为数组的下标了。
面试题：哈希表如何保证元素唯一？
哈希表保证元素唯一依赖两个方法：hashCode和equals。
哈希表底层其实还是一个数组，元素在存储的时候，会先通过hashCode算法结合数组长度得到一个索引。然后判断该索引位置是否有元素：如果没有，不用调用equals函数，直接存储；如果有，再调用元素的equals方法比较是否相同：相同，直接舍弃；如果不同，也存储。
2.3 HashSet保存自定义对象
package cn.itcast.sh.set;
import java.util.HashSet;
import java.util.Iterator;
/*
* 使用哈希表存储自定义对象
*/
public class HashSetDemo2 {
public static void main(String[] args) {
//创建集合对象
HashSet set=new HashSet();
//向集合中添加自定义对象数据
set.add(new Person("黑旋风",19));
set.add(new Person("助教",18));
set.add(new Person("班导",28));
set.add(new Person("班长",19));
set.add(new Person("黑旋风",19));
//循环遍历集合
for (Iterator it = set.iterator(); it.hasNext();) {
//输出数据
System.out.println(it.next());
}
}
}
结果如下
上述代码有问题，为什么以上程序中的HashSet集合中会出现相同的Person类的对象？
给哈希表中保存自定义对象时，由于每次创建的都是新的Person对象，而每个Person对象都有自己的唯一的内存地址，就是每个对象的内存地址都不相同。并且在给哈希表中存放这些对象的时候每个对象都需要调用自己从Object类中继承到的hashCode函数，而hashCode函数会根据每个对象自己内存地址计算每个对象哈希值，每个对象的内存地址不同，计算出来的哈希值也一定不同，最后就会导致生成的底层的数组的下标也不相同。如果下标不一样，根本就不会去调用equals比较是否是同一个元素，直接就会导致每个对象都可以正常的保存到哈希表中。
自己定义的对象，有自己所属的类，而这个类继承到了Object的hashCode函数，所以导致这个函数是根据对象内存地址计算哈希值，而我们更希望根据对象自己的特有数据(name和age的属性值)来计算哈希值。
问题：那么为什么我们之前向集合中保存String类的字符串对象时没有出现这种现象呢？
因为在String类中已经复写了Object类中的hashCode()和equals()函数，所以存储字符串对象的时候，底层调用的hashCode()和equals()函数根本就不是Object类中的而是String类中已经复写好的函数。
也就是对于String类的对象调用自己的hashCode函数，根本就不是根据字符串对象的地址计算出来的哈希码值，而是根据字符串内容计算出来的。
对于equals函数，也是调用自己的函数，底层根本比较不是 this==obj,而是比较的是字符串对象的内容。
解决上述问题的办法：
所以我们需要重写Object类中的hashCode方法。这样重写完之后就会根据对象特有的数据来计算哈希值了，而不再是根据对象的随机地址生成哈希值了。在这里：根据姓名和年龄计算。
上述办法只重写hashCode函数，仅仅是保证了对象内容相同时计算的数组下标相同。同时即使一个人的姓名和年龄不相等，也有可能计算的下标是相同的。所以，当数组下标相同时，我们接下来还要调用equals函数来比较对象元素的内容。根据我们之前所学的Object类中的equals函数得知，Object类中的equals函数体是比较两个对象的地址值是否相等，那么即使两个对象内容的下标相同，但是equals函数比较的不是两个对象的内容，是地址，也会永远不相等，所以这里也得复写Object类中的equals()函数。这样才能保证当两个对象内容一致不会被保存到HashSet集合中。
所以还得重写equals方法。