4 ms·

That would be a very strange hash map :) Could it be that you are confusing hash functions with PRNGs?

adastra22 1y ago
Why do you think they are different? That's what a hash function is--mapping input to outputs with a pseudo-random distribution. Different words for literally the same thing.
- spacechild1 1y ago
  > That's what a hash function is--mapping input to outputs with a pseudo-random distribution That's not what a PRNG does. A PRNG produces a sequence of pseudo-random values (with a particular distribution) based on an initial seed value. A hash function is stateless, a PRNG is not.
  - adastra22 1y ago
    When used as a hasher, the 'seed' is the input. When used as a PRNG tool, the seed is an incrementing counter or something. It's the same function though.
    - spacechild1 1y ago
      I see what you mean. You can use a hash function to build a PRNG, but the hash function itself it not a PRNG. In a hash table, the hash function is not used to produce a series of random numbers, that's why it's a bit silly to call it a PRNG. Instead, the purpose is to reduce a (possibly larger) input value to a fixed size output value, often with the requirement that similar input values should result in very different output values to avoid clustering. However, your hash table example is still useful as an analogy.
SideQuark 1y ago
A many hash tables use PRNG sequences for collision resolution by moving around to other buckets. That PRNG seed comes from the hash value. PRNGs are chosen for good uniform spread and repeatable sequence and speed. The naive collision resolution ideas start like this: chained items (slow, memory costs), linear probing (results in clustering), quadratic probing (better, still has problems), double hashing (good), PRNG sequences with good properties (so any item hitting the same spot checks the same seq of overflow slots. One can alternate linear and PRNG or other combos. Start with the basic wiki article https://en.wikipedia.org/wiki/Hash_table https://en.wikipedia.org/wiki/Hash_table, check through many of the modern has table types linked from there.

Why do you think they are different? That's what a hash function is--mapping input to outputs with a pseudo-random distribution. Different words for literally the same thing.

spacechild1 1y ago
> That's what a hash function is--mapping input to outputs with a pseudo-random distribution That's not what a PRNG does. A PRNG produces a sequence of pseudo-random values (with a particular distribution) based on an initial seed value. A hash function is stateless, a PRNG is not.
- adastra22 1y ago
  When used as a hasher, the 'seed' is the input. When used as a PRNG tool, the seed is an incrementing counter or something. It's the same function though.
  - spacechild1 1y ago
    I see what you mean. You can use a hash function to build a PRNG, but the hash function itself it not a PRNG. In a hash table, the hash function is not used to produce a series of random numbers, that's why it's a bit silly to call it a PRNG. Instead, the purpose is to reduce a (possibly larger) input value to a fixed size output value, often with the requirement that similar input values should result in very different output values to avoid clustering. However, your hash table example is still useful as an analogy.

SideQuark 1y ago

A many hash tables use PRNG sequences for collision resolution by moving around to other buckets. That PRNG seed comes from the hash value. PRNGs are chosen for good uniform spread and repeatable sequence and speed. The naive collision resolution ideas start like this: chained items (slow, memory costs), linear probing (results in clustering), quadratic probing (better, still has problems), double hashing (good), PRNG sequences with good properties (so any item hitting the same spot checks the same seq of overflow slots. One can alternate linear and PRNG or other combos. Start with the basic wiki article https://en.wikipedia.org/wiki/Hash_table https://en.wikipedia.org/wiki/Hash_table, check through many of the modern has table types linked from there.