Java--集合类之Collection与Map

上一篇:Java--集合类之Vector、BitSet、Stack、Hashtable

  • 集合(Collection):一组单独的元素,通常应用了某种规则。在这里,一个 List(列表)必须按特定的顺序容纳元素,而一个Set(集)不可包含任何重复的元素。相反,“包”(Bag)的概念未在新的集合库中实现,因为“列表”已提供了类似的功能。
  • 映射(Map):一系列“键-值”对(这已在散列表身上得到了充分的体现)。从表面看,这似乎应该成为一个“键-值”对的“集合”,但假若试图按那种方式实现它,就会发现实现过程相当笨拙。这进一步证明了应该分离成单独的概念。另一方面,可以方便地查看 Map的某个部分。只需创建一个集合,然后用它表示那一部分即可。这样一来,Map 就可以返回自己键的一个Set、一个包含自己值的List 或者包含自己“键 -值”对的一个List。和数组相似,Map可方便扩充到多个“维”,毋需涉及任何新概念。只需简单地在一 个Map 里包含其他 Map。 

Collection和 Map可通过多种形式实现,具体由编程要求决定。可以得出,如果访问List集合中的元素,可以通过元素的索引访问;如果访问Map集合中的元素,可以通过元素的键来访问;如果访问Set集合中的元素,只能通过元素本身来访问。

Collection:

下面总结集合能做的所有事情(亦可对 Set和List 做同样的事情,尽管 List 还提供了一 些额外的功能)。Map不是从 Collection 继承的,所以要单独对待。 

  • boolean add(Object) *保证集合内包含了自变量。如果它没有添加自变量,就返回 false
  • boolean addAll(Collection) *添加自变量内的所有元素。如果没有添加元素返回 true
  • void clear() *删除集合内的所有元素
  • boolean contains(Object) 若集合包含自变量,就返回“true”
  • boolean containsAll(Collection) 若集合包含了自变量内的所有元素,就返回“true”
  • boolean isEmpty() 若集合内没有元素,就返回“true”
  • Iterator iterator() 返回一个反复器,以用它遍历集合的各元素
  • boolean remove(Object) *如自变量在集合里,就删除那个元素的一个实例。如果已进行了删除,就返回 “true”
  • boolean removeAll(Collection) *删除自变量里的所有元素。如果已进行了任何删除,就返回“true”
  • boolean retainAll(Collection) *只保留包含在一个自变量里的元素(一个理论的“交集”)。如果已进行了任何改变,就返回“真”
  • int size() 返回集合内的元素数量
  • Object[] toArray() 返回包含了集合内所有元素的一个数组

*这是一个“可选的”方法,有的集合可能并未实现它。若确实如此,该方法就会遇到一个 UnsupportedOperatiionException,即一个“操作不支持”

Lists:

List(接口) 顺序是 List 最重要的特性;它可保证元素按照规定的顺序排列。List 继承Collection 并添加了大量方法,以便我们在 List 中部插入和删除元素(只推荐对LinkedList 这样做)。List 也会生成一个 ListIterator(列表反复器),利用它可在一个列表里朝两个方向遍历,同时插入和删除位于列表中部的元素(同样地,只建议对 LinkedList这样做)

ArrayList:

由一个数组后推得到的,ArrayList内部封装了一个动态的、允许再分配的Object数组。用于替换原先的Vector。允许我们快速访问元素,但在从列表中部插入和删除元素时,速度却嫌稍慢。一般只应该用ListIterator对一 个ArrayList 进行向前和向后遍历,不要用它删除和插入元素;与 LinkedList相比,它的效率要低许多。

ArrayList是线程不安全的,Vector是线程安全的。但由于Vector是非常古老的集合类,性能很差,通常我们都不使用Vector,即使对线程安全有需求,ArrayList也可以通过一些手段实现线程安全。

LinkedList:

LinkedList类是List接口的实现类,这意味着它可以根据索引随机访问集合中的元素。同时,LinkedList内部是以链表的形式保存元素,所以它的删除、插入效率很高。同时,LinkedList还实现了Deque接口,可以被当成双端队列来使用,因此既可以用作“栈”,也可以用作“队列”。

Sets:

Set拥有与 Collection完全相同的接口,所以和两种不同的 List 不同,它没有什么额外的功能。相反,Set 完全就是一个Collection,只是具有不同的行为。在这里,一个Set只允许每个对象存在一个实例。 添加到 Set里 的对象必须定义equals(),从而建立对象的唯一性。一个 Set不能保证自己可按任何特定的顺序维持自己的元素。

HashSet:

  • 最常用的Set实现类,按Hash算法存储元素,具有很好的存取和查找性能。
  • 不能保证元素和排列顺序。
  • HashSet不是线程同步的。
  • 集合的元素值可以为Null.
  • HashSet判断两个元素相等的标准是两个对象通过equals()方法比较相等,并且两个对象的hashCode()返回值相等。

创建一个新类并且要添加到一个HashSet中时,需要重写equals()方法和hashCode()方法,并且要保证两个对象equals()相等时hashCode()也要相等。

HashSet类有一个子类LinkedHashSet,子类在存储元素的时候会使用链表维护元素的次序,相对的,效率会较HashSet低一些。

LinkedHashSet:

HashSet的一个子类,也是根据hashCode()决定元素存储位置。但它同时用链表维护元素插入的顺序,这样使元素看起来像是以插入顺序保存的。也就是说当遍历LinkedHashSet时,LinkedHashSet会按元素添加顺序来遍历。

EnumSet:

  • EnumSet中所有key都必须是单个枚举类的枚举值,创建EnumSet时必须显式或隐式指定它的枚举类;
  • EnumSet内部以数组形式保存,所以这种形式非常紧凑、高效;
  • EnumSet根据枚举值在枚举类中的定义顺序排序;
  • EnumSet不允许加入null值。

TreeSet:

由一个“红黑树”后推得到的顺序 Set,是SortedSet接口的实现类。TreeSet可以保证元素的排序顺序。因为TreeSet是有序的,所以API提供了访问第一个、后一个、最后一个、前一个元素的方法,还提供了截取子TreeSet的方法。另外,TreeSet也不是线程同步的。

比较和排序问题:TreeSet会调用集合元素的compareTo(Object obj)方法来比较元素之间的大小关系,然后按升序排列。所以我们放进TreeSet中的对象都必须保证其所属类实现了Comparable接口(该接口中声明了compareTo()方法)。Java类库中的很多类都实现有Comparable接口。

注意,实现compareTo()方法时,必须将比较对象强制转换为相同类型。可以这样说,如果想让TreeSet正常工作,集合中只能添加同种类型的对象。当然,要保证compareTo()方法和equals()方法返回的意义相同。

定制排序:如果想要改变排序方式,可以通过Comparator接口实现。该接口是一个函数式接口。在创建一个TreeSet对象时,提供一个Comparator对象与该TreeSet集合关联,由该Comparator对象负责集合元素的排序逻辑。

Maps:

Map(接口) 维持“键-值”对应关系(对),以便通过一个键查找相应的值。 Map和Set有点类似,比如:

  • 如果把Map里所有key放一起看,就组成了一个Set(所有key没有顺序,不能重复),实际上Map有一个方法keySet()返回key组成的Set集合;
  • Map的key集和Set集合存储形式很像,Set有HashSet、LinkedHashSet、SortedSet、TreeSet、EnumSet等子接口和实现类,Map也有HashMap、LinkedHashMap、SortedMap、TreeMap、EnumMap等子接口和实现类。

HashMap:

基于散列表实现(用它代替Hashtable)。针对“键-值”对的插入和检索,这种形式具有最稳定的性能。

HashMap和Hashtable的关系类似于ArrayList和Vector的关系。Hashtable线程安全,性能比较差,现在很少使用;HashMap是线程不安全的,性能较好,可以实现线程安全,推荐使用。另外,HashMap允许使用null作为key或value,但Hashtable中key和value都不可以使用null.

为了成功地在HashMap和Hashtable中存储对象,用作key的对象必须实现equals()方法和hashCode()方法。

  • 判断两个key相等的标准是:两个key的equals()方法返回true,并且hashCode()返回值也相等。
  • 判断两个value相等的标准:只要两个对象通过equals()方法比较为true即可。

使用自定义类作为HashMap、Hashtable的key时,如果重写该类的equals()方法和hashCode()方法,必须保证两个方法判断标准一致, 即两个key通过equals()方法返回true时,它们的hashCode()返回值应该也相等。

TreeMap:

是SortedMap接口的一个实现类,在一个“红-黑”树的基础上实现。每个键值对即作为红黑树的一个结点。TreeMap保存结点时,需要对节点进行排序,所以我们会得到有顺序排列的键值对。

TreeMap的排列方式类似与TreeSet的排序方式:

  • 默认排序:TreeSet的所有key必须实现Comparable接口,而且所有key应该是同一类型的对象。
  • 定制排序:创建TreeMap对象时,传入一个Comparator对象,该对象负责对TreeMap中的key进行排序。采用定制排序时不要求Map的key实现Comparable接口。

类似于TreeSet中判断两个元素相等的标准,TreeMap判断两个key相等的标准是:两个key通过compareTo()方法返回0即可。

LinkedHashMap:

是HashMap的一个子类,使用双向链表维护key-value对的次序。该链表负责维护Map的迭代顺序,迭代顺序与插入的顺序保持一致。因为需要维护元素插入顺序,性能略低于HashMap。但因为使用链表,在迭代访问Map里的全部元素时将有较好的性能。

WeakHashMap:

与HashMap不同的是,HashMap的key保留了对实际对象的强引用,这意味着只要该HashMap对象不被销毁,其中所有的key所引用的对象都不会被垃圾回收器回收,HashMap也不会自动删除这些键值对;但WeakHashMap保留的是弱引用,如果WeakHashMap对象保存的key所引用的对象没有被其他强引用变量引用,这些key引用的变量可能被垃圾回收,WeakHashMap也可能自动删除这些键值对。

IdentityHashMap:

和HashMap的区别在于,它处理两个key相等比较独特:当且仅当两个key严格相等(key1==key2)时,IdentityHashMap才认为它们相等。

EnumMap:

  • EnumMap中所有key都必须是单个枚举类的枚举值,创建EnumMap时必须显式或隐式指定它的枚举类;
  • EnumMap内部以数组形式保存,所以这种形式非常紧凑、高效;
  • EnumMap根据key的自然排序(即枚举值在枚举类中的定义顺序)来维护键值对顺序;
  • EnumMap不允许使用null作为key,但允许使用null作为value。
enum Season    //定义枚举类
{ SPRING, SUMMER, FALL, WINTER }

public class EnumMapTest{
    public static void main(String[] args){
        EnumMap enum = new EnumMap(Season.class);
        enum.put(Season.SUMMER,"夏日炎炎");
        enum.put(Season.SPRING,"春暖花开");
        System.out.println(enum);
    }
}

/********输出结果:********/
{SPRING=春暖花开, SUMMER=夏日炎炎}

各Map实现类性能分析:

  • EnumMap性能最好,但只能使用同一枚举类的枚举值作为key;
  • LinkHashMap要比HashMap慢一些,因为它需要维护一个链表;
  • IIdentityHashMap性能和HashMap差不多,因为两者有基本相似的实现;
  • TreeMap通常比HashMap和Hashtable要慢,因为它底层采用红黑树实现;
  • Hashtable通常比HashMap慢,因为它是一个古老的,线程安全的集合。

(各Map对应相应的Set类,性能分析也适用于上面的那些Set类)

包装线程不安全的集合

线程相关知识可以看这篇博客

上面讲到的ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap等都是线程不安全的。如果程序中有多个线程需要访问以上这些集合,就可以使用Collections提供的类方法把这些集合包装成线程安全的集合。Collections提供了如下几个静态方法:

  • <T> Collection<T> synchronizedCollection(Collection<T> c):返回指定collection对应线程安全的collection。
  • static <T> List<T> synchronizedList(List<T> list):返回指定List对象对应线程安全的List对象。
  • static <K,T>Map<K,V> synchronizedMap(Map<K,V> m):返回指定Map对象对应线程安全的Map对象。
  • static <T>Set<T> synchronizedSet(Set<T> s):返回指定Set对象对应线程安全的Set对象。
  • static <K,T>SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m):返回指定SortedMap对象对应线程安全的SortedMap对象。
  • static <T>SortSet<T> synchronizedSortSet(SortSet<T> s):返回指定SortSet对象对应线程安全的SortSet对象。

例如需要在多线程中使用线程安全的HashMap对象:

HashMap m = Collection.synchronizedMap(new HashMap());

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术小站

(转)JAVA HashSet 去除重复值原理

Java中的set是一个不包含重复元素的集合,确切地说,是不包含e1.equals(e2)的元素对。Set中允许添加null。Set不能保证集合里元素的顺序。

2321
来自专栏数据结构与算法

P1341 无序字母对

题目描述 给定n个各不相同的无序字母对(区分大小写,无序即字母对中的两个字母可以位置颠倒)。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。...

3508
来自专栏Java帮帮-微信公众号-技术文章全总结

第十九天 集合-Map接口容器工具类集合框架总结【悟空教程】

Map集合的特点,如是否可重复,是否有序仅作用在键上,如HashMap集合的键不得重复,值可以重复。

1863
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedHashMap

34614
来自专栏Hongten

java中的List记录是否完全匹配方法

===================================================

1001
来自专栏desperate633

LintCode 二分查找题目分析代码

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组...

892
来自专栏mathor

堆及其相关应用

 提到堆就不得不说到二叉树这个结构,堆就是一颗完全二叉树,什么叫完全二叉树,用一句话来概括就是:设二叉树的深度为h,除第h层外,其它各层的结点数都达到最大个数,...

922
来自专栏IT可乐

JDK1.8源码(八)——java.util.HashSet 类

  在上一篇博客,我们介绍了 Map 集合的一种典型实现  HashMap  ,在 JDK1.8 中,HashMap 是由 数组+链表+红黑树构成,相对于早期版...

1142
来自专栏Java技术栈

Java集合从菜鸟到大神演变

先来看一张集合概况图,这里从上到下列举了几个最经常用的集合 ? 1、集合接口 java.util.Collection 是一个集合接口。它提供了对集合对象进行基...

4256
来自专栏算法与数据结构

数据结构 链表改进

主要介绍循环链表和双向循环链表 循环链表 双向循环链表 2-1 对于一非空的循环单链表,h和p分别指向链表的头、尾结点,则有() ? 循环单链表判空: 设头结点...

4377

扫码关注云+社区