Code: Select all
'' Some defs needed for the FNV-1a hashing algorithm
'' Hash Size Prime Offset
'' =========== =========================== =================================
'' 32-bit 16777619 2166136261
'' 64-bit 1099511628211 14695981039346656037
'' 128-bit 309485009821345068724781371 144066263297769815596495629667062367629
#define HASHSIZE_32
'#define HASHSIZE_64 '' Use 64-bit hash
#ifdef HASHSIZE_32
const as uinteger FNV_offset_basis = 2166136261
const as uinteger FNV_prime = 16777619
function fnv1a_hash( byref s as const string ) as ulong
dim as ulong hash = FNV_offset_basis
for i as uinteger = 0 to len( s ) - 1
hash = hash xor s[ i ]
hash = hash * FNV_prime
next
return( hash )
end function
#endif
#ifdef HASHSIZE_64
const as ulongint FNV_offset_basis = 14695981039346656037ull
const as ulongint FNV_prime = 1099511628211ull
function fnv1a_hash( byref s as const string ) as ulongint
dim as ulongint hash = FNV_offset_basis
for i as integer = 0 to len( s ) - 1
hash = hash xor s[ i ]
hash = hash * FNV_prime
next
return( hash )
end function
#endif
function rot_hash( byref key as const string ) as ulong
dim as ulong hash
for i as uinteger = 0 to len( key ) - 1
hash = ( hash shl 4 ) xor ( hash shr 28 ) xor key[ i ]
next
return( hash )
end function
function djb_hash( byref key as const string ) as ulong
dim as ulong hash
for i as uinteger = 0 to len( key ) - 1
hash = 33 * hash xor key[ i ]
next
return( hash )
end function
function sax_hash( byref key as const string ) as ulong
dim as ulong hash
for i as uinteger = 0 to len( key ) - 1
hash xor= ( hash shl 5 ) + ( hash shr 2 ) + key[ i ]
next
return( hash )
end function
function fnv_hash( byref key as const string ) as ulong
dim as ulong hash = 2166136261
for i as uinteger = 0 to len( key ) - 1
hash = ( hash * 16777619 ) xor key[ i ]
next
return( hash )
end function
function oat_hash( byref key as const string ) as ulong
dim as ulong hash
for i as uinteger = 0 to len( key ) - 1
hash += key[ i ]
hash += ( hash shl 10 )
hash xor= ( hash shr 6 )
next
hash += ( hash shl 3 )
hash xor= ( hash shr 11 )
hash += ( hash shl 15 )
return( hash )
end function
randomize( timer() )
'' Lookup table needed for JSW hash
dim shared as ulong iTable( 0 to 255 )
for i as uinteger = 0 to 255
iTable( i ) = rnd() * 22545435435
next
function jsw_hash( byref key as const string ) as ulong
dim as ulong hash = 16777551
for i as uinteger = 0 to len( key ) - 1
hash = ( hash shl 1 or hash shr 31 ) xor iTable( key[ i ] )
next
return( hash )
end function
function elf_hash( byref key as const string ) as ulong
dim as ulong hash, g
for i as uinteger = 0 to len( key ) - 1
hash = ( hash shl 4 ) + key[ i ]
g = hash and &hf0000000L
if( g <> 0 ) then
hash xor= g shr 24
end if
hash and= not g
next
return( hash )
end function
#macro mix( a, b, c )
: a -= b: a -= c: a xor= ( c shr 13 ):
b -= c: b -= a: b xor= ( a shl 8 ):
c -= a: c -= b: c xor= ( b shr 13 ):
a -= b: a -= c: a xor= ( c shr 12 ):
b -= c: b -= a: b xor= ( a shl 16 ):
c -= a: c -= b: c xor= ( b shr 5 ):
a -= b: a -= c: a xor= ( c shr 3 ):
b -= c: b -= a: b xor= ( a shl 10 ):
: c -= a: c -= b: c xor= ( b shr 15 )
#endmacro
function jen_hash( byref k as const string ) as ulong
dim as ulong a, b
dim as ulong c = 7
dim as uinteger _len = len( k )
a = &h9e3779b9
b = &h9e3779b9
dim as uinteger _pos = 0
do while( _len >= 12 )
a += k[ _pos ] + ( k[ _pos + 1 ] shl 8 ) + ( k[ _pos + 2 ] shl 16 ) + ( k[ _pos + 3 ] shl 24 )
b += k[ _pos + 4 ] + ( k[ _pos + 5 ] shl 8 ) + ( k[ _pos + 6 ] shl 16 ) + ( k[ _pos + 7 ] shl 24 )
c += k[ _pos + 8 ] + ( k[ _pos + 9 ] shl 8 ) + ( k[ _pos + 10 ] shl 16 ) + ( k[ _pos + 11 ] shl 24 )
mix( a, b, c )
_pos += 12
_len -= 12
loop
c += len( k )
select case as const( _len )
case 11
c += k[ 10 ] shl 24
case 10
c += k[ 9 ] shl 16
case 9
c += k[ 8 ] shl 8
case 8
b += k[ 7 ] shl 24
case 7
b += k[ 7 ] shl 16
case 6
b += k[ 5 ] shl 8
case 5
b += k[ 4 ]
case 4
a += k[ 3 ] shl 24
case 3
a += k[ 2 ] shl 16
case 2
a += k[ 1 ] shl 8
case 1
a += k[ 0 ]
end select
mix( a, b, c )
return( c )
end function
function add_hash( byref key as const string ) as ulong
dim as ulong hash
for i as uinteger = 0 to len( key ) - 1
hash += key[ i ]
next
return( hash )
end function
function xor_hash( byref key as const string ) as ulong
dim as ulong hash
for i as uinteger = 0 to len( key ) - 1
hash xor= key[ i ]
next
return( hash )
end function
dim hashFuncs( ... ) as function( byref as const string ) as ulong = { _
@add_hash, @xor_hash , @rot_hash, @djb_hash, @sax_hash, @fnv_hash, _
@fnv1a_hash, @oat_hash, @jsw_hash, @elf_hash, @jen_hash }
dim as string hashFuncNames( ... ) = { "Addition hash", "XOR hash", "Rotating hash", _
"Bernstein hash", "Shift-Add-XOR hash", "FNV hash", "FNV1a hash", "One-at-a-time hash", _
"JSW hash", "ELF hash", "Jenkins hash" }
'' select the hashing function
dim hashFunc as function( byref as const string ) as ulong
dim as integer mapSize = 8192
dim as integer n = mapSize * 0.89 '' load factor
dim as integer map( 0 to mapSize - 1 ) '' a simple array to map the hash to
dim as uinteger hash '' the generated hash
dim as uinteger collisions '' total number of collisions
dim as uinteger maxSlot = 0 '' maximum collisions in that bucket
dim as integer textLen = 40 '' the len of the randomly generated text to be hashed
dim as string text = space( textLen )
dim as double t, sum
dim as uinteger count = 10000000
for k as integer = 0 to ubound( hashFuncs )
hashFunc = hashFuncs( k )
? "--- "; hashFuncNames( k ); " ---"
for i as integer = 0 to n - 1
'' create a random string to hash
for j as integer = 0 to textLen - 1
text[ j ] = rnd() * 255
next
hash = hashFunc( text ) mod mapSize
if( map( hash ) > 0 ) then
collisions += 1
end if
map( hash ) += 1
if( map( hash ) > maxSlot ) then
maxSlot = map( hash )
end if
next
for i as integer = 0 to count - 1
t = timer()
hash = hashFunc( space( textLen ) )
t = timer() - t
sum += t
next
? "Hash map size: "; mapSize
? "Hash string length: "; textLen
? "Load factor: "; ( n / mapSize ) * 100
?
? "Number of items: "; n
? "Number of collisions (less is better): "; collisions
? "Max number of items in a single slot (less is better): "; maxSlot
? "Ratio (more is better): "; n / collisions
? "Speed factor (more is better): "; int( 1 / ( sum / count ) )
?
for i as integer = 0 to mapSize - 1
map( i ) = 0
next
maxSlot = 0
collisions = 0
sum = 0.0
next
? "Done. Press a key to end."
sleep()
EDIT: 5/9/2018 - Changed the hashing functions to return the expected values in 64-bit also. Thanks to dodicat for pointing this out.