JAVA集合Set之HashSet详解

大家好，又见面了，我是你们的朋友全栈君。

HashSet这个类实现了Set集合，实际为一个HashMap的实例。对集合的迭代次序没有任何保证; 特别是，它不能保证订单会随着时间的推移保持不变。这个类允许null 元素。

并且HashSet提供了三个构造函数：

无参数的构造函数，此构造函数创建一个大小为16的容器，加载因子为0.75（容器的大小始终是2的冥，默认为16不在赘述，在后面文章中介绍另外的构造函数，添加指定值的时候会介绍程序是如何保证始终是2的冥，透露一点如果我们传值为5的一个容器大写，那么创建的容器实际大小为8，感兴趣的可以先去看一下算法。），具体看一下实例化一个hashSet的具体参数，并且为了保证速度，我们在实例化的这个参数的时候尽量不要把容器设置的太大，或者加载因子设置太小，后面在说得到HashSet的另外三个构造函数。

Set<String> set =new HashSet<>();

由此图我们可以看到确实实例化了一个容量为16的HashMap，其中loadFactor为加载因子，当容量*加载因子=threshold,

为这个容器的临界值，当存储的元素到了这个临界值，那么容器就会自动扩容。

那么我接下来思考，容器是怎么保证添加的元素不重复的呢？（由于Set取值的时候是调用值本身来取值的，所以不能重复，如果重复了，根据值去取的时候就会不知道取哪一个。list是根据下标map是根据具体key取值）

接下来我们看一下HashSet的add方法：

这个方法实际上是添加的一个put方法，描述的意思是：向这个set集合中添加元素，如果这个元素没有在集合中则添加到这个集合中。如果这个集合已经存在元素调用将离开。（其中PRESENT）

K为我们添加的参数，V为一个Object的定值。

下面我们看一下具体的put方法：

如果key为空，我们添加一个null=value的一个元素到容器里面，如果此时容器中有一个k,v 为 null=“1234”的元素，我们在添加一个null= “456”的一个元素，容器是怎么计算的：

我们看一下这个方法return putForNullKey(value)：

卸载这个put空的key。什么意思？就是删除并替换的意思。

会循环拿出容器里面的元素，e=table[0]，然后判断e ！= null 说明这个集合中是有元素的，那么紧接着开始判断，因为是K,V的形式，拿到这个k判断是否为空，如果为空，那么就用当前的value值替换原来对应的value值，也就是 null = 1234 的这个元素被null = 456 的元素替换掉。

如果第一个e=table[0]的元素，e=null 那么就不在进入这个方法，直接modCount 做累加，然后添加这个key=null,value=456的值。上面是添加key=null,后面讲addEntry方法的具体实现。

下面我们分析具体添加的实现，来理解key是如何保证key不重复的：

其中

为计算的具体hash值，具体实现如下：

useAltHashing具体是什么目前还没有理解，我们就按默认的false来计算这个hash值。

^为异或运算符这里简单说一下这个异或：

^是异或运算符（把数据转换成二进制，然后按位进行运算）。
运算规则：0^0 = 0， 1^0 = 1，  0^1 = 1，  1^1 = 0，运算对象相同为0，不同为1.
如：3^5 的运算过程为：
    (1)先将3和5转换成二进制的11和101
    (2)再按对应的位分别进行运算，11位数不足补零
             011
       ^   101
      ———–
             110
     (3)运算结果转换成10进制：6
 
异或运算的三个个特点:
    (1) 0^0=0,   0^1=1   0与任何数异或＝任何数
    (2) 1^0=1,   1^1=0   1与任何数异或 =任何数取反
    (3) 任何数异或自己＝把自己置0

还有 | & 可以百度了解下

然后简单介绍一下HashCode的算法：下面说两种

1.Integer的算法：

return当前的一个值，这个比较简单。

2.String的算法：

String中的hash算法，我们以int h = hash; h = 0 为基础算：例如传值为：String str = “srt”;

char val[] = {‘s’,’r’,’t’}

循环获取数组val的值，其中  h = 31 * h + val[i],val[i] 获取的是ASCII十进制的对应值，循环计算相加。最后返回具体的hash值。

最后在

这样计算出具体的hash值，也就是存储在map中的具体位置，相当于数组中的下标，所以效率上是非常快的。

后面就好理解了：

根据hash得到具体的位置，然后判断这个位置上面你的值是否hash一样并且key是否一样，如果一样，那么就替换掉，如果不一样就填加进去，具体添加方法为：

其中处理为：

添加值到容器中，在适当的时候扩容，什么时候扩容，当当前size >= threshold,临界值时候，扩容当前table大小的两倍，如16，到了size= 12 时候扩容到32.

具体添加如下：

另外三个构造函数简答列举一下：

HashSet(Collection<? extends E> c)
构造一个包含指定集合中的元素的新集合。  
HashSet(int initialCapacity)
构造一个新的空集合; 背景HashMap实例具有指定的初始容量和默认负载因子（0.75）。  
HashSet(int initialCapacity, float loadFactor)
构造一个新的空集合; 背景HashMap实例具有指定的初始容量和指定的负载因子。 

这些都有在jdk的API中可以具体看一下。

最后总结一下：

此文章主要介绍了一下Set的一种实现HashSet的具体实现和保证key不重复的源码算法和原因。并且在最后说明一下上面忘记了：此实现不同步，为线程不安全的实现，如果有多个线程同时访问这个容器（HashSet），并对立面的元素进行了修改，则需要在外部同步。保证数据的冥等性（幂等是数据中得一个概念，表示N次变换和1次变换的结果相同。）

后面后再其他文章分别介绍TreeSet和LinkedHashSet

如果有对此文好的建议欢迎评价交流。