爲可變大小的布爾數組

Question

散列算法，我有一些布爾數組它們的大小不是恆定的，而我需要一個強大和快速的散列算法給散列衝突對他們的最小機會。

我自己的想法是計算每個布爾陣列的整數值，但例如這些2個陣列將得到的3相同的哈希：
[0,1，1]和[1,1]

我想在計算整數值後乘以數組的大小，但這個想法也很糟糕，因爲哈希碰撞的可能性很高。

有沒有人有一個好主意？

Answer 1

在陣列的開始處插入一個前哨true元件，然後解釋該陣列爲二進制數。對於少於32個元素的數組，這是一個完美哈希（無衝突）。對於更大的陣列，我建議以大於2的毛數進行算術模運算。

實例：

Array  | Binary | Decimal 
------------+--------+--------- 
[ 0, 1, 1 ] | 01011 |  11 
[ 1, 1 ] | 00111 |  7 

這是相同的解釋數組作爲二進制數並取逐位OR與1 << n，其中n是陣列的尺寸。

實現：

int hash(int[] array) 
{ 
    int h = (1 << array.length); 
    for (int i = 0; i < array.length; i++) 
    { 
     h = h | (array[i] << (array.length - i - 1)); 
    } 
    return h; 
} 

Answer 2

一種簡單高效的哈希碼被替換0和1具有素數，並執行通常的移累加器循環：

hash=0 
for (bits in list): 
    hash = hash*31 + 2*bit + 3 
return hash 

這裏0被視爲3和1被視爲5，從而使前導零不會被忽略。乘以31確保順序很重要。然而，這不是一個強加密的方法：給定一個短序列的哈希碼是一個簡單的算術來反轉它。

Answer 3

我的想法：

方法1：

1. 計算第一2n素數，其中n是數組的長度。

2. 讓散列= 1

3. 對於i = 0至n：如果位在i位置爲1，由第2i和2i + 1 ST素相乘hash。如果它是0，則只乘以2i。

方法2：

1. 對待二進制數組作爲三元。位是0 =>三位數字是0;位是1 =>三位數字是1;位不存在=>三位數字是2（這是因爲數組有最大可能的長度）。

2. 計算使用這種取代的三進制數 - 結果將是唯一的。

---

下面是示出這些算法在C++和其中用於長度爲0 ... 18的每個布爾數組生成哈希值的測試程序的執行一些代碼。我使用C++ 11類std::unordered_map，以便每個散列都是唯一的。因此，如果我們沒有任何重複（即如果散列函數是完美的），我們應該得到的一套2^19 - 1元素，which we do（我不得不整數更改爲unsigned long long上IDEone，否則哈希並不是完美的 - 我懷疑這與32與64位架構做）：

#include <unordered_set> 
#include <iostream> 

#define MAX_LEN 18 

unsigned long prime_hash(const unsigned int *arr, size_t len) 
{ 
    /* first 2 * MAX_LEN primes */ 
    static const unsigned long p[2 * MAX_LEN] = { 
      2, 3, 5, 7, 11, 13, 17, 19, 23, 
     29, 31, 37, 41, 43, 47, 53, 59, 61, 
     67, 71, 73, 79, 83, 89, 97, 101, 103, 
     107, 109, 113, 127, 131, 137, 139, 149, 151 
    }; 

    unsigned long h = 1; 
    for (size_t i = 0; i < len; i++) 
     h *= p[2 * i] * (arr[i] ? p[2 * i + 1] : 1); 

    return h; 
} 

unsigned long ternary_hash(const unsigned int *arr, size_t len) 
{ 
    static const unsigned long p3[MAX_LEN] = { 
       1,   3,   9,   27, 
       81,   243,   729,   2187,   
      6561,  19683,  59049,  177147, 
      531441,  1594323,  4782969,  14348907, 
     43046721, 129140163 
    }; 

    unsigned long h = 0; 
    for (size_t i = 0; i < len; i++) 
     if (arr[i]) 
      h += p3[i]; 

    for (size_t i = len; i < MAX_LEN; i++) 
     h += 2 * p3[i]; 

    return h; 
} 

void int2barr(unsigned int *dst, unsigned long n, size_t len) 
{ 
    for (size_t i = 0; i < len; i++) { 
     dst[i] = n & 1; 
     n >>= 1; 
    } 
} 

int main() 
{ 
    std::unordered_set<unsigned long> phashes, thashes; 


    /* generate all possible bool-arrays from length 0 to length 18 */ 

    /* first, we checksum the only 0-element array */ 
    phashes.insert(prime_hash(NULL, 0)); 
    thashes.insert(ternary_hash(NULL, 0)); 

    /* then we checksum the arrays of length 1...18 */ 
    for (size_t len = 1; len <= MAX_LEN; len++) { 
     unsigned int bits[len]; 
     for (unsigned long i = 0; i < (1 << len); i++) { 
      int2barr(bits, i, len); 

      phashes.insert(prime_hash(bits, len)); 
      thashes.insert(ternary_hash(bits, len)); 
     } 
    } 

    std::cout << "prime hashes: " << phashes.size() << std::endl; 
    std::cout << "ternary hashes: " << thashes.size() << std::endl; 

    return 0; 
}