需要生成100万个随机七位数
下面这个程序分别用HashSet和自定义的MyHashSet产生,时间分别需要两秒,四秒,怎么改善MyHashSet的算法?感觉比HashSet算法简单,但不知为什么用的时间会更长,或者有没其它更好的算法。
package common;import java.util.HashSet;
import java.util.Random;public class Bounce {    public static void main(String args[])
    {
     long startTime=System.currentTimeMillis();
        new Bounce().run();
     long endTime=System.currentTimeMillis();
     System.out.println("HashSet 运行时间:"+(endTime-startTime));
     startTime=System.currentTimeMillis();
        new Bounce().run1();
     endTime=System.currentTimeMillis();
     System.out.println("MyHashSet 运行时间:"+(endTime-startTime));
    }
    
    public void run1(){
     int N=1000000;
     Integer[] ps=new Integer[1000000];
     MyHashSet<Integer> hs=new MyHashSet<Integer>(3000000);
     Random r=new Random();
     for(int i=0;hs.size()!=N;i++){
     hs.add(r.nextInt(10000000));
     }
     ps=hs.toArray(ps);     for(int i=10000;i<10050;i++){
     // System.out.println(ps[i]);
     }
    }
    public void run(){
     int N=1000000;
     Integer[] ps=new Integer[1000000];
     HashSet<Integer> hs=new HashSet<Integer>(3000000);
     Random r=new Random();
     for(int i=0;hs.size()!=N;i++){
     hs.add(r.nextInt(10000000));
     }
     ps=hs.toArray(ps);
    
     for(int i=10000;i<10050;i++){
     // System.out.println(ps[i]);
     }
    }
}
class MyHashSet<T>{ Entry[] table;
int size;
MyHashSet(int initialCapacity){
table=new Entry[initialCapacity];
}
    
public void add(T t){
int hash=hash(t.hashCode());
int i = hash&(table.length-1);
        for (Entry<T> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.value) ==t || t.equals(k))) {
                return ;
            }
        }
        addEntry(hash, t, i);
}
void addEntry(int hash, T t, int bucketIndex) {
Entry<T> e = table[bucketIndex];
    table[bucketIndex] = new Entry<T>(hash, t,e);
    size++;
  }
static int hash(int h) {
        // 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);
    }
int size(){
return size;
}
public <E1> E1[] toArray(E1[] a) {
int ll=table.length;
int j=0;
for(int i=0;i<ll;i++){
for (Entry<T> e = table[i]; e != null; e = e.next) {
            a[j]=(E1)e.getValue();
            j++;
        }
}
return a;
}
    static class Entry<T>{
     T value;
     Entry next;
     int hash;
     Entry(int h,T t,Entry n){
     hash=h;
     value=t;
     next=n;
     }
     public final T getValue() {
            return value;
        }
     public final boolean equals(Object o) {
     throw new java.lang.UnsupportedOperationException();
//     Entry e = (Entry)o;
//            return value.equals(e.getValue());
        }
    }
}

解决方案 »

  1.   

    1 如果你的速度快,那么sun的技术人员水平就不如你了。 hashset 这个可是用量很大的类。算法他们一定优化过了。2 100万,2秒,根据机器不同,已经很不错了。3 使用比较大的next值,可以极大的降低重复的几率。
      

  2.   

    这个算法就是根据HashSet代码改的啊,java内库需要考虑太多的东西,而我们自己写类时可以去掉很多检查,按道理是要比内库快的,就不知这个算法什么地方慢啦。
    另外我是需要七位以内的数
      

  3.   

    我大致看了一下楼主的代码,
    既然楼主不惜牺牲内存来保证生成号码的速度,
    那么,我做了一下简单的修改,
    因为只存储整数所以要比使用sun的HashSet稍微好一点。
    建议楼主自己编一个更简单的缓冲进行处理,那样时间更短。class MyHashSet<T> extends HashSet<T>{ private static final long serialVersionUID = 1L; public MyHashSet(int initialCapacity) {
    super(initialCapacity);
    } static int hash(int h) {
    // 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);
    }
    }
      

  4.   

    一激动,代码帖错了。
    hash方法的方法体,直接return h;就可以了
      

  5.   

    这样不行的,试过直接使用Integer的HashCode,就是说都不使用这个函数,速度几乎还是一样
    想啦很久,也许可能性只有本地码有关,因为虚拟机会把部分代码编译成本地码,而我们写的代码是及时编译,这样也许就产生啦这样的结果
      

  6.   

    如果采用HashSet,每一步都是要判断是否溢出的,比如添加内容时,都会判断size等很多东西