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. 
Home Table Hash Table Implementation  
Search the VIAS Library  Index  
Hash Table Implementation
The reason that the builtin 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 keyvalue pair and add it to the List. Both of these are constanttime operations. In the other case, we have to traverse the List to find the existing keyvalue 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.


Home Table Hash Table Implementation 