RollingWindowedMinHash implements MinHasher { @Override public synchronized void add(long id,long time) { long hash = hasher.hash(id); int idx = hashes.size() - 1; int cSum = 0; while(idx >= 0 && hash < hashes.get(idx).minHash) { cSum += hashes.get(idx).count; hashes.remove(idx); idx--; } if (idx > -1) { int lastIdx = hashes.size() - 1; if (hash == hashes.get(lastIdx).minHash) { hashes.get(lastIdx).time = time; hashes.get(lastIdx).count = hashes.get(lastIdx).count + cSum + 1; } else hashes.add(new MinHashEntry(hash,time,cSum+1)); } else { hashes = new ArrayList<>(); hashes.add(new MinHashEntry(hash,time,cSum + 1)); } this.removeOldEntries(time); } RollingWindowedMinHash(Hasher h,long window); @Override synchronized void add(long id,long time); @Override synchronized Long getMinHash(long time); @Override synchronized int getCount(long time); @Override String toString();  }
@Test public void sizeTest() { Hasher h = new SimplePrimeHash(1,2); RollingWindowedMinHash mh = new RollingWindowedMinHash(h, 10000); Random r = new Random(); int timeSteps = 100000; for(int i=1;i<timeSteps;i++) { int id = r.nextInt(2000); mh.add(id, i); } System.out.println(mh.hashes.size()); }