Suppose I have a dictionary of ASCII words stored in uppercase. I also want to save those words into separate files so that the total word count of each file is approximately the same. By simply looking at the word I need to know which file it should be in (if it’s there at all). Duplicate words should go into the same file and overwrite the last one.
My first attempt at solving this problem is to use .NET’s object.GetHashCode() function and .Trim() to get one of the “random” characters that pop up. I asked a similar question here
If I only use one character of object.GetHashCode() I would get a hash code character of A..Z or 0..9. However saving the result of GetHashCode to disk is a no-no so I need a substitute.
Question:
What algorithm (or subset of an algorithm) is appropriate for pigeonholing strings into a single character or range of characters (Like hex 0..F offers 16 chars)?
Real world usage:
I’ll use this answer to modify the Partition key used in Azure Table storage as described here
9
The simplest ‘hash’ function would be to take the first character of the string and that is the hash code. It works. It doesn’t have a good distribution, but it works for some degree of ‘works’.
To get a better hash, sum up the value of the string (A = 1, B = 2, C = 3 …) and then take the modulus of the resulting value. If this is to be assigned to the ‘A-Z’ hash range, take this mod 26 and assign that back into the character array (in this case, A = 0). If this is to be in the hex range hash, take the value mod 16.
2
It feels like your question is very related to your previous stackoverflow question.
Generally speaking, Azure Table IO performance improves as more partitions are used (with some tradeoffs in continuation tokens and batch updates I won’t go into).
Since the partition key is always a string I am considering using a “natural” load balancing technique based on a subset of the GetHashCode() of the partition key, and appending this subset to the partition key itself. This will allow all direct PK/RK queries to be computed with little overhead and with ease. Batch updates may just need an intermediate to group similar PKs together prior to submission
With that background information the problem is not simply taking a database of words and splitting into multiple smaller but equal sized databases of the same words. Instead it looks like you are trying to determine how to automatically partition your data based on a key so that it is separated into equal parts.
If our end goal is to partition the words evenly across the shards I would not do so based on the data itself. That is to say if my method for determining which partition a bit of data goes into is based on what is included in that data I would not expect my end distribution to be even.
Given the follow list of words as an example
Programmer,Programmer,StackExchange
The value Programmer is repeated twice. If that value is what I am using to determine which partition the data will end up in I would expect that both Programmers would end up in the same partition. If the end goal is to keep all closely related words on the same partition this may be the way you want to go, but I don’t think it is.
If instead we do not care which words are where and want an even distribution I would first determine the number of shards that I want to run and then simply loop through my database of words assigning the partition key 1-N where N is the number of partitions I have.
i.e.
int totalPartitions = 5;
int currentPartition = 1;
Foreach(var item in MyData) {
MyData.PartitionKey = currentPartition;
if(currentPartition < totalPartitions)
currentPartition++
else
currentPartition = 1;
}
3