本文共 6716 字,大约阅读时间需要 22 分钟。
http://blog.csdn.net/guoweimelon/article/details/50804799
HashSet是Java Map类型的集合类中最常使用的,本文基于Java1.8,对于HashSet的实现原理做一下详细讲解。
(Java1.8源码:)
一、HashSet实现原理总结
HashSet的实现原理总结如下:
①是基于HashMap实现的,默认构造函数是构建一个初始容量为16,负载因子为0.75 的HashMap。封装了一个 HashMap 对象来存储所有的集合元素,所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存,而 HashMap 的 value 则存储了一个 PRESENT,它是一个静态的 Object 对象。
②当我们试图把某个类的对象当成 HashMap的 key,或试图将这个类的对象放入 HashSet 中保存时,重写该类的equals(Object obj)方法和 hashCode() 方法很重要,而且这两个方法的返回值必须保持一致:当该类的两个的 hashCode() 返回值相同时,它们通过 equals() 方法比较也应该返回 true。通常来说,所有参与计算 hashCode() 返回值的关键属性,都应该用于作为 equals() 比较的标准。
③HashSet的其他操作都是基于HashMap的。
二、HashSet的实现原理详解
(转自:http://zhangshixi.iteye.com/blog/673143)
1. HashSet概述:
HashSet实现Set接口,由哈希表(实际上是一个HashMap实例)支持。它不保证set 的迭代顺序;特别是它不保证该顺序恒久不变。此类允许使用null元素。
2. HashSet的实现:
对于HashSet而言,它是基于HashMap实现的,HashSet底层使用HashMap来保存所有元素,因此HashSet 的实现比较简单,相关HashSet的操作,基本上都是直接调用底层HashMap的相关方法来完成, HashSet的源代码如下:
- public class HashSet<E>
- extends AbstractSet<E>
- implements Set<E>, Cloneable, java.io.Serializable
- {
- static final long serialVersionUID = -5024744406713321676L;
-
-
- private transient HashMap<E,Object> map;
-
-
- private static final Object PRESENT = new Object();
-
-
-
-
-
-
- public HashSet() {
- map = new HashMap<E,Object>();
- }
-
-
-
-
-
-
-
-
- public HashSet(Collection<? extends E> c) {
- map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
- addAll(c);
- }
-
-
-
-
-
-
-
-
- public HashSet(int initialCapacity, float loadFactor) {
- map = new HashMap<E,Object>(initialCapacity, loadFactor);
- }
-
-
-
-
-
-
-
- public HashSet(int initialCapacity) {
- map = new HashMap<E,Object>(initialCapacity);
- }
-
-
-
-
-
-
-
-
-
-
- HashSet(int initialCapacity, float loadFactor, boolean dummy) {
- map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
- }
-
-
-
-
-
-
-
-
-
- public Iterator<E> iterator() {
- return map.keySet().iterator();
- }
-
-
-
-
-
-
-
- public int size() {
- return map.size();
- }
-
-
-
-
-
-
-
- public boolean isEmpty() {
- return map.isEmpty();
- }
-
-
-
-
-
-
-
-
-
-
- public boolean contains(Object o) {
- return map.containsKey(o);
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- public boolean add(E e) {
- return map.put(e, PRESENT)==null;
- }
-
-
-
-
-
-
-
-
-
-
-
- public boolean remove(Object o) {
- return map.remove(o)==PRESENT;
- }
-
-
-
-
-
-
- public void clear() {
- map.clear();
- }
-
-
-
-
-
-
- public Object clone() {
- try {
- HashSet<E> newSet = (HashSet<E>) super.clone();
- newSet.map = (HashMap<E, Object>) map.clone();
- return newSet;
- } catch (CloneNotSupportedException e) {
- throw new InternalError();
- }
- }
- }
参考文献:http://alex09.iteye.com/blog/539549
********************************
1. LinkedHashSet概述:
LinkedHashSet是具有可预知迭代顺序的Set接口的哈希表和链接列表实现。此实现与HashSet的不同之处在于,后者维护着一个运行于所有条目的双向链表。此链接列表定义了迭代顺序,该迭代顺序可为插入顺序或是访问顺序(同LinkedHashMap)。
注意,此实现不是同步的。如果多个线程同时访问链接的哈希Set,而其中至少一个线程修改了该Set,则它必须保持外部同步。
2. LinkedHashSet的实现:
对于LinkedHashSet而言,它继承与HashSet、又基于LinkedHashMap来实现的。
LinkedHashSet底层使用LinkedHashMap来保存所有元素,它继承与HashSet,其所有的方法操作上又与HashSet相同,因此LinkedHashSet 的实现上非常简单,只提供了四个构造方法,并通过传递一个标识参数,调用父类的构造器,底层构造一个LinkedHashMap来实现,在相关操作上与父类HashSet的操作相同,直接调用父类HashSet的方法即可。LinkedHashSet的源代码如下:
- public class LinkedHashSet<E>
- extends HashSet<E>
- implements Set<E>, Cloneable, java.io.Serializable {
-
- private static final long serialVersionUID = -2851667679971038690L;
-
-
-
-
-
-
-
-
- public LinkedHashSet(int initialCapacity, float loadFactor) {
- super(initialCapacity, loadFactor, true);
- }
-
-
-
-
-
-
-
- public LinkedHashSet(int initialCapacity) {
- super(initialCapacity, .75f, true);
- }
-
-
-
-
-
-
- public LinkedHashSet() {
- super(16, .75f, true);
- }
-
-
-
-
-
-
-
-
- public LinkedHashSet(Collection<? extends E> c) {
- super(Math.max(2*c.size(), 11), .75f, true);
- addAll(c);
- }
- }
在父类HashSet中,专为LinkedHashSet提供的构造方法如下,该方法为包访问权限,并未对外公开。
-
-
-
-
-
-
-
-
-
- HashSet(int initialCapacity, float loadFactor, boolean dummy) {
- map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
- }
由上述源代码可见,LinkedHashSet通过继承HashSet,底层使用LinkedHashMap,以很简单明了的方式来实现了其自身的所有功能。