HashSet原理

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.75public HashSet() {map = new HashMap<>();}// 构造一个指定Collection中元素的新set,实际底层使用默认的加载因子为0.75和足以包含指定Collection中	// 左右元素的初始容量来定义一个hashmappublic 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构造一个空的mappublic HashSet(int initialCapacity) {map = new HashMap<>(initialCapacity);}// 指定初始长度和加载因子构造一个新的空链接哈希集合// 此构造函数为包含访问权限,不对外公开,实际只是对LinkedHashSet的支持// 实际以指定的参数创建一个空的LinkedHashMap集合HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);}

3.原理图解

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方法,以保证存入的对象唯一性.