User Defined Functions » StringHash » Analysis

*This is an analysis of bit transmutation and distribution patterns of the StringHash function, mainly in comparison to the "Java hash", a variant of Dan Bernstein's old "33" hash posted long ago in the comp.lang.c newsgroup.*

## Contents

- 1 Reference code
- 2 Tests performed and result analysis
- 2.1 Performance test
- 2.2 Bit distribution test
- 2.3 Collision frequency test
- 2.4 Bit transmutation test
- 2.5 Collision finding test
- 2.5.1 ASCII codes 64-89 (upper case A-Z), 3 bytes
- 2.5.2 ASCII codes 64-89 (upper case A-Z), 4 bytes
- 2.5.3 ASCII codes 32-127 (all printable), 2 bytes
- 2.5.4 ASCII codes 32-127 (all printable), 3 bytes
- 2.5.5 ASCII codes 32-127 (all printable), 3 bytes, with prefix
- 2.5.6 ASCII codes 32-127 (all printable), 3 bytes, with suffix
- 2.5.7 ASCII codes 64-82 (A-S), 5 bytes
- 2.5.8 Result analysis

- 3 Result summary
- 4 Applicability to other languages
- 5 Appendix: Lua hash analysis code

# Reference code[edit | edit source]

## Java hash[edit | edit source]

for i = 1, len do counter = (counter*31) + string.byte(text, i) counter = mod(counter, 4294967296); -- 2^32 end; return mod(counter, 4294967296); -- 2^32

This is the function implemented in the Java String.hashCode library call.

The multiplication by 31 basically translates to "new = old<<5 - old", i.e. you never completely lose data from earlier bytes as you would by only shifting data up. The relation to Bernstein's original "33" function is pretty clear; it simply uses 33 instead of 31.

The mod() is necessary in Lua, otherwise the value turns floating-point and you lose precision after ~10 characters; Lua, at least under x86, uses 64-bit ("double-precision") IEEE 764 floats, which have a mantissa of 52 bits.

This function would be slightly better with a prime modulus, but 2^32 is chosen as a modulus to emulate 32-bit integer math as used in the Java SDK.

## StringHash[edit | edit source]

for i = 1, len, 3 do counter = mod(counter*8161, 4294967279) + -- 2^32 - 17: Prime! (string.byte(text,i)*16776193) + ((string.byte(text,i+1) or (len-i+256))*8372226) + ((string.byte(text,i+2) or (len-i+256))*3932164); end; return mod(counter, 4294967291); -- 2^32 - 5: Prime (and different from the prime in the loop)

This string hash is ~30% faster than the Java hash due to working with 3 characters at a time; the modulus call is fairly expensive compared to the other operations.

The multiplications are all chosen to affect 3 areas of the accumulator at a time:

8161 = 8192 - 32 + 1 : 2<<13, 2<< 5, 2<<0 16776193 = 16777216 - 1024 + 1 : 2<<24, 2<<10, 2<<0 8372226 = 8388608 - 16384 + 2 : 2<<23, 2<<14, 2<<5 3932164 = 4194304 - 262144 + 4 : 2<<22, 2<<18, 2<<10

It is tempting to make the first multiplication much larger, but beware that the result of (4294967279+(256*29080583))*8161 must fit in a 52-bit mantissa without losing precision. The result is currently a 48-bit number so meets that contraint.

# Tests performed and result analysis[edit | edit source]

Below is an array of tests that both algorithms have been submitted to. For a hash analysis, these tests are fairly basic and the result analysis is somewhat unscientific, but they will do to illustrate the difference between the Java hash and StringHash, which is all this document set out to do.

- Performance test - raw measurement of relative hash speed
- Bit distribution test - how often is each bit of the 32-bit output used?
- Collision frequency test - compare observed collision statistics to expected numbers
- Bit transmutation test - determine how many bits are changed as a result of 1 input bit changing
- Collision finding test - find and count collisions for exhaustive input sets

## Performance test[edit | edit source]

This test simply hashes the string "abcdefghijklmnopqrstuvwxyz" in a loop 20 000 times and clocks the start and stop time. The loop is included in the resulting time.

- Java hash execution time: 1.719s
- StringHash execution time: 1.313s

### Result analysis[edit | edit source]

StringHash is slightly faster than the Java hash; likely not enough to matter, but certainly enough that the perceived "increased size" of StringHash can be discounted as an argument against it - it's actually faster!

The reason is of course that the math.mod() call is relatively expensive compared to extracting characters from a string and performing multiplications. StringHash does 3 extract + multiply per mod() call. The Java hash in its standard implementation has to do one mod() call per character.

On the testing computer, a P4 at ~3Ghz, StringHash hashes in the neighborhood of half a megabyte per second; certainly not bad for a scripted language using only standard math library operations!

## Bit distribution test[edit | edit source]

This test measures how many times each bit is 1 for a given set of inputs. The target value is for each bit to be 1 50% of the time, and 0 50% of the time, though there will obviously be deviations from this, which are expected and accepted, up to a certain point.

In this test, we feed each hash the same set of inputs: 10000 random strings consisting of "aaaaaaaaa" followed by 15 random bytes.

The results show the absolute difference between 50% and the result, i.e. 49.4 and 50.6 will both be reported as "0.6". Only differences of 0.5% or greater are shown (0.5% is in no way a ceiling of the expected difference; it just cuts down on the amount of output).

### Inputs 0-255[edit | edit source]

Java | StringHash |

2: 0.8% 4: 0.6% 9: 0.6% 11: 0.5% 13: 0.5% 14: 0.5% 15: 1.0% 17: 1.1% 20: 0.5% 21: 0.9% 23: 0.8% 25: 0.9% 28: 0.6% 31: 0.7% 32: 1.2% |
2: 0.5% 3: 0.5% 7: 0.7% 12: 0.6% 15: 0.9% 16: 1.0% 17: 0.9% 20: 0.7% 21: 1.1% 25: 0.6% 29: 0.8% 30: 0.6% 31: 0.7% |

### Inputs 32-127[edit | edit source]

Java | StringHash |

2: 0.9% 7: 0.7% 8: 0.6% 9: 0.7% 10: 0.6% 11: 0.6% 12: 1.5% 15: 0.8% 16: 0.5% 18: 0.7% 22: 0.8% 27: 0.5% 29: 0.5% 30: 0.6% 32: 0.5% |
1: 1.0% 3: 0.5% 6: 0.8% 14: 0.6% 19: 0.5% 23: 0.5% 25: 0.7% 28: 0.5% |

### Result analysis[edit | edit source]

Both algorithms perform roughly as expected. With these samples, StringHash performs a little bit better, but that is to be expected as it mixes more bits; either way, the differences are not really meaningful. The test only attempts to evaluate if all possible result bits are used efficiently without unexpected "holes" in the output.

A more thorough test would attempt to find biases in different sets of bits, but that is really more meaningful for PRNG testing and secure hashes than it is for this type of light string hash.

## Collision frequency test[edit | edit source]

This test takes the result of 20000 random strings consisting of ASCII characters 0-255, and selects 15 bits for testing. The resulting value becomes 0--32767, which, for anything other than a perfect hash, will result in a fair amount of collisions. We expect the frequency of collisions to match a Poisson distribution and compare the test results to it.

### Long random string 32-127 bits 1-15[edit | edit source]

Java SH Expected 1: 10940 10981 10863 2: 6552 6554 6630 3: 2043 1998 2023 4: 388 396 411 5: 65 65 62 6: 12 6 7

### Long random string 0-255 bits 1-15[edit | edit source]

Java SH Expected 1: 10717 10728 10863 2: 6796 6724 6630 3: 1995 2073 2023 4: 376 420 411 5: 110 55 62 6: 6 7

### Long random string 0-255 bits 6-20[edit | edit source]

Java SH Expected 1: 10788 10875 10863 2: 6768 6628 6630 3: 1989 1971 2023 4: 400 460 411 5: 55 60 62 6: 6 7

### Long random string 0-255 bits 12-26[edit | edit source]

Java SH Expected 1: 10917 10791 10863 2: 6630 6612 6630 3: 1881 2049 2023 4: 492 452 411 5: 80 90 62 6: 6 7

### Long random string 0-255 bits 18-32[edit | edit source]

Java SH Expected 1: 10828 10795 10863 2: 6590 6860 6630 3: 2127 1932 2023 4: 380 360 411 5: 75 35 62 6: 18 7

### Result analysis[edit | edit source]

Both hashes perform roughly as expected without showing too great variations over different bits; there are one or two aberrations in the higher collision counts, but that may just be the result of a too-small sample size. I will not investigate further as this test is only a rough indication of performance.

A more complete analysis would include testing smaller modulii, and certainly ones that are not a power of 2. A modulus constructed around series involving 31 and 32 will most likely produce "interesting" results for the Java hash, but that is an expected side effect of its construction.

## Bit transmutation test[edit | edit source]

This test measures how many bits of the hash changes as a result of a single input bit changing, i.e. how close to an avalanche effect we're getting. The result is described as the number of times a given number of bits have been seen to change for the entire run.

The input starts out as a string of 0s (ASCII NULs), flipping bits on and off one at a time. Then a number of runs are executed starting out with random values.

All the below tests work with 13-byte strings, and execute for 50 runs, i.e. one run based on ASCII NULs, and 49 runs with fresh random numbers each time.

A good generic hash algorithm will tend toward flipping 50% of the bits for each input bit changed, though that is obviously unattainable. We do however expect a fair hump around 13-17 bits changed, and very low counts toward the extremes. 0 bits flipping may indicate a broken hash algorithm (the hash result didn't change at all as a result of changing the input).

### Java, flip all bits in bytes 1 through 13[edit | edit source]

0: 0 1: 173 2: 208 3: 194 4: 188 5: 159 6: 160 7: 150 8: 200 9: 231 10: 228 11: 292 12: 343 13: 476 14: 503 15: 469 16: 418 17: 318 18: 210 19: 143 20: 69 21: 45 22: 11 23: 9 24: 2 25: 1 26: 0 27: 0 28: 0 29: 0 30: 0 31: 0 32: 0

This test does not show 0 bits changing, but the changes we do see are spread quite flat over the spectrum. There is a hump around 13-17 but not as marked as it should be. We get quite a few single bit changes, which is quite expected given the algorithm. The last few bytes in the string do not end up affecting very much of the end result.

### StringHash, flip all bits in bytes 1 through 13[edit | edit source]

0: 0 1: 0 2: 0 3: 45 4: 70 5: 77 6: 71 7: 56 8: 45 9: 53 10: 115 11: 203 12: 327 13: 405 14: 533 15: 588 16: 620 17: 593 18: 499 19: 371 20: 259 21: 146 22: 76 23: 32 24: 12 25: 3 26: 1 27: 0 28: 0 29: 0 30: 0 31: 0 32: 0

StringHash has a much more pronounced hump around the 16 bits changed mark. There are no single bit changes, and no two-bit changes in the tests. This is expected as each bit changed is guaranteed to affect at least three bits of the hash, even for the last few bytes of the input.

### Java, flip all bits in bytes 12 through 13[edit | edit source]

0: 0 1: 173 2: 208 3: 154 4: 108 5: 75 6: 53 7: 17 8: 6 9: 1 10: 3 11: 2 12: 0 (rest 0)

Here is where the weakness of the hash shows the most: changes in the last few bytes affect relatively few bits, thereby increasing chances for collisions.

### StringHash, flip all bits in bytes 12 through 13[edit | edit source]

0: 0 1: 0 2: 0 3: 45 4: 70 5: 77 6: 71 7: 56 8: 36 9: 26 10: 36 11: 40 12: 54 13: 51 14: 57 15: 49 16: 42 17: 39 18: 23 19: 15 20: 9 21: 3 22: 1 23: 0 24: 0 (rest 0)

While not precisely shining compared to strong hashes, StringHash stirs quite a few more bits over a much larger spectrum.

### Result analysis[edit | edit source]

StringHash outperforms the Java hash by distributing bit changes over more result bits, thus reducing the collision chance.

## Collision finding test[edit | edit source]

This test exhaustively computes all possible values of a given input set and tests for collisions. The size of the input sets is unfortunately constrained by RAM and CPU, but it is believed to be a fair indication of hash strength.

### ASCII codes 64-89 (upper case A-Z), 3 bytes[edit | edit source]

JavaHash 17576 non-colliding values StringHash 17576 non-colliding values

### ASCII codes 64-89 (upper case A-Z), 4 bytes[edit | edit source]

JavaHash 456976 non-colliding values StringHash 456976 non-colliding values

### ASCII codes 32-127 (all printable), 2 bytes[edit | edit source]

JavaHash 62 non-colliding values 62 instances of 2 inputs producing the same hash (124 strings) 2638 instances of 3 inputs producing the same hash (7914 strings) 279 instances of 4 inputs producing the same hash (1116 strings) StringHash 9216 non-colliding values

Already here, with only searching all possible combinations of 2 letters of printable ASCII, the Java hash is showing poor results.

### ASCII codes 32-127 (all printable), 3 bytes[edit | edit source]

This is about as exhaustive we can go in Lua without resulting to data compression techniques for the result sets: all possible combinations of 3 letters of printable ASCII for a total of 884736 outputs.

JavaHash 62 non-colliding values 62 instances of 2 inputs producing the same hash (124 strings) 1630 instances of 3 inputs producing the same hash (4890 strings) 224 instances of 4 inputs producing the same hash (896 strings) 62 instances of 5 inputs producing the same hash (310 strings) 1630 instances of 6 inputs producing the same hash (9780 strings) 62 instances of 7 inputs producing the same hash (434 strings) 224 instances of 8 inputs producing the same hash (1792 strings) 68606 instances of 9 inputs producing the same hash (617454 strings) 5214 instances of 10 inputs producing the same hash (52140 strings) 5214 instances of 11 inputs producing the same hash (57354 strings) 9672 instances of 12 inputs producing the same hash (116064 strings) 558 instances of 13 inputs producing the same hash (7254 strings) 558 instances of 14 inputs producing the same hash (7812 strings) 558 instances of 15 inputs producing the same hash (8370 strings) StringHash 884736 non-colliding values

### ASCII codes 32-127 (all printable), 3 bytes, with prefix[edit | edit source]

The same input values as the 32-127 x 3 test, except all prefixed with the string "01234567890123456789". This is to test for loss of accuracy.

JavaHash 62 non-colliding values 62 instances of 2 inputs producing the same hash (124 strings) 1630 instances of 3 inputs producing the same hash (4890 strings) 224 instances of 4 inputs producing the same hash (896 strings) 62 instances of 5 inputs producing the same hash (310 strings) 1630 instances of 6 inputs producing the same hash (9780 strings) 62 instances of 7 inputs producing the same hash (434 strings) 224 instances of 8 inputs producing the same hash (1792 strings) 68606 instances of 9 inputs producing the same hash (617454 strings) 5214 instances of 10 inputs producing the same hash (52140 strings) 5214 instances of 11 inputs producing the same hash (57354 strings) 9672 instances of 12 inputs producing the same hash (116064 strings) 558 instances of 13 inputs producing the same hash (7254 strings) 558 instances of 14 inputs producing the same hash (7812 strings) 558 instances of 15 inputs producing the same hash (8370 strings) StringHash 884736 non-colliding values

### ASCII codes 32-127 (all printable), 3 bytes, with suffix[edit | edit source]

The same input values as the 32-127 x 3 test, except all suffixed with the string "01234567890123456789". This is to test for loss of "old" information (data from earlier on in the string) in the mixing function.

JavaHash 62 non-colliding values 62 instances of 2 inputs producing the same hash (124 strings) 1630 instances of 3 inputs producing the same hash (4890 strings) 224 instances of 4 inputs producing the same hash (896 strings) 62 instances of 5 inputs producing the same hash (310 strings) 1630 instances of 6 inputs producing the same hash (9780 strings) 62 instances of 7 inputs producing the same hash (434 strings) 224 instances of 8 inputs producing the same hash (1792 strings) 68606 instances of 9 inputs producing the same hash (617454 strings) 5214 instances of 10 inputs producing the same hash (52140 strings) 5214 instances of 11 inputs producing the same hash (57354 strings) 9672 instances of 12 inputs producing the same hash (116064 strings) 558 instances of 13 inputs producing the same hash (7254 strings) 558 instances of 14 inputs producing the same hash (7812 strings) 558 instances of 15 inputs producing the same hash (8370 strings) StringHash 884736 non-colliding values

### ASCII codes 64-82 (A-S), 5 bytes[edit | edit source]

The Lua memory churn becomes somewhat ugly here, consuming several hundred megabytes. Even attempting A-Z with the same length brings a machine with 1GB RAM to its knees.

JavaHash 2476099 non-colliding values StringHash 2476099 non-colliding values

### Result analysis[edit | edit source]

The Java hash is shown to produce many more collisions even for rather simple inputs. The only cases where it behaves well are the A-Z cases; as long as the input subset is constricted to 32 unique values, it is collision free for 6 bytes (6 * 5 bits = 30 bits), in other words, it is a perfect hash for e.g. short strings consisting of only upper case ASCII letters A-Z. This is an expected property of the algorithm. Though taken with the rather abysmal results for more generic strings above (or, indeed, any sort of string longer than 6 bytes), the Java hash demonstrably makes for a poor choice for general input.

# Result summary[edit | edit source]

In the two simplest cases: collision frequency and bit distribution, the two hashes seem comparable. But on comparing bit transmutation patterns, StringHash tends toward much better spreads of input bits to output bits.

The theory is confirmed in the exhaustive collision search tests, where StringHash remains collision free for the small data sets used, while the Java hash produces more collisions (double, tripe, quadruple, etc) than it does collision-free results.

Added to this, the Lua implementation of StringHash is slightly faster than the Lua implementation of the Java hash (at least in its most straight-forward implementation).

# Applicability to other languages[edit | edit source]

StringHash was designed to be reasonably collision-resistant and fast in a Lua standard library environment. Other interpreted languages capable of 50-bit integer math (i.e. through using 64-bit floats) should also be able to make a fair use of it.

Languages with access to lower level primitives (XOR, ANDs, rotations) would do better to look at e.g. Bob Jenkins' lookup3 hash, or at least read his page on hash analysis.

# Appendix: Lua hash analysis code[edit | edit source]

mod=math.mod; -- This is the "Java hash", a variant of Dan Bernstein's old "33" hash posted long ago in the comp.lang.c newsgroup. -- The *31 basically translates to "new = old<<5 - old", i.e. you never completely lose data from earlier bytes as you would by only shifting -- The mod is necessary in Lua; otherwise the value turns floating-point and you lose precision after ~10 characters -- This function would be better with a prime modulus, but 2^32 is chosen as a mod to emulate the 32-bit math used in the original function JavaHash(text) local counter = 0; local len = string.len(text); for i = 1, len do counter = (counter*31) + string.byte(text, i) counter = mod(counter, 4294967296); -- 2^32 end; return mod(counter, 4294967296); -- 2^32 end -- This string hash is ~30% faster due to working with 3 characters at a time; the mod expression is fairly expensive -- The multiplications are all chosen to affect 3 areas of the accumulator at a time: -- 8161 = 8192 - 32 + 1 : 2<<13, 2<< 5, 2<<0 -- 16776193 = 16777216 - 1024 + 1 : 2<<24, 2<<10, 2<<0 -- 8372226 = 8388608 - 16384 + 2 : 2<<23, 2<<14, 2<<5 -- 3932164 = 4194304 - 262144 + 4 : 2<<22, 2<<18, 2<<10 function StringHash(text) local counter = 1; local len = string.len(text); for i = 1, len, 3 do counter = mod(counter*8161, 4294967279) + -- 2^32 - 17: Prime! (counter*8161 is at most a 48-bit number, which easily fits in the 52-bit mantissa of a double precision float) (string.byte(text,i)*16776193) + ((string.byte(text,i+1) or (len-i+256))*8372226) + ((string.byte(text,i+2) or (len-i+256))*3932164); end; return mod(counter, 4294967291); -- 2^32 - 5: Prime (and different from the prime in the loop) end -- Utility function: return number of bits changed between a and b function bitsdiff(a,b) local n=0; for i=1,32 do if(mod(a,2) ~= mod(b,2)) then n=n+1; end a=math.floor(a/2); b=math.floor(b/2); end return n; end function tcopy(to,from) for k,v in pairs(from) do to[k]=v; end end -- Bit transmutation test: Count how many bits change as a result of a single bit of input flipping function transtest(func,num, len, first, last) local bitsdiffhits = {} local origstrbytes = { }; for c=1,len do table.insert(origstrbytes, 0); end math.randomseed(2); for rep=1,num do local strbytes = {}; for c=first,last do tcopy(strbytes, origstrbytes); local bitval=1; for b=1,8 do local before = func(string.char(unpack(strbytes))); strbytes[c] = origstrbytes[c]; strbytes[c] = math.mod(origstrbytes[c] + bitval, 256); local after = func(string.char(unpack(strbytes))); local n = bitsdiff(before,after); bitsdiffhits[n] = (bitsdiffhits[n] or 0) + 1; bitval=bitval*2; end end for c=1,table.getn(origstrbytes) do origstrbytes[c]=math.random(0,255); end end local score=0; for i=0,32 do score = score - (bitsdiffhits[i] or 0)*(math.abs(16-i)/16); -- 16 = 50% of the bits, which is how many bits we want to change in a perfect distribution print(string.format(" %2u: %5u", i, bitsdiffhits[i] or 0)); end print(" SCORE: "..score); -- 0 is unimaginatively good. negative is bad. end -- Performance test: Just measure the time it takes to execute a hash on a fixed string lots of times (including the cost of the loop, obviously) function perftest(func, num) local x=os.clock(); for i=1,num do func("abcdefghijklmnopqrstuvwxyz"); end return os.clock()-x; end -- Count the number of single, double, triple etc collisions given a certain manipulation of the resultant hash: -- div by X, take modulus Y -- The modulus is there to create an artificial range clamping; testing would take too long otherwise. -- Should match expected Poisson distribution closely for an unbiased hash. function collisiontest(func, num, div,modulus, randfunc) local x = os.clock(); local outputs = {} local collisions = {} math.randomseed(1); for i=1,num do str = randfunc(); local n = math.mod(math.floor(func(str)/div), modulus); outputs[n] = (outputs[n] or 0)+1; end for _,n in pairs(outputs) do collisions[n] = (collisions[n] or 0) + n; end local y = os.clock(); local sortcol = {} for k,v in pairs(collisions) do table.insert(sortcol, k); end table.sort(sortcol); -- Compute expected Poisson distribution expect = {} lambda = num/modulus; fly = lambda * math.exp(-lambda); for c=1,10 do expect[c] = fly * modulus; fly = fly * lambda / c; end -- Output results and expected results for _,k in ipairs(sortcol) do print(string.format(" %2u: %5u (expected %5u)", k, collisions[k], expect[k] or -1)); end return y-x; end -- Bit distribution test: Measure number of times each bit is set, should average out to 50% chance in the end -- Will be presented as the absolute difference from 50% function bitdistribtest(func,num,lo,hi,dispmin) math.randomseed(1); local bitsset={}; for i=1,num do str = string.char(math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi), math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi), math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi)); local n = func(str); for k=1,32 do if(mod(n,2)==1) then bitsset[k] = (bitsset[k] or 0)+1; end n=math.floor(n/2); end end for k=1,32 do local diff = math.abs(50-(bitsset[k] or 0)/num*100); if(diff > dispmin) then print(string.format(" %2u: %.1f%%", k, diff)); end end end -- Collision finder test: Loop all possible values in given set and count collisions (yes, this is slow, and uses quite a bit of ram) function collisionfinder(func, lo, hi, bytes, prefix, suffix) local str; local coll={}; prefix = prefix or ""; suffix = suffix or ""; if(bytes==2) then for b=lo,hi do for a=lo,hi do str = prefix .. string.char(a,b) .. suffix; local n = func(str); coll[n] = (coll[n] or 0) + 1; end end elseif(bytes==3) then for c=lo,hi do for b=lo,hi do for a=lo,hi do str = prefix .. string.char(a,b,c) .. suffix; local n = func(str); coll[n] = (coll[n] or 0) + 1; end end end elseif(bytes==4) then for d=lo,hi do for c=lo,hi do for b=lo,hi do for a=lo,hi do str = prefix .. string.char(a,b,c,d) .. suffix; local n = func(str); coll[n] = (coll[n] or 0) + 1; end end end end elseif(bytes==5) then for e=lo,hi do for d=lo,hi do for c=lo,hi do for b=lo,hi do for a=lo,hi do str = prefix .. string.char(a,b,c,d,e) .. suffix; local n = func(str); coll[n] = (coll[n] or 0) + 1; end end end end end end local collcnt = {}; for k,n in coll do collcnt[n] = (collcnt[n] or 0) + 1; end for colls, count in pairs(collcnt) do if(colls==1) then print(string.format(" %5u non-colliding values", count)); else print(string.format(" %5u instances of %u inputs producing the same hash (%u strings)", count, colls, count*colls)); end end end --------------------------------------------------------------------------- -- Run the tests if(true) then local colls; local function longrand(lo,hi) return function() local ret = ""; while colls[ret] do ret = "aaaaaaaaa"..string.char(math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi), math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi), math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi),math.random(lo,hi)); end colls[ret] = true; return ret; end end print ""; print ""; print "Collision test - long random string 32-127 (20000 values into 32768 buckets)"; print "------------------------------------------" print("JavaHash:"); colls = {}; print(collisiontest(JavaHash, 20000, 1,32768, longrand(32,127))); print("StringHash:"); colls = {}; print(collisiontest(StringHash, 20000, 1,32768, longrand(32,127))); print ""; print "Collision test - long random string 0-255 (20000 values into 32768 buckets, bits 1-15)"; print "------------------------------------------" print("JavaHash:"); colls = {}; print(collisiontest(JavaHash, 20000, 1,32768, longrand(0,255))); print("StringHash:"); colls = {}; print(collisiontest(StringHash, 20000, 1,32768, longrand(0,255))); print ""; print "Collision test - long random string 0-255 (20000 values into 32768 buckets, bits 6-20)"; print "------------------------------------------" print("JavaHash:"); colls = {}; print(collisiontest(JavaHash, 20000, math.pow(2,5),32768, longrand(0,255))); print("StringHash:"); colls = {}; print(collisiontest(StringHash, 20000, math.pow(2,5),32768, longrand(0,255))); print ""; print "Collision test - long random string 0-255 (20000 values into 32768 buckets, bits 12-26)"; print "------------------------------------------" print("JavaHash:"); colls = {}; print(collisiontest(JavaHash, 20000, math.pow(2,11),32768, longrand(0,255))); print("StringHash:"); colls = {}; print(collisiontest(StringHash, 20000, math.pow(2,11),32768, longrand(0,255))); print ""; print "Collision test - long random string 0-255 (20000 values into 32768 buckets, bits 18-32)"; print "------------------------------------------" print("JavaHash:"); colls = {}; print(collisiontest(JavaHash, 20000, math.pow(2,17),32768, longrand(0,255))); print("StringHash:"); colls = {}; print(collisiontest(StringHash, 20000, math.pow(2,17),32768, longrand(0,255))); end if(true) then print ""; print ""; print "Performance test"; print "-----------------" print("JavaHash speed: ", perftest(JavaHash, 20000)); print("StringHash speed: ", perftest(StringHash, 20000)); end if(true) then print ""; print ""; print "Bit transmutation test (how many bits change if a single bit changes?)"; print "----------------------"; print(""); print("JavaHash 13 bytes total, change 1-13:"); transtest(JavaHash,50, 13, 1,13); print(""); print("StringHash 13 bytes total, change 1-13:"); transtest(StringHash,50, 13, 1,13); print(""); print("JavaHash 13 bytes total, change 1-2:"); transtest(JavaHash,50, 13, 1,2); print(""); print("StringHash 13 bytes total, change 1-2:"); transtest(StringHash,50, 13, 1,2); print(""); print("JavaHash 13 bytes total, change 12-13:"); transtest(JavaHash,50, 13, 12,13); print(""); print("StringHash 13 bytes total, change 12-13:"); transtest(StringHash,50, 13, 12,13); end if(true) then print ""; print ""; print "Bit distribution test (what's the chance of each bit being set? expressed as abs diff from 50%)"; print "---------------------"; print(""); print("JavaHash 0-255, 10000 loops: (showing diffs>0.4%)"); bitdistribtest(JavaHash,10000,0,255, 0.4); print(""); print("StringHash 0-255, 10000 loops: (showing diffs>0.4%)"); bitdistribtest(StringHash,10000,0,255, 0.4); print(""); print("JavaHash 32-127, 10000 loops: (showing diffs>0.4%)"); bitdistribtest(JavaHash,10000,32,127, 0.4); print(""); print("StringHash 32-127, 10000 loops: (showing diffs>0.4%)"); bitdistribtest(StringHash,10000,32,127, 0.4); end if(true) then print ""; print ""; print "Collision finder (run through all possible values of a set and count collisions)"; print "----------------"; print(""); print("JavaHash, 64-89 x 3 bytes"); collisionfinder(JavaHash, 64, 89, 3); print(""); print("StringHash, 64-89 x 3 bytes"); collisionfinder(StringHash, 64, 89, 3); print(""); print(""); print("JavaHash, 64-89 x 4 bytes"); collisionfinder(JavaHash, 64, 89, 4); print(""); print("StringHash, 64-89 x 4 bytes"); collisionfinder(StringHash, 64, 89, 4); print(""); print(""); print("JavaHash, 32-127 x 2 bytes"); collisionfinder(JavaHash, 32, 127, 2); print(""); print("StringHash, 32-127 x 2 bytes"); collisionfinder(StringHash, 32, 127, 2); print(""); print(""); print("JavaHash, 32-127 x 3 bytes"); collisionfinder(JavaHash, 32, 127, 3); print(""); print("StringHash, 32-127 x 3 bytes"); collisionfinder(StringHash, 32, 127, 3); print(""); print(""); print("JavaHash, 32-127 x 3 bytes, prefix '01234567890123456789'"); collisionfinder(JavaHash, 32, 127, 3, "01234567890123456789"); print(""); print("StringHash, 32-127 x 3 bytes, prefix '01234567890123456789'"); collisionfinder(StringHash, 32, 127, 3, "01234567890123456789"); print(""); print(""); print("JavaHash, 32-127 x 3 bytes, suffix '01234567890123456789'"); collisionfinder(JavaHash, 32, 127, 3, "", "01234567890123456789"); print(""); print("StringHash, 32-127 x 3 bytes, suffix '01234567890123456789'"); collisionfinder(StringHash, 32, 127, 3, "", "01234567890123456789"); print(""); -- This test takes a looooong time if(true) then print(""); print("JavaHash, 64-82 x 5 bytes"); collisionfinder(JavaHash, 64, 82, 5); print(""); print("StringHash, 64-82 x 5 bytes"); collisionfinder(StringHash, 64, 82, 5); end end