HashSet是如何做到无序的

发表于 | 分类于 | |

参考资料：

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
23
package 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
3
public 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
21
public 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
19
final 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
5
def 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
2
3
4
5
6
7
8
9
10
11
12
>>> i(49)
2
>>> i(101)
3
>>> i(98)
4
>>> i(53)
6
>>> i(52)
7
>>> i(97)
7

发现通过传入hashCode值得到的下标跟输出的顺序非常符合，两个下标7当然会进行哈希再探测，至此HashSet的无序存储的疑惑就解决了。

有钱的捧个钱场~