5 ms·

You can't really say much in general about hash functions - they're just general functions. The more you try to infer additional rules about hash functions, the

You can't really say much in general about hash functions - they're just general functions. The more you try to infer additional rules about hash functions, the more use cases you start to exclude. For example, _mostly_ hash functions have a fixed bit size for values in their range, but there's a small handful with variable length output (HAS-V & HAVAL, eg) that would otherwise be considered examples of cryptographic hash functions. At the risk of making absolute statements in a field with vague and imprecise definitions, only perfect hash functions are injective. Imperfect hash functions (typically) map a large domain to a smaller range. The presence of collisions indicates a non-injective function. Surjection is not required for all hash functions. Cryptographic hashes should be surjective, but indexing hashes that not surjective may have other desirable properties. Since in general hash functions are neither injective nor surjective, they're definitely not bijective. You can have bijective hash functions, but the practicality of them would be extremely narrow.

deleted 3y ago
[deleted]
mxkopy 3y ago
You’d better hope your hashmap is bijective, unless you’re ok with not being able to retrieve some data. Though granted the differentiating aspect of a hashmap AFAIK is the hash function.
- codebje 3y ago
  The hash key is only an index, and the same input always gives the same hash value, so you can retrieve your item just fine even if you can't recover the original key from the hashed value. A hash _map_ is not a hash _function_.
  - mxkopy 3y ago
    > the same input always gives the same hash value, so you can retrieve your item just fine You’ll retrieve a bunch of items that hash to the same value, so not exactly. You can retrieve the set of items that have the same hash as your item just fine - which is not exactly the same. > A hash _map_ is not a hash _function_. This is more or less what I was getting at. I know hash functions aren’t bijective, but hashmaps are often used as if they are. I guess I’m not sure if LSHs refer to a family of functions or hashmaps, and I guess the word hashes often implies functions - my bad.

deleted 3y ago

[deleted]

mxkopy 3y ago

You’d better hope your hashmap is bijective, unless you’re ok with not being able to retrieve some data. Though granted the differentiating aspect of a hashmap AFAIK is the hash function.

codebje 3y ago
The hash key is only an index, and the same input always gives the same hash value, so you can retrieve your item just fine even if you can't recover the original key from the hashed value. A hash _map_ is not a hash _function_.
- mxkopy 3y ago
  > the same input always gives the same hash value, so you can retrieve your item just fine You’ll retrieve a bunch of items that hash to the same value, so not exactly. You can retrieve the set of items that have the same hash as your item just fine - which is not exactly the same. > A hash _map_ is not a hash _function_. This is more or less what I was getting at. I know hash functions aren’t bijective, but hashmaps are often used as if they are. I guess I’m not sure if LSHs refer to a family of functions or hashmaps, and I guess the word hashes often implies functions - my bad.