Hash Maps

From Progzoo
Jump to: navigation, search

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.
Typical operations required:

  • add or put or set
    • insert a new (key,value) pairs
  • lookup or get
    • retrieve the value for a given key
  • iterate
    • run over every key
hash
keyvalue
andrew2753
sally2742
gordon2754

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
[Font] [Default] [Show] [Resize] [History] [Profile]

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.
[Font] [Default] [Show] [Resize] [History] [Profile]

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
[Font] [Default] [Show] [Resize] [History] [Profile]

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
[Font] [Default] [Show] [Resize] [History] [Profile]

See also

  • TreeMap: The TreeMap is slower, but it keeps keys in sort order
  • Hashtable: The Hashtable is slower than HashMap but it is safe to use if more than one thread is reading/writing to the structure.