Hash Maps
Contents
A hash table (also known as associative array, lookup table, dictionary, hash)
is a way of storing values against keys. Often the keys are strings, in this
example the values are numbers.
|
|
This structure is so useful that we find it in most programming languages. Often there are many different options that have subtly different characteristics. Usually we want fast retrieval and we may or may not care about: fast insert, efficient use of memory, the order of the keys.
We can put
values into a HashMap then get
them out.
The HashMap
allows us to index a list of items using a string (or other
objects). This we can treat the HashMap as a lookup table.
The HashMap
is fabulously useful. It is fast for both inserts and
lookups.
Telephone book
When we create the structure we specify the type of the key and the type of the value.
We can lookup the phone number for "Sally" using the get method.
The output is
Sally C46
Missing items
If we look for an item that isn't there the null value is returned.
In this example we try to retrieve an entry that isn't in the list.
We also use containsKey
to test if the item exists.
Ouput:
Output all in the list: Hilary C49 Patrick null Alexander null Test for inclusion: Hilary C49 Patrick was not found. Alexander was not found.
Getting all values back
Commonly we want to loop over all of the keys in the HashMap.
The method keySet()
permits this. We can also use
values()
to get
a list of values or entrySet()
to get both keys and values.
Output:
Here are the keys: Gordon Sally Ken Andrew Here are the values: C49 C46 D52 C49 Here are the pairs: Gordon : C49 Sally : C46 Ken : D52 Andrew : C49
Getting keys back in the right order
The keys come back as a Set
- this cannot be sorted.
However we can copy them into a ArrayList
this can be sorted.
If you want to maintain key order you can use a TreeMap, that will ensure that keys are kept in order and there is no need to sort them. If you want to retrieve items in key order then a TreeMap will be more effient - the cost of each insert or delete will be slightly more but the sort operation (which is very costly) can be avoided. Output:
Here are the keys: Gordon Sally Ken Andrew Here are the keys in order: Andrew Gordon Ken Sally