Help with uniform hash distribution

BTW, changing the order in which the bytes are presented appears not to improve it (I'm not surprised):

function TForm1.HashIndex(Value: Pointer): Integer;
var Key:      Integer;
    vCRC32 : Cardinal;
    ik, ix : Integer;
    currentByte : ARRAY [1..4] of Byte;
begin

  // Seed the CRC calculation
  vCRC32 := CRCSeed;
  ik := Integer(Value) shr 6;
  for ix := 1 to 4 do
  begin
    currentByte[ix] := ik MOD 256;
    ik := ik DIV 256;
  end {for};
  for ix := 4 downto 1 do
  begin
    vCRC32 := CRC32(currentByte[ix],vCRC32);
  end {for};
  vCRC32 := CRCEnd(vCRC32);
  // Mod the value with the hash size
  result := vCRC32 mod HASH_SIZE;

end;

There's some more info about CRC16 and CRC32 at http://www.efg2.com/Lab/Mathematics/CRC.htm

sftweng,
First, thank you for the information on crc's; though I already have 16/32 bit crcs, lrcs, and vrc routines in my bag of code. ;-).

My question now, is did you run the new hash routine through the test application to determine the results? I did, and am posting the results that I saw:

Original Baseline
----------------------------------------
8 bucket(s) with 9 items
60 bucket(s) with 10 items
210 bucket(s) with 11 items
714 bucket(s) with 12 items
1349 bucket(s) with 13 items
2037 bucket(s) with 14 items
2464 bucket(s) with 15 items
2651 bucket(s) with 16 items
2508 bucket(s) with 17 items
1954 bucket(s) with 18 items
1240 bucket(s) with 19 items
681 bucket(s) with 20 items
311 bucket(s) with 21 items
107 bucket(s) with 22 items
35 bucket(s) with 23 items
15 bucket(s) with 24 items
4 bucket(s) with 25 items
1 bucket(s) with 26 items
----------------------------------------

Suggested implementation using CRC
----------------------------------------
52 bucket(s) with 0 items
1 bucket(s) with 1 items
115 bucket(s) with 2 items
160 bucket(s) with 3 items
161 bucket(s) with 4 items
314 bucket(s) with 5 items
373 bucket(s) with 6 items
426 bucket(s) with 7 items
608 bucket(s) with 8 items
644 bucket(s) with 9 items
771 bucket(s) with 10 items
852 bucket(s) with 11 items
886 bucket(s) with 12 items
915 bucket(s) with 13 items
890 bucket(s) with 14 items
967 bucket(s) with 15 items
895 bucket(s) with 16 items
888 bucket(s) with 17 items
895 bucket(s) with 18 items
816 bucket(s) with 19 items
714 bucket(s) with 20 items
619 bucket(s) with 21 items
541 bucket(s) with 22 items
495 bucket(s) with 23 items
430 bucket(s) with 24 items
383 bucket(s) with 25 items
312 bucket(s) with 26 items
264 bucket(s) with 27 items
211 bucket(s) with 28 items
169 bucket(s) with 29 items
126 bucket(s) with 30 items
118 bucket(s) with 31 items
83 bucket(s) with 32 items
67 bucket(s) with 33 items
37 bucket(s) with 34 items
40 bucket(s) with 35 items
37 bucket(s) with 36 items
21 bucket(s) with 37 items
14 bucket(s) with 38 items
12 bucket(s) with 39 items
8 bucket(s) with 40 items
3 bucket(s) with 41 items
4 bucket(s) with 42 items
2 bucket(s) with 43 items
6 bucket(s) with 44 items
1 bucket(s) with 45 items
0 bucket(s) with 46 items
1 bucket(s) with 47 items
1 bucket(s) with 48 items
0 bucket(s) with 49 items
0 bucket(s) with 50 items
0 bucket(s) with 51 items
0 bucket(s) with 52 items
1 bucket(s) with 53 items
----------------------------------------

So its not exactly what I would call an improvement, especially when you consider the extra overhead. Now, if you saw a different result set than what I am seeing (taking into account the slight deviation that can be attributed to the random function), then I would like to hear it, as it means that I need to consider system deviations as well.

Thanks again,
Russell

Hi Russell, yes I did run the whole test suite and achieved similar results. My observation about improvement was based on the fact that the number of buckets with 16 or fewer items was almost twice as many using the CRC (around 17000 versus 9000).

Alan

I withdraw the comment - made a stupid mistake in arithmetic - the result is no better.

Have you tried something like this?

         RandSeed := Integer(Value) shr 6;
         result := Random(HASH_SIZE);

I haven't done a valid test yet because the use of "RandSeed" in the hashkey function collides with your use outside (changing the seed used to generate the addresses as a side-effect) but I'd expect a better result.

Alan,

No problem on the previous ;-)
I was going to mention the backside of the slide... meaning there are a lot MORE keys in the 19 and over buckets.

I am also running a Mean on the final result, and currently its between
820-920, and I am trying to improve that number.

Regarding the randseed...
Not sure if the randseed will work, but I will check it out. Bottom line is that this needs to be able to hash the key so the same index is always returned (otherwise I would never find anything)

Will take a look though @ the randseed though, thanks.
Russell

Priming RandSeed gives repeatable results.

Here's what I tried so far. Knuth multiplicative doesn't seem much better either. I added a RadioGroup to allow choice of algorithm.

function TForm1.HashIndex(Value: Pointer): Integer;
var Key:      Integer;
    vCRC32 : Cardinal;
    ik, ix : Integer;
    i64 : Int64;
    currentByte : ARRAY [1..4] of Byte;
begin

  if RadioGroup1.ItemIndex = 0
  then result := (Integer(value) shr 6) mod HASH_SIZE
  else if RadioGroup1.ItemIndex = 2
  then begin
         RandSeed := Integer(Value) shr 6;
         result := Random(HASH_SIZE);
       end
  else if RadioGroup1.ItemIndex = 3
  then begin
         i64 := (Integer(value) shr 6) * 2654435761;
         result := i64 mod HASH_SIZE;
       end
  else begin
    // Seed the CRC calculation
    vCRC32 := CRCSeed;
    ik := Integer(Value) shr 6;
    for ix := 1 to 4 do
    begin
      currentByte[ix] := ik MOD 256;
      ik := ik DIV 256;
    end {for};
    for ix := 4 downto 1 do
    begin
      vCRC32 := CRC32(currentByte[ix],vCRC32);
    end {for};
    vCRC32 := CRCEnd(vCRC32);
    // Mod the value with the hash size
    result := vCRC32 mod HASH_SIZE;
  end {if};

end;

There are some more interesting hash functions at http://www.concentric.net/~Ttwang/tech/inthash.htm. Regrettably I have to stop playing now and go prepare dinner. Good luck on your quest. I'll check back in again later to see how it's going.

Alan

Thanks for your help so far Alan, here is where I am currently at:

// Best avgerage mean so far
function TForm1.HashIndex(Value: Pointer): Integer;
begin

  result:=((Integer(Value) shr 6)+(Integer(Value) shr 5)) mod HASH_SIZE;

end;

----

Still think there is something to the numbers that I am missing....

Russell

listening  . . .

The "Weighted Avg 'Cost'" is coming out best with CRC32 with this code (note the cost calculation in the mainline):
------------------- Code
unit main;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, ExtCtrls;

// Prime number for hash size
const
  HASH_SIZE      =  16349;

// Hash definition
type
  THashArray     =  Array [0..Pred(HASH_SIZE)] of Integer;

type
  TForm1         =  class(TForm)
     Button1:    TButton;
     ListBox1:   TListBox;
    RadioGroup1: TRadioGroup;
     procedure   Button1Click(Sender: TObject);
     procedure   FormCreate(Sender: TObject);
     procedure   ListBox1DrawItem(Control: TWinControl; Index: Integer; Rect: TRect; State: TOwnerDrawState);
  private
     // Private declarations
     FMaxCount:  Integer;
     FHashArray: THashArray;
  public
     // Public declarations
     function    HashIndex(Value: Pointer): Integer;
  end;

var
  Form1:         TForm1;

implementation
{$R *.DFM}
uses CRC32c;

function TForm1.HashIndex(Value: Pointer): Integer;
var Key:      Integer;
    vCRC32 : Cardinal;
    ik, ix : Integer;
    i64 : Int64;
    currentByte : ARRAY [1..4] of Byte;
begin

  if RadioGroup1.ItemIndex = 0
  then result := (Integer(value) shr 3) mod HASH_SIZE
  else if RadioGroup1.ItemIndex = 1
  then begin
         // Seed the CRC calculation
         vCRC32 := CRCSeed;
         ik := (Integer(Value) shr 6);
         for ix := 1 to 4 do
         begin
           currentByte[ix] := ik MOD 256;
           ik := ik DIV 256;
           vCRC32 := CRC32(currentByte[ix],vCRC32);
         end {for};
         vCRC32 := CRCEnd(vCRC32);
         // Mod the value with the hash size
         result := vCRC32 mod HASH_SIZE;
       end
  else if RadioGroup1.ItemIndex = 2
  then begin
         RandSeed := Integer(Value) shr 5;
         result := Random(HASH_SIZE);
       end
  else if RadioGroup1.ItemIndex = 3
  then begin
         i64 := (Integer(value) shr 3) * 2654435761;
         result := (i64 shr 8) mod HASH_SIZE;
       end
  else if RadioGroup1.ItemIndex = 4
  then begin
         i64 := (Integer(value) shr 5) + (Integer(value) shr 6);
         result := i64 mod HASH_SIZE;
       end
  else begin
         result := (Integer(Value) shr 6) mod HASH_SIZE;
       end;

end;

procedure TForm1.Button1Click(Sender: TObject);
var  List:       TList;
     i:          Integer;
     j:          Integer;
     p:          Pointer;
     dwStats:    Array [0..2] of Integer;
     dwSlots:    Integer;
     arrInts:    Array of Integer;
     tot:        Integer;
begin


  // Setup for test
  List:=TList.Create;
  ListBox1.Items.Clear;
  ZeroMemory(@FHashArray, SizeOf(THashArray));
  Randomize;

  try
     // Allocate memory blocks and increment the hash slot of where the item falls
     for i:=0 to 262144 do
     begin
        p:=AllocMem(Succ(Random(32)));
        Inc(FHashArray[HashIndex(p)]);
        List.Add(p);
     end;
     // Calculate the hash stats
     dwStats[0]:=0;       // Max value
     dwStats[1]:=MaxInt;  // Min value
     dwStats[2]:=0;       // Count of empty slots
     for i:=0 to High(FHashArray) do
     begin
        if (FHashArray[i] > dwStats[0]) then dwStats[0]:=FHashArray[i];
        if (FHashArray[i] < dwStats[1]) then dwStats[1]:=FHashArray[i];
        if (FHashArray[i] = 0) then Inc(dwStats[2]);
     end;
     // Allocate memory for the number of slots
     dwSlots:=Succ(dwStats[0]-dwStats[1]);
     SetLength(arrInts, dwSlots);
     // Fill in the count for each slot
     for i:=dwStats[1] to dwStats[0] do
     begin
        for j:=0 to High(FHashArray) do
        begin
           if (FHashArray[j] = i) then Inc(arrInts[i-dwStats[1]]);
        end;
     end;
     // Graph the hash statistics
     ListBox1.Items.BeginUpdate;
     FMaxCount:=0;
     tot := 0;
     for i:=dwStats[1] to dwStats[0] do
     begin
        j:=arrInts[i-dwStats[1]];
        if (j > FMaxCount) then FMaxCount:=j;
        ListBox1.Items.AddObject(Format('%d bucket(s) with %d items', [j, i]), Ptr(j));
        tot := tot + i*j;
     end;
     tot := tot div dwStats[0];
     ListBox1.Items.EndUpdate;
     Caption:=Format('Min bucket count = %d, Max bucket count = %d, Weighted Avg ''Cost''= %d', [dwStats[1], dwStats[0], tot]);
     // Free memory
     SetLength(arrInts, 0);
  finally
     // Free test memory
     for i:=Pred(List.Count) downto 0 do FreeMem(List[i]);
     // Tear down test
     List.Clear;
     List.Free;
  end;

end;

procedure TForm1.FormCreate(Sender: TObject);
begin

  FMaxCount:=0;

end;

procedure TForm1.ListBox1DrawItem(Control: TWinControl; Index: Integer; Rect: TRect; State: TOwnerDrawState);
var  dwCount:       Integer;
     rcFill:        TRect;
     dblPct:        Double;
begin

  // Calculate the percentage based on max and count
  dwCount:=Integer(ListBox1.Items.Objects[Index]);
  dblPct:=(dwCount / Succ(FMaxCount));

  // Get the rect to draw
  with ListBox1.Canvas do
  begin
     FillRect(Rect);
     rcFill:=Rect;
     rcFill.Right:=rcFill.Left+Trunc((rcFill.Right-rcFill.Left) * dblPct);
     Brush.Color:=clYellow;
     FillRect(rcFill);
     Brush.Color:=clWindow;
     SetBkMode(Handle, TRANSPARENT);
     TextOut(Rect.Left+2, Rect.Top+2, ListBox1.Items[Index]);
  end;

end;

end.
--------------------- Form
object Form1: TForm1
  Left = 80
  Top = 117
  Width = 638
  Height = 373
  Caption = 'Form1'
  Color = clBtnFace
  Font.Charset = DEFAULT_CHARSET
  Font.Color = clWindowText
  Font.Height = -11
  Font.Name = 'MS Sans Serif'
  Font.Style = []
  OldCreateOrder = False
  OnCreate = FormCreate
  PixelsPerInch = 96
  TextHeight = 13
  object Button1: TButton
    Left = 8
    Top = 8
    Width = 75
    Height = 25
    Caption = 'Button1'
    TabOrder = 0
    OnClick = Button1Click
  end
  object ListBox1: TListBox
    Left = 136
    Top = 0
    Width = 494
    Height = 339
    Style = lbOwnerDrawFixed
    Align = alRight
    ItemHeight = 16
    TabOrder = 1
    OnDrawItem = ListBox1DrawItem
  end
  object RadioGroup1: TRadioGroup
    Left = 8
    Top = 48
    Width = 121
    Height = 89
    Caption = 'Method'
    ItemIndex = 0
    Items.Strings = (
      'Original'
      'CRC32'
      'RandSeed'
      'Knuth'
      'RLLibby')
    TabOrder = 2
  end
end

Sorry Alan, thats not the case; your calculation is skewing the numbers...

Take the CRC example, which gives me a cost/mean of 5140/315. This is not taking into account the fact that 115,329 items fall into buckets with a depth greater than 19. Some buckets are heavy, while others are very (too) light. That is also why I was displaying the min/max of buckets, which for the crc is between 0-50

The we take this example:

result:=((LongWord(Value) shr 5) * 5) mod HASH_SIZE

It displays a cost/mean of 10485/920. In this example, only 17844 items fall into buckets with a depth greater than 19. The min/max for this calculation is between 8 - 25, which when used with the mean, clearly shows a much more even distribution bewteen the buckets.

If I take the following

result:=((LongWord(Value) div 4) shr 12) mod HASH_SIZE;

it returns a cost/mean of 345/22. It may have the lowest "cost", but I can't ignore the fact that 16,050 buckets are empty. ;-)

Kind Regards,
Russell

I must be missing something in your analysis. The "Weighted Avg 'Cost'" is the average of the product of the number of entries in the bin times the depth of the bin and should, therefore, represent a figure of merit for the algorithm if the access to the hash table is uniform (random) or is traversed sequentially and the cost of examining each entry in the bin is linear. Therefore, it does take into account the number of entries with large numbers - it's a weighted average.

The bin population with CRC32 is not sparse (empty) so I don't see how that comes into consideration in this particular comparison though I agree that in general it would.

I guess I'm having trouble understanding by what you mean by "improvement" in your original question. It appears to me that the CRC32 has a more random dispersal, lower mean and lower total processing cost on average than the others.

If you could publish a true "cost" algorithm or way to derive a "figure of merit" then it would be easier to know what to aim for. Is the cost associated with looking an entry up in each bin not linear with the number of entries in the bin, as it would be with a sequential search through the entries? That seems to me to be the likliest worst case.

Alan,
Sorry if this was not clear from the original question, though I thought it was. I was looking for a closer uniform hash distribution than I currently have now. The closer I am to this, the flatter the "worst" case cost becomes, in a "perfect" world this would be O(16) for the worst case. I AM concerned with the average running case as well, but the worst case does factor in.

Anyways, I realize there are alot of factors that come into play with this. Such as best case, worst case, average case, overhead for index calculation, etc. So I decided to run this through a "real" world test, where the pointers are added to the hash, the hash is chained for overflows, and then 1 million random pointer lookups are performed. This way I could get a feel for average case, while also taking into consideration the worst case scenarion (and its percentage for occurance).

Needless to say I got interesting results...

Item Count = 262144
Hash Count = 16441

"Perfect Uniform Hash" (I hashed integers to get a perfect spread)
---------------------------
Min / Max - 15..16
Worst case is 16 scans
0 items (0%) will require > 16 scans to locate
78 ms add time
1240 ms locate time / 1 million random lookups

This was what I was shooting for, but now see that it has its flaws because of a slower average case, even though it has a constant O(16) worst case

CRC
----------------
Min / Max - 0..50
Worst case is ~50 scans
45,455 (17%) items will require > 16 scans to locate
125 ms add time
906 ms locate time / 1 million random lookups


(LongWord(Value) shr 6) mod HASH_SIZE
----------------
Min / Max - 3..30
Worst case is ~30 scans  
25,051 (9%) items will require > 16 scans to locate
78 ms add time
782 ms locate time / 1 million random lookups

(LongWord(Value) shr 7) mod HASH_SIZE;
----------------
Min / Max - 0..34
Worst case is ~34 scans  
34,561 (13%) items will require > 16 scans to locate
78 ms add time
610 ms locate time / 1 million random lookups

(Makes my brain hurt) So at this point I'm going to close this question out, and award you the points for the help / comments in regards to optimizing this. I do appreciate the time you have spent on this, as It gave me MANY things to look at when evaluating what is "optimal" for me.

In the end, I am going with:

  result:=(LongWord(Value) shr 7) mod HASH_SIZE;

As the calculation
1.) is faster than the crc routine
2.) produces a better average real world time than the rest
3.) produces an average worst case scenario.

Thanks again,
Russell

Thanks, Russell. I found the exercise interesting too. One parting comment - I had also been thinking about doing some benchmarking and you beat me to it. Had I done so, I'd have optimized the CRC32 calculation a bit, probably throwing awa the initial and final conditioning and making one procedure call rather than four.

Nonetheless, this was fun and I enjoyed working on it with you.

Alan