首先list与set都继承于Collection( 描述所有集合共性的接口),list以序列的形式存储元素。所以取出来的顺序可能和放入顺序不同。set的特点是无法存放重复的元素。map特点:一个映射不能包含重复的键;每个键最多只能映射一个值。以键值对存放数据。三者都是接口且不能被实例化。
1. List
定义:实现了 Collection 接口,实现类:ArrayList 、 LinkedList 和 Vector,ArrayList提供了使用索引的随意访问,而 LinkedList 则对于经常需要从 List 中添加或删除元素的场合更为合适。Vector实现了一个动态数组。
特点:
1.可以允许重复的对象。
2.可以插入多个null元素。
3.是一个有序容器,保持了每个元素的插入顺序,输出的顺序就是插入的顺序。
1.1 ArrayList
ArrayList 是一个数组队列,相当于 动态数组。与Java中的数组相比,它的容量能动态增长。它继承于AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。
提供了快速的基于索引的成员访问方式,对尾部成员的增加和删除支持较好。使用 ArrayList 创建的集合,允许对集合中的元素进行快速的随机访问,不过,向 ArrayList 中插入与删除元素的速度相对较慢。该类的常用构造方法有如下两种重载形式。ArrayList():构造一个初始容量为 10 的空列表。ArrayList(Collection<?extends E>c):构造一个包含指定 Collection 的元素的列表,这些元素是按照该 Collection 的迭代器返回它们的顺序排列的。
方法 | 作用 |
---|---|
add(int index, Object obj) | 增加元素, |
size() | 长度 |
get() | 获取第i个 |
set() | 修改某位置的元素 |
remove() | 可以放下标,也可以放元素;ps:如果删除的元素存在多个,删除第一个; |
indexOf(), | 用来获得指定对象的索引位置,当存在多个时返回第一个的索引位置,否则返回-1 |
lastIndexOf(Object obj) | 用来获得指定对象的索引位置,当存在多个时返回最后一个的索引位置,否则返回-1 |
addAll(int, Collection coll) | 用来向集合的指定索引位置添加指定集合的所有对象 |
toArray() | 入参为一个数组,将list的元素复制到数组中 |
clear() | 清空集合中的所有元素 |
contains() | 判断集合是否包含制定元素 |
containsAll() | 判断集合是否包含制定集合的所有元素,跟顺序无关 |
isEmpty() | 判断集合是否为空size == 0 |
trimToSize() | 将数组还原到当前大小容量 |
1 | public class Demo7 { |
1.2 LinkedList
采用链表结构保存对象,这种结构的优点是便于向集合中插入或者删除元素。需要频繁向集合中插入和删除元素时,使用 LinkedList 类比 ArrayList 类效果高,但是 LinkedList 类随机访问元素的速度则相对较慢。这里的随机访问是指检索集合中特定索引位置的元素。
1.3 Vector
实现了一个动态数组。和 ArrayList 很相似,但是两者是不同的:
- Vector 是同步访问的。
- Vector 包含了许多传统的方法,这些方法不属于集合框架。
Vector 主要用在事先不知道数组的大小,或者只是需要一个可以改变大小的数组的情况。
1 | public class Demo6 { |
2. Set
特点:
1.不允许重复对象
2.无序容器,你无法保证每个元素的存储顺序,TreeSet通过 Comparator 或者 Comparable 维护了一个排序顺序。
3.只允许一个 null 元素
Set 接口最流行的几个实现类是 HashSet、LinkedHashSet 以及 TreeSet。最流行的是基于 HashMap 实现的 HashSet;TreeSet 还实现了 SortedSet 接口,因此 TreeSet 是一个根据其 compare() 和 compareTo() 的定义进行排序的有序容器。
2.1 HashSet
线程不安全,存取速度快。底层是以哈希表实现的
1 | public class Demo { |
2.2 HashSet判断元素重复原理
通过hashCode方法和equals方法来保证元素的唯一性,add()返回的是boolean类型。
判断两个元素是否相同,先要判断元素的hashCode值是否一致,只有在该值一致的情况下,才会判断equals方法,如果存储在HashSet中的两个对象hashCode方法的值相同equals方法返回的结果是true,那么HashSet认为这两个元素是相同元素,只存储一个(重复元素无法存入)。
注意:HashSet集合在判断元素是否相同先判断hashCode方法,如果相同才会判断equals。如果不相同,是不会调用equals方法的。
2.3 TreeSet
适用场景:同时要求数据有序且不重复时。ArrayList 、 LinkedList不能去除重复数据。HashSet可以去除重复,但是是无序。
1 | public class Demo { |
3 map
1.Map不是collection的子接口或者实现类。Map是一个接口。
2.Map 的 每个 Entry 都持有两个对象,也就是一个键一个值,Map 可能会持有相同的值对象但键对象必须是唯一的。
3.TreeMap 也通过 Comparator 或者 Comparable 维护了一个排序顺序。
4.Map 里你可以拥有随意个 null 值但最多只能有一个 null 键。
Map 接口最常用的几个实现类是 HashMap、LinkedHashMap、Hashtable 和 TreeMap。(HashMap、TreeMap最常用)
3.1 HashMap
最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值,具有很快的访问速度。HashMap最多只允许一条记录的键为Null(多条会覆盖);允许多条记录的值为 Null。
hashmap是一个散列表,存储内容为键值对(key: value)的映射形式
hashmap继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口
HashMap的实现不是同步的,这意味着它不是线程安全的。它的key、value都可以为null。此外,HashMap中的映射不是有序的。
HashMap实例有两个影响其性能的参数:初始容量和oad因子。容量是哈希表中的桶数,初始容量就是创建哈希表时的容量。负载因子是衡量在哈希表的容量被自动增加之前,哈希表被允许获得多少满的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时,哈希表将被重新哈希(即重新构建内部数据结构),这样哈希表的桶数大约是桶数的两倍。
3.2 HashMap四种遍历
增强for循环keySet(), entrySet(),与迭代器keySet(), entrySet()。
1 | public class Demo3 { |
总结:
- 增强for循环使用方便,但性能较差,不适合处理超大量级的数据。
- 迭代器的遍历速度要比增强for循环快很多,是增强for循环的2倍左右。
- 使用entrySet遍历的速度要比keySet快很多,是keySet的1.5倍左右。
3.3 Hashtable
与 HashMap类似,不同的是:key和value的值均不允许为null;它支持线程的同步,即任一时刻只有一个线程能写Hashtable,因此也导致了Hashtale在写入时会比较慢。
1 | public class Demo2 { |
3.4 TreeMap
TreeMap用于存储与HashMap
类非常相似的键值对。区别在于TreeMap提供了一种以排序顺序存储键/值对的有效方法。它是基于红黑树的NavigableMap
实现。能够把它保存的记录根据键(key)排序,默认是按升序排序,也可以指定排序的比较器,当用Iterator 遍历TreeMap时,得到的记录是排过序的。TreeMap不允许key的值为null。非同步的。
1 | public class Demo1 { |
3.5 红黑树
红黑树是一棵二叉搜索树,它在每个节点增加了一个存储位记录节点的颜色,可以是RED,也可以是BLACK;通过任意一条从根到叶子简单路径上颜色的约束,红黑树保证最长路径不超过最短路径的二倍,因而近似平衡。
具体性质如下:
1.每个节点颜色非黑即红。
2.根节点是黑色的
3.如果一个节点是红色,那么它的两个子节点就是黑色的(没有连续的红节点)
4.对于每个节点,从该节点到其后代叶节点的简单路径上,均包含相同数目的黑色节点
3.6 LinkedHashMap
保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的.在遍历的时候会比HashMap慢。key和value均允许为空,非同步的
1 | public class Demo8 { |