1
2
3
4
5
6
7
8
9
10
11
12
13
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
* Use of this file is governed by the BSD 3-clause license that
* can be found in the LICENSE.txt file in the project root.
*/
namespace Antlr4.Runtime.Misc
{
/// <author>Sam Harwell</author>
public sealed class MurmurHash
{
private const int DefaultSeed = 0;
/// <summary>Initialize the hash using the default seed value.</summary>
/// <remarks>Initialize the hash using the default seed value.</remarks>
/// <returns>the intermediate hash value</returns>
public static int Initialize()
{
return Initialize(DefaultSeed);
}
/// <summary>
/// Initialize the hash using the specified
/// <paramref name="seed"/>
/// .
/// </summary>
/// <param name="seed">the seed</param>
/// <returns>the intermediate hash value</returns>
public static int Initialize(int seed)
{
return seed;
}
/// <summary>
/// Update the intermediate hash value for the next input
/// <paramref name="value"/>
/// .
/// </summary>
/// <param name="hash">the intermediate hash value</param>
/// <param name="value">the value to add to the current hash</param>
/// <returns>the updated intermediate hash value</returns>
public static int Update(int hash, int value)
{
int c1 = unchecked((int)(0xCC9E2D51));
int c2 = unchecked((int)(0x1B873593));
int r1 = 15;
int r2 = 13;
int m = 5;
int n = unchecked((int)(0xE6546B64));
int k = value;
k = k * c1;
k = (k << r1) | ((int)(((uint)k) >> (32 - r1)));
k = k * c2;
hash = hash ^ k;
hash = (hash << r2) | ((int)(((uint)hash) >> (32 - r2)));
hash = hash * m + n;
return hash;
}
/// <summary>
/// Update the intermediate hash value for the next input
/// <paramref name="value"/>
/// .
/// </summary>
/// <param name="hash">the intermediate hash value</param>
/// <param name="value">the value to add to the current hash</param>
/// <returns>the updated intermediate hash value</returns>
public static int Update(int hash, object value)
{
return Update(hash, value != null ? value.GetHashCode() : 0);
}
/// <summary>
/// Apply the final computation steps to the intermediate value
/// <paramref name="hash"/>
/// to form the final result of the MurmurHash 3 hash function.
/// </summary>
/// <param name="hash">the intermediate hash value</param>
/// <param name="numberOfWords">the number of integer values added to the hash</param>
/// <returns>the final hash result</returns>
public static int Finish(int hash, int numberOfWords)
{
hash = hash ^ (numberOfWords * 4);
hash = hash ^ ((int)(((uint)hash) >> 16));
hash = hash * unchecked((int)(0x85EBCA6B));
hash = hash ^ ((int)(((uint)hash) >> 13));
hash = hash * unchecked((int)(0xC2B2AE35));
hash = hash ^ ((int)(((uint)hash) >> 16));
return hash;
}
/// <summary>
/// Utility function to compute the hash code of an array using the
/// MurmurHash algorithm.
/// </summary>
/// <remarks>
/// Utility function to compute the hash code of an array using the
/// MurmurHash algorithm.
/// </remarks>
/// <param name="data">the array data</param>
/// <param name="seed">the seed for the MurmurHash algorithm</param>
/// <returns>the hash code of the data</returns>
public static int HashCode<T>(T[] data, int seed)
{
int hash = Initialize(seed);
foreach (T value in data)
{
hash = Update(hash, value);
}
hash = Finish(hash, data.Length);
return hash;
}
private MurmurHash()
{
}
}
}