The Java Course provides a general introduction to programming in Java. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.


Hash Table Implementation

The reason that the built-in implementation of the Table ADT is called Hashtable is that it uses a particularly efficient implementation of a Table called a hashtable.

Of course, the whole point of defining an ADT is that it allows us to use an implementation without knowing the details. So it is probably a bad thing that the people who wrote the Java library named this class according to its implementation rather than its ADT, but I suppose of all the bad things they did, this one is pretty small.

Anyhoo, you might be wondering what a hashtable is, and why I say it is particularly efficient. We'll start by analyzing the performance of the List implementation we just did.

Looking at the implementation of put, we see that there are two cases. If the key is not already in the table, then we only have to create a new key-value pair and add it to the List. Both of these are constant-time operations.

In the other case, we have to traverse the List to find the existing key-value pair. That's a linear time operation. For the same reason, get and containsKey are also linear.

Although linear operations are often good enough, we can do better. It turns out that there is a way to implement the Table ADT so that both put and get are constant time operations!

The key is to realize that traversing a list takes time proportional to the length of the list. If we can put an upper bound on the length of the list, then we can put an upper bound on the traverse time, and anything with a fixed upper bound is considered constant time.

But how can we limit the length of the lists without limiting the number of items in the table? By increasing the number of lists. Instead of one long list, we'll keep many short lists.

As long as we know which list to search, we can put a bound on the amount of searching.



Last Update: 2011-01-24