HashSet与TreeSet如果输入的数为非负整型的话，则二者输出都应该为有序的
来源：2-8 实现邻接表的改进
叼着烟斗的男孩
2019-09-16
测试用例
@Test
public void oderTest(){
Integer[] nums = new Integer[]{6,10,9,7,2,0,1,2,1,11,13,-11};
List<Integer> list =Arrays.asList(nums);
HashSet<Integer> hashSet = new HashSet<>(list);
TreeSet<Integer> treeSet = new TreeSet<>(list);
for(int n : hashSet){
System.out.print(n + " ");
}
System.out.println();
for(int n : treeSet){
System.out.print(n + " ");
}
}
因为在HashSet沿用了HashMap，其中的hash函数为
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
因此非负Integer得到的hashCode再异或上其无符号右移得到的值恰好不变，在构建哈希表时也是恰好从小到大排序的
- 测试如下
@Test
public void hashTest(){
int h;
Integer key = 110;
//Integer的hashCode
System.out.println(Integer.toBinaryString(key.hashCode()));
//无符号右移16位
System.out.println(Integer.toBinaryString(key.hashCode() >>> 16));
//最终结果
System.out.println(Integer.toBinaryString((h = key.hashCode()) ^ (h >>> 16)));
}
所以说在这次课程中如果用HashSet也是可以的？
写回答
1回答
-
liuyubobobo
2019-09-17
首先，使用 HashSet 肯定是可以的。课程中也介绍了。其实我们对遍历一个节点的相邻节点的序是没有要求的。使用 TreeSet 只是为了 100% 保证后续算法运行结果（包括中间步骤），和课程一致而已。这就好比对于随机算法，我们用一个固定的随机种子进行讲解，道理是一样的。
其次，你给出的 hash 函数，是 HashMap 内部对哈希值进行二次哈希的结果。具体哈希值是多少，取决于 hash.keyCode 的实现。比如下面的代码，取 50 个 1000 以内的随机数（非负数）扔进哈希表，再拿出来，大概率是非顺序的。
HashSet<Integer> set = new HashSet<>(); Random rand = new Random(); for(int i = 0; i < 50; i ++) set.add(rand.nextInt(1000)); ArrayList<Integer> arr = new ArrayList<>(); for(int e: set) arr.add(e); for(int i = 1; i < arr.size(); i ++) if(arr.get(i - 1) > arr.get(i)) throw new RuntimeException(); // 如果 arr 非顺序抛异常
最后，不同语言的 HashSet 或者 HahsMap，内部实现也不一样。整体，不能认为哈希表是顺序的。
不够依然是，对于图论算法，在大多数情况下，并不需要我们存储每个顶点的相邻顶点列表是顺序的。所以，选择哈希表是 ok 的。但是这个 ok 的原因是：我们不需要顺序，而不是哈希表满足了顺序性。
P.S. 课程中也介绍了，哈希表的另一个缺点是占内存。不过在大多数情况下无所谓。只有在极个别的情况下，这也是一个需要考虑的问题。
继续加油！：）
012019-09-17
相似问题