【数据结构】HashSet原理及实现学习总结

缺乏、安全感 2022-08-23 00:48 182阅读 0赞

在上一篇博文[（HashMap原理及实现学习总结）][HashMap]详细总结了HashMap的实现过程，对于HashSet而言，它是基于HashMap来实现的，底层采用HashMap来保存元素。所以如果对HashMap比较熟悉，那么HashSet的原理应该很好理解!

## 一.HsahSet概述 ##

HashSet实现Set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null元素。

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable

HashSet继承AbstractSet类，实现Set、Cloneable、Serializable接口。其中AbstractSet提供 Set 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。Set接口是一种不包括重复元素的Collection，它维持它自己的内部排序，所以随机访问没有任何意义。  
**基本属性：**

// 底层使用HashMap来保存HashSet中所有元素。
        private transient HashMap<E, Object> map;
    
        // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。
        private static final Object PRESENT = new Object();

**构造函数：**  
从构造函数中可以看出HashSet所有的构造都是构造出一个新的HashMap，其中最后一个构造函数，为包访问权限是不对外公开，仅仅只在使用LinkedHashSet时才会发生作用。

## 二.HsahSet实现 ##

因为HashSet是基于HashMap，所以对于HashSet，其方法的实现过程是非常简单的。  
1. iterator()  
iterator()方法 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。底层实际调用底层HashMap的keySet来返回所有的key。 可见HashSet中的元素，只是存放在了底层HashMap的key上， value使用一个static final的Object对象标识。

public Iterator<E> iterator() {
            return map.keySet().iterator();
        }

2.size()  
返回此set中的元素的数量（set的容量）。底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数,即HashMap容器的大小。

public int size() {
            return map.size();
        }

3.isEmpty()  
isEmpty()判断HashSet()集合是否为空，如果此set不包含任何元素，则返回true。 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。

public boolean isEmpty() {
            return map.isEmpty();
        }

4.contains(Object o)  
contains()，判断某个元素是否存在于HashSet()中，存在返回true，否则返回false。更加确切的讲应该是要满足这种关系才能返回true：(o==null ? e==null : o.equals(e))。底层调用containsKey判断HashMap的key值是否为空。

public boolean contains(Object o) {
            return map.containsKey(o);
        }

5.add()  
add()如果此 set 中尚未包含指定元素，则添加指定元素。如果此Set没有包含满足(e==null ? e2==null : e.equals(e2)) 的e2时，则将e2添加到Set中，否则不添加且返回false。由于底层使用HashMap的put方法将key = e，value=PRESENT构建成key-value键值对，当此e存在于HashMap的key中，则value将会覆盖原有value，但是key保持不变，所以如果将一个已经存在的e元素添加中HashSet中，新添加的元素是不会保存到HashMap中，所以这就满足了HashSet中元素不会重复的特性。

public boolean add(E e) {
            return map.put(e, PRESENT) == null;
        }

6.remove()  
remove()如果指定元素存在于此 set 中，则将其移除。底层使用HashMap的remove方法删除指定的Entry。

public boolean remove(Object o) {
            return map.remove(o) == PRESENT;
        }

7.clear()  
clear()从此 set 中移除所有元素。底层调用HashMap的clear方法清除所有的Entry。

public void clear() {
            map.clear();
        }

8.clone()  
底层实际调用HashMap的clone()方法，获取HashMap的浅表副本,并没有复制这些元素本身。

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();
            }
        }

[HashMap]: http://blog.csdn.net/jianyuerensheng/article/details/51579091

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】HashTable原理及实现学习总结

有两个类都提供了一个多种用途的hashTable机制，他们都可以将可以key和value结合起来构成键值对通过put(key,value)方法保存起来，然后通过get

叁歲伎倆/ 2022年08月23日 00:52/ 0 赞/ 135 阅读

相关【数据结构】HashSet原理及实现学习总结

在上一篇博文[（HashMap原理及实现学习总结）][HashMap]详细总结了HashMap的实现过程，对于HashSet而言，它是基于HashMap来实现的，底层采用Has

缺乏、安全感/ 2022年08月23日 00:48/ 0 赞/ 183 阅读

相关【数据结构】HashMap原理及实现学习总结

HashMap是Java中最常用的集合类框架之一，是Java语言中非常典型的数据结构。本篇主要是从HashMap的工作原理，数据结构分析，HashMap存储和读取几个方面对其进

╰+攻爆jí腚メ/ 2022年08月23日 00:44/ 0 赞/ 166 阅读

相关【数据结构】二叉树的原理及实现学习总结

二叉树概述数组、向量、链表都是一种顺序容器，它们提供了按位置访问数据的手段。而很多情况下，我们需要按数据的值来访问元素，而不是它们的位置来访问元素。比如有这样一个数组i

妖狐艹你老母/ 2022年08月21日 08:45/ 0 赞/ 137 阅读

相关【数据结构】LinkedList原理及实现学习总结

一、LinkedList实现原理概述 LinkedList 和 ArrayList 一样，都实现了 List 接口，但其内部的数据结构有本质的不同。LinkedList

r囧r小猫/ 2022年08月21日 06:37/ 0 赞/ 199 阅读

相关【数据结构】ArrayList原理及实现学习总结

一、ArrayList介绍 ArrayList是一种线性数据结构，它的底层是用数组实现的，相当于动态数组。与Java中的数组相比，它的容量能动态增长。类似于C语言中的动态

柔光的暖阳◎/ 2022年07月30日 15:28/ 0 赞/ 192 阅读

相关 HashSet实现原理及源码分析

HashSet简介 HashSet是Set接口实现，它按照Hash算法来存储集合中的元素不保证元素顺序 HashSet是非同步的，如果多个线程同时访问一个

今天药忘吃喽~/ 2022年06月11日 01:58/ 0 赞/ 253 阅读

相关 HashMap、HashTable、HashSet的实现原理和底层数据结构

原文：[http://blog.51cto.com/10414498/1846953][http_blog.51cto.com_10414498_1846953] HashM

Love The Way You Lie/ 2022年05月26日 08:21/ 0 赞/ 251 阅读

相关 HashSet数据结构原理

hashSet数据结构原理 ![hashset原代码][hashset] 从源码中发现HashSet源码内部维护一个HashMap变量，来看看add方法： ![ad

朱雀/ 2022年05月14日 09:23/ 0 赞/ 199 阅读

相关 HashSet实现原理和存储数据

HashSet实现原理： hashSet类似于一个16个元素table表，相当于16个桶。往HashSet添加元素的时候，首先，会通过计算元素的hashCode值

Love The Way You Lie/ 2022年04月13日 04:54/ 0 赞/ 205 阅读