Class: Antlr4ruby::MurmurHash

Inherits:
Object
  • Object
show all
Defined in:
lib/antlr4ruby/misc/murmur_hash.rb

Constant Summary collapse

DEFAULT_SEED = 
0

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ MurmurHash

Returns a new instance of MurmurHash.



8
9
10
 
# File 'lib/antlr4ruby/misc/murmur_hash.rb', line 8

def initialize
  raise "不能实例化 #{self.class.name}."
end

Class Method Details

.finish(hash, number_of_words) ⇒ Object 



43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/antlr4ruby/misc/murmur_hash.rb', line 43

def finish(hash, number_of_words)
  mask = 0xffffffff
  hash &= mask; number_of_words &= mask

  hash = (hash ^ (number_of_words << 2)) & mask
  hash = (hash ^ (hash >> 16)) & mask
  hash =  (hash * 0x85EBCA6B) & mask
  hash = (hash ^ (hash >> 13)) & mask
  hash = (hash * 0xC2B2AE35) & mask
  hash = (hash ^ (hash >> 16)) & mask
  if hash > 2147483647
    hash - 4294967296
  else
    hash
  end
end

.hash(data, seed) ⇒ Object 



60
61
62
63
64
65
66
67
 
# File 'lib/antlr4ruby/misc/murmur_hash.rb', line 60

def hash(data, seed)
  hash = init(seed)
  data.each do |value|
    hash = update(hash, value)
  end

  finish(hash, data.length)
end

.init(seed = DEFAULT_SEED) ⇒ Object 



13
 
# File 'lib/antlr4ruby/misc/murmur_hash.rb', line 13

def init(seed = DEFAULT_SEED) seed; end

.update(hash, value) ⇒ Object 



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/antlr4ruby/misc/murmur_hash.rb', line 14

def update(hash, value)
  v = value.hash
  # 首先判断 hash 是否在 32 位整数所能够表达的范围内, 貌似超出范围也无所谓
  # raise "hash 值超出范围" if v < -2147483648 || v > 2147483647

  c1 = 0xCC9E2D51
  c2 = 0x1B873593
  r1 = 15
  r2 = 13
  m = 5
  n = 0xE6546B64
  mask = 0xffffffff

  v = (v * c1) & mask # 通过 & 0xffffffff 可以将有符号数转换为无符号
  v = ((v << r1) | (v >> (32 - r1))) & mask
  v = (v * c2) & mask

  hash = (hash ^ v) & mask
  hash = ((hash << r2) | hash >> (32 - r2)) & mask

  # 减去 4294967296 是为了将无符号数再次转换回有符号数
  hash = ((hash * m + n) & mask)
  if hash > 2147483647
    hash - 4294967296
  else
    hash
  end
end