《Java编程思想》为什么我的HashSet有排序功能？

#《Java编程思想》为什么我的HashSet有排序功能？| 来源: 网络整理| 查看: 265

《Java编程思想》为什么我的HashSet有排序功能？ HashSet排序现象源码分析Integer的hash值是多少呢？扩展

HashSet排序现象

最近在看Set集合的知识，Set是一种不保存重复元素的集合，如下代码我们添加100次 0-29之间的数字，但是最后的运行结果intSet里面只有0到29之间的数字。

import java.util.*; public class SetOfInteger { public static void main(String[] args) { Random random = new Random(47); Set intSet = new HashSet(); for (int i = 0; i < 100; i++) { intSet.add(random.nextInt(30)); } System.out.println(intSet); } } /* output * [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] **/

但是这个输出的结果却让我非常的好奇，为什么有排序的功能，不是HashSet不会排序么？或许应该深入源码

源码分析

我们可以找到HashSet里面的add方法，原来HashSet也是通过HashMap来完成的，Key是插入的数字，Value是new的一个对象。

//HashSet.java private transient HashMap map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); public boolean add(E e) { return map.put(e, PRESENT)==null; }

随后是HashMap的put方法，而真正影响我们的排序的就是下面的代码，putVal里面传入3个hash,key,value。这是就有一个猜想就是我们的Integer的hash就是他的值，通过debug putVal函数我们也可以清楚的发现。我们知道其实真正影响排序问题的是hash，找到源码发现，hash值是通过key.hashCode()函数来决定的。也就是我们返回的是(h = key.hashCode()) 和 (h >>> 16) 的异或结果

//HashMap.java public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { ...... } static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } Integer的hash值是多少呢？

上面我们放入HashSet的元素是Integer，Integer的hashCode就是他本来的值。我们在Integer类中可以找到hashCode()函数

//Integer.java @Override public int hashCode() { return Integer.hashCode(value); } public static int hashCode(int value) { return value; }

h=key.hashCode()和h>>>16（h的值向右移动16位）对于小于2的16次方的数，异或结果还是原来的值。

所以说原因分析出来了

扩展 (h = key.hashCode()) ^ (h >>> 16)

上面代码的意思是：h值等于key的hashCode，然后对h的二进制右移16位，一个Integer是32位，那么对于小于2^16=65536的值前面都是0

Integer h = 1; //h等于1 0000 0000 0000 0000 0000 0000 0000 0001 //h的二进制 h >>> 16 //h右移16位 0000 0000 0000 0000 0000 0000 0000 0000 //右移后的二进制如果和原来的h异或 0000 0000 0000 0000 0000 0000 0000 0001 //异或结果

网上还有其他的说法就是加上某一个值65536，这个意思也很简单就是通过增加二进制大于16位的数字，这样右移就会有变化，可以生成一个和原来只不一样的hash值。（这个值应该加多少我还没有细看）下面是栗子呀

import java.util.*; public class SetOfInteger { public static void main(String[] args) { Random random = new Random(); Set intSet = new HashSet(); for (int i = 0; i < 100; i++) { int a = random.nextInt(20); intSet.add(a + 65536*2*10); } Iterator it = intSet.iterator(); while (it.hasNext()) { Integer integer = (Integer) it.next(); System.out.print(integer-65536*2*10 + " "); } //System.out.println(intSet); } } /*output *16 17 18 19 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 */

【本文地址】

公司简介

联系我们