2.0 具体的集合

Wu Jun 2020-01-01 08:43:49
Categories: > > Tags:
集合类型 同步 可null 有序 描述
ArrayList 动态增缩的索引序列
Vector 过时,同步的ArrayList
LinkedList 高效插删的有序序列
ArrayDeque 循环数组实现的双端队列
PriorityQueue - 数组实现的小顶堆
TreeMap 一种键值有序排列的映射表
TreeSet TreeMap的适配器
HashMap 一种存储键值关联的数据结构
HashSet HashMap的适配器
Hashtable 同步HashMap,单个锁,效率低
ConcurrentHashMap 同步HashMap,锁分离,get不需锁,推荐
ConcurrentHashSet ConcurrentHashMap 的适配器
ConcurrentSkipListMap
ConcurrentSkipListSet
ConcurrentLinkedQueue
CopyOnWriteArrayList - - 写时复制,读多写少时替代ArrayList
CopyOnWriteArraySet - - CopyOnWriteArrayList的适配器
LinkedHashMap 有序的映射表
LinkedHashSet LinkedHashMap的适配器
WeakHashMap 弱引用的HashMap
EnumSet - - - 一种包含枚举类型值的集合
EnumMap - - - 一种键值属于枚举类型的映射表
IdentityHashMap - - - 一种用==,而不是用equals比较键值的映射表

1 链表

LinkedList

2 动态数组列表

ArrayList

vector 是同步安全的,效率低下,这是 ArrayList 取代它的原因。在不需要同步的时候使用 ArrayList。

3 散列集

Hashtable

HashSet

4 树集

TreeSet 与散列集相比,更加有序,树集是一个有序集合,该有序是指插入元素具备的自然顺序,不是插入顺序。将一个元素添加到树集比添加到散列表中要慢,但是,与数组和链表相比还是快很多。由于是二叉树,呈现对数级的消耗。树集相对于散列表的优点是遍历时是有序遍历的。

与 TreeSet 一样,一个优先队列即可以保存实现了 Comparable 接口的对象,也可以保存在构造器中提供比较器的对象。

HashSet 与 TreeSet 选择时,如果不需要对数据进行排序,就没必要选用 TreeSet

5 对象的比较

5.1 Comparable

Comparable 接口定义了 compareTo 方法

如果 a 与 b 相等,调用 a.compareTo(b) 一定返回 0;如果排序后 a 位于 b 之前,则返回负值;如 果a位于b之后,则返回正值。

5.2 Comparator

Comparator 接口声明了一个带有两个显式参数的 compare(a,b) 方法
与compareTo方法一样,如果a位于b之前compare方法则返回负值;如果a和b相等则返回0, 否则返回正值

匿名内部类

Collections.sort(persons,new 
    Comparator<Person>() {
        @Override
        public int compare(Person p1,Person p2) {
            if(p1.age > p2.age) return 1;
            else if (p1.age == p2.age) return 0;
            else return -1;
        }
    });

6 队列与双端队列

Deque 接口,ArrayDeque 和 LinkedList 都实现了双端队列结构,并且在必要时候可以进行扩容。

7 优先级队列

优先级队列 PriorityQueue 中的元素可以按照任意的顺序插入,却总按照排序的顺序进行检索。采用的二叉堆(binary heap)的数据结构,堆是一个可以自我调整的二叉树,对树执行添加和删除操作,可以让最小的元素移动到根,而不必花费必要的时间进行排序。

8 映射表

HashMap 和 TreeMap 类比于 HashSet 和 TreeSet,TreeMap 键有序,但是插入效率低于HashMap。

集合框架没有包括映射表,Map 和 Collection 是一级。但是可以通过 entrySet() 获取映射表的视图,即 Set<Map.Entry<K,V>>。