Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
1  
Why can't you use a character of GetHashCode()? –  Patrick James McDougle Nov 20 '12 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 Nov 20 '12 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. –  makerofthings7 Nov 20 '12 at 22:04
    
@zxcdw I'm looking to use the pigeonhole principle to do Azure LoadBalancing as referenced in the linked question. –  makerofthings7 Nov 20 '12 at 22:07
1  
Why not an 8 bit CRC? –  whatsisname Nov 20 '12 at 22:15

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
Yeah, the first character is probably a bad idea, you'd get too many T's. –  Patrick James McDougle Nov 20 '12 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. –  MichaelT Nov 20 '12 at 22:02
    
ha! That's what I was going to suggest too! –  Andrew Wagner Nov 21 '12 at 0:30
    
Interesting. Thanks for that interesting bit of trivia! –  Patrick James McDougle Nov 21 '12 at 13:29

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;
}
share|improve this answer
    
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. –  makerofthings7 Nov 20 '12 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 Nov 20 '12 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. –  makerofthings7 Nov 20 '12 at 22:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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