COMPSCI 61B Lecture Notes - Lecture 21: Hash Table, Trie, Dissociation Constant
Document Summary
We"ve seen 2 fairly general implementations of sets and maps. Hash table: requires that keys can be hashed. Search tree: requires that keys can be compared. Data indexed array: requires that keys are small. 2d range searching: how many objects are in the highlighted rectangle. Suppose the set is stored as a hash table, where the hash code of each body is given below. The bucket that each object is effectively random. The problem with hash tables is that the bucket # of an item is random. One fix is to ensure that the bucket #s depend only on position. Example on right for 4x4 grid of such buckets. Nice improvement, no need to look at points in bucket. Simplest idea: partition space into uniform rectangular buckets ( bins ) Typical implementation would have the container itself compute a bucket number. This is sometimes called spatial hashing , though it is unofficial.
