如何用Map对象创建Set对象

Java中的Map和Set有不少相似之处。本文将分享一个把Map类转化成Set类的小技巧。

或许你已经知道,HashSet其实是一个披着Set方法外衣的HashMap;同样,TreeSet其实也是一个披着Set方法外衣的TreeMap。Map并不支持直接用迭代器进行遍历,因此下面的这段代码编译无法通过:

我们可以通过遍历Map中的key集合、value集合和entry集合来实现Map的遍历。由于Map中的value是可以重复出现的,因此values()方法返回的是一个Collection类型的集合。而Map中的key是不允许重复的,因此keySet()方法和entrySet()返回的都是Set类型的集合。

因此,我们可以采用下面的方法来遍历Map:

从直观上看,采用遍历entry的方式遍历Map会更加高效一些,这种遍历方式的时间复杂度是O(n)。然而,如果HashMap中的元素分布均匀,调用get()方法查找元素的时间复杂度将是O(1),那么这两种方法遍历HashMap的时间复杂度是一样的,都是O(n)。这两种遍历方式虽然有所不同,但时间复杂度都是线性的。但这个结论并不适用于其它类型的Map,特别是TreeMap。TreeMap的平均查找效率是O(log n),因此通过keySet遍历TreeMap的时间复杂度是O(n x log n)。

java.util包中有很多Map类,其中一些Map类有着对应类型的Set类实现,例如TreeMap和HashMap。这些Set类都是基于对应的Map类实现的,因此它们和对应的Map类保持相同的算法复杂度以及并发特性。

本文的重点来了。我在完成并发专修课程中的某道练习题时,需要一个快速高效并且线程安全的HashSet。起初,我直接把ConcurrentHashMap当作Set用,把要插入Set的元素以Key的形式插入Map,Key所对应的Value则是一个无意义的默认值。后来我发现,Java 6中的java.util.Collections类提供了一个newSetFromMap()方法,该方法能够基于指定的Map对象创建一个新的Set对象。在创建这个Map<K, V>对象时,K的数据类型必须与你想要创建的Set中元素的数据类型一致;而V必须是Boolean类型的,这是因为value字段用于标记该元素是否存在。

当然,newSetFromMap()方法只能返回标准Set接口类型的对象。如果你的Map类有着更丰富的接口(与标准Map<K, V>接口相比),你还是需要自行封装实现对应的Set类。

希望读者能从本文中有所收获。如果你曾经为找不到ConcurrentHashSet而烦恼,现在你就可以自己创建一个了。

原文链接: javaspecialists 翻译: ImportNew.com - 夏千林

原文发布于微信公众号 - java一日一条(mjx_java)

原文发表时间:2015-09-29

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏zingpLiu

LeetCode【第217题】Contains Duplicate

1155
来自专栏LinkedBear的个人空间

唠唠SE的集合-03——List接口 原

有序的 collection(也称为序列)。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。

843
来自专栏desperate633

LintCode 用递归打印数字题目分析代码

recursion(i) { if i > largest number: return results.add(i) recursion(i + 1)...

661
来自专栏小樱的经验随笔

【Java数据结构学习笔记之一】线性表的存储结构及其代码实现

应用程序后在那个的数据大致有四种基本的逻辑结构: 集合:数据元素之间只有"同属于一个集合"的关系 线性结构:数据元素之间存在一个对一个的关系 树形结构:数...

3045
来自专栏积累沉淀

必须掌握的八种排序(3-4)--简单选择排序,堆排序

3、简单选择排序 (1)基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换; 然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第...

2169
来自专栏尾尾部落

[LeetCode]Degree of an Array 数组的度 [LeetCode]Degree of an Array 数组的度

链接:https://leetcode.com/problems/degree-of-an-array/description/ 难度:Easy 题目:69...

1162
来自专栏desperate633

LintCode 子数组之和题目分析代码

给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置

632
来自专栏互扯程序

Java常用集合源码级深度解析

Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分:...

5046
来自专栏我是业余自学C/C++的

Remove Duplicates from Sorted Array II

1714
来自专栏武培轩的专栏

剑指Offer-第一个只出现一次的字符位置

题目描述 在一个字符串(1<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置 思路 思路一: 使用整型数组对出现次数进行...

3879

扫码关注云+社区

领取腾讯云代金券