Section 33.1 Constant Time Lookup Table
Using a self-balancing tree can allow us to build a data structure that can insert, delete, and lookup values in \(O(\log n)\) time. That is a massive improvement over the \(O(n)\) time complexity we would get for at least some of those operations if we used an array or linked list. However, we can do even better than that.
To understand how, let’s start with a very simple idea. Let’s say we want to store some numbers between 0 and 99. We could create an array with 100 cells, where each cell represents one of those numbers. If we want to store a number, we can just set the value of the corresponding cell to 1. To delete the number, we can set the value back to 0. Because accessing any item in an array is an \(O(1)\) operation, we can insert, delete, and lookup values in constant time!
Of course, there are some issues with this approach:
-
It only works for integers (because they can be indexes in the array)
-
We have to know the range of values in advance (or reallocate the array if the range changes)
-
It is very wasteful of space if we are only storing a few numbers in a large range
So, for this approach to be useful, we need to find a way to map any value we want to store to an index in a fixed-size array. That way we can have the size of the array be proportional to the number of values we are storing, rather than the range of possible values.
The method we will use to do this mapping process is known as hashing, and the data structure we will build using hashing is known as a hash table. Together, they will allow us to build a data structure that can insert, delete, and lookup values in constant time, while using space proportional to the number of values we are storing.
You have attempted of activities on this page.
