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
| | | h...@hjp.at | management tools.
__/ | http://www.hjp.at/ | -- Ross Anderson <https://www.edge.org/>
signature.asc
Description: PGP signature
