TIMING THE HASH CLASSES

Review of Maps and Sets

In this lab, you will run some timing experiments that compare HashSets to TreeSets and compare HashMaps to TreeMaps. But first, let's start with a brief review of maps and sets in general, and these four classes in particular. A Set is simply a Collection in which duplicates are not allowed. In a Map, each element consists of a unique key and a value.

In a TreeMap, the elements are organized in a red-black tree, ordered by the keys. A TreeSet object is a TreeMap object in which each element has the same dummy value.

In a HashMap, the elements are organized in an array of singly-linked lists. Given an array index, the list stored at that index consists of all the elements whose keys hashed to that index. A HashSet object is a HashMap object in which each element has the same dummy value.

The essential fields in the HashMap class are:

transient Entry[] table;   
transient int size;
final float loadFactor;

The length of the array table is always a power of 2. As you saw in Chapter 14, this allows the conversion of the hash value into a table index to be performed very quickly: hash & (table.length - 1). The length of table is doubled if size becomes greater than or equal to

(int)(table.length * loadFactor)

The variable size is not incremented until after the test for expansion is made. For example, if table.length = 16 and loadFactor = 0.75, then expansion occurs only when the put method is called with size equal to 12. That is, expansion occurs when the 13th element is inserted.