Daniel Trebbien wrote:
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.
Although I disagree with your conclusion that the container as-is doesn't guarantee perfect hashing, your posting was very insightful. Please read on why I think so. 1. In order to maintain the "perfect" property, the size of the store
only needs to be a multiple of the initial size.
Correct. The container grows exponentially, that is: a) SIZE_new = SIZE_prev * 2 where the initial size is a multiple of 2. Specifically, the constructor establishes the initial size as: double target_cap = (1 << key_type(ceil(log(capacity_hint)/log(2)))); Subsequently, the container grows exactly following the formula (a): double target_cap = store_.capacity() << 1; after it fails to obtain a free slot or the load_factor tells it so. 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.
I agree. The container does not allow users to influence its size past construction, ensuring the invariant of perfect hashing stays. Given the conditions 1 and 2 from your posting are met by the container's present implementation, I believe there is no problem. -sl