Java's Built-In HashMap (and Hashtable) Classes

Differences Between Java's HashMap and HashTable Classes

Though both Hashtable and HashMap are data-structure based upon hashing and implementation of Map interface, the main difference between them is that HashMap is not thread-safe but Hashtable is thread-safe. Which means you cannot use HashMap in multi-threaded Java application without external synchronization. Another difference is HashMap allows one null key and null values but Hashtable doesn't allow null key or values. Also, thread-safety of the hash table is achieved using internal synchronization, which makes it slower than HashMap. The difference between HashMap and Hashtable in Java is one of the frequently asked in core Java interviews to check whether the candidate understands correct usage of collection classes and aware of alternative solutions available.


Using Java's HashMap to Build an Associative Array

The following video shows how Java's built-in HashMap class can be used to construct an associative array. In addition, it shows how to iterate through all the values in the Map using a for-each loop.

Prelude to Java's HashMap Internals: Java's Bitwise Operators

As a reminder, if we have the java expression (x % y), the variable x is referred to as the dividend and y is the divisor. The result of the expression is the remainder or modulo. For the special case of when the divisor is a power of 2, the modulo operator (%) can be replaced with a bitwise-and operator with the divisor being decreased by one. For example:

int answer = 172 % 32;

can also be written as:

int answer = 172 & 31; // bitwise AND operator has replaced modulo for speed reasons

As the video, below, shows, the above bitwise and operation is used instead of modulo to calculate hashcodes for java's HashMap class. The reason this substitution is made is because the bitwise-and operator is a good deal faster than the modulo operator as can be seen in the following bar chart:

How a Java HashMap Works Internally

Summary of Important Points About Java's HashMap Implementation

  • Initially, an empty HashMap is created with an array of 16 LinkedList pointers; the default loadfactor is 75%;
  • Alternatively, you can specifiy the initial table size and loadfactor when you create the HashMap through the use of an alternate constructor: 
    public HashMap(int initialCapacity, float loadFactor)
  • Each entry in the table stores the original hashcode, the key, the value and the next pointer;

  • When the number of entries reaches the threshhold (determined by the loadfactor), the size of the underlying table doubles;

  • Unlike Java's Hashtable class, the HashMap class does permit one entry with a null key value. This entry is always stored in the first row of the HashMap's underyling table (at index 0);

  • When a HashTable is resized, all existing entries must be rehashed and redistributed in the new table;

  • Starting with Java Version 8, the LinkedList implementation of the HashMap's underlying table is sometimes replaced with self-balancing (Red-Black) binary search trees, when the lists get too long;