Hash Tables


An ArrayList encapsulates an array, a contiguous block of space in memory. Finding an object in an array requires serially traversing the array in order to find an element. The class java.util.HashMap is built around the hash table construct mentioned at the beginning of this lesson. It too is based on a contiguous block of space in memory.

I can pictorially represent a hash table as a bunch of slots (Figure 9.2).

Figure 9.2. A Hash Table with Ten Slots


When inserting an element into a hash table, the code rapidly determines a slot for the element by first asking it for its hash code. A hash code is simply an integer, ideally as unique as possible. The contract for hash code is based on the definition of equality for a class: If two objects are equal, their hash code should be equal. If two objects are not equal, then their hash codes are ideally (but not necessarily) unequal.

Once the hash code is available, a bit of arithmetic determines the slot:

 hash code % table size = slot number 

(Remember that the modulus operator, %, returns the remainder of the equivalent integer division.) For example, if you insert a Course object into a hash table of size 10 and the hash code value of the course is 65, it would go into the fifth slot:

 65 % 10 = 5 

Just as in an array, Java calculates the memory address for the start of a slot using the formula:

 offset + (slot size * slot number) 

Figure 9.3 shows a Course element slotted into a hash table.

Figure 9.3. Hash Table with Course in the Fifth Slot


The hash code is an int that is retrieved by sending the message hashCode to any Object. The class java.lang.Object supplies a default definition of hashCode. It returns a unique number based upon the memory address of the object.

To retrieve an object from a hash table, you recalculate the slot by asking for the object's hashCode again. You can then do the same offset calculation to immediately retrieve the object.

So what goes in a hashCode method? It must return an int, and as mentioned, two equal objects must return the same hashCode. The simplest, but worst, solution would be to return a constant, such as the number 1.



Agile Java. Crafting Code with Test-Driven Development
Agile Javaв„ў: Crafting Code with Test-Driven Development
ISBN: 0131482394
EAN: 2147483647
Year: 2003
Pages: 391
Authors: Jeff Langr

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net