yu.algorithm.hash source code

1 module yu.algorithm.hash;
2 
3 import yu.traits : isCharByte;
4 
5 @nogc:
6 
7 uint SDBMHash(CHAR)(const CHAR[] str) if(isCharByte!CHAR)
8 {
9     uint hash = 0;
10     foreach(ch; str)// equivalent to: hash = 65599*hash + (*str++);
11         hash = ch + (hash << 6) + (hash << 16) - hash;
12     return (hash & 0x7FFFFFFF);
13 }
14 
15 // RS Hash Function
16 uint RSHash(CHAR)(const CHAR[] str) if(isCharByte!CHAR)
17 {
18     uint b = 378551;
19     uint a = 63689;
20     uint hash = 0;
21     
22     foreach(ch; str)
23     {
24         hash = hash * a + ch;
25         a *= b;
26     }
27     
28     return (hash & 0x7FFFFFFF);
29 }
30 
31 // JS Hash Function
32 uint JSHash(CHAR)(const CHAR[] str) if(isCharByte!CHAR)
33 {
34     uint hash = 1315423911;
35     
36     foreach(ch; str)
37         hash ^= ((hash << 5) + ch + (hash >> 2));
38     
39     return (hash & 0x7FFFFFFF);
40 }
41 
42 // P. J. Weinberger Hash Function
43 uint PJWHash(CHAR)(const CHAR[] str) if(isCharByte!CHAR)
44 {
45     enum BitsInUnignedInt  = cast(uint)(uint.sizeof * 8);
46     enum ThreeQuarters    = cast(uint)((BitsInUnignedInt  * 3) / 4);
47     enum OneEighth        = cast(uint)(BitsInUnignedInt / 8);
48     enum HighBits         = cast(uint)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
49     uint hash             = 0;
50     uint test             = 0;
51     
52     foreach(ch; str)
53     {
54         hash = (hash << OneEighth) + ch;
55         if ((test = hash & HighBits) != 0)
56         {
57             hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
58         }
59     }
60     
61     return (hash & 0x7FFFFFFF);
62 }
63 
64 // ELF Hash Function
65 uint ELFHash(CHAR)(const CHAR[] str) if(isCharByte!CHAR)
66 {
67     uint hash = 0;
68     uint x    = 0;
69     
70     foreach(ch; str)
71     {
72         hash = (hash << 4) + ch;
73         if ((x = hash & 0xF0000000L) != 0)
74         {
75             hash ^= (x >> 24);
76             hash &= ~x;
77         }
78     }
79     
80     return (hash & 0x7FFFFFFF);
81 }
82 
83 // BKDR Hash Function
84 uint BKDRHash(CHAR)(const CHAR[] str) if(isCharByte!CHAR)
85 {
86     enum seed = 131; // 31 131 1313 13131 131313 etc..
87     uint hash = 0;
88     
89     foreach(ch; str)
90         hash = hash * seed + ch;
91     
92     return (hash & 0x7FFFFFFF);
93 }
94 
95 // DJB Hash Function
96 uint DJBHash(CHAR)(const CHAR[] str) if(isCharByte!CHAR)
97 {
98     uint hash = 5381;
99     
100     foreach(ch; str)
101         hash += (hash << 5) + ch;
102     
103     return (hash & 0x7FFFFFFF);
104 }
105 
106 // AP Hash Function
107 uint APHash(CHAR)(const CHAR[] str) if(isCharByte!CHAR)
108 {
109     uint hash = 0;
110     foreach(i,ch; str)
111     {
112         if ((i & 1) == 0)
113             hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
114         else
115             hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
116     }
117     
118     return (hash & 0x7FFFFFFF);
119 }
120  
121 //Jenkins hash function one-at-a-time
122 uint JKOhash(CHAR)(const CHAR[] str) if(isCharByte!CHAR)
123 {
124     uint hash = 0;
125     foreach(ch; str)
126     {
127         hash += ch;
128         hash += (hash << 10);
129         hash ^= (hash >> 6);
130     }
131     hash += (hash << 3);
132     hash ^= (hash >> 11);
133     hash += (hash << 15);
134     return hash;
135 }
136 
137 size_t Murmur3Hash(CHAR)(const CHAR[] str, size_t seed = 0) if(isCharByte!CHAR)
138 {
139     import core.internal.hash : bytesHash;
140     return bytesHash(str.ptr, str.length,seed);
141 }
142 
143 unittest {
144     string hash = "tets hash!!!";
145     const ubyte[] thash = cast(const ubyte[])hash;
146     assert(SDBMHash(hash) == SDBMHash(thash));
147     assert(RSHash(hash) == RSHash(thash));
148     assert(JSHash(hash) == JSHash(thash));
149     assert(PJWHash(hash) == PJWHash(thash));
150     assert(BKDRHash(hash) == BKDRHash(thash));
151     assert(DJBHash(hash) == DJBHash(thash));
152     assert(APHash(hash) == APHash(thash));
153     assert(JKOhash(hash) == JKOhash(thash));
154     assert(Murmur3Hash(hash) == Murmur3Hash(thash));
155 }