Shared hash map implementations provide a linearizable programmatic interface to calling threads and support lock-free hash map operations. In addition to supporting lock-free operation, the shared hash map implementations are especially useful where the hash map is stored in a fixed-sized memory location such as, for example, in a shared memory segment, or in other situations where resizing the hash map is impractical or not desired.