Hashtable implementation details
Factor handbook » The language » Collections » Hashtables

Prev:Hashtable utilities


This hashtable implementation uses only one auxiliary array in addition to the hashtable tuple itself. The array stores keys in even slots and values in odd slots. Values are looked up with a hashing strategy that uses quadratic probing to resolve collisions.

There are two special objects: the +tombstone+ marker and the +empty+ marker. Neither of these markers can be used as hashtable keys.

The count slot is the number of entries including deleted entries, and deleted is the number of deleted entries.
<hash-array> ( n -- array )

set-nth-pair ( value key array n -- )


If a hashtable's keys are mutated, or if hashing algorithms change, hashtables can be rehashed:
rehash ( hash -- )