Why is creating a HashMap faster than creating an Object[]?

Question

I've tried to build my own Map to increase the performance for a special environment, and I realized something pretty interesting: Creating a new Hashmap<Integer,String>(2000) is faster than new Object[2000] - no matter in which order I execute these commands. That's pretty confusing to me, esp. because the Hashmap constructor contains a table = new Entry[capacity], according to this. Is there something wrong with my testbench?

public static void test(int amm){ //amm=1_000_000
    Map<Integer,String> m1 = null;
    Object[] arr = null;

    long time = System.nanoTime();
    for(int i = 0; i < amm; i++){
        m1 = new HashMap<Integer, String>(2000);
    }
    System.out.println("m1: " + (System.nanoTime() - time)); //m1: 70_455_065

    time = System.nanoTime();
    for(int i = 0; i < amm; i++){
        arr = new Object[2000];
    }
    System.out.println("arr: " + (System.nanoTime() - time)); //arr: 1_322_473_803
}

I'd love to see the results of testing on another computer. I've got no clue why creating a HashMap is 10 times faster than creating a Object[].

It depends on the JDK implementation. Which JDK and version are you using to perform this test? — BladeCoder
– BladeCoder, Commented Jul 14, 2015 at 23:29
@BladeCoder I'm using 1.7.0_79 (IceTea 2.5.5) (7u79-2.5.5-0ubuntu0.14.04.2) accoring to java.version. — alex berne
– alex berne, Commented Jul 14, 2015 at 23:40
Indeed in a close version of OpenJDK 1.7, no array is initialized in the constructor of HashMap (it's done on first insertion) which explains the speed gap: grepcode.com/file_/repository.grepcode.com/java/root/jdk/… — BladeCoder
– BladeCoder, Commented Jul 14, 2015 at 23:45

Amir Raminfar · Accepted Answer · 2015-07-14 23:27:06Z

51

If you look at the implementation of HashMap, the constructor looks like:

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    this.loadFactor = loadFactor;
    threshold = initialCapacity;
    init();
}

And init() looks like:

/**
 * Initialization hook for subclasses. This method is called
 * in all constructors and pseudo-constructors (clone, readObject)
 * after HashMap has been initialized but before any entries have
 * been inserted.  (In the absence of this method, readObject would
 * require explicit knowledge of subclasses.)
 */
void init() {
}

So initialCapacity doesn't actually get used to create an array. Where does it get used? Look at the put() method.

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // hidden
}

When doing a put, the array is actually created. I didn't show inflateTable() but it does some math and initializes the array.

answered Jul 14, 2015 at 23:27

Amir Raminfar

34.2k8 gold badges97 silver badges125 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

alex berne Over a year ago

where's you're source Code from? I've found docjar.com/html/api/java/util/HashMap.java.html - what says something different. I'll try it, though :) EDIT: you're right, adding a put(5,"Hello") fixes the problem. Interesting, ty

Amir Raminfar Over a year ago

@alexberne I used intellij's view source, which was JDK_1.7.0_51 on MacOS

Falco Over a year ago

Interesting... so the OpenJDK Implementation will show different performance if you have a program which initializes a big HashMap on loading and puts elements inside when the user clicks a button. -- On OpenJDK the app will take long to load and be fast on user-interaction While on OracleJDK the app will load fast and take long on the first button-click. -- The benefit of the OracleJDK Solution is obviously being able to create a lot of unused HashMaps without much memory footprint

Holger Over a year ago

@Falco: I doubt that you will notice the performance impact of creating an object array of size 2000 on a button click.

alexkasko Over a year ago

@Falco, nope, this code is from OpenJDK, not some Oracle proprietary patches. Oracle Java is VERY close to OpenJDK, just not all components were opened (WebStart, JMC, HotSpot for ARM etc).

|

Greg Hewgill · Accepted Answer · 2015-07-14 23:22:54Z

21

An empty HashMap object is much smaller than an array of 2000 Object references. Even though you pass 2000 to the initialCapacity parameter of the HashMap constructor, it's not actually creating 2000 spaces for objects yet.

answered Jul 14, 2015 at 23:22

Greg Hewgill

1.0m192 gold badges1.2k silver badges1.3k bronze badges

Collectives™ on Stack Overflow

Why is creating a HashMap faster than creating an Object[]?

2 Answers 2

8 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related