Hash Tables


You need to create a student directory to contain students enrolled in the university. The system must allow each student to be assigned a unique identifier, or ID. The system must allow you to later retrieve each student from the directory using its ID.


To build this story, you will create a StudentDirectory class. While you could use an ArrayList to store all students, you will instead use a Map. You learned a bit about maps in Lesson 6. As a reminder, Map is the interface for a data structure that allows elements to be stored and received based on a key. A map is a collection of key-value pairs. You store, or put, an element at a certain key in a map. You later retrieve, or get, that element by supplying the proper key.

In Lesson 6, you learned about the EnumMap implementation of the Map interface. If the keys in a Map are of enum type, you should use an EnumMap. Otherwise you will usually want to use the workhorse implementation of Map, java.util.HashMap. HashMap is a general-use map based on a data structure known as a hash table. Most Map code you encounter will use the HashMap implementation (or the legacy Hashtable implementationsee Lesson 7).

A hash table provides a specific way to implement a map. It is designed for rapid insertion and retrieval.

To build the student directory, start with the test:

 package sis.studentinfo; import junit.framework.*; import java.io.*; public class StudentDirectoryTest extends TestCase {    private StudentDirectory dir;    protected void setUp() {       dir = new StudentDirectory();    }    public void testStoreAndRetrieve() throws IOException {       final int numberOfStudents = 10;       for (int i = 0; i < numberOfStudents; i++)          addStudent(dir, i);       for (int i = 0; i < numberOfStudents; i++)          verifyStudentLookup(dir, i);   }   void addStudent(StudentDirectory directory, int i)          throws IOException {       String id = "" + i;       Student student = new Student(id);       student.setId(id);       student.addCredits(i);       directory.add(student);    }    void verifyStudentLookup(StudentDirectory directory, int i)          throws IOException {       String id = "" + i;       Student student = dir.findById(id);       assertEquals(id, student.getLastName());       assertEquals(id, student.getId());       assertEquals(i, student.getCredits());    } } 

The test, testStoreAndRetrieve, uses a for loop to construct and insert a number of students into the StudentDirectory. The test verifies, again using a for loop, that each student can be found in the directory using the Student directory method findById.

The StudentDirectory code is brief.

 package sis.studentinfo; import java.util.*; public class StudentDirectory {    private Map<String,Student> students =       new HashMap<String,Student>();    public void add(Student student) {       students.put(student.getId(), student);    }    public Student findById(String id) {       return students.get(id);    } } 

A StudentDirectory object encapsulates a HashMap, students. When client code invokes the add method, the code in add inserts the student argument into the HashMap. The key for the inserted student is the student's ID.

The ID must be unique. If you put a new value at an ID for which an entry already exists, the old value is replaced.

Later in this lesson, you will revisit hash tables. First, however, you will learn about equality. And before you can learn about equality, you have a story to implement.



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