JAVA进阶之集合类（一）

 一、数组与集合类的关系

    我们知道数组可以用来保存多个数据或者对象，但是使用数组却存在两个问题：

• 数组大小不可扩展
• 数组无法反映映射关系

    举例来说，我们创建一个数组，int[] a = new int[3]，用数组a来保存我们的数组。在创建的时候，我们就需要声明数组的大小，这样虚拟机才会分配一个连续的内存空间来存储数组。假如此时我又有了新的数据，但是由于我们的数组已经满了，因此新的数据无法保存，我们只能创建一个更大的数组来保存数组，而无法在原有基础上进行扩展。

    其次，我们在数组里保存了很多数据，但是只是单一的数据而已，如果我们需要保存映射的关系，比如Key-value关系，那么数组就无法满足我们了。

    因此，针对数组存在的这两个问题，JAVA为我们提供了集合类。

二、集合类总述

        集合类分为四类：Set、List、Queue、Map。其中Set集合通常表示无序且不重复的，List集合通常表示有序且可重复的，Map通常表示映射关系，Queue则表示队列。

        其中Set、List、Queue都是实现了Collecion接口，具体关系如 图1 ：

图 1 Collection接口关系图

    而Map的关系图 如图2：

图 2 Map接口关系图

1、Collection接口

    Set、Queue、List都是实现了Collection接口，在Collection接口中定义了一些公共的方法，如下：

• boolean add（Object o）：向集合中添加一个元素
• boolean addAll（Collection c）：将集合c中所有的元素添加到指定集合中
• void clear（）： 清除集合中所有的元素，清除后结合中元素个数为0（size = 0）
• boolean contains（object o）： 判断是否存在指定元素（注意如何判断的对象是我们自定义的类，那么就需要覆写该类的equals（）方法）
• boolean containsAll(Collection o) ：判断是否包含o中所有元素，如果不是包含所有则返回false
• boolean isEmpty() ：返回集合是否为空
• Iterator iterator（）： 返回一个Iterator对象，用来遍历集合中的元素
• boolean remove（Object o） ：删除指定 的元素，如果包含一个或者多个元素o,则这些元素都会被删除。
• boolean retainAll（Collection a）：从集合中删除指定集合a中不包含的元素，即求原集合和a的交集
• boolean removeAll（Colleciton a）：从集合中删除集合a中包含的元素，如果删除一个或者一个以上则返回true
• Object[] toArray()： 将集合转化为数组

2、Iterator

    Iterator又称为遍历器，通常我们可以通过它来遍历Collecion集合中的元素。常用的方法如下：

• boolean hasNext（）：判断集合中是否还有元素没有遍历
• Object next（）：返回集合中的下一个元素
• void remove（）：删除当前next（）方法返回的元素

三、Set集合

        前面我们已经提到，Set集合通常用来表示无序且不可重复的数据。Set集合常见的实现类有HashSet、EnumSet、SortedSet，此外还有SortedSet的子类TreeSet以及HashSet的子类LinkedHashSet。

        在面试的时候，面试官经常会问，你对HashSet了解多少，它是同步的么？能否插入null值，是否有序？HashSet和HashMap有什么区别？带着这些问题，接下来我将会大家一一讲解。

1、HashSet

      HashSet，我们把它拆分为两部分，Hash和Set，Set上面已经讲过了，我们就来主要讲讲Hash。

（1）Hash算法

        由于Set集合是无序并且不重复的，因为元素彼此之间没有太大的关联，并且没有顺序。那么如果我们需要查找一个元素，那么我们就需要遍历整个集合来查找，这样性能很低。而HashSet则是按照Hash算法来进行数据的存储，因此就有很好的存取性能和查找性能。

（2）HashSet的特点：

• HashSet是无序的并且不可重复
• HashSet是不同步的，因此在多线程执行时需要手动同步
• HashSet中可以插入null值

（3）HashSet如何保证不重复

        要保证HashSet的值不重复，那么就需要在我们执行add（）方法添加元素时，判断我们添加的元素是否已经存在，也就是我们需要判断两个元素是否相等。

        在HashSet中，我们通常是通过计算元素的hash值来保存元素的，类似与数组中的索引，因此我们判断元素是否相等除了要考虑equals（）方法外，还有比较两个元素的hashCode（）。具体原则如下：

• 如果两个元素的equals（）返回true，那么他们的hashCode（）也应该相同
• 在对象中我们用来做为equals（）方法中比较的属性，都应该用来计算hashCode

总之，我们需要保证equals（）和hashCde都相等。    

2、LinkedHashSet

    LinkedHashSet是HashSet的子类，它除了使用HashCode来决定元素的存储位置外，还使用了链表来维护元素的次序，即保证了元素是按照插入顺序保存的。

3、TreeSet

        TreeSet是SortedSet的唯一实现类，相比于Set，它保证了Set中的元素是有序的，在这一点上似乎是与我们最初提出的Set是无序相违背的。

    （1）TreeSet的常用方法

• Comparator comparator（）：返回当前Set使用的Comparator，或者返回null表示以自然方式排序（具体后面会讲）
• Object first（）：返回第一个元素
• Object last（）：返回最后一个元素
• Object lower（Object e）:返回当前元素之前的元素
• Object higher（Object e）:返回当前元素之后的元素
• SortedSet subSet（fromElement，toElement）：返回从from（包含）到toElement（不包含）的Set子集合
• SortedSet headSet（toElment）：返回小于toElement的子集合
• SortedSet tailSet（fromElemt）:返回大于或者等于fromElement的子集合

    （2）TreeSet的排序规则

        TreeSet的排序是通过红黑树来实现的，而它的排序规则呢，通常分为两种：自然排序和定制排序

•  自然排序    

       Java中提供了一个Comparable接口，接口中有一个compareto（Object c）方法，利用该方法返回的int值（0是等于，整数大于，负数小于）来比较两个元素大小。常见的实现了此接口的类：String、Character、Boolean、BigDecimal、BigInteger、Date等。

        如果我们在TreeSet中的元素是JAVA提供的实现了Comparable接口的类的实例，那么就可以直接进行升序排序。

      如果我们使用的是自己定义的类，那么我们就需要实现Comparable接口，以及接口中的compareto(Object c)方法，这样我们才能进行比较，从而进行排序。但是需要注意一点为了保证数据的不可重复性，我们需要保证Compareto（）方法和equals（）方法在判断元素相等时统一，也就是在equals（）方法相等时，那么Comparato（）也应该判断相等。

• 定制排序    

    前面我们介绍的排序都是实现了Comparator接口和接口下的compareto（）方法来进行一个升序排序，但是如果我们需要进行一个降序排序呢？此时我们就需要自己定义排序的规则。

    具体方法是：在TreeSet中传入一个Comparator接口，并实现compare（Object  o1,Object o2）方法，通过返回的正数、负数、0来比较两个元素。

（3）TreeSet的特点

• TreeSet是有序的
• TreeSet中 的值一般是不允许重复的
• TreeSet中通常不允许放入null值
• TreeSet不是同步的