Java集合(二)List和set
一、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常用方法:
- add([int index],E element)和addAll([int index],Collection c)增加元素
- contains(Object o)和containsAll(Collection c)判断元素是否存在
- get(int index)根据索引获取元素(集合下表从0开始)
- indexOf(Object o)和lastIndexOf(Object o)获取指定元素索引
- indexOf(Object o)和lastIndexOf(Object o)获取指定元素索引
- isEmpty()判断是否为空
- remove(int index)和remove(Object o)和removeAll(Collection c)删除元素
- set(int index,Object o)覆盖元素
- size()返回集合的大小
- toArray()按照从前到后的顺序返回包含此列表中所有元素的数组
- iterator()和listIterator([int index]) 迭代器
- clear()清空集合
LinkedList新增方法:、
-
void addFirst(Object obj):在0的位置新增一个obj
-
void addLast(Object obj):在最后的位新增一个obj
-
Object getFirst():获取第一个元素
-
Object getLast():获取最后一个元素
-
Object removeFirst():删除第一个元素
-
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子类对象。