I decided to make an experiment. I created two hash maps in Java. One hash map with 100 entries and a second hash map with 10000000 entries.
public class MainJava {
private static int NUMBER_OF_ITERATIONS = 1000000;
private static int SMALL_MAP_SIZE = 100;
private static int BIG_MAP_SIZE = 10000000;
public static void main(String[] args) {
Map<Integer, String> smallMap = createSmallHashMap();
long start = System.currentTimeMillis();
for (int i = 0; i < NUMBER_OF_ITERATIONS; i++) {
smallMap.get(i % SMALL_MAP_SIZE);
}
long end = System.currentTimeMillis();
System.out.println("small: " + (end - start));
Map<Integer, String> bigMap = createBigHashMap();
start = System.currentTimeMillis();
for (int i = 0; i < NUMBER_OF_ITERATIONS; i++) {
bigMap.get(i % BIG_MAP_SIZE);
}
end = System.currentTimeMillis();
System.out.println("big: " + (end - start));
}
private static Map<Integer, String> createSmallHashMap() {
Map<Integer, String> smallMap = new HashMap<>();
for (int i = 0; i < SMALL_MAP_SIZE; i++) {
smallMap.put(i, "small-map" + i);
}
return smallMap;
}
private static Map<Integer, String> createBigHashMap() {
Map<Integer, String> bigMap = new HashMap<>();
for (int i = 0; i < BIG_MAP_SIZE; i++) {
bigMap.put(i, "big-map" + i);
}
return bigMap;
}
}
I retrieved values from both hashmaps and measured the time it took in both cases. I ran the code several and saw that the time to retrieve values from the big hashmap was almost ALWAYS longer than the small hashmap.
How is it possible? Retrieval time complexity of a hash map is 0(1). I'd expect similar time values for both maps.
