Once the key is generated, it's "perfect" and collisions in find or pop are not possible.
I spent some time trying to understand the secret of this property, and came up with a description of the problem and solution which I thought was helpful. A `tokenmap` is essentially a dynamic array-backed hash map (from tokens [32-bit unsigned integers, WLOG] to `mapped_type` objects) with custom find, rehash, and insert members. Calling the array `store` and its size `store_size`, the find member returns the `mapped_type` object `store[key % store_size]`. The rehash member doubles the size of `store`, and for each element in the old store, the element is placed at `new_store[key % 2*old_store_size]`. Finally, the insert member basically finds an unused element of `store` where the given `mapped_type` object can be placed, and returns some token value (key) such that the token mod `store_size` is the index where the `mapped_type` object was placed. I denote the set of integers by Z and the ring of integers mod s by Z_s. Elements of Z_s are denoted with so-called "class notation": [x]_s is the set of integers that have the same remainder as x when divided by s; in other words, for x an integer, [x]_s is the set of all integers that are congruent mod s. The size of `store` begins with s_0, the initial size, and proceeds to s_1 after the first rehash. Generally, s_k is the size of the store after k rehashes. In order for the token-generating strategy to be "perfect", then the key property of generated tokens x and y is: [x]_{s_0} != [y]_{s_0} -> [x]_{s_k} != [y]_{s_k} (If x and y mod s_0 have different indices in the store of length s_0, then they must have different indices in the store of length s_k.) and: [x]_{s_k} != [y]_{s_k} -> [x]_{s_{k + 1}} != [y]_{s_{k + 1}} Some choices of the sequence {s_k} will not work. For example, suppose s_0 was 2 and s_1 was 3. Then, tokens 0x25b786ef and 0x0010b86c can be generated while the store size is 2 (because mod 2, they are 1 and 0, respectively), but once the store size becomes 3, then they hash to the same location (they are both 2 mod 3). In `tokenmap`, the sequence of sizes is 2^k*s_0. Generally, because the size of the store is always a multiple of the initial size, then the "perfect" property is maintained; I claim that [x]_s != [y]_s -> [x]_{c*s} != [y]_{c*s} for any natural number c. In order to prove the claim, I consider the logically-equivalent contrapositive: [x]_{c*s} == [y]_{c*s} -> [x]_s == [y]_s: [x]_{c*s} == [y]_{c*s} -> c*s | (x - y) c*s | (x - y) -> s | (x - y) -> [x]_s == [y]_s qed. So, in conclusion: 1. In order to maintain the "perfect" property, the size of the store only needs to be a multiple of the initial size. 2. Special support from the container is needed so that the size of the store is always a multiple of the initial size and rehashing is performed correctly.