This is only really useful if you know (or at least can have a good guess at) the number of items your new map is going to store, which is often the case. To help do this, you can pass the initial size of the underlying array as a argument when constructing your hash map. The reallocation of elements to a new backing array is an expensive operation (at best linear time in the number of items in the map) so it's best to avoid having to do it if at all possible. In order to do this, it periodically creates an entirely new, larger backing array and moves all the existing items over to it However, as more and more items are added, it needs to ensure that an acceptable ratio between the number of items it's storing and the length of the underlying array is maintained.

finding/adding/removing elements) in constant time.

This means that so long number of items stored in the map is small in comparison to the length of the backing array, and the hash codes allow the items to be evenly distributed throughout it, it can performs many operations (e.g. Each item is allocated an index in the array based on its hash code (the value returned by invoking the hashCode() method) and the length of the array. Hash based maps are one of the most commonly used data structures in programming and Java provides two different implementations of these - the commonly used HashMap and the older synchronized Hashtable.Ī hash map is essentially a wrapper for an array containing linked lists of the items in it. This post looks at how to construct Java's built-in hash based Map implementations to ensure they have sufficient, but not excessive capacity.

Java hashmap source code