java容器学习笔记(二)set接口及其实现类的相关知识总结

java容器学习笔记(二)set接口及其实现类的相关知识总结

ID:35318620

大小:93.17 KB

页数:8页

时间:2019-03-23

java容器学习笔记(二)set接口及其实现类的相关知识总结_第1页
java容器学习笔记(二)set接口及其实现类的相关知识总结_第2页
java容器学习笔记(二)set接口及其实现类的相关知识总结_第3页
java容器学习笔记(二)set接口及其实现类的相关知识总结_第4页
java容器学习笔记(二)set接口及其实现类的相关知识总结_第5页
资源描述:

《java容器学习笔记(二)set接口及其实现类的相关知识总结》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、Java容器学习笔记(二)Set接口及其实现类的相关知识总结分类: Java学习 实习笔记2011-10-2100:54 652人阅读 评论(4) 收藏 举报在Java容器学习笔记(一)中概述了Collection的基本概念及接口实现,并且总结了它的一个重要子接口List及其子类的实现和用法。本篇主要总结Set接口及其实现类的用法,包括HashSet(无序不重复),LinkedHashSet(按放入顺序有序不重复),TreeSet(按红黑树方式有序不重复),EnumSet,ConcurrentSkipListSet(来自于java.util.concurrent包),CopyO

2、nWriteArraySet(来自于java.util.concurrent包)等。 2.    Set接口及其实现类Set接口中方法清单:Set集合和List集合都存放的是单个元素的序列,但是Set集合不允许集合中有重复元素(主要依赖于equals方法)。Set接口的父接口为Collection和Iterable,直接实现该接口的子接口有SortedSet和NavigableSet。实现Set接口的重要类有HashSet(无序不重复),LinkedHashSet(按放入顺序有序不重复),TreeSet(按红黑树方式有序不重复),EnumSet,ConcurrentSkipLi

3、stSet(来自于java.util.concurrent包),CopyOnWriteArraySet(来自于java.util.concurrent包)。在Set接口中没有新增任何方法,所有方法均来自其父接口。它无法提供像List中按位存取的方法。在数学上一个集合有三个性质:确定性,互异性,无序性。Ø  HashSet的特点、实现机制及使用方法a)     HashSet的特点:HashSet中存放的元素是无序的,底层是用HashMap实现的,其中key是要放入的元素,value是一个Object类型的名为PRESENT的常量,由于用到了散列函数,因此其存取速度是非常快的,在

4、地址空间很大的情况下它的存取速度可以达到O(1)级。如果首先了解了HashMap的实现方法,那么HashSet的实现是非常简单的。b)HashSet的实现机制:首先需要了解一下散列或者哈希的用法。我们知道,当数据量很大时hash函数计算的结果将会重复,按照下图所示的形式进行存贮。在HashSet中有个loadFactor(负载因子),对于上图所示总共有11个位置,目前有4个位置已经存放,即40%的空间已被使用。在HashSet的默认实现中,初始容量为16,负载因子为0.75,也就是说当有75%的空间已被使用,将会进行一次再散列(再哈希),之前的散列表(数组)将被删除,新增加的散

5、列表是之前散列表长度的2倍,最大值为Integer.MAX_VALUE。负载因子越高,内存使用率越大,元素的寻找时间越长。负载因子越低,内存使用率越小,元素的寻找时间越短。从上图可以看出,当哈希值相同时,将存放在同一个位置,使用链表方式依次链接下去。(面试官问到这个问题,当时我的回答是再哈希,其实我并不知道HashSet真正是怎么实现的,我只知道在学习数据结构时学习过再哈希,就是这个哈希表很满时需要重新建立哈希表,以便于存取,因为大量的值放在一个位置上就变成了链表的查询了,几乎是O(n/2)级别的,但是我没有说出来再哈希的过程,以及哈希值相同时到底如何存放,所以……~~o(>_

6、<)o~~)。为了说明HashSet在Java中确实如上实现,下面附上JDK中两个重要方法的源码:(下面源码来自于HashMap,原因是HashSet是基于HashMap实现的)viewplainprint?1./** 1.     * Rehashes the contents of this map into a new array with a 2.     * larger capacity.  This method is called automatically when the 3.     * number of keys in this map reaches

7、 its threshold. 4.     * 5.     * If current capacity is MAXIMUM_CAPACITY, this method does not 6.     * resize the map, but sets threshold to Integer.MAX_VALUE. 7.     * This has the effect of preventing future calls. 8.     * 9.     * @param newC

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。