10.3: Associative Array Implementation
- Page ID
- 49322
Associative arrays—that is, hash tables and binary search trees, represent a heavyweight but general representation of sets. Binary trees generally have \(O(logn)\) time implementations for lookup and mutation for a particular key, and hash tables have a \(O(1)\) implementation (though there is a higher constant factor). Additionally, they are capable of storing nearly any key type. The membership test is trivial: simply test if the potential set member exists as a key in the associative array. To add an element, just add the set member as a key in the associative array, with a dummy value. In optimized implementations, instead of reusing an existing associative array implementation, it is possible to write a specialized hash table or binary tree which does not store values corresponding to keys. Values are not meaningful here, and they take up a constant factor of additional memory space.