HashSet原理

短命女 2023-09-24 22:01 45阅读 0赞

### HashSet原理 ###

*  HashSet原理
 *   *  1.概述
     *  2.底层代码
     *  3.原理图解
     *  4.总结
     *   *  4.1: 1.7原理总结
         *  4.2: 1.8原理总结
 *  扩展链接

# HashSet原理 #

## 1.概述 ##

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

## 2.底层代码 ##

HashSet 它是基于 HashMap 实现的，HashSet 底层使用 HashMap 来保存 所有元素，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底 层 HashMap 的相关方法来完成

public class HashSet<E>
        extends AbstractSet<E>
        implements Set<E>, Cloneable, java.io.Serializable
    {
        
        static final long serialVersionUID = -5024744406713321676L;
    
    	// 底层使用hashmap来保存hashset中所有的元素
        private transient HashMap<E,Object> map;
    
        // Dummy value to associate with an Object in the backing Map
        // 定义一个虚拟的object对象作为hashmap的value,将次对象定义为static final,放在map的值的位置
        private static final Object PRESENT = new Object();
    
    	// 默认无参构造,实际底层初始化一个空的hashmap,并使用默认初始容量为16和加载因子为0.75
        public HashSet() {
        
            map = new HashMap<>();
        }
    
    	// 构造一个指定Collection中元素的新set,实际底层使用默认的加载因子为0.75和足以包含指定Collection中	// 左右元素的初始容量来定义一个hashmap
        public HashSet(Collection<? extends E> c) {
        
            map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
            addAll(c);
        }
    
    	// 以指定的initialCapacity和loadFactor构造一个空的set,实际底层以相同的参数,构造一个空的map集合
    	// initialCapacity:初始容量,loadFactor:加载因子
        public HashSet(int initialCapacity, float loadFactor) {
        
            map = new HashMap<>(initialCapacity, loadFactor);
        }
    
    	// 指定初始长度创建一个空的集合,实际使用一样的参数,与加载因子为0.75构造一个空的map
        public HashSet(int initialCapacity) {
        
            map = new HashMap<>(initialCapacity);
        }
    
    	// 指定初始长度和加载因子构造一个新的空链接哈希集合
    	// 此构造函数为包含访问权限,不对外公开,实际只是对LinkedHashSet的支持
    	// 实际以指定的参数创建一个空的LinkedHashMap集合
        HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        
            map = new LinkedHashMap<>(initialCapacity, loadFactor);
        }

## 3.原理图解 ##

![hashset1.7原理][hashset1.7]

![hashset1.8原理][hashset1.8]

![hashset1.8元素存储][hashset1.8 1]

## 4.总结 ##

### 4.1: 1.7原理总结 ###

1.  底层结构:哈希表.(数组+链表)
2.  数组的长度默认为16,加载因子为0.75
3.  首先会先获取元素的哈希值,计算出在数组中应存入的索引
    
    1.  判断该索引处是否为null
    2.  如果是null,直接添加
    3.  如果不是null,则与链表中所有的元素,通过equals方法进行比较属性值只要有一个相同就不存入,如果都不一样,就存入.

### 4.2: 1.8原理总结 ###

1.  底层结构:哈希表.(数组+链表+红黑树)
2.  当挂在下面的元素过多,那么不利于添加,也不利于查询,所以在1.8之后
3.  当链表长度超过8的时候,自动转换为红黑树
4.  存储流程不变.

对于hsahset中保存对象,一定注意正确重写equals和hsahcode方法,以保证存入的对象唯一性.

# 扩展链接 #

[HashMap和HashSet][HashMap_HashSet]

[hashset1.7]: https://img-blog.csdnimg.cn/a02ba81c56484bea9d59ff66b12c7b2f.png
[hashset1.8]: https://img-blog.csdnimg.cn/30d1144be6c4417ab5268b961b92eb6f.png
[hashset1.8 1]: https://img-blog.csdnimg.cn/aa445bda263a44ca93ad4ede74d7ee64.png
[HashMap_HashSet]: https://blog.csdn.net/m0_67683346/article/details/126068054