2

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
  • 1
    Why can't you use a character of GetHashCode()? Commented Nov 20, 2012 at 21:54
  • So you have a file with arbitrary number of lines of text which you want to save to number of files which have about equal number of lines in them? Now how do hashes have anything to do with the problem?
    – zxcdw
    Commented Nov 20, 2012 at 22:00
  • 2
    @PatrickJamesMcDougle The results of GetHashCode() may change based on .NET version or patch. MSFT doesn't want us to save or rely on the hash code in offline storage. I mentioned this in my question. Commented Nov 20, 2012 at 22:04
  • @zxcdw I'm looking to use the pigeonhole principle to do Azure LoadBalancing as referenced in the linked question. Commented Nov 20, 2012 at 22:07
  • 1
    Why not an 8 bit CRC? Commented Nov 20, 2012 at 22:15

2 Answers 2

4

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
  • Yeah, the first character is probably a bad idea, you'd get too many T's. Commented Nov 20, 2012 at 21:56
  • @PatrickJamesMcDougle The pendant in me says its actually S, C, P, B, M for the first character. S has 16k starting letters while 'T' has only 7.5k starting. cut -c1 words | tr 'a-z' 'A-Z' | sort | uniq -c | sort -rn -- and yes, they are very poorly distributed.
    – user40980
    Commented Nov 20, 2012 at 22:02
1

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
  • Yes this is related to the SO question. When that question was migrated I learned that I need to ask algorithm questions on Programmers.SE. Back to this question... if the ASCII version of PROGRAMMERS == PROGRAMMERS (and they are equal and not similar) then I want my app to be able to calculate what Azure partition the word is in. Knowing this allows me to gain efficiency with batch features and be able to directly query one partition rather than guessing at which partition the data is in. Commented Nov 20, 2012 at 22:25
  • If you want to be able to determine the partition for any string with no other data than the ASCII string itself then I believe you will have to settle for an uneven distribution of your data. If we use just the string PROGRAMMER to get another key that represents a partition, we have no way to distinguish it from another string with the same exact contents. Knowing that, we can see that a database of 100 identical strings would end up in one partition.
    – Mike
    Commented Nov 20, 2012 at 22:33
  • Yes, I don't care about historic data if it's overwritten with a match. Yes distribution will not be perfectly even, but I need a way to make it reasonably even for performance. Perhaps an 8 bit CRC of "PROGRAMMERS" gives me "8". I would then save the value into the partition "PROGRAMMERS8". I just need an algorithm that load balances strings. Maybe 8 bit CRC, or MichaelT's answer is correct. Commented Nov 20, 2012 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.