HashSet 是否无序
(一) 问题起因：
《Core Java Volume I—Fundamentals》中对HashSet的描述是这样的：
解释：我们一般说HashSet是无序的，它既不能保证存储和取出顺序一致，更不能保证自然顺序（a-z）
下面是《Thinking in Java》中的使用Integer对象的HashSet的示例
在0-29之间的10000个随机数被添加到了Set中，大量的数据是重复的，但输出结果却每一个数只有一个实例出现在结果中，并且输出的结果没有任何规律可循。 这正与其不重复，且无序的特点相吻合。
看来两本书的结果，以及我们之前所学的知识，看起来都是一致的，一切就是这么美好。
随手运行了一下这段书中的代码，结果却让人大吃一惊
//JDK1.8下 Idea中运行
import java.util.*;
public class SetOfInteger {
public static void main(String[] args) {
Random rand = new Random(47);
Set<Integer> intset = new HashSet<Integer>();
for (int i = 0; i<10000; i++)
intset.add(rand.nextInt(30));
System.out.println(intset);
}
}
//运行结果
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
嗯！不重复的特点依旧吻合，但是为什么遍历输出结果却是有序的？？？
写一个最简单的程序再验证一下：
import java.util.*;
public class HashSetDemo {
public static void main(String[] args) {
Set<Integer> hs = new HashSet<Integer>();
hs.add(1);
hs.add(2);
hs.add(3);
//增强for遍历
for (Integer s : hs) {
System.out.print(s + " ");
}
}
}
//运行结果
1 2 3
我还不死心，是不是元素数据不够多，有序这只是一种巧合的存在，增加元素数量试试
import java.util.*;
public class HashSetDemo {
public static void main(String[] args) {
Set<Integer> hs = new HashSet<Integer>();
for (int i = 0; i < 10000; i++) {
hs.add(i);
}
//增强for遍历
for (Integer s : hs) {
System.out.print(s + " ");
}
}
}
//运行结果
1 2 3 ... 9997 9998 9999
可以看到，遍历后输出依旧是有序的
(二) 过程
通过一步一步分析源码，我们来看一看，这究竟是怎么一回事，首先我们先从程序的第一步——集合元素的存储开始看起，先看一看HashSet的add方法源码：
// HashSet 源码节选-JKD8
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
我们可以看到，HashSet直接调用HashMap的put方法，并且将元素e放到map的key位置（保证了唯一性 ）
顺着线索继续查看HashMap的put方法源码：
//HashMap 源码节选-JDK8
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
而我们的值在返回前需要经过HashMap中的hash方法
接着定位到hash方法的源码：
//HashMap 源码节选-JDK8
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash方法的返回结果中是一句三目运算符，键 (key) 为null即返回 0,存在则返回后一句的内容
(h = key.hashCode()) ^ (h >>> 16)
JDK8中 HashMap——hash 方法中的这段代码叫做 “扰动函数”
我们来分析一下：
hashCode是Object类中的一个方法，在子类中一般都会重写，而根据我们之前自己给出的程序，暂以Integer类型为例，我们来看一下Integer中hashCode方法的源码：
/**
* Returns a hash code for this {@code Integer}.
*
* @return a hash code value for this object, equal to the
* primitive {@code int} value represented by this
* {@code Integer} object.
*/
@Override
public int hashCode() {
return Integer.hashCode(value);
}
/**
* Returns a hash code for a {@code int} value; compatible with
* {@code Integer.hashCode()}.
*
* @param value the value to hash
* @since 1.8
*
* @return a hash code value for a {@code int} value.
*/
public static int hashCode(int value) {
return value;
}
Integer中hashCode方法的返回值就是这个数本身
注：整数的值因为与整数本身一样唯一，所以它是一个足够好的散列
所以，下面的A、B两个式子就是等价的
//注：key为 hash(Object key)参数
A：(h = key.hashCode()) ^ (h >>> 16)
B：key ^ (key >>> 16)
分析到这一步，我们的式子只剩下位运算了，先不急着算什么，我们先理清思路
HashSet因为底层使用哈希表（链表结合数组）实现，存储时key通过一些运算后得出自己在数组中所处的位置。
我们在hashCoe方法中返回到了一个等同于本身值的散列值，但是考虑到int类型数据的范围：-2147483648~2147483647 ，着很显然，这些散列值不能直接使用，因为内存是没有办法放得下，一个40亿长度的数组的。所以它使用了对数组长度进行取模运算，得余后再作为其数组下标，indexFor( ) ——JDK7中，就这样出现了，在JDK8中 indexFor()就消失了，而全部使用下面的语句代替，原理是一样的。
//JDK8中
(tab.length - 1) & hash；
//JDK7中
bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {
return h & (length - 1);
}
提一句，为什么取模运算时我们用 & 而不用 % 呢，因为位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快，这样就导致位运算 & 效率要比取模运算 % 高很多。
看到这里我们就知道了，存储时key需要通过hash方法和indexFor( )运算，来确定自己的对应下标
(取模运算，应以JDK8为准，但为了称呼方便，还是按照JDK7的叫法来说，下面的例子均为此，特此提前声明)
但是先直接看与运算(&)，好像又出现了一些问题，我们举个例子：
HashMap中初始长度为16，length - 1 = 15；其二进制表示为 00000000 00000000 00000000 00001111
而与运算计算方式为：遇0则0，我们随便举一个key值
1111 1111 1010 0101 1111 0000 0011 1100
& 0000 0000 0000 0000 0000 0000 0000 1111
----------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 1100
我们将这32位从中分开，左边16位称作高位，右边16位称作低位，可以看到经过&运算后 结果就是高位全部归0，剩下了低位的最后四位。但是问题就来了，我们按照当前初始长度为默认的16，HashCode值为下图两个，可以看到，在不经过扰动计算时，只进行与(&)运算后 Index值均为 12 这也就导致了哈希冲突
例子中，两个不同的HashCode值却经过运算后，得到了相同的值，也就代表，他们都需要被放在下标为2的位置
一般来说，如果数据分布比较广泛，而且存储数据的数组长度比较大，那么哈希冲突就会比较少，否则很高。
但是，如果像上例中只取最后几位的时候，这可不是什么好事，即使我的数据分布很散乱，但是哈希冲突仍然会很严重。
别忘了，我们的扰动函数还在前面搁着呢，这个时候它就要发挥强大的作用了,还是使用上面两个发生了哈希冲突的数据，这一次我们加入扰动函数再进行与(&)运算
可以看到，本发生了哈希冲突的两组数据，经过扰动函数处理后，数值变得不再一样了，也就避免了冲突
其实在扰动函数中，将数据右位移16位，哈希码的高位和低位混合了起来，这也正解决了前面所讲 高位归0，计算只依赖低位最后几位的情况, 这使得高位的一些特征也对低位产生了影响，使得低位的随机性加强，能更好的避免冲突
到这里，我们一步步研究到了这一些知识
HashSet add() → HashMap put() → HashMap hash() → HashMap (tab.length - 1) & hash；
有了这些知识的铺垫，我对于刚开始自己举的例子又产生了一些疑惑,我使用for循环添加一些整型元素进入集合，难道就没有任何一个发生哈希冲突吗，为什么遍历结果是有序输出的，经过简单计算 2 和18这两个值就都是2
(这个疑惑是有问题的，后面解释了错在了哪里)
//key = 2,(length -1) = 15
h = key.hashCode() 0000 0000 0000 0000 0000 0000 0000 0010
h >>> 16 0000 0000 0000 0000 0000 0000 0000 0000
hash = h^(h >>> 16) 0000 0000 0000 0000 0000 0000 0000 0010
(tab.length-1)&hash 0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0000 0010
-------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0010
//2的十进制结果：2
//key = 18,(length -1) = 15
h = key.hashCode() 0000 0000 0000 0000 0000 0000 0001 0010
h >>> 16 0000 0000 0000 0000 0000 0000 0000 0000
hash = h^(h >>> 16) 0000 0000 0000 0000 0000 0000 0001 0010
(tab.length-1)&hash 0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0000 0010
-------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0010
//18的十进制结果：2
按照我们上面的知识，按理应该输出 1 2 18 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 但却仍有序输出了
import java.util.*;
public class HashSetDemo {
public static void main(String[] args) {
Set<Integer> hs = new HashSet<Integer>();
for (int i = 0; i < 19; i++) {
hs.add(i);
}
//增强for遍历
for (Integer s : hs) {
System.out.print(s + " ");
}
}
}
//运行结果：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
再试一试
import java.util.*;
public class HashSetDemo {
public static void main(String[] args) {
Set<Integer> hs = new HashSet<Integer>();
hs.add(0)
hs.add(1);
hs.add(18);
hs.add(2);
hs.add(3);
hs.add(4);
......
hs.add(17)
//增强for遍历
for (Integer s : hs) {
System.out.print(s + " ");
}
}
}
//运行结果：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
真让人头大，不死心再试一试，由与偷懒，就只添加了几个，就是这个偷懒，让我发现了新大陆！
import java.util.*;
public class HashSetDemo {
public static void main(String[] args) {
Set<Integer> hs = new HashSet<Integer>();
hs.add(1);
hs.add(18);
hs.add(2);
hs.add(3);
hs.add(4);
//增强for遍历
for (Integer s : hs) {
System.out.print(s + " ");
}
}
}
//运行结果：
1 18 2 3 4
这一段程序按照我们认为应该出现的顺序出现了！！！
突然恍然大悟，我忽略了最重要的一个问题，也就是数组长度问题
//HashMap 源码节选-JDK8
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
我们还观察到一个叫做加载因子的东西，他默认值为0.75f，这是什么意思呢，我们来补充一点它的知识：
现在可以解决我们上面的疑惑了
数组初始的实际长度 = 16 * 0.75 = 12
这代表当我们元素数量增加到12以上时就会发生扩容，当我们上例中for循环添加0-18， 这19个元素时，先保存到前12个到第十三个元素时，超过加载因子，导致数组发生了一次扩容，而扩容以后对应与(&)运算的(tab.length-1)就发生了变化,从16-1 变成了 32-1 即31
我们来算一下
//key = 2,(length -1) = 31
h = key.hashCode() 0000 0000 0000 0000 0000 0000 0001 0010
h >>> 16 0000 0000 0000 0000 0000 0000 0000 0000
hash = h^(h >>> 16) 0000 0000 0000 0000 0000 0000 0001 0010
(tab.length-1)&hash 0000 0000 0000 0000 0000 0000 0011 1111
0000 0000 0000 0000 0000 0000 0000 0010
-------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0010
//十进制结果：2
//key = 18,(length -1) = 31
h = key.hashCode() 0000 0000 0000 0000 0000 0000 0001 0010
h >>> 16 0000 0000 0000 0000 0000 0000 0000 0000
hash = h^(h >>> 16) 0000 0000 0000 0000 0000 0000 0001 0010
(tab.length-1)&hash 0000 0000 0000 0000 0000 0000 0011 1111
0000 0000 0000 0000 0000 0000 0000 0010
-------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0001 0010
//十进制结果：18
当length - 1 的值发生改变的时候，18的值也变成了本身。
到这里，才意识到自己之前用2和18计算时 均使用了 length -1 的值为 15是错误的，当时并不清楚加载因子及它的扩容机制，这才是导致提出有问题疑惑的根本原因。
(三) 总结
JDK7到JDK8，其内部发生了一些变化，导致在不同版本JDK下运行结果不同，根据上面的分析，我们从HashSet追溯到HashMap的hash算法、加载因子和默认长度。
由于我们所创建的HashSet是Integer类型的，这也是最巧的一点，Integer类型hashCode()的返回值就是其int值本身，而存储的时候元素通过一些运算后会得出自己在数组中所处的位置。由于在这一步，其本身即下标(只考虑这一步)，其实已经实现了排序功能，由于int类型范围太广，内存放不下，所以对其进行取模运算，为了减少哈希冲突，又在取模前进行了，扰动函数的计算，得到的数作为元素下标，按照JDK8下的hash算法，以及load factor及扩容机制，这就导致数据在经过 HashMap.hash()运算后仍然是自己本身的值，且没有发生哈希冲突。
补充：对于有序无序的理解
集合所说的序，是指元素存入集合的顺序，当元素存储顺序和取出顺序一致时就是有序，否则就是无序。
并不是说存储数据的时候无序，没有规则，当我们不论使用for循环随机数添加元素的时候，还是for循环有序添加元素的时候，最后遍历输出的结果均为按照值的大小排序输出，随机添加元素，但结果仍有序输出，这就对照着上面那句，存储顺序和取出顺序是不一致的，所以我们说HashSet是无序的，虽然我们按照123的顺序添加元素，结果虽然仍为123，但这只是一种巧合而已。
所以HashSet只是不保证有序，并不是保证无序
结尾：
如果内容中有什么不足，或者错误的地方，欢迎大家给我留言提出意见, 蟹蟹大家 ！
如果能帮到你的话，那就来关注我吧！（系列文章均会在公众号第一时间更新）