Float.hash is based on the reduction of float modulo the prime #4581

akzhan · 2017-06-16T19:35:00Z

P= 2**HASH_BITS - 1.

It's designed so that x.hash == y.hash whenever x and y are numerically equal, even if x and y have different types.

Implementation same as CPython pyhash.c.

https://github.com/python/cpython/blob/master/Python/pyhash.c

akzhan · 2017-06-16T20:17:19Z

@asterite I should note that proposed implementation of Float64.hash returns same hash high bits for 1_i32 and 1_f64,

These values are equal in terms of ==, so now {1 => 10, 1.0 => 20}[1] will return 20.

I suppose that's good.

Hashes for different binary representations of same float number now equal too (canonicalization).

bew

Your last "formatting" commit looks weird to me, is it the result of the Crystal tool formatter?

akzhan · 2017-06-16T21:47:22Z

@bew yes, it is. Formatted by bin/crystal tool format.

…= 2**HASH_BITS - 1. It's designed so that x.hash == y.hash whenever x and y are numerically equal, even if x and y have different types. Implementation same as CPython pyhash.c.

doesn't include crystal-lang#4581 yet (number normalization)

To protect against Hash DoS, change the way hash value is computed. Class|Struct should define method `def hash(hasher)` and call `hasher << @ivar` inside. As an option, for speed, and for backward compatibility, `def hash` still could be implemented. It will be used for Hash of matched type. `Thread#hash` and `Signal#hash` is implemented as unseeded cause they are used before `StdHasher @@seed` is initialized. But it is better to implement `def hash(hasher)`. StdHasher is default hasher that uses `hash(hasher)` and it is used as default seeded hasher. It also implements `unseeded` for `Enums`. Also, number normalization for hashing introduced, ie rule 'equality forces hash equality' is forced (`a == b` => `a.hash == b.hash`). Normalization idea is borrowed from Python implementation. Fixes crystal-lang#4578 Prerequisite for crystal-lang#4557 Replaces crystal-lang#4581

@akzhan

To protect against Hash DoS, change the way hash value is computed. Class|Struct should define method `def hash(hasher)` and call `hasher << @ivar` inside. As an option, for speed, and for backward compatibility, `def hash` still could be implemented. It will be used for Hash of matched type. `Thread#hash` and `Signal#hash` is implemented as unseeded cause they are used before `StdHasher @@seed` is initialized. But it is better to implement `def hash(hasher)`. StdHasher is default hasher that uses `hash(hasher)` and it is used as default seeded hasher. It also implements `unseeded` for `Enums`. Also, number normalization for hashing introduced, ie rule 'equality forces hash equality' is forced (`a == b` => `a.hash == b.hash`). Normalization idea is borrowed from Python implementation. (idea by Akzhan Abdulin @akzhan) Fixes crystal-lang#4578 Prerequisite for crystal-lang#4557 Replaces crystal-lang#4581

akzhan · 2017-07-05T08:42:23Z

Should be closed due to a more accurate #4675.

To protect against Hash DoS, change the way hash value is computed. Class|Struct should define method `def hash(hasher)` and call `hasher << @ivar` inside. As an option, for speed, and for backward compatibility, `def hash` still could be implemented. It will be used for Hash of matched type. `Thread#hash` and `Signal#hash` is implemented as unseeded cause they are used before `StdHasher @@seed` is initialized. Hash::Hasher is default hasher that uses `hash(hasher)` and it is used as default seeded hasher. Also, number normalization for hashing introduced, ie rule 'equality forces hash equality' is forced (`a == b` => `a.hash == b.hash`). Normalization idea is borrowed from Python implementation. It fixes several issues with BigInt and BigFloat on 32bit platform, but not all issues. Fixes crystal-lang#4578 Fixes crystal-lang#3932 Prerequisite for crystal-lang#4557 Replaces crystal-lang#4581 Correlates with crystal-lang#4653

Prepare hash infrastructor to future change of hashing algrorithm to protect against Hash DoS. Class|Struct should define method `def hash(hasher)` and call `hasher << @ivar` inside. As an option, for speed, and for backward compatibility, `def hash` still could be implemented. It will be used for Hash of matched type. `Thread#hash` and `Signal#hash` is implemented as unseeded cause they are used before `StdHasher @@seed` is initialized. Hash::Hasher is default hasher that uses `hash(hasher)` and it is used as default seeded hasher. Also, number normalization for hashing introduced, ie rule 'equality forces hash equality' is forced (`a == b` => `a.hash == b.hash`). Normalization idea is borrowed from Python implementation. It fixes several issues with BigInt and BigFloat on 32bit platform, but not all issues. Fixes crystal-lang#4578 Fixes crystal-lang#3932 Prerequisite for crystal-lang#4557 Replaces crystal-lang#4581 Correlates with crystal-lang#4653

As declared by Crystal language reference, 1i32.hash should equal to 1f64.hash. Extracted from crystal-lang#4675, also replaces crystal-lang#4581.

* Introduces real Number normalization for Crystal::Hasher. As declared by Crystal language reference, 1i32.hash should equal to 1f64.hash. Extracted from #4675, also replaces #4581. * hash specializations for BigInt, BigFloat, BigRational.

akzhan changed the title ~~Float64.hash is based on the reduction of float64 modulo the prime~~ Float.hash is based on the reduction of float modulo the prime Jun 16, 2017

akzhan force-pushed the Float64.hash-inspired-by-_Py_HashDouble branch from 8a638d5 to 2b6a792 Compare June 16, 2017 20:49

bew reviewed Jun 16, 2017

View reviewed changes

akzhan mentioned this pull request Jun 26, 2017

change computation of hash value. #4621

Closed

akzhan added 8 commits June 26, 2017 20:04

Float64.hash is based on the reduction of float64 modulo the prime P …

58b2cb1

…= 2**HASH_BITS - 1. It's designed so that x.hash == y.hash whenever x and y are numerically equal, even if x and y have different types. Implementation same as CPython pyhash.c.

Fix Hash specification. 1 and 1.0 keys are equal in Crystal.

560fa13

Use same canonicalization on floats with Float32.hash.

82cbb4f

formatting

fc3a7a4

Float::Hasher module now available as Number::Hasher.

b3fc636

Extract Number::Hasher to allow build on 32bit.

97dbed2

U32_MINUS_TWO is useless.

7593e6c

Python hasher returns -2 hash for -1 value. It's useless for us.

8de32ac

akzhan force-pushed the Float64.hash-inspired-by-_Py_HashDouble branch 3 times, most recently from fec9bd6 to 8de32ac Compare June 26, 2017 17:44

mverzilli added kind:feature topic:stdlib labels Jun 26, 2017

funny-falcon added a commit to funny-falcon/crystal that referenced this pull request Jun 27, 2017

intermediate hasher commit

161bc70

doesn't include crystal-lang#4581 yet (number normalization)

funny-falcon mentioned this pull request Jul 5, 2017

change computation of hash value. #4675

Closed

akzhan closed this Jul 5, 2017

akzhan mentioned this pull request Oct 8, 2017

Implement BigDecimal #4876

Merged

akzhan mentioned this pull request Nov 11, 2017

Number normalization for Crystal::Hasher #5276

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Float.hash is based on the reduction of float modulo the prime #4581

Float.hash is based on the reduction of float modulo the prime #4581

akzhan commented Jun 16, 2017

akzhan commented Jun 16, 2017 •

edited

bew left a comment •

edited

akzhan commented Jun 16, 2017 •

edited

akzhan commented Jul 5, 2017

Float.hash is based on the reduction of float modulo the prime #4581

Float.hash is based on the reduction of float modulo the prime #4581

Conversation

akzhan commented Jun 16, 2017

akzhan commented Jun 16, 2017 • edited

bew left a comment • edited

Choose a reason for hiding this comment

akzhan commented Jun 16, 2017 • edited

akzhan commented Jul 5, 2017

akzhan commented Jun 16, 2017 •

edited

bew left a comment •

edited

akzhan commented Jun 16, 2017 •

edited