【Java】基础25：List、Set以及哈希表

昨天学习了几种简单数据结构，为何要了解数据结构？一方面的原因是因为集合的底层就是与其息息相关的。

• 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集合，存储和取出的顺序一致。 总结