4 ms·
One property I find interesting about this scheme is that resizing the table (doubling or halving) could be done without recomputing any index — and therefore b
by Findecanor 3y ago
One property I find interesting about this scheme is that resizing the table (doubling or halving) could be done without recomputing any index — and therefore be superfast compared to the mod-prime method.
Each bucket in the smaller table maps to precisely two buckets in the larger table. The differences are in the lowest bit in the larger table's indices.
If you'd store the product in each entry then you wouldn't need to redo the multiplication when resizing. I suppose that the product would work just as well as the hash value when looking up an entry in a bucket, so you could just store that instead.
- camel-cdr 3y agoThis is also true for power of two hash tables, but it doesn't work anymore once you use open addressing.