Skip to content

Commit f9237fd

Browse files
asteriteasterite
committedSep 11, 2017
Introduce Crystal::Hasher for computing a hash value
·
v0.24.10.24.0
1 parent 177028e commit f9237fd

39 files changed

+204
-162
lines changed
 

Diff for: ‎spec/std/big/big_int_spec.cr

+6-3
Original file line numberDiff line numberDiff line change
@@ -324,9 +324,12 @@ describe "BigInt" do
324324
end
325325

326326
it "#hash" do
327-
hash = 5.to_big_i.hash
328-
hash.should eq(5)
329-
typeof(hash).should eq(UInt64)
327+
b1 = 5.to_big_i
328+
b2 = 5.to_big_i
329+
b3 = 6.to_big_i
330+
331+
b1.hash.should eq(b2.hash)
332+
b1.hash.should_not eq(b3.hash)
330333
end
331334

332335
it "clones" do

Diff for: ‎spec/std/bool_spec.cr

+1-2
Original file line numberDiff line numberDiff line change
@@ -28,8 +28,7 @@ describe "Bool" do
2828
end
2929

3030
describe "hash" do
31-
it { true.hash.should eq(1) }
32-
it { false.hash.should eq(0) }
31+
it { true.hash.should_not eq(false.hash) }
3332
end
3433

3534
describe "to_s" do

Diff for: ‎spec/std/enum_spec.cr

+1-1
Original file line numberDiff line numberDiff line change
@@ -142,7 +142,7 @@ describe Enum do
142142
end
143143

144144
it "has hash" do
145-
SpecEnum::Two.hash.should eq(1.hash)
145+
SpecEnum::Two.hash.should_not eq(SpecEnum::Three.hash)
146146
end
147147

148148
it "parses" do

Diff for: ‎spec/std/float_spec.cr

+2-2
Original file line numberDiff line numberDiff line change
@@ -206,11 +206,11 @@ describe "Float" do
206206

207207
describe "hash" do
208208
it "does for Float32" do
209-
1.2_f32.hash.should_not eq(0)
209+
1.2_f32.hash.should eq(1.2_f32.hash)
210210
end
211211

212212
it "does for Float64" do
213-
1.2.hash.should_not eq(0)
213+
1.2.hash.should eq(1.2.hash)
214214
end
215215
end
216216

Diff for: ‎spec/std/hash_spec.cr

+4-5
Original file line numberDiff line numberDiff line change
@@ -146,7 +146,7 @@ describe "Hash" do
146146
end
147147

148148
it "works with mixed types" do
149-
{1 => :a, "a" => 1, 1.0 => "a", :a => 1.0}.values_at(1, "a", 1.0, :a).should eq({:a, 1, "a", 1.0})
149+
{1 => :a, "a" => 1, 2.0 => "a", :a => 1.0}.values_at(1, "a", 2.0, :a).should eq({:a, 1, "a", 1.0})
150150
end
151151
end
152152

@@ -542,14 +542,13 @@ describe "Hash" do
542542
end
543543

544544
it "computes hash" do
545-
h = { {1 => 2} => {3 => 4} }
546-
h.hash.should_not eq(h.object_id)
547-
545+
h1 = { {1 => 2} => {3 => 4} }
548546
h2 = { {1 => 2} => {3 => 4} }
549-
h.hash.should eq(h2.hash)
547+
h1.hash.should eq(h2.hash)
550548

551549
h3 = {1 => 2, 3 => 4}
552550
h4 = {3 => 4, 1 => 2}
551+
553552
h3.hash.should eq(h4.hash)
554553
end
555554

Diff for: ‎spec/std/named_tuple_spec.cr

+1-1
Original file line numberDiff line numberDiff line change
@@ -135,7 +135,7 @@ describe "NamedTuple" do
135135

136136
it "computes a hash value" do
137137
tup1 = {a: 1, b: 'a'}
138-
tup1.hash.should_not eq(0)
138+
tup1.hash.should eq(tup1.dup.hash)
139139

140140
tup2 = {b: 'a', a: 1}
141141
tup2.hash.should eq(tup1.hash)

Diff for: ‎spec/std/proc_spec.cr

+1-3
Original file line numberDiff line numberDiff line change
@@ -91,7 +91,5 @@ describe "Proc" do
9191
f2.call('r').should eq(2)
9292
end
9393

94-
it "#hash" do
95-
->{ 1 }.hash.should_not eq(0)
96-
end
94+
typeof(->{ 1 }.hash)
9795
end

Diff for: ‎spec/std/struct_spec.cr

+3-2
Original file line numberDiff line numberDiff line change
@@ -42,11 +42,12 @@ describe "Struct" do
4242

4343
it "does hash" do
4444
s = StructSpec::TestClass.new(1, "hello")
45-
s.hash.should eq(31 + "hello".hash)
45+
s.hash.should eq(s.dup.hash)
4646
end
4747

4848
it "does hash for struct wrapper (#1940)" do
49-
StructSpec::BigIntWrapper.new(BigInt.new(0)).hash.should eq(0)
49+
s = StructSpec::BigIntWrapper.new(BigInt.new(0))
50+
s.hash.should eq(s.dup.hash)
5051
end
5152

5253
it "does dup" do

Diff for: ‎spec/std/time/span_spec.cr

+3-1
Original file line numberDiff line numberDiff line change
@@ -176,7 +176,9 @@ describe Time::Span do
176176
end
177177

178178
it "test hash code" do
179-
Time::Span.new(77).hash.should eq(77)
179+
t1 = Time::Span.new(77)
180+
t2 = Time::Span.new(77)
181+
t1.hash.should eq(t2.hash)
180182
end
181183

182184
it "test subtract" do

Diff for: ‎src/big/big_float.cr

+2-3
Original file line numberDiff line numberDiff line change
@@ -76,9 +76,8 @@ struct BigFloat < Float
7676
new(mpf)
7777
end
7878

79-
def hash
80-
to_f64.hash
81-
end
79+
# TODO: improve this
80+
def_hash to_f64
8281

8382
def self.default_precision
8483
LibGMP.mpf_get_default_prec

Diff for: ‎src/big/big_int.cr

+2-3
Original file line numberDiff line numberDiff line change
@@ -343,9 +343,8 @@ struct BigInt < Int
343343
io << "_big_i"
344344
end
345345

346-
def hash
347-
to_u64
348-
end
346+
# TODO: improve this
347+
def_hash to_u64
349348

350349
# Returns a string representation of self.
351350
#

Diff for: ‎src/big/big_rational.cr

+2-3
Original file line numberDiff line numberDiff line change
@@ -161,9 +161,8 @@ struct BigRational < Number
161161
BigRational.new { |mpq| LibGMP.mpq_abs(mpq, self) }
162162
end
163163

164-
def hash
165-
to_f64.hash
166-
end
164+
# TODO: improve this
165+
def_hash to_f64
167166

168167
# Returns the `Float64` representing this rational.
169168
def to_f

Diff for: ‎src/bool.cr

+3-3
Original file line numberDiff line numberDiff line change
@@ -41,9 +41,9 @@ struct Bool
4141
self != other
4242
end
4343

44-
# Returns a hash value for this boolean: 0 for `false`, 1 for `true`.
45-
def hash
46-
self ? 1 : 0
44+
# See `Object#hash(hasher)`
45+
def hash(hasher)
46+
hasher.bool(self)
4747
end
4848

4949
# Returns `"true"` for `true` and `"false"` for `false`.

Diff for: ‎src/char.cr

+3-3
Original file line numberDiff line numberDiff line change
@@ -414,9 +414,9 @@ struct Char
414414
Unicode.upcase(self, options) { |char| yield char }
415415
end
416416

417-
# Returns this char's codepoint.
418-
def hash
419-
ord
417+
# See `Object#hash(hasher)`
418+
def hash(hasher)
419+
hasher.char(self)
420420
end
421421

422422
# Returns a Char that is one codepoint bigger than this char's codepoint.

Diff for: ‎src/class.cr

+3-2
Original file line numberDiff line numberDiff line change
@@ -3,8 +3,9 @@ class Class
33
to_s(io)
44
end
55

6-
def hash
7-
crystal_type_id
6+
# See `Object#hash(hasher)`
7+
def hash(hasher)
8+
hasher.class(self)
89
end
910

1011
def ==(other : Class)

Diff for: ‎src/compiler/crystal/syntax/ast.cr

+3-9
Original file line numberDiff line numberDiff line change
@@ -1175,9 +1175,7 @@ module Crystal
11751175
self
11761176
end
11771177

1178-
def hash
1179-
0
1180-
end
1178+
def_hash
11811179
end
11821180

11831181
# A qualified identifier.
@@ -1545,9 +1543,7 @@ module Crystal
15451543
Self.new
15461544
end
15471545

1548-
def hash
1549-
0
1550-
end
1546+
def_hash
15511547
end
15521548

15531549
abstract class ControlExpression < ASTNode
@@ -2025,9 +2021,7 @@ module Crystal
20252021
Underscore.new
20262022
end
20272023

2028-
def hash
2029-
0
2030-
end
2024+
def_hash
20312025
end
20322026

20332027
class Splat < UnaryExpression

Diff for: ‎src/crystal/hasher.cr

+59
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
require "crystal/system/random"
2+
3+
# :nodoc:
4+
struct Crystal::Hasher
5+
# Implementation of a Hasher to compute a fast and safe hash
6+
# value for primitive and basic Crystal objects. All other
7+
# hashes are computed based on these.
8+
#
9+
# TODO: the implementation is naive and should probably use
10+
# another algorithm like SipHash or FNV.
11+
12+
@@seed = uninitialized UInt64
13+
Crystal::System::Random.random_bytes(Slice.new(pointerof(@@seed).as(UInt8*), 8))
14+
15+
property result : UInt64 = @@seed
16+
17+
def nil
18+
self
19+
end
20+
21+
def bool(value)
22+
(value ? 1 : 0).hash(self)
23+
end
24+
25+
def int(value)
26+
@result = @result * 31 + value.to_u64
27+
self
28+
end
29+
30+
def float(value)
31+
@result *= @result * 31 + value.to_f64.unsafe_as(UInt64)
32+
self
33+
end
34+
35+
def char(value)
36+
value.ord.hash(self)
37+
end
38+
39+
def enum(value)
40+
value.value.hash(self)
41+
end
42+
43+
def symbol(value)
44+
value.to_i.hash(self)
45+
end
46+
47+
def reference(value)
48+
@result = @result * 31 + value.object_id.to_u64
49+
self
50+
end
51+
52+
def string(value)
53+
value.to_slice.hash(self)
54+
end
55+
56+
def class(value)
57+
value.crystal_type_id.hash(self)
58+
end
59+
end

Diff for: ‎src/enum.cr

+3-3
Original file line numberDiff line numberDiff line change
@@ -274,9 +274,9 @@ struct Enum
274274
value == other.value
275275
end
276276

277-
# Returns a hash value. This is the hash of the underlying value.
278-
def hash
279-
value.hash
277+
# See `Object#hash(hasher)`
278+
def hash(hasher)
279+
hasher.enum(self)
280280
end
281281

282282
# Iterates each values in a Flags Enum.

Diff for: ‎src/float.cr

+5-8
Original file line numberDiff line numberDiff line change
@@ -86,6 +86,11 @@ struct Float
8686
end
8787
end
8888

89+
# See `Object#hash(hasher)`
90+
def hash(hasher)
91+
hasher.float(self)
92+
end
93+
8994
# Writes this float to the given *io* in the given *format*.
9095
# See also: `IO#write_bytes`.
9196
def to_io(io : IO, format : IO::ByteFormat)
@@ -153,10 +158,6 @@ struct Float32
153158
io << "_f32"
154159
end
155160

156-
def hash
157-
unsafe_as(Int32)
158-
end
159-
160161
def clone
161162
self
162163
end
@@ -211,10 +212,6 @@ struct Float64
211212
Printer.print(self, io)
212213
end
213214

214-
def hash
215-
unsafe_as(Int64)
216-
end
217-
218215
def clone
219216
self
220217
end

Diff for: ‎src/hash.cr

+15-11
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,5 @@
1+
require "crystal/hasher"
2+
13
# A `Hash` represents a mapping of keys to values.
24
#
35
# See the [official docs](http://crystal-lang.org/docs/syntax_and_semantics/literals/hash.html) for the basics.
@@ -706,18 +708,20 @@ class Hash(K, V)
706708
true
707709
end
708710

709-
# See also: `Object#hash`.
710-
#
711-
# ```
712-
# foo = {"foo" => "bar"}
713-
# foo.hash # => 3247054
714-
# ```
715-
def hash
716-
hash = size
711+
# See `Object#hash(hasher)`
712+
def hash(hasher)
713+
# The hash value must be the same regardless of the
714+
# order of the keys.
715+
result = hasher.result
716+
717717
each do |key, value|
718-
hash += key.hash ^ value.hash
718+
copy = hasher
719+
copy = key.hash(copy)
720+
copy = value.hash(copy)
721+
result += copy.result
719722
end
720-
hash
723+
724+
result.hash(hasher)
721725
end
722726

723727
# Duplicates a `Hash`.
@@ -864,7 +868,7 @@ class Hash(K, V)
864868
end
865869

866870
private def bucket_index(key)
867-
key.hash.to_u32.remainder(@buckets_size).to_i
871+
key.hash.remainder(@buckets_size).to_i
868872
end
869873

870874
private def calculate_new_size(size)

Diff for: ‎src/http/headers.cr

+3-5
Original file line numberDiff line numberDiff line change
@@ -9,13 +9,11 @@ struct HTTP::Headers
99
record Key, name : String do
1010
forward_missing_to @name
1111

12-
def hash
13-
h = 0
12+
def hash(hasher)
1413
name.each_byte do |c|
15-
c = normalize_byte(c)
16-
h = 31 * h + c
14+
hasher = normalize_byte(c).hash(hasher)
1715
end
18-
h
16+
hasher
1917
end
2018

2119
def ==(key2)

0 commit comments

Comments
 (0)
Please sign in to comment.