在实际开发中我们会遇到这样的需求，生成1-10的随机乱序不重复数字。首先想到的就是Random生成随机数，然后将这些随机数放入set中，利用set的特性排除相同数据。最后输出set里面的数字。但是实际使用的时候会有文中的问题。
我们在使用HashSet的时候都知道，Set的特性是元素唯一，并且乱序存储。但是在实际时候的时候。会有下面的情况发生：
源码如下：
publicvoid test1() throws InterruptedException{
long randomSeed= System.currentTimeMillis() ;
Random random = new Random(45) ;
Set randomSet = new HashSet() ;
System.out.println("开始放入：");
for(int i = 0 ; i < 100 ; i++){
Integer in = random.nextInt(10) ;
System.out.print(in+" , ");
randomSet.add(in) ;
TimeUnit.MILLISECONDS.sleep(2);
}
System.out.println() ;
System.out.println("结果:");
System.out.println(randomSet.toString()) ;
}
}
以上代码的输出：
开始放入：
9 , 1 , 1 , 0 , 7 , 1 , 1 , 3 , 4 , 3 , 0 , 9 , 0 , 8 , 0 , 6 , 4 , 5 , 0 , 7 ,2 , 1 , 4 , 4 , 8 , 9 , 7 , 0 , 9 , 1 , 2 , 3 , 1 , 2 , 4 , 3 , 9 , 0 , 7 , 0 ,1 , 1 , 2 , 4 , 3 , 1 , 7 , 3 , 2 , 1 , 9 , 0 , 2 , 2 , 2 , 3 , 6 , 5 , 8 , 3 ,1 , 0 , 3 , 4 , 0 , 1 , 3 , 2 , 4 , 8 , 7 , 1 , 5 , 1 , 4 , 1 , 7 , 9 , 3 , 4 ,5 , 3 , 7 , 1 , 9 , 0 , 0 , 3 , 4 , 7 , 4 , 1 , 8 , 7 , 4 , 3 , 8 , 9 , 2 , 2,
结果:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
这里HashSet.toString()给出的输出结果貌似进行了排序，如果将toString的输出修改成for的遍历看，如下：
for(Integer ele : randomSet){
System.out.print(ele+" , ") ;
}
那么输出的结果一样是
开始放入：
9 , 1 , 1 , 0 , 7 , 1 , 1 , 3 , 4 , 3 , 0 , 9 , 0 , 8 , 0 , 6 , 4 , 5 , 0 , 7 ,2 , 1 , 4 , 4 , 8 , 9 , 7 , 0 , 9 , 1 , 2 , 3 , 1 , 2 , 4 , 3 , 9 , 0 , 7 , 0 ,1 , 1 , 2 , 4 , 3 , 1 , 7 , 3 , 2 , 1 , 9 , 0 , 2 , 2 , 2 , 3 , 6 , 5 , 8 , 3 ,1 , 0 , 3 , 4 , 0 , 1 , 3 , 2 , 4 , 8 , 7 , 1 , 5 , 1 , 4 , 1 , 7 , 9 , 3 , 4 ,5 , 3 , 7 , 1 , 9 , 0 , 0 , 3 , 4 , 7 , 4 , 1 , 8 , 7 , 4 , 3 , 8 , 9 , 2 , 2,
结果:
0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ,
好像也进行了排序。这样就和JDK中的描述不相符了，SET应该是一个乱序的集合，怎么会进行排序输出？
HashSet.java中迭代器的方法如下：
public Iterator<E> iterator() {
return map.keySet().iterator();
}
其中map是HashSet的 private transient HashMap<E,Object> map;
好吧，这样看来HashSet 的数据其实是以HashMap的形式在进行存储。我们通过迭代方法iterator()获得的其实是这个HashMap的Key的迭代对象。
在HashMap的源码中，最后找到了
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
这个HashIterator是map.keySet().iterator();的真正执行方法。就是说我们无论使用HashSet.toString()还是使用for(::) 进行迭代遍历HashSet。起始返回的都是HashMap的Key的迭代对象。输出的东西都是这个对象的元素指向的数据。Set是存储一组相同类型数据的集合，Map是一key-value的模式存储数据。HashSet的add方法实际是将存储的值，以键的形式放在了HashMap的key上。源码如下：
public boolean add(E e) {
returnmap.put(e, PRESENT)==null;
}
这里需要注意的是HashMap的put方法实际如下：
public Vput(K key, V value) {
if (key== null)
return putForNullKey(value);
int hash = hash(key.hashCode());
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);
returnnull;
}
这里通过Key进行hashCode()的计算得出hash值，然后通过这个Hash值计算到它在table中的位置。然后通过addEntry进行保存。这里的key.hashCode()方法就是最开始导致HashSet().toString()排序假象的元凶。如果key是Integer类型。那么他们的hashCode计算结果是其本身。下面的Integer的hashCode()源码：
public int hashCode() {
return value;
}
这就导致了在散列分布的时候，实际上hashMap中的key值就是随机写入的Integer类型的值。也就是为什么toString()方法返回了一个看似正向排序的结果。但如果按照以上的说法，这种“排序”应该是正确的，为什么说是假象呢？是因为在每一回进行addEntry(hash, key, value, i);的时候，都会判断当前的table长度是否足够hashcode算出来的索引，即i值，如果它超出了索引，就将table的大小乘2，用来扩充实际的大小。上面的例子中，只取了前10个元素。那么他们不存在增大的部分，看起来像是被排序了。如果我们修改代码如下：
publicvoid test1() throws InterruptedException{
longrandomSeed = System.currentTimeMillis() ;
Random random = new Random(45) ;
Set randomSet = new HashSet() ;
System.out.println("开始放入：");
for(int i = 0 ; i < 100 ; i++){
Integer in = random.nextInt(100) ;
System.out.print(in+" , ");
randomSet.add(in) ;
TimeUnit.MILLISECONDS.sleep(2);
}
System.out.println() ;
System.out.println("结果:");
System.out.println(randomSet.toString()) ;
}
}
那么输出就会变成：
开始放入：
9 ,31 , 31 , 40 , 87 , 31 ,1 , 43 , 94 , 93 , 20 ,19 , 90 , 38 , 90 , 6 ,14 , 85 , 30 , 47 , 82 ,81 , 84 , 74 , 48 , 29 ,47 , 70 , 49 , 51 , 92 ,23 , 81 , 12 , 94 , 33 ,9 , 70 , 67 , 10 , 61 ,61 , 82 , 74 , 73 , 91 ,77 , 93 , 22 , 71 , 59 ,80 , 72 , 62 , 12 , 13 ,66 , 5 , 38 , 13 , 31 ,60 , 13 , 14 , 10 , 51 ,93 , 42 , 24 , 18 , 47 ,1 , 75 , 71 , 94 , 71 ,47 , 49 , 33 , 74 , 35 ,73 , 67 , 61 , 69 , 20 ,90 , 13 , 54 , 67 , 4 ,71 , 68 , 47 , 64 , 93 ,38 , 29 , 82 , 22 ,
结果:
1 , 4 , 5 , 6 , 9 , 10 , 12 , 13 , 14 , 19, 18 , 20 , 23 , 22 , 24 , 29 , 31 , 30 , 35 , 33 , 38 , 42 , 43 , 40 , 47 , 51, 49 , 48 , 54 , 59 , 62 , 61 , 60 , 68 , 69 , 70 , 71 , 64 , 66 , 67 , 77 , 72, 73 , 74 , 75 , 85 , 84 , 87 , 81 , 80 , 82 , 93 , 92 , 94 , 91 , 90 ,
就能看出来HashSet的无顺序分布的特征。JavaJdk默认的加载因子是0.75。默认的table长度是12。虽然整体的输出是从大到小的趋势排列。但是在一些特殊的位置上，不保证顺序。在12的倍数的位置上尤其明显。
以上。
下面给出真正实现随机生成1-10的数字，并且随机排序的代码。这里使用了LinkedHashSet，顺序记录我们随机生成的乱序数。并且利用set的特质。排除相同的数字。
public void test2(){
Random random = new Random(45) ;
Set randomSet = new LinkedHashSet() ;
int setsize = 0 ;
while(setsize<100){
Integer ii = random.nextInt(100) ;
ii++;
System.out.print(ii+" , ");
setsize = randomSet.size() ;
System.out.print(setsize+" , ") ;
System.out.println(setsize<100) ;
randomSet.add(ii) ;
}
System.out.println() ;
for(Integer in : randomSet){
System.out.print(in+" ") ;
}
}
|
|
收藏
淘帖
踩
