Game Engine Architecture

240 5. Engine Support Systems

Hashing

Hashing is the process of turning a key of some arbitrary data type into an

integer, which can be used modulo the table size as an index into the table.

Mathematically, given a key k, we want to generate an integer hash value h us-

ing the hash function H, and then fi nd the index i into the table as follows:

h = H(k),

i = h mod N,

where N is the number of slots in the table, and the symbol mod represents the

modulo operation, i.e., fi nding the remainder of the quotient h/N.

If the keys are unique integers, the hash function can be the identity func-

tion, H(k) = k. If the keys are unique 32-bit fl oating-point numbers, a hash func-

tion might simply re-interpret the bit patt ern of the 32-bit fl oat as if it were a

32-bit integer.

U32 hashFloat(float f)

{

union

{

float asFloat;

Slot 0

Slot 1

Slot 2

Slot 3

Slot 4

(55, apple) (0, or ange)

(26, grape)

(33, plum)

Figure 5.10. An open hash table.

(55, apple) (0, orange)

collision!

(33, plum)

(55, apple)

(26, grape)

(33, plum)

(0, orange)

(26, grape)

probe to

find new

slot

0

1

2

3

4

0

1

2

3

4

Figure 5.11. A closed hash table.