Java集合（二）List和set

时间  2021-01-09

一、List集合

List集合是有序，可重复的集合。每个元素都有其对应的顺序索引。List 是 Collection 的子接口。

在List集合中，我们常用到ArrayList和LinkedList这两个类。（还有个vector类集合）

ArrayList是Java集合框架中使用最多的一个类，是一个数组队列，线程不安全集合。

它继承于AbstractList，实现了List, RandomAccess, Cloneable, Serializable接口。
(1)ArrayList实现List，得到了List集合框架基础功能；
(2)ArrayList实现RandomAccess，获得了快速随机访问存储元素的功能，RandomAccess是一个标记接口，没有任何方法；
(3)ArrayList实现Cloneable，得到了clone()方法，可以实现克隆功能；
(4)ArrayList实现Serializable，表示可以被序列化，通过序列化去传输，典型的应用就是hessian协议。

它具有如下特点：

  • 容量不固定，随着容量的增加而动态扩容（阈值基本不会达到）
  • 有序集合（插入的顺序==输出的顺序）
  • 插入的元素可以为null
  • 增删改查效率更高（相对于LinkedList来说）
  • 线程不安全

数据结构：（JDK1.7）

image

LinkedList是一个双向链表，每一个节点都拥有指向前后节点的引用。相比于ArrayList来说，LinkedList的随机访问效率更低。

它继承AbstractSequentialList，实现了List, Deque, Cloneable, Serializable接口。
(1)LinkedList实现List，得到了List集合框架基础功能；
(2)LinkedList实现Deque，Deque 是一个双向队列，也就是既可以先入先出，又可以先入后出，说简单些就是既可以在头部添加元素，也可以在尾部添加元素；
(3)LinkedList实现Cloneable，得到了clone()方法，可以实现克隆功能；
(4)LinkedList实现Serializable，表示可以被序列化，通过序列化去传输，典型的应用就是hessian协议。

数据结构：（JDK1.7）

ArrayList和LinkedList比较

（1）元素新增性能比较：

ArrayList效率不如LinkedList，因为ArrayList底层是数组实现，在动态扩容时，性能有所损耗，而LinkedList不存在数组扩容机制，所以LinkedList效率更高。但在现在两者速度基本差不多。

（2）元素获取比较：

由于LinkedList是链表结构，没有角标的概念，没有实现RandomAccess接口，不具备随机元素访问功能，所以在get方面表现的差强人意，ArrayList再一次完胜。

结果：

从结果中可以看到，ArrayList在随机访问方面表现的十分优秀，比LinkedList强了很多，基本上保持在10多倍以上。

LinkedList为什么这么慢呢？这主要是LinkedList的代码实现所致，每一次获取都是从头开始遍历，一个个节点去查找，每查找一次就遍历一次，所以性能自然得不到提升。

ArrayList常用方法：

  1. add([int index],E element)和addAll([int index],Collection c)增加元素
  2. contains(Object o)和containsAll(Collection c)判断元素是否存在
  3. get(int index)根据索引获取元素（集合下表从0开始）
  4. indexOf(Object o)和lastIndexOf(Object o)获取指定元素索引
  5. indexOf(Object o)和lastIndexOf(Object o)获取指定元素索引
  6. isEmpty()判断是否为空
  7. remove(int index)和remove(Object o)和removeAll(Collection c)删除元素
  8. set(int index,Object o)覆盖元素
  9. size()返回集合的大小
  10. toArray()按照从前到后的顺序返回包含此列表中所有元素的数组
  11. iterator()和listIterator([int index]) 迭代器
  12. clear()清空集合

LinkedList新增方法：、

  1. void addFirst(Object obj)：在0的位置新增一个obj

  2. void addLast(Object obj)：在最后的位新增一个obj

  3. Object getFirst()：获取第一个元素

  4. Object getLast()：获取最后一个元素

  5. Object removeFirst()：删除第一个元素

  6. Object removeLast()：删除最后一个元素

二、set集合

Set:注重独一无二的性质,该体系集合可以知道某物是否已近存在于集合中,不会存储重复的元素

用于存储无序(存入和取出的顺序不一定相同)元素，值不能重复。

对象的相等性

引用到堆上同一个对象的两个引用是相等的。如果对两个引用调用hashCode方法，会得到相同的结果，如果对象所属的类没有覆盖Object的hashCode方法的话，hashCode会返回每个对象特有的序号（java是依据对象的内存地址计算出的此序号），所以两个不同的对象的hashCode值是不可能相等的。

如果想要让两个不同的Person对象视为相等的，就必须覆盖Object继下来的hashCode方法和equals方法，因为Object hashCode方法返回的是该对象的内存地址，所以必须重写hashCode方法，才能保证两个不同的对象具有相同的hashCode，同时也需要两个不同对象比较equals方法会返回true

该集合中没有特有的方法，直接继承自Collection。

1、HashSet

哈希表边存放的是哈希值。HashSet存储元素的顺序并不是按照存入时的顺序（和List显然不同） 是按照哈希值来存的所以取数据也是按照哈希值取得。

HashSet不存入重复元素的规则.使用hashcode和equals

在像HashSet集合中添加一个元素的时候，会先用其hashcode进行比较，如果hashcode相等，那么在调用equals方法

来判断这两个元素是否是同一个元素，如果是同一个元素的话，就不允许添加进来，这就是HashSet中元素的单一性。

由于Set集合是不能存入重复元素的集合。那么HashSet也是具备这一特性的。HashSet如何检查重复？HashSet会通过元素的hashcode（）和equals方法进行判断元素师否重复。

当你试图把对象加入HashSet时，HashSet会使用对象的hashCode来判断对象加入的位置。同时也会与其他已经加入的对象的hashCode进行比较，如果没有相等的hashCode，HashSet就会假设对象没有重复出现。

简单一句话，如果对象的hashCode值是不同的，那么HashSet会认为对象是不可能相等的。

因此我们自定义类的时候需要重写hashCode，来确保对象具有相同的hashCode值。

如果元素(对象)的hashCode值相同,是不是就无法存入HashSet中了? 当然不是,会继续使用equals 进行比较.如果 equals为true 那么HashSet认为新加入的对象重复了,所以加入失败。如果equals 为false那么HashSet 认为新加入的对象没有重复.新元素可以存入.

 

2、TreeSet类
TreeSet是SortedSet接口的实现类，TreeSet可以确保集合元素处于排序状态。

treeSet存入数据后自动调用元素的compareTo(Object obj) 方法，自动对数据进行排序 * 所以输出的数据是经过排序的数据 * 注：compareTo方法返回值有：负数，零，正数。分别表示小于，等于，大于 * 对于存入自定义的对象元素，要重写元素的compareTo(Object obj)方法 * 元素定义时，需要实现Comparable接口

内部存储机制
TreeSet内部实现的是红黑树，默认整形排序为从小到大。


与HashSet集合相比，TreeSet还提供了几个额外方法：

Comparator comparator():如果TreeSet采用了定制顺序，则该方法返回定制排序所使用的Comparator，如果TreeSet采用自然排序，则返回null；
Object first():返回集合中的第一个元素；
Object last():返回集合中的最后一个元素；
Object lower(Object e)：返回指定元素之前的元素。
Object higher(Object e)：返回指定元素之后的元素。
SortedSet subSet（Object fromElement，Object toElement）：返回此Set的子集合，含头不含尾；
SortedSet headSet(Object toElement)：返回此Set的子集，由小于toElement的元素组成；
SortedSet tailSet(Object fromElement)：返回此Set的子集，由大于fromElement的元素组成;

自然排序

TreeSet会调用集合元素的compareTo(Objec obj)方法来比较元素之间的大小关系，然后将集合元素按升序排列，这就是自然排序。

Java提供了一个Comparable接口，该接口里定义了一个compareTo(Object obj)方法，该方法返回一个整数值，实现该接口的类必须实现该方法，实现了该接口的类必须实现该方法，实现接口的类就可以比较大小了。当调用一个一个对象调用该方法与另一个对象进行比较时，obj1.compareTo(obj2)如果返回0表示两个对象相等；如果返回正整数则表明obj1大于obj2,如果是负整数则相反。

当把一个对象添加进集合时，集合调用该对象的CompareTo(Object obj)方法与容器中的其他对象比较大小，然后根据红黑树结构中找到它的存储位置。如果两个对象相等则新对象无法加入到集合中。

注意问题

大部分类在实现CompareTo(Object o)方法时，都需要将被比较对象obj强制类型转换成相同类型，因为只有相同的两个实例才会比较大小。
加入集合的类都必须实现Comparable接口，否则会引发ClassCastException异常。
向TreeSet集合中添加元素时，只有第一个元素无须实现Comparable接口，后面添加的所有元素都必须实现Comparable接口。当然这也不是一种好做法，当试图从TreeSet中取出元素时，依然会引发ClassCastException异常。
不要修改已经存入集合的实例变量，这将导致它与其他对象的大小顺序发生改变，但TreeSet集合不会再次调整它们的顺序，这点和HashSet一样。
总结：如果希望TreeSet能正常工作，TreeSet只能添加同一种类型的对象

对于TreeSet集合而言，它判断两个对象是否相等的唯一标准是：两个对象通过compareTo(Object obj)方法比较是否返回0，如果是0则认为对象相等，否则认为不相等。

定制排序

TreeSet的自然排序是根据集合元素的大小，TreeSet将它们以升序排列。如果需要实现定制排序，例如降序排序，则可通过Comparator接口的帮助。该接口里包含一个int compare(T o1,T o2)方法，用于比较o1和o2的大小。由于Comparator是一个函数式接口，因此还可以使用Lambda表达式来代替Comparator子类对象。  

联系我们 沪ICP备2021010478号-7