Simple Summaries for Hashing With Choices
Adam Kirsch, Michael Mitzenmacher · IEEE/ACM Transactions on Networking · 2008
In a multiple-choice hashing scheme, each item is stored in one of d ges 2 possible hash table buckets. The availability of these multiple choices allows for a substantial reduction in the maximum load of the buckets. However, a lookup may now require examining each of the locations. For applications where this cost is undesirable, Song propose keeping a summary that allows one to determine which of the locations is appropriate for each item, where the summary may allow false positives for items not in hash table. We propose alternative, simple constructions of such summaries that use less space for both the summary and the underlying hash table. Moreover, our constructions are easily analyzable and tunable.