Section 33.10 Implementing a Set or Map
A hash table is another tool that can be used to implement the abstract data types of set and map. As with our BST based implementations, a set is a very simple wrapper around a hash table to provide the set interface. Implementing a map takes a little more work because we need to store both keys and values. We can do this by creating a simple class to represent a key-value pair and then storing instances of that class in the hash table.
In a similar way, we can retrieve a value by hashing the key to find the appropriate cell and then searching (either using probing or through the linked list) for the key-value pair with the matching key. We then return the associated value.
Compared to a BST, a hash table based implementation of a set or map is generally more efficient for lookups, insertions, and removals. (\(O(1)\) on average vs \(O(\log n)\) on average for a BST.)
However, it is worth remembering that the difference between \(O(1)\) and \(O(\log n)\) is not large. Going from \(O(n)\) performance to \(O(1)\) performance is a huge deal. Given an \(n\) of 1,000,000,000, it is the difference between doing ~1,000,000,000 operations and doing ~30 operation. Going from \(O(\log n)\) to \(O(1)\) is the difference between doing about 30 operations and doing 1 operation. So, while a hash table is more efficient than a BST, the difference is not likely to be dramatic unless we are working with very large data sets and/or doing a very large number of operations.
In exchange for slightly worse performance, a BST based implementation of a set or map stores data in sorted order. This makes it easier to support operations like finding the minimum or maximum key, or finding the next key after a given key. If we care about those operations, we should favor a BST based implementation.
You have attempted of activities on this page.
