001package squidpony.squidmath; 002 003/** 004 * Simple hashing functions that we can rely on staying the same cross-platform. 005 * These use the Fowler/Noll/Vo Hash (FNV-1a) algorithm, which is public domain. 006 * The hashes this returns are always 0 when given null to hash. Arrays with identical 007 * elements of identical types will hash identically. Arrays with identical numerical 008 * values but different types will hash differently. There are faster hashes out there, 009 * but many of them are intended to run on very modern desktop processors (not, say, 010 * Android phone processors, and they don't need to worry about uncertain performance 011 * on GWT regarding 64-bit math). We probably don't need to hash arrays or Strings so 012 * often that this (still very high-performance!) hash would be a bottleneck. 013 * <br> 014 * Note: This class was formerly called StableHash, but since that refers to a specific 015 * category of hashing algorithm that this is not, and since the goal is to be cross- 016 * platform, the name was changed to CrossHash. 017 * Created by Tommy Ettinger on 1/16/2016. 018 * @author Glenn Fowler 019 * @author Phong Vo 020 * @author Landon Curt Noll 021 * @author Tommy Ettinger 022 */ 023public class CrossHash { 024 public static int hash(boolean[] data) 025 { 026 if(data == null) 027 return 0; 028 int h = -2128831035, len = data.length, o = 0; 029 for (int i = 0; i < len; i++) { 030 o |= (data[i]) ? (1 << (i % 8)) : 0; 031 if(i % 8 == 7 || i == len - 1) { 032 h ^= o; 033 h *= 16777619; 034 o = 0; 035 } 036 } 037 return h; 038 } 039 public static int hash(byte[] data) 040 { 041 if(data == null) 042 return 0; 043 int h = -2128831035, len = data.length; 044 for (int i = 0; i < len; i++) { 045 h ^= data[i]; 046 h *= 16777619; 047 } 048 return h; 049 } 050 public static int hash(char[] data) 051 { 052 if(data == null) 053 return 0; 054 int h = -2128831035, len = data.length; 055 for (int i = 0; i < len; i++) { 056 h ^= data[i] & 0xff; 057 h *= 16777619; 058 h ^= data[i] >>> 8; 059 h *= 16777619; 060 } 061 return h; 062 } 063 public static int hash(short[] data) 064 { 065 if(data == null) 066 return 0; 067 int h = -2128831035, len = data.length; 068 for (int i = 0; i < len; i++) { 069 h ^= data[i] & 0xff; 070 h *= 16777619; 071 h ^= data[i] >>> 8; 072 h *= 16777619; 073 } 074 return h; 075 } 076 public static int hash(int[] data) 077 { 078 if(data == null) 079 return 0; 080 int h = -2128831035, len = data.length; 081 for (int i = 0; i < len; i++) { 082 h ^= data[i] & 0xff; 083 h *= 16777619; 084 h ^= (data[i] >>> 8) & 0xff; 085 h *= 16777619; 086 h ^= (data[i] >>> 16) & 0xff; 087 h *= 16777619; 088 h ^= data[i] >>> 24; 089 h *= 16777619; 090 } 091 return h; 092 } 093 public static int hash(long[] data) 094 { 095 if(data == null) 096 return 0; 097 int h = -2128831035, len = data.length; 098 for (int i = 0; i < len; i++) { 099 h ^= (int)(data[i] & 0xff); 100 h *= 16777619; 101 h ^= (int)((data[i] >>> 8) & 0xff); 102 h *= 16777619; 103 h ^= (int)((data[i] >>> 16) & 0xff); 104 h *= 16777619; 105 h ^= (int)((data[i] >>> 24) & 0xff); 106 h *= 16777619; 107 h ^= (int)((data[i] >>> 32) & 0xff); 108 h *= 16777619; 109 h ^= (int)((data[i] >>> 40) & 0xff); 110 h *= 16777619; 111 h ^= (int)((data[i] >>> 48) & 0xff); 112 h *= 16777619; 113 h ^= (int)(data[i] >>> 56); 114 h *= 16777619; 115 } 116 return h; 117 } 118 119 public static int hash(float[] data) 120 { 121 if(data == null) 122 return 0; 123 int h = -2128831035, len = data.length, t; 124 for (int i = 0; i < len; i++) { 125 t = Float.floatToIntBits(data[i]); 126 h ^= t & 0xff; 127 h *= 16777619; 128 h ^= (t >>> 8) & 0xff; 129 h *= 16777619; 130 h ^= (t >>> 16) & 0xff; 131 h *= 16777619; 132 h ^= t >>> 24; 133 h *= 16777619; 134 } 135 return h; 136 } 137 public static int hash(double[] data) 138 { 139 if(data == null) 140 return 0; 141 int h = -2128831035, len = data.length; 142 long t; 143 for (int i = 0; i < len; i++) { 144 t = Double.doubleToLongBits(data[i]); 145 h ^= (int)(t & 0xff); 146 h *= 16777619; 147 h ^= (int)((t >>> 8) & 0xff); 148 h *= 16777619; 149 h ^= (int)((t >>> 16) & 0xff); 150 h *= 16777619; 151 h ^= (int)((t >>> 24) & 0xff); 152 h *= 16777619; 153 h ^= (int)((t >>> 32) & 0xff); 154 h *= 16777619; 155 h ^= (int)((t >>> 40) & 0xff); 156 h *= 16777619; 157 h ^= (int)((t >>> 48) & 0xff); 158 h *= 16777619; 159 h ^= (int)(t >>> 56); 160 h *= 16777619; 161 } 162 return h; 163 } 164 public static int hash(String s) 165 { 166 if(s == null) 167 return 0; 168 return hash(s.toCharArray()); 169 } 170 171 public static int hash(String[] data) 172 { 173 if(data == null) 174 return 0; 175 int h = -2128831035, len = data.length, t; 176 for (int i = 0; i < len; i++) { 177 t = hash(data[i]); 178 h ^= t & 0xff; 179 h *= 16777619; 180 h ^= (t >>> 8) & 0xff; 181 h *= 16777619; 182 h ^= (t >>> 16) & 0xff; 183 h *= 16777619; 184 h ^= t >>> 24; 185 h *= 16777619; 186 } 187 return h; 188 } 189 190 public static int hash(String[]... data) 191 { 192 if(data == null) 193 return 0; 194 int h = -2128831035, len = data.length, t; 195 for (int i = 0; i < len; i++) { 196 t = hash(data[i]); 197 h ^= t & 0xff; 198 h *= 16777619; 199 h ^= (t >>> 8) & 0xff; 200 h *= 16777619; 201 h ^= (t >>> 16) & 0xff; 202 h *= 16777619; 203 h ^= t >>> 24; 204 h *= 16777619; 205 } 206 return h; 207 } 208 public static long hash64(boolean[] data) 209 { 210 if(data == null) 211 return 0; 212 long h = -3750763034362895579L, len = data.length, o = 0; 213 for (int i = 0; i < len; i++) { 214 o |= (data[i]) ? (1 << (i % 8)) : 0; 215 if(i % 8 == 7 || i == len - 1) { 216 h ^= o; 217 h *= 1099511628211L; 218 o = 0; 219 } 220 } 221 return h; 222 } 223 public static long hash64(byte[] data) 224 { 225 if(data == null) 226 return 0; 227 long h = -3750763034362895579L, len = data.length; 228 for (int i = 0; i < len; i++) { 229 h ^= data[i]; 230 h *= 1099511628211L; 231 } 232 return h; 233 } 234 public static long hash64(char[] data) 235 { 236 if(data == null) 237 return 0; 238 long h = -3750763034362895579L, len = data.length; 239 for (int i = 0; i < len; i++) { 240 h ^= data[i] & 0xff; 241 h *= 1099511628211L; 242 h ^= data[i] >>> 8; 243 h *= 1099511628211L; 244 } 245 return h; 246 } 247 public static long hash64(short[] data) 248 { 249 if(data == null) 250 return 0; 251 long h = -3750763034362895579L, len = data.length; 252 for (int i = 0; i < len; i++) { 253 h ^= data[i] & 0xff; 254 h *= 1099511628211L; 255 h ^= data[i] >>> 8; 256 h *= 1099511628211L; 257 } 258 return h; 259 } 260 public static long hash64(int[] data) 261 { 262 if(data == null) 263 return 0; 264 long h = -3750763034362895579L, len = data.length; 265 for (int i = 0; i < len; i++) { 266 h ^= data[i] & 0xff; 267 h *= 1099511628211L; 268 h ^= (data[i] >>> 8) & 0xff; 269 h *= 1099511628211L; 270 h ^= (data[i] >>> 16) & 0xff; 271 h *= 1099511628211L; 272 h ^= data[i] >>> 24; 273 h *= 1099511628211L; 274 } 275 return h; 276 } 277 public static long hash64(long[] data) 278 { 279 if(data == null) 280 return 0; 281 long h = -3750763034362895579L, len = data.length; 282 for (int i = 0; i < len; i++) { 283 h ^= (data[i] & 0xff); 284 h *= 1099511628211L; 285 h ^= ((data[i] >>> 8) & 0xff); 286 h *= 1099511628211L; 287 h ^= ((data[i] >>> 16) & 0xff); 288 h *= 1099511628211L; 289 h ^= ((data[i] >>> 24) & 0xff); 290 h *= 1099511628211L; 291 h ^= ((data[i] >>> 32) & 0xff); 292 h *= 1099511628211L; 293 h ^= ((data[i] >>> 40) & 0xff); 294 h *= 1099511628211L; 295 h ^= ((data[i] >>> 48) & 0xff); 296 h *= 1099511628211L; 297 h ^= (data[i] >>> 56); 298 h *= 1099511628211L; 299 } 300 return h; 301 } 302 public static long hash64(float[] data) 303 { 304 if(data == null) 305 return 0; 306 long h = -3750763034362895579L, len = data.length, t; 307 for (int i = 0; i < len; i++) { 308 t = Float.floatToIntBits(data[i]); 309 h ^= t & 0xff; 310 h *= 1099511628211L; 311 h ^= (t >>> 8) & 0xff; 312 h *= 1099511628211L; 313 h ^= (t >>> 16) & 0xff; 314 h *= 1099511628211L; 315 h ^= t >>> 24; 316 h *= 1099511628211L; 317 } 318 return h; 319 } 320 public static long hash64(double[] data) 321 { 322 if(data == null) 323 return 0; 324 long h = -3750763034362895579L, len = data.length, t; 325 for (int i = 0; i < len; i++) { 326 t = Double.doubleToLongBits(data[i]); 327 h ^= (t & 0xff); 328 h *= 1099511628211L; 329 h ^= ((t >>> 8) & 0xff); 330 h *= 1099511628211L; 331 h ^= ((t >>> 16) & 0xff); 332 h *= 1099511628211L; 333 h ^= ((t >>> 24) & 0xff); 334 h *= 1099511628211L; 335 h ^= ((t >>> 32) & 0xff); 336 h *= 1099511628211L; 337 h ^= ((t >>> 40) & 0xff); 338 h *= 1099511628211L; 339 h ^= ((t >>> 48) & 0xff); 340 h *= 1099511628211L; 341 h ^= (t >>> 56); 342 h *= 1099511628211L; 343 } 344 return h; 345 } 346 public static long hash64(String s) 347 { 348 if(s == null) 349 return 0; 350 return hash64(s.toCharArray()); 351 } 352 public static long hash64(String[] data) 353 { 354 if(data == null) 355 return 0; 356 long h = -3750763034362895579L, len = data.length, t; 357 for (int i = 0; i < len; i++) { 358 t = hash64(data[i]); 359 h ^= (t & 0xff); 360 h *= 1099511628211L; 361 h ^= ((t >>> 8) & 0xff); 362 h *= 1099511628211L; 363 h ^= ((t >>> 16) & 0xff); 364 h *= 1099511628211L; 365 h ^= ((t >>> 24) & 0xff); 366 h *= 1099511628211L; 367 h ^= ((t >>> 32) & 0xff); 368 h *= 1099511628211L; 369 h ^= ((t >>> 40) & 0xff); 370 h *= 1099511628211L; 371 h ^= ((t >>> 48) & 0xff); 372 h *= 1099511628211L; 373 h ^= (t >>> 56); 374 h *= 1099511628211L; 375 } 376 return h; 377 } 378 public static long hash64(Iterable<String> data) 379 { 380 if(data == null) 381 return 0; 382 long h = -3750763034362895579L, t; 383 for (String datum : data) { 384 t = hash64(datum); 385 h ^= (t & 0xff); 386 h *= 1099511628211L; 387 h ^= ((t >>> 8) & 0xff); 388 h *= 1099511628211L; 389 h ^= ((t >>> 16) & 0xff); 390 h *= 1099511628211L; 391 h ^= ((t >>> 24) & 0xff); 392 h *= 1099511628211L; 393 h ^= ((t >>> 32) & 0xff); 394 h *= 1099511628211L; 395 h ^= ((t >>> 40) & 0xff); 396 h *= 1099511628211L; 397 h ^= ((t >>> 48) & 0xff); 398 h *= 1099511628211L; 399 h ^= (t >>> 56); 400 h *= 1099511628211L; 401 } 402 return h; 403 } 404 public static long hash64(String[]... data) 405 { 406 if(data == null) 407 return 0; 408 long h = -3750763034362895579L, len = data.length, t; 409 for (int i = 0; i < len; i++) { 410 t = hash64(data[i]); 411 h ^= (t & 0xff); 412 h *= 1099511628211L; 413 h ^= ((t >>> 8) & 0xff); 414 h *= 1099511628211L; 415 h ^= ((t >>> 16) & 0xff); 416 h *= 1099511628211L; 417 h ^= ((t >>> 24) & 0xff); 418 h *= 1099511628211L; 419 h ^= ((t >>> 32) & 0xff); 420 h *= 1099511628211L; 421 h ^= ((t >>> 40) & 0xff); 422 h *= 1099511628211L; 423 h ^= ((t >>> 48) & 0xff); 424 h *= 1099511628211L; 425 h ^= (t >>> 56); 426 h *= 1099511628211L; 427 } 428 return h; 429 } 430 431 /** 432 * Hashes only a subsection of the given data, starting at start (inclusive) and ending before end (exclusive). 433 * @param data the char array to hash 434 * @param start the start of the section to hash (inclusive) 435 * @param end the end of the section to hash (exclusive) 436 * @return 437 */ 438 public static long hash64(char[] data, int start, int end) 439 { 440 if(data == null) 441 return 0; 442 long h = -3750763034362895579L, len = data.length; 443 start %= len; 444 end %= len; 445 if(end <= start || start < 0 || end <= 0) 446 return 0; 447 for (int i = start; i < end; i++) { 448 h ^= data[i] & 0xff; 449 h *= 1099511628211L; 450 h ^= data[i] >>> 8; 451 h *= 1099511628211L; 452 } 453 return h; 454 } 455}