Perfect hashing question

[Gerd Isenberg]

Minimal perfect hashing maps a set of N keys to an array containing N distinct values. A bijective one to one mapping, like in the De Bruijn multiplication to map the least significant one bit to the bit index in a 0..63 range.

In kindergarten bitboards it is about to map 64 different occupied sets (inner six bits of a line) to up to 12 different attack sets of a square. The hashing is perfect, but requires 64 entries per square for {7,6,10,12,12,10,6,7} different values. It is therefor not minimal perfect, only perfect. On the other hand the array has no gaps, but same values (attack sets) occur on different indices.

Is there a distinction in the terminology concerning perfect hashing, whether there are gaps inside the lookup but otherwise unique different values versus no gaps but multiple same values?

And what kind of perfect hashing does magic bitboards apply, where we may have gaps due to constructive collisions, also compressing N occupied bits to a N-1 bit index range for some squares.

How can one differantiate these three kinds of none minimal but perfect hashing? Bijective, surjective and sujective mapping with constructive collisions for instance?

Thanks,
Gerd


Some code samples four different kinds of perfect hashing:

1. Minimal Perfect Hashing Sample

Code: Select all

/**
 * bitScanForward
 * @author Charles E. Leiserson
 *         Harald Prokop
 *         Keith H. Randall
 * "Using de Bruijn Sequences to Index a 1 in a Computer Word"
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   static const int lookup64[64] = {
      63,  0, 58,  1, 59, 47, 53,  2,
      60, 39, 48, 27, 54, 33, 42,  3,
      61, 51, 37, 40, 49, 18, 28, 20,
      55, 30, 34, 11, 43, 14, 22,  4,
      62, 57, 46, 52, 38, 26, 32, 41,
      50, 36, 17, 19, 29, 10, 13, 21,
      56, 45, 25, 31, 35, 16,  9, 12,
      44, 24, 15,  8, 23,  7,  6,  5
   };
   return lookup64[((bb & -bb) * 0x07EDD5E59A4E28C2) >> 58];
}

2. Perfect Hashing, bijective, but not exactly minimal

Code: Select all

/**
 * trailingZeroCount
 * @param bb bitboard to scan
 * @return index (0..63) of least significant one bit, 64 if bb is zero
 */
int trailingZeroCount(U64 bb) {
   static const int lookup67[67] = {
      64,  0,  1, 39,  2, 15, 40, 23,
       3, 12, 16, 59, 41, 19, 24, 54,
       4, -1, 13, 10, 17, 62, 60, 28,
      42, 30, 20, 51, 25, 44, 55, 47,
       5, 32, -1, 38, 14, 22, 11, 58,
      18, 53, 63,  9, 61, 27, 29, 50,
      43, 46, 31, 37, 21, 57, 52,  8,
      26, 49, 45, 36, 56,  7, 48, 35,
       6, 34, 33
   };
   return lookup67[(bb & -bb) % 67];
}

3. None Minimal Perfect Hashing without gaps, surjective

Code: Select all

// Kindergarten Bitboards
U64 fillUpAttacks[8][64];  // 4 KByte, might be shared by diagonals as well
 
U64 fileAttacks(U64 occ, int sq) {
   occ = (fileMaskEx[sq] & occ) * 0x0202020202020202 >> 58;
   return fileMaskEx[sq] & fillUpAttacks[sq&7][occ];
}

4. None Minimal Perfect Hashing likely with gaps, surjective

Code: Select all

// Grant Osborne's dense Magic mix

U64 aFileAttacks[4*32+4*16]; // 1.5KByte
U64 aPtrFileAttacks[8]; // points to appropriate aFileAttacks
U64 rookMagic[8];
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   unsigned int file = sq &  7;
   unsigned int rank = sq >> 3;
 
   occ =  0x0001010101010100 & (occ >> file);
   occ = (rookMagic[rank] * occ) >> (rookMagic[rank] >> 58);  // four&five bit index
   return *(aPtrFileAttacks[rank] + occ) << file;
}

[Gerd Isenberg]

3. None Minimal Perfect Hashing without gaps, surjective

Code: Select all

// Kindergarten Bitboards
U64 fillUpAttacks[8][64];  // 4 KByte, might be shared by diagonals as well
 
U64 fileAttacks(U64 occ, int sq) {
   occ = (fileMaskEx[sq] & occ) * 0x0202020202020202 >> 58;
   return fileMaskEx[sq] & fillUpAttacks[sq&7][occ];
}

oups, wrong replacement, above routine should be rankAttacks or diagonalAttacks, sorry:

Code: Select all

// Kindergarten Bitboards
U64 fillUpAttacks[8][64];  // 4 KByte
 
U64 diagonalAttacks(U64 occ, int sq) {
   occ = (diagonalMaskEx[sq] & occ) * 0x0202020202020202 >> 58;
   return diagonalMaskEx[sq] & fillUpAttacks[sq&7][occ];
}

Wikipedia is quite ambiguous:
http://en.wikipedia.org/wiki/Hash_function

Injective and perfect hashing
The ideal hashing function should be injective — that is, it should map each valid input to a different hash value. Such a function would directly locate the desired entry in a hash table, without any additional search.

An injective hash function whose range is all integers between 0 and n−1, where n is the number of valid inputs, is said to be perfect. Besides providing single-step lookup, a perfect hash function also results in a compact hash table, without any vacant slots.

http://en.wikipedia.org/wiki/Hash_table

Perfect hashing

If all of the keys that will be used are known ahead of time, and there are no more keys than can fit the hash table, perfect hashing can be used to create a perfect hash table, in which there will be no collisions. If minimal perfect hashing is used, every location in the hash table can be used as well.

http://en.wikipedia.org/wiki/Perfect_ha ... tion[quote]
A minimal perfect hash function is a perfect hash function that maps n keys to n consecutive integers -- usually [0..n-1] or [1..n]. A more formal way of expressing this is: Let j and k be elements of some set K. F is a minimal perfect hash function iff F(j) =F(k) implies j=k and there exists an integer a such that the range of F is a..a+|K|-1.

A minimal perfect hash function F is order-preserving if for any keys j and k, j<k implies F(j)<F(k).[/quote]