Friday, June 5, 2015

Selecting an index based on hashed value of data

Background

Let's say we have 5 resources. We want to select one of these resources based on the incoming data (key).

String[] resources = new String[]
{
"Server 1",
"Server 2",
"Server 3",
"Server 4",
"Server 5"
};

Helper Methods


// returns an index based on a key
static int SelectIndex(String key, int totalIndices)
{
return (int)(GetInt64HashCode(key) % (ulong)totalIndices);
}

// helper method to calculate a numeric hash for a string
static UInt64 GetInt64HashCode(string str)
{
UInt64 hashedValue = UInt64.MaxValue / UInt32.MaxValue;
 UInt64 hashedValueMultiplier = UInt64.MaxValue / UInt16.MaxValue;
for (int i = 0; i < str.Length; i++)
{
hashedValue += str[i];
hashedValue *= hashedValueMultiplier;
}
return hashedValue;
}

Test

{
"Server 1",
"Server 2",
"Server 3",
"Server 4",
"Server 5"
};

Dictionary<int, int> selectionDistribution = new Dictionary<int, int>();
for (int i=0; i<resources.Length; i++)
{
selectionDistribution.Add(i, 0);
}

int keyCount = 10000;
for (int i = 0; i < keyCount; i++)
{
String key = Guid.NewGuid().ToString();
int selectedIndex = SelectIndex(key, resources.Length);
selectionDistribution[selectedIndex] = ++selectionDistribution[selectedIndex];
Console.WriteLine("{0} goes to {1}", key, resources[selectedIndex]);
}

Console.WriteLine("*** Distribution ***");
foreach(KeyValuePair<int, int> pair in selectionDistribution)
{
Console.WriteLine("{0}: {1}", resources[pair.Key], pair.Value);
}
Console.ReadKey();

Output

21b33e71-9bb6-49c9-a8f1-b435a0896596 goes to Server 3
9453c55f-409c-45f0-9941-fc5623c8d5da goes to Server 4
e26eef17-e357-4c22-b546-9a9a3329fc5b goes to Server 1
f2a516d6-5bed-4736-abad-e508d77d1c12 goes to Server 1
0fe01f0d-1860-4358-80ab-c7f27ab400ca goes to Server 4
.....
....
704441d5-7f2f-444a-90ea-60478fcebb85 goes to Server 4
c2b7ec3f-2d48-49f2-aa0d-541ea6c464d4 goes to Server 3
1fc81dce-4e5b-41b7-bd49-fe9abefffcda goes to Server 1
*** Distribution ***
Server 1: 2036
Server 2: 1962
Server 3: 1986
Server 4: 2035
Server 5: 1981