putting items into hashmap and treemap
Hi all, this is my first time posting here, I tried doing a search but i didn't find what i was looking for so i hope someone out there and help me out~
Anyways, my question is that howcome when I am putting entries into either of these maps, the times for entry acutally gets faster as more entries are entered?
For instance, in my hashMap, it took approximately 8 seconds to enter 1447 entries, but when i am entering in 23042 entries, it takes just a bit over 1 second?
Does it have soemthing to do with how the methods in hashMap takes on constant time (O(1)) ?
the same thing happens for HashMap, but the time cost is (O(log n)) for putting entries so i am not sure how to explain this..
I hope someone understands my question, thanks in advance!
[789 byte] By [
BlazinSuna] at [2007-11-26 21:10:18]
# 2
8 seconds for 1400 entries sounds VERY long.
In any case, earlier chunks may take longer due to VM startup or hotspot warmup overhead. Resizing the backing store, GC, VM acquiring more memory, OS giving CPU time to other proesses, etc., could all throw off your timing.
I got the following results:
HashMap:
first 350,000: 1 s
next 300,000: 1 s
next 250,000: 1 s
TreeMap:
First 100,000: 1 s
Next 50,000: 3 s
Next 100, 000: 2 s
Next 50,000: 1 s
Next 50,000: 1 s
and so on--generally 1 or 2 seconds per 50,000
import java.util.*;
public class MapTiming {
public static void main(String[] args) throws Exception {
Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
Map<Integer, Integer> tm = new TreeMap<Integer, Integer>();
long start;
start = System.currentTimeMillis();
for (int ix = 1; ix <= 1000000; ix++) {
hm.put(ix, ix);
if (ix % 50000 == 0) {
long end = System.currentTimeMillis();
System.out.println("HashMap " + ix + ": " + ((end - start) / 1000) + " sec.");
}
}
start = System.currentTimeMillis();
for (int ix = 1; ix <= 1000000; ix++) {
hm.put(ix, ix);
if (ix % 50000 == 0) {
long end = System.currentTimeMillis();
System.out.println("TreeMap " + ix + ": " + ((end - start)/ 1000)+ " sec.");
}
}
}
}
:; java -cp classes MapTiming
HashMap 50000: 0 sec.
HashMap 100000: 0 sec.
HashMap 150000: 0 sec.
HashMap 200000: 0 sec.
HashMap 250000: 0 sec.
HashMap 300000: 0 sec.
HashMap 350000: 1 sec.
HashMap 400000: 1 sec.
HashMap 450000: 1 sec.
HashMap 500000: 1 sec.
HashMap 550000: 1 sec.
HashMap 600000: 1 sec.
HashMap 650000: 2 sec.
HashMap 700000: 2 sec.
HashMap 750000: 2 sec.
HashMap 800000: 2 sec.
HashMap 850000: 2 sec.
HashMap 900000: 3 sec.
HashMap 950000: 3 sec.
HashMap 1000000: 3 sec.
TreeMap 50000: 0 sec.
TreeMap 100000: 1 sec.
TreeMap 150000: 4 sec.
TreeMap 200000: 4 sec.
TreeMap 250000: 6 sec.
TreeMap 300000: 7 sec.
TreeMap 350000: 8 sec.
TreeMap 400000: 11 sec.
TreeMap 450000: 12 sec.
TreeMap 500000: 14 sec.
TreeMap 550000: 14 sec.
TreeMap 600000: 16 sec.
TreeMap 650000: 18 sec.
TreeMap 700000: 19 sec.
TreeMap 750000: 21 sec.
TreeMap 800000: 22 sec.
TreeMap 850000: 25 sec.
TreeMap 900000: 25 sec.
TreeMap 950000: 26 sec.
TreeMap 1000000: 29 sec.
# 3
Hi there thanks for the replies.
and sorry I probably left out important information regarding why I am doing this and how the benchmarks were obtained.
This is acutally for a project for school (again, sorry this thread is placed in the wrong section) where we are compressing files with the LZW Compression Algorithm. And these two trees are used to store the entries generated by the algorithm. The seconds I indicated was the time it took for the compression to occur, going from source file, through the algorithm, and then stored by either using treeMap or hashMap.
After consulting with some friends, we think it might be partly due to the algorithm, being that it's not very efficient, and not so much on the tree it self.
