On 2019-05-18 17:14:59 -0500, Ron wrote:
> On 5/18/19 3:49 PM, Peter J. Holzer wrote:
>
> On 2019-05-18 15:19:22 -0500, Ron wrote:
>
> On 5/18/19 2:27 PM, Peter J. Holzer wrote:
>
> On 2019-05-18 10:49:53 -0700, David G. Johnston wrote:
>
> You don’t perform math on a hash
>
> That's not generally true. Hashes are used for further computation for
> example in hash tables or in cryptography.
>
> How is it "using math" to use a hash key in a hash lookup table?
>
> hash modulo table size.
>
>
> I've seen that used when the tablespace is pre-allocated, and you hash modulo
> the tablespace page number. (Yes, performance tanks when you start filling up
> pages.) How do you hash on the (ever growing) table size?
The hash function returns a number in a range much larger than the
possible number of buckets. 64 bits is a good choice today.
To determine the bucket you need to reduce this number to something in
the range [0, nr_buckets). This is where modulo comes in:
i = h % nr_buckets
If the the table fills up, you increase nr_buckets, reallocate and
rehash all entries.
(If nr_buckets is a power of two, the modulo operation can be
efficiently implemented by using bitwise and)
hp
--
_ | Peter J. Holzer | we build much bigger, better disasters now
|_|_) | | because we have much more sophisticated
| | | hjp@hjp.at | management tools.
__/ | http://www.hjp.at/ | -- Ross Anderson <https://www.edge.org/>