Hash Maps

Data Structures

Hash Maps

Array Lists

Arrays

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 key value andrew 2753 sally 2742 gordon 2754

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

.

import java.util.HashMap; public class Demo{ public static void main(String argv[]) { HashMap<String,String> phone = new HashMap<String,String>(); phone.put("Andrew", "C49"); phone.put("Sally", "C46"); phone.put("Ken", "D52"); phone.put("Gordon", "C49"); String who = "Sally"; System.out.printf("%s\t%s\n", who, phone.get(who)); } }

[Font] [Default] [Show] [Resize] [History] [Profile]

test text

 

 

 

 

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.

.

import java.util.HashMap; public class Demo{ public static void main(String[] argv) { //Create a small hash map with three entries HashMap<String,String> phone = new HashMap<String,String>(); phone.put("Hilary", "C49"); phone.put("Pat", "C50"); phone.put("Sandy", "C51"); //The test list includes some non-keys String [] lst={"Hilary","Patrick","Alexander"}; System.out.println("Output all in the list:"); for(String s:lst) System.out.println(s + " " + phone.get(s)); System.out.println("\nTest for inclusion:"); for(String s:lst) if (phone.containsKey(s)) System.out.println(s + " " + phone.get(s)); else System.out.println(s + " was not found."); } }

[Font] [Default] [Show] [Resize] [History] [Profile]

test text

 

 

 

 

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

.

import java.util.HashMap; import java.util.Map; public class Demo{ public static void main(String argv[]) { HashMap<String,String> phone = new HashMap<String,String>(); phone.put("Andrew", "C49"); phone.put("Sally", "C46"); phone.put("Ken", "D52"); phone.put("Gordon", "C49"); System.out.println("Here are the keys:"); for (String s : phone.keySet()) System.out.println(s); System.out.println("\nHere are the values:"); for (String s : phone.values()) System.out.println(s); System.out.println("\nHere are the pairs:"); for (Map.Entry<String,String> e : phone.entrySet()) System.out.printf("%s : %s\n", e.getKey(),e.getValue()); } }

[Font] [Default] [Show] [Resize] [History] [Profile]

test text

 

 

 

 

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

.

import java.util.HashMap; import java.util.ArrayList; import java.util.Collections; public class Demo{ public static void main(String argv[]) { HashMap<String,String> phone = new HashMap<String,String>(); phone.put("Andrew", "C49"); phone.put("Sally", "C46"); phone.put("Ken", "D52"); phone.put("Gordon", "C49"); System.out.println("Here are the keys:"); for (String s : phone.keySet()) System.out.println(s); ArrayList<String> keys = new ArrayList<String>(phone.keySet()); Collections.sort(keys); System.out.println("Here are the keys in order:"); for (String s : keys) System.out.println(s); } }

[Font] [Default] [Show] [Resize] [History] [Profile]

test text

 

 

 

 

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.