Friday, 9 October 2015

Load factor in HashMap and HashTable

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor.

The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

threshold = (int)(newCapacity * loadFactor);

When the number of entries in the hash table exceeds threshold, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

Minimize the number of rehash operations

Load factor should be taken into account when setting its initial capacity. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur. So we minimize the number of rehash operations using load factor.

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;

        Entry[] newTable = new Entry[newCapacity];
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);

Why load factor 0.75?

The default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put).

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...