Java中List集合与Set集合
一、List 集合
List 是一个接口，是有序的 collection，此接口的用户可以对列表中每个元素的插入位置进行精确的控制，用户可以根据元素的整数索引访问元素，并搜索列表中的元素。List 接口允许存放重复的元素，并且元素都是有序的（Set 接口不允许存放重复元素，元素是无序的）
1、List 接口特点
它是一个有序的集合
他是一个带索引的集合，通过索引就可以精确地操作集合中的元素（与数组的索引是一个道理）
集合中可以有重复的元素，可以通过 equals 方法来比较是否为重复的元素
List 接口常用的子类有：ArrayList 集合、LinkedList 集合
2、List 接口中常用的方法
boolean add(Object e)：向集合末尾添加指定元素
void add(int index，Object e)：向集合指定索引处添加指定元素，原有元素依次后移
remove(Object e)：将指定元素对象从集合中删除，返回被删除的元素
remove(int index)：将指定索引处的元素从集合中删除，返回被删除的元素
set(int index，Object e)：将指定索引处的元素替换成指定的元素，返回替换前的元素
get(int index)：获取指定索引处的元素，返回该元素
public static void main(String[] args)
{
List<String> L = new ArrayList<>();
//末尾添加元素
L.add("abc");
L.add("bcd");
L.add("cde");
L.add("def");
L.add("efg");
//指定位置添加元素
L.add(2,"fgh");
//删除指定元素
L.remove("abc");
//删除指定索引元素
L.remove(1);
//将指定索引处的元素替换成指定元素
L.set(1,"hello");
//获取指定索引处的元素
L.get(1);
//使用迭代器获取出集合中的元素,最好使用listIterator进行迭代
Iterator<String> it = L.listIterator();
while(it.hasNext())
{
System.out.println(it.next());
}
//由于List集合是有索引的，还可以使用索引进行迭代
for(int i = 0;i < L.size();i++)
{
System.out.println(L.get(i));
}
}
注：
List 集合是带索引的有序集合，因此除了使用迭代器进行获取元素外，还可以使用索引下表进行元素获取
Iterator 迭代 List 异常问题：在迭代过程中，如果要添加一个新的元素，使用集合的方法对元素进行操作，会导致迭代器不知道集合中的变化，容易发生数据的不确定性。因此，通过 listIterator 迭代能避免这个异常。
3、List 集合存储数据结构
List 接口下有多个集合，它们存储元素所采用的数据结构方式有所不同，这就导致了不同集合有其不同特点，供程序员在不同的环境下使用。
数据存储的常用结构有：堆栈、队列、数组、链表
堆栈
(1) 先进后出
(2) 栈的入口、出口都是栈的顶端位置
(3) 压栈：即存元素
(4) 出栈：即取元素
队列
(1) 先进先出
(2) 队列的入口、出口为两端
数组
(1) 查找元素快：通过索引快速访问指定元素位置
(2) 增删元素慢：指定位置增加、删除元素都需要创建一个新的数组，将指定新元素存储在指定索引位置，再把原数组索引根据索引复制到新数组对应索引位置
链表
(1) 多个节点之间，通过地址进行连接
(2) 查找元素慢：想要查找某个元素，需要通过连接的节点，依次向后查找指定元素
(3) 增删元素快：只需修改连接下个元素的地址即可
4、ArrayList 集合
ArrayList 集合是最常用的集合，是用存储数据结构，元素增删慢，查找快。
在我的另一篇博客：Java中ArrayList集合有其的介绍，这里不多说
5、LinkedList 集合
LinkedList 集合数据存储的结构是链表结构，对元素的增删很方便，实际开发中对一个集合元素的增删经常涉及到首位操作，而 LinkedList 集合提供了大量的首位操作方法。
void addFirst(E e)：将指定元素插入链表的开头
void addLast(E e)：将指定元素插入链表的结尾
E getFirst()：返回链表的第一个元素
E getLast()：返回链表的最后一个元素
E removeFirst()：移除并返回链表的第一个元素
E removeLast()：移除并返回链表的最后一个元素
E pop(E e)：取出链表栈顶元素
void push(E e)：将元素推入此链表所示的堆栈
boolean isEmpty()：判断链表中是否有元素
逻辑实例：
public static void main(String[] args)
{
//创建链表
LinkedList<String> link = new LinkedList<>();
//添加元素
link.add("abc");
link.add("bcd");
link.add("cde");
link.add("def");
//获取元素
System.out.println(link.getFirst());
System.out.println(link.getLast());
//删除元素
System.out.println(link.remove("abc"));
System.out.println(link.removeFirst());
while (link.isEmpty()) //判断集合是否有元素
{
System.out.println(link.pop()); //取出栈顶元素
}
}
6、Vector 集合
Vector 集合数据存储结构是数组结构，与 ArrayList 不同之处在于提供了一个独特的取出方法：枚举Enumeration，与 Iterator 接口功能类似。Vector 集合已被 ArrayList 集合替代，枚举Enumeration 已被迭代器 Iterator 替代
二、Set 接口
Set 集合里面存储的是无序的不重复元素，没有索引，可以采用迭代器和增强for来获取元素，Set 常用的子类有 HashSet、LinkedHashSet 集合，可以通过 equals 方法来判断是否为重复元素。
1、HashSet 集合
HashSet 类实现 Set 接口，由哈希表支持（实际上是一个 HashMap 集合），HashSet 集合不能保证迭代顺序与元素存储顺序相同，采用哈希表结构存储数据结构，保证元素唯一性的方式依赖于：hashCode() 于 equals() 方法。
特点：无序集合，存储和取出的顺序不同，没有索引，不存储重复元素
在代码编写上和 ArrayList 完全一致
存储、取出数据都比较快
线程不安全，运行速度快
底层数据结构为哈希表（链表数组结合体）
public static void main(String[] args)
{
//使用多态创建哈希表
Set<String> S = new HashSet<>();
S.add("abc");
S.add("bcd");
S.add("cde");
//使用迭代器获取元素
Iterator<String> it = S.iterator();
while (it.hasNext())
{
System.out.println(it.next());
}
//使用增强获取元素
for(String s : S)
{
System.out.println(s);
}
}
2、HashSet 集合存储数据的结构（哈希表）
哈希表介绍：
哈希表底层使用的是数组机制，数组中也存放对象，而这些对象往数组中存放时的位置比较特殊，当需要把对象在这些数组中存放时，会根据这些对象特有的数据来结合相应的算法，计算出这个对象在数组中的位置，然后把这个对象存放在数组中。这样的数组就称为哈希数组，即哈希表。
在哈希表存储数组时，会先记录第一个元素的地址，继续存储时，会让先来的元素记录后来的地址，在这里有一个“桶”和“加载因子”的概念，桶：数组的初始容量，初始容量为16；加载因子：数组的长度百分比，默认为0.75。数组的长度：16*0.75 = 12；当存放的数据超出数组长度 12 时，数组就会进行扩容，即复制（这个过程很耗费资源），这个过程也称为数据的再哈希 rehash。
当向哈希表存放元素时，会根据元素的特有数据结合响应的算法，这个算法就是 Object 类中的 hashCode 方法。由于任何对象都是 Object 类的子类，所以任何对象都有这个方法，即：在哈希表中存放对象时，会调用对象的 hashCode 方法，算出对象在表中的位置，需要注意的是，如果两个对象 hashCode 方法算出结果一样，称为哈希冲突，这样会调用对象 equals 方法来比较两个对象是不是同一个对象，如果返回 true，则把第一个对象存放在哈希表中，如果返回 false，就会把这两个值都存放在哈希表中。
总结：保证 HashSet 集合元素的唯一，其实就是根据对象 hashCode 和 equals 方法来决定的。如果往集合中存放自定义对象，为了保证唯一性，就必须重写 hashCode 和 equals 方法建立属于当前对象的比较方法。
3、String 类的哈希值
哈希值表示普通的十进制整数， 是父类 Object 方法 public int hashCode() 的计算结果，String 类继承了Object，重写了 hashCode 方法。String 类中 hashCode 源码：
public int hashCode() {
int h = hash; //一开始变量 hash 为 0
if (h == 0 && value.length > 0) {
char val[] = value;
//返回字符串ASCII经过计算的和
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
因此，当使用String类定义两个对象：String S1 = new String("abc"); String S2 = new String("abc"); 对象S1和S2哈希值是相同的，然后集合会让后来的对象调用 equals 方法，如果返回 true，则集合判定元素重复，将其去除。
4、自定义对象重写hashCode和equals
给HashSet中存放自定义类型元素时，需要重写对象中的hashCode和equals方法，建立自己的比较方式，才能保证HashSet集合中的对象唯一。
创建Person类，在类中重写 hashCode 方法和 equals 方法
public class Person {
private String name;
private int age;
public Person(String name,int age)
{
this.name = name;
this.age = age;
}
public void setName(String name)
{
this.name = name;
}
public void setAge(int age)
{
this.age = age;
}
public String getName()
{
return name;
}
public int getAge()
{
return age;
}
public String toString() {
return name + age;
}
//重写hashCode方法
public int hashCode()
{
return name.hashCode() + age;
}
//重写equals方法
public boolean equals(Object obj)
{
if(this == obj)
return true;
if(obj == null)
return false;
if(obj instanceof Person)
{
Person P = (Person)obj;
return name.equals(obj.name) && age == P.age;
}
return false;
}
}
在main中调用，由于重写了 hashCode 和 equals 方法，所以相同类型元素将不会打印出
public static void main(String[] args)
{
//创建存储Person类的哈希表
HashSet<Person> H = new HashSet<>();
H.add(new Person("a",18));
H.add(new Person("a",18));
H.add(new Person("b",19));
H.add(new Person("c",20));
System.out.println(H);
}
5、LinkedHashSet集合
LinkedHashSet 类是基于链表的哈希表的实现，继承自 HashSet，是 Set 接口的实现，此实现与 HashSet 的不同之外在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，即按照将元素插入到 set 中的顺序（插入顺序）进行迭代。
LinkedHashSet 特点：具有顺序，存储和取出元素顺序相同
public class LinkedHashSetDemo {
public static void main(String[] args) {
LinkedHashSet<Integer> link = new LinkedHashSet<Integer>();
link.add(123);
link.add(44);
link.add(33);
link.add(33);
link.add(66);
link.add(11);
System.out.println(link);
}
}
hashCode 和 equals 方法的面试题
(1) 两个对象 Person P1 P2，如果两个对象的哈希值相同，则两个对象的 equals 一定返回 true 吗？
不一定为 true
(2) 两个对象 Person P1 P2，如果两个对象的 equals 方法返回 true，则两个对象的哈希值一定相同吗？
一定相同
