参考资料:
jzhf2012的专栏,这位大神对源码的分析十分详尽,但是也比较长,我在此处总结题目中的问题。
问题引入:
执行如下JAVA程序测试HashSet的存储顺序:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23package learnCollection;
import java.util.HashSet;
import java.util.Iterator;
public class Main {
public static void main(String[] args) {
HashSet<Character> hs = new HashSet<Character>(11);
hs.add('a');
hs.add('b');
hs.add('1');
hs.add('5');
hs.add('4');
hs.add('e');
System.out.println(hs);//输出hs的元素
Iterator<Character> it = hs.iterator();
while(it.hasNext()){
System.out.print(it.next().hashCode()+" ");//输出各元素的hashCode
}
System.out.println();
}
}
输出结果如下:1
2[1, e, b, 5, 4, a]
49 101 98 53 52 97
可见是完全乱序的,就算是从hashCode()可看不出任何规律。
源码分析:
在Eclipse下按住Control键鼠标左键单击add()方法进入HashSet的源码,发现add()方法看似十分简洁:1
2
3public boolean add(E e) {
return map.put(e, PRESENT)==null;//将要存储的元素当作键,一个Object对象当作值存入一个HashMap
}
怎么有个map?继续点进put()的源码,发现进入了HashMap的类文件:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);//以上代码是边界判断
int hash = hash(key);//获得传入值的哈希值
int i = indexFor(hash, table.length);//获得哈希表中的下标
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}//如果键已经存在,则更新对应值
modCount++;
addEntry(hash, key, value, i);//添加到表中
return null;
}
原来HashSet的存储是基于HashMap的,所以也就不难理解它的乱序了。HashMap通过键值对来存储数据,所以要理解HashSet的乱序,只要分析HashMap的存储方式就OK了,当然,存储方式是哈希表。
其中hash()函数和indexFor()函数都定义在HashMap中,在理解了它们的源码后可以写个测试程序对存储结果进行验证,源码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19final int hash(Object k) {
int h = hashSeed;//此常数默认是零,老版本中没有此定义,老版本此函数直接传入k的hashCode
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();//0与k.hashCode()进行异或结果还是k.hashCode()
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);//这两句对h通过移位进行优化,减少哈希值重复
}
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);//lentgh是HashMap当前的容量,默认为16
}
综合上述分析,可以写个简单的函数对我们的测试结果进行验证,图省事用python脚本写个函数:1
2
3
4
5def i(h):
h = h^(h>>20)^(h>>12)
h = h^(h>>7)^(h>>4)
h = h&15
return h
对前面的输出结果进行验证1
2[1, e, b, 5, 4, a]
49 101 98 53 52 97
1 | >>> i(49) |
发现通过传入hashCode值得到的下标跟输出的顺序非常符合,两个下标7当然会进行哈希再探测,至此HashSet的无序存储的疑惑就解决了。