source: trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashUtil.cs @ 16218

Last change on this file since 16218 was 16218, checked in by bburlacu, 2 years ago

#2950: Initial commit of hashing functionality as well as simplification rules for symbolic expression trees. As this is still in development the public api is not yet established (all methods public for now).

File size: 3.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Security.Cryptography;
24
25namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
26  public static class HashUtil {
27    // This class contains some hash functions adapted from http://partow.net/programming/hashfunctions/index.html#AvailableHashFunctions
28
29    // A simple hash function from Robert Sedgwicks Algorithms in C book.I've added some simple optimizations to the algorithm in order to speed up its hashing process.
30    public static int RSHash(int[] input) {
31      const int b = 378551;
32      int a = 63689;
33      int hash = 0;
34
35      foreach (var v in input) {
36        hash = (hash * a) + v;
37        a *= b;
38      }
39      return hash;
40    }
41
42    // A bitwise hash function written by Justin Sobel
43    public static int JSHash(int[] input) {
44      int hash = 1315423911;
45      for (int i = 0; i < input.Length; ++i)
46        hash ^= (hash << 5) + input[i] + (hash >> 2);
47      return hash;
48    }
49
50    // This hash function comes from Brian Kernighan and Dennis Ritchie's book "The C Programming Language". It is a simple hash function using a strange set of possible seeds which all constitute a pattern of 31....31...31 etc, it seems to be very similar to the DJB hash function.
51    public static int BKDRHash(int[] input) {
52      const int seed = 131;
53      int hash = 0;
54      foreach (var v in input) {
55        hash = (hash * seed) + v;
56      }
57      return hash;
58    }
59
60    // This is the algorithm of choice which is used in the open source SDBM project. The hash function seems to have a good over-all distribution for many different data sets. It seems to work well in situations where there is a high variance in the MSBs of the elements in a data set.
61    public static int SDBMHash(int[] input) {
62      int hash = 0;
63      foreach (var v in input) {
64        hash = v + (hash << 6) + (hash << 16) - hash;
65      }
66      return hash;
67    }
68
69    // An algorithm produced by Professor Daniel J. Bernstein and shown first to the world on the usenet newsgroup comp.lang.c. It is one of the most efficient hash functions ever published.
70    public static int DJBHash(int[] input) {
71      int hash = 5381;
72      foreach (var v in input) {
73        hash = (hash << 5) + hash + v;
74      }
75      return hash;
76    }
77
78    // An algorithm proposed by Donald E.Knuth in The Art Of Computer Programming Volume 3, under the topic of sorting and search chapter 6.4.
79    public static int DEKHash(int[] input) {
80      int hash = input.Length;
81      foreach (var v in input) {
82        hash = (hash << 5) ^ (hash >> 27) ^ v;
83      }
84      return hash;
85    }
86
87    public static int CryptoHash(HashAlgorithm ha, int[] input) {
88      return BitConverter.ToInt32(ha.ComputeHash(input.ToByteArray()), 0);
89    }
90
91    public static byte[] ToByteArray(this int[] input) {
92      const int size = sizeof(int);
93      var bytes = new byte[input.Length * sizeof(int)];
94      for (int i = 0; i < input.Length; ++i) {
95        Array.Copy(BitConverter.GetBytes(bytes[i]), 0, bytes, i * size, size);
96      }
97      return bytes;
98    }
99  }
100}
Note: See TracBrowser for help on using the repository browser.