Module: PearsonHashing

Defined in:
lib/pearson-hashing.rb,
lib/pearson-hashing/version.rb

Constant Summary collapse

TABLE = 
[49, 118,  63, 252,  13, 155, 114, 130, 137,  40, 210,  62, 219, 246, 136, 221,
174, 106,  37, 227, 166,  25, 139,  19, 204, 212,  64, 176,  70,  11, 170,  58,
146,  24, 123,  77, 184, 248, 108, 251,  43, 171,  12, 141, 126,  41,  95, 142,
167,  46, 178, 235,  30,  75,  45, 208, 110, 230, 226,  50,  32, 112, 156, 180,
205,  68, 202, 203,  82,   7, 247, 217, 223,  71, 116,  76,   6,  31, 194, 183,
 15, 102,  97, 215, 234, 240,  53, 119,  52,  47, 179,  99, 199,   8, 101,  35,
 65, 132, 154, 239, 148,  51, 216,  74,  93, 192,  42,  86, 165, 113,  89,  48,
100, 195,  29, 211, 169,  38,  57, 214, 127, 117,  59,  39, 209,  88,   1, 134,
 92, 163,   0,  66, 237,  22, 164, 200,  85,   9, 190, 129, 111, 172, 231,  14,
181, 206, 128,  23, 187,  73, 149, 193, 241, 236, 197, 159,  55, 125, 196,  60,
161, 238, 245,  94,  87, 157, 122, 158, 115, 207,  17,  20, 145, 232, 107,  16,
 21, 185,  33, 225, 175, 253,  81, 182,  67, 243,  69, 220, 153,   5, 143,   3,
 26, 213, 147, 222, 105, 188, 229, 191,  72, 177, 250, 135, 152, 121, 218,  44,
120, 140, 138,  28,  84, 186, 198, 131,  54,   2,  56,  78, 173, 151,  83,  27,
255, 144, 249, 189, 104,   4, 168,  98, 162, 150, 254, 242, 109,  34, 133, 224,
228,  79, 103, 201, 160,  90,  18,  61,  10, 233,  91,  80, 124,  96, 244,  36]
VERSION = 
"0.0.4"

Class Method Summary collapse

Class Method Details

.digest16(string) ⇒ Fixnum

Calculates a bit more complex 16bit hash, as describe in page 679 of: (values range from 0 to 65536)

cs.mwsu.edu/~griffin/courses/2133/downloads/Old_Assignments/p677-pearson.pdf

Parameters:

  • string (String)

Returns:

  • (Fixnum) —

    hash



50
51
52
53
54
55
 
# File 'lib/pearson-hashing.rb', line 50

def self.digest16(string)
  h1 = PearsonHashing.digest8 string
  h2 = PearsonHashing.digest8 shift string
  format = '%03d'
  (format % h1 + format % h2).to_i
end

.digest32(string) ⇒ Object

32 bit hash

Parameters:

  • string (String)
  • hashvalue (Fixnum) 


60
61
62
63
64
65
66
 
# File 'lib/pearson-hashing.rb', line 60

def self.digest32(string)
  h1 = PearsonHashing.digest8 string
  h2 = PearsonHashing.digest8 shift string
  h3 = PearsonHashing.digest8 shift shift string
  format = '%03d'
  (format % h1 + format % h2 + format % h3).to_i
end

.digest8(string) ⇒ Fixnum Also known as: digest

Calculates a 8bit hash based on pearson hashing algorithm (values range from 0 to 256)

Further descriptions can be found here:

* http://en.wikipedia.org/wiki/Pearson_hashing
* http://cs.mwsu.edu/~griffin/courses/2133/downloads/Old_Assignments/p677-pearson.pdf

Parameters:

  • string (String)

Returns:

  • (Fixnum) —

    hash



31
32
33
34
35
36
37
 
# File 'lib/pearson-hashing.rb', line 31

def self.digest8(string)
  hash = string.size % 256
  string.each_byte do |byte|
    hash = TABLE[ (hash + byte) % 256 ]
  end
  hash
end

.digest_with_x_bytes(string, no_of_bytes) ⇒ Fixnum

this is a dynamic implementation just to enable longer hashes but known to be slower than the hardcoded methods above

1 byte = 8 bit 2 bytes = 16 bit …

Parameters:

  • string (String)
  • no (Fixnum) —

    of bytes

Returns:

  • (Fixnum) —

    hashvalue



78
79
80
81
82
83
84
85
86
 
# File 'lib/pearson-hashing.rb', line 78

def self.digest_with_x_bytes(string, no_of_bytes)
  tmp_str = string.dup
  result = ''
  no_of_bytes.times do
    result = result + "%03d" % PearsonHashing.digest8(tmp_str)
    tmp_str = shift(tmp_str)
  end
  result.to_i
end