Graphics Reference
In-Depth Information
index = hash(x,y)
mod
n
index:
01
n
-1
Figure 7.2
A (potentially infinite) 2D grid is mapped via a hash function into a small number
of hash buckets.
To handle collisions (the mapping of two keys to the same bucket) in the hash
table, two methods are traditionally used:
open hashing
and
closed hashing
. In open
hashing (also known as
separate chaining
), each bucket is allowed to contain a linked
list of records. When a new entry is added to the hash table, the bucket index is
computed and the entry is added at the start of the linked list of the corresponding
bucket. Each of the stored records contains a key along with associated data. In this
case, the key would be the original cell coordinates and the data would be the head
of a linked list of objects contained in that cell. As this representation ends up with
buckets containing lists of lists, the code for updating the data structure as objects
are added or deleted from a grid cell and its corresponding bucket becomes slightly
more complicated than desired.
In contrast, closed hashing (or
open addressing
) stores records directly within the
hash buckets themselves. When the computed bucket index of a new entry points
at an occupied bucket, new bucket indices are computed (in a consistent manner)
until an empty bucket is found and the record is inserted. The simplest such method,
known as
linear probing
, simply tries subsequent buckets until one is found, wrapping
around at the end of the hash table if necessary. Although linear probing has good
cache behavior, it performs poorly as the hash table fills. Using linear probing, hash
table utilization should not be much higher than 50% for good performance. Other,
better but more complicated, probing approaches exist. See [Knuth98] for a detailed
analysis of the behavior of linear probing and alternative probing methods.
A problem with closed hashing is that objects cannot be directly deleted from the
hash table, but must be lazily deleted to avoid having subsequent searches fail. A
lazy deletion involves marking the slot so that it is free for an insertion yet is not
considered empty, which would (incorrectly) terminate a search of the hash table for
some other object.
