@antirez When we resize the dict ( from a bigger size to a smaller size ), we can calculate the index in the new hash table by the index in the old hash table, and we don't need to call dictHashKey function again.
And we can change the line:
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
To:
h = ((d->ht[1].size < d->ht[0].size) ? d->rehashidx : dictHashKey(d, de->key)) & d->ht[1].sizemask;
This is a proof: Let Size(new) is the size of the new hash table. Let Size(old) is the size of the old hash table. Let Hash(x) is the Hash function used by both the new hash table and the old hash table. Let Idx(old)(x) is the index of the element x in the old hash table. Let Idx(new)(x) is the index of the element x in the new hash table. Prove it: If Size(new) < Size(old), then Idx(new)(x) = ( Hash(x) mod Size(new) ) = ( Idx(old)(x) mod Size(new) ).
Since both Size(new) and Size(old) are powers of 2, and Size(new) < Size(old), So Size(old) mod Size(new) = 0. Let D = Size(old) div Size(new). Then Size(old) = D * Size(new) ... (1) Let N(old)(x) = Hash(x) div Size(old). Then Hash(x) = Size(old) * N(old)(x) + Idx(old)(x) ... (2) Let N(new)(x) = Hash(x) div Size(new). Then Hash(x) = Size(new) * N(new)(x) + Idx(new)(x) ... (3) Combine (2) and (3), Size(old) * N(old)(x) + Idx(old)(x) = Size(new) * N(new)(x) + Idx(new)(x) ... (4) Plug (1) into (4), D * Size(new) * N(old)(x) + Idx(old)(x) = Size(new) * N(new)(x) + Idx(new)(x). Reformat it. Idx(old)(x) = ( N(new)(x) - D * N(old)(x) ) * Size(new) + Idx(new)(x). Hence, Idx(new)(x) = Idx(old)(x) mod Size(new).
Comment From: haiyuzhu
Wow! Great idea. However, I think there is no scenario where we should cut down the size of dictionary.