HashSet是基于HashMap实现的，HashSet 底层使用HashMap来保存所有元素，
因此HashSet 的实现比较简单，相关HashSet 的操作，基本上都是直接调用底层HashMap的相关方法来完成，HashSet不允许有重复的值，并且元素是无序的。

HashSet是用Hash算法来实现存取对象的，所以每个对象都有自己的hashCode. 当存储自定义类型元素时，在类中必须重写hashCode（）和equals（）方法。将hashCode（）方法重写为属性相同的对象值返回值必须一样，属性不同的返回值尽量不一样。将equals（）方法重写为属性相同时返回true，属性不同时返回false。因此，在存取对象是，HashSet会调用对象的hashCode来比较set里面是否有hashcode一样的对象，如果没有，就直接存入，如果有，就调用equals来继续比较hashcode一样的对象，如果返回值为true就不存入，如果返回值为false就存入。

Java中的HashMap可以说是平时开发中最常用的数据结构之一了，经常使用的集合类还有ArrayList、HashSet，基本上用好HashMap、ArrayList、HashSet这三大集合类，大多数的业务场景就满足了，掌握这三大集合类也是作为一名Java程序员的基础能力。

HashMap的Put⽅法的⼤体流程：

1. 根据Key通过哈希算法与与运算得出数组下标

2. 如果数组下标位置元素为空，则将key和value封装为Entry对象(JDK1.7中是Entry对象，JDK1.8中是Node对象)并放⼊该位置

3. 如果数组下标位置元素不为空，则要分情况讨论

a. 如果是JDK1.7，则先判断是否需要扩容，如果要扩容就进⾏扩容，如果不⽤扩容就⽣成Entry对象，并使⽤头插法添加到当前位置的链表中

b. 如果是JDK1.8，则会先判断当前位置上的Node的类型，看是红⿊树Node，还是链表Node

i. 如果是红⿊树Node，则将key和value封装为⼀个红⿊树节点并添加到红⿊树中去，在这个过程中会判断红⿊树中是否存在当前key，如果存在则更新value

ii. 如果此位置上的Node对象是链表节点，则将key和value封装为⼀个链表Node并通过尾插法插⼊到链表的最后位置去，因为是尾插法，所以需要遍历链表，在遍历链表的过程中会判断是否存在当前key，如果存在则更新value，当遍历完链表后，将新链表Node插⼊到链表中，插⼊到链表后，会看当前链表的节点个数，如果⼤于等于8，那么则会将该链表转成红⿊树

iii. 将key和value封装为Node插⼊到链表或红⿊树中后，再判断是否需要进⾏扩容，如果需要就扩容，如果不需要就结束PUT⽅法

平时开发大多数的业务场景都是CRUD，且数据量都很小，所以基本上不会有什么问题。那么还需要知道其底层实现原理吗?还需要知道这些集合类的数据结构吗?

当然需要，这很重要!这里就拿HashMap来具体说一说了解它的设计思想多么的重要!

HashMap的数据结构

HashMap的底层数据结构简单来说就是数组+链表+红黑树，这个大家都知道，面试也是高频面试题，用一张图来形容就是：

那这个时候你就得知道数组的好处了，基于下标的随机访问和赋值数组元素的时间复杂度都是O(1)，这就能保证HashMap数据没有哈希冲突的时候它的set/put方法都是O(1)的，这也是HashMap要追求的极致目标(尽管会有哈希冲突)。这就是HashMap查询性能快、插入数据快的主要原因，是一个空间换时间的思想。

哈希

但前提是我们得知道我们要把一个数据插入到数组的哪个下标，因此就采用了哈希的思想。一个对象一定有一个唯一的hash值，但是两个对象也有可能有相同的hash值，这叫“哈希冲突”。所以为了更好的利用数组，哈希值计算要尽可能的避免冲突，也就是追求“低碰撞率”。

这也涉及到另外一个问题，比较一个对象的时候为什么要重写它的hashcode()方法和equals()方法。

那业内除了Java自带的Hashcode()方法还有哪些hash算法你了解吗?比如MurmurHash算法。他们都在哪些开源软件中应用到?各种哈希算法的性能比较又如何?

数组与链表

当哈希冲突的时候，HashMap就会使用到链表，即数组+链表，那你知道数组和链表的区别吗?LinkedHashMap和HashMap的区别呢?都适合在哪些场景用到?如果让你手写一个LRU缓存，你会怎么写?

你可能想说我不需要知道数组和链表的数据结构，我也没有手写LRU缓存的场景，我只想做一条安静的咸鱼，简简单单CRUD就好。

高效查找

大家都说平时开发都是CRUD，那你知道如何把CRUD写的高大上一点吗?比如其中的C(查询)应该是最为频繁的。学过数据结构的都知道，高效查找主要的两种算法：有序查找(二分)和哈希查找。HashMap的数组就是用到了哈希查找，时间复杂度是O(1)，那么你理解了HashMap的原理是不是就基本掌握了哈希查找算法的原理?另外当哈希冲突导致链表节点数量达到8时候，就会变成红黑树，红黑树就是有序查找的变种。如果你又进一步掌握了红黑树的查找原理，是不是就基本掌握了有序查找算法的原理?所以HashMap的原理重不重要?掌握了HashMap的原理是不是就掌握了高效查找的方法?如果你没掌握这些原理，你觉得掌握了没有用，但是当你掌握了，在日常业务开发中你会发现受用无穷。

HashSet简单的理解就是HashSet对象中不能存储相同的数据,存储数据时是无序的。

• HashSet只存储不同的值，set中是不会出现重复值的。

• HashSet和HashMap一样也需要实现hash算法来计算对象的hash值，但不同的是，HashMap中添加一个键值对的时候， (Key, Value)，hash函数计算的是Key的hash值。而HashSet则是计算value的hash值。当我们调用HashSet的add（E e）的方法 的时候，我们会计算机元素e的hash值，如果这个值之前没出现过，就说明这个元素在set中不存在，如果出现过，就说明。set中已经存在了，就添加失败。

知道了上述的基本概念之后，我们就可以打开JDK源码，来一探究竟了。

关于hashSet的实现原理，最重要的一个点就是HashSet内部是使用HashMap来存储对象的。

HashSet实际上是一个HashMap实例，都是一个存放链表的数组。它不保证存储元素的迭代顺序;此类允许使用null元素。HashSet中不允许有重复元素，这是因为HashSet是基于HashMap实现的，HashSet中的元素都存放在HashMap的key上面，而value中的值都是统一的一个固定对象private static final Object PRESENT = new Object();

HashSet中add方法调用的是底层HashMap中的put()方法，而如果是在HashMap中调用put，首先会判断key是否存在，如果key存在则修改value值，如果key不存在这插入这个key-value。而在set中，因为value值没有用，也就不存在修改value值的说法，因此往HashSet中添加元素，首先判断元素(也就是key)是否存在，如果不存在这插入，如果存在着不插入，这样HashSet中就不存在重复值。

所以判断key是否存在就要重写元素的类的equals()和hashCode()方法，当向Set中添加对象时，首先调用此对象所在类的hashCode()方法，计算次对象的哈希值，此哈希值决定了此对象在Set中存放的位置;若此位置没有被存储对象则直接存储，若已有对象则通过对象所在类的equals()比较两个对象是否相同，相同则不能被添加。

iterator：返回对此set中元素进行迭代的迭代器 size：返回此set中元素的数量(set的容量) isEmpty：判断Hashset集合是否为空 contains：判断某个元素是否存在于HashSet中 add()：如果此set中尚未包含指定元素，则添加指定元素