A hashmap is a data table with a special index structure that allows fast retrieval of data objects. The position of a data object is defined by a hash function. In the hashmap, the data is stored as key-value pairs. The values can be retrieved via the key. The time required for this remains constant and is independent of the table size.
What is a Hashmap?
Alternative terms for hashmap are hash table, hash table, or scatter table. It is a special form of a data table with a special index structure. With the help of hashmaps, data objects can be quickly searched and found in large amounts of data.
A mathematical hash function calculates the position of the data object in the table. The data is stored as key-value pairs. The values and their position can be identified and retrieved via the key. There is no need to search through many data objects. The special feature of hash maps is that the time required for searching and finding remains constant compared to other index structures such as tree structures and is independent of the table size.
If the hash function does not deliver unique results, so-called collisions occur, which require special handling and can negatively affect the performance of the table. The first ideas and concepts for hashmaps emerged as early as the 1950s. Hashmaps are used in many areas and applications such as programming languages, caches, or databases.
How hashmaps work
In a hashmap, data is stored in a special index structure as key-value pairs. The storage location is not determined by the key, but by the hash value calculated from the key using a mathematical hash procedure. For the data object, this hash value determines the storage location, also called a bucket.
When searching for a data object, a hash value is again calculated from the key, making the bucket discoverable by storing the key-value pair. In an ideal hash map, exactly one bucket is assigned to each data object. If the hash procedure is not unique and provides the same hash values for different initial values (keys), collisions occur. In this case, several data objects must be stored in one bucket. Since collisions require special handling and can negatively affect the performance of the data table, attempts are made to avoid them.
Depending on the type of data and the application, different hashing methods exist such as concatenated hashing, open hashing, or closed hashing.
Possible applications of hashmaps
Hashmaps are used in many different applications. For example, they are used for caches, are part of the functionality of programming languages such as C++, PHP, or Java, or form the basis for associative arrays, symbol tables, or the indexing of databases.
The advantages and disadvantages of hashmaps
The advantages of a Hashmap are:
- Short and constant access times to data objects, independent of the amount of data in a table
- Index structure suitable for large amounts of data and data tables
As disadvantages of Hashmaps can be specified:
- Collisions can occur, which negatively influence the performance of the table and the access time behavior
- The data positions are randomly viewed from the outside and independent of possible relations between the data objects – the data seem to be distributed arbitrarily in the table
- The hash function to be executed at each data operation consumes CPU power