CODEWITHSUNDEEP
.netalgorithmcolors
serhio
serhio

Reputation: 28586

Generate unique color from a string

I have to draw some arbitrary strings in some opaque rectangular areas. I need that the background color of that areas be unique foe a given string.

Say, if I draw "Paris" and "Paris1" their color should be different. But if I draw "Paris" in blue, each other "Paris" should be drawn in blue too.

I emphasize once again that the color should be opaque.

For this I found a simple solution:

rectangleBackColor = Color.FromArgb(myString.GetHashCode())

The problem is the opacity. I need to "eliminate" the "A"(alpha) component.

Now, such a code may work

  rectangleBackColor = Color.FromArgb(myString.GetHashCode())
  ' set the alpha value = 255 for an opaque color '
  rectangleBackColor = Color.FromArgb(255, rectangleBackColor)

but it can loose the string-color uniqueness.

Say, I have two different hashCodes (in hexa) x AB 11 22 33 and x FF 11 22 33.
Setting AB to FF I makes to two different strings the same background color (x FF 11 22 33). This is not good.

Upvotes: 2

Views: 1857

Answers (4)

AShelly
AShelly

Reputation: 35600

Two ideas:

1) If all your N strings are known before you start coloring, calculate a Perfect Hash (implementations in C and C# here). Then you can multiply each hash value by 256^3/N to spread the results over the color space.

2) If they are not known, you could resolve the collisions manually. Something like this pseudocode:

tries = 5; //arbitrary number       
colorcode = myString.GetHashCode()&0xFFFFFF;
while ( Dictionary.containsKey(colorcode ) && 
        Dictionary.getValue(colorcode )!= myString &&
        tries-->0) {
    colorcode = ((colorcode+3) * 92821) &0xFFFFFF;  //rehash
}
if (tries) {
    Dictionary.insert(colorcode , myString);
} 
rectangleBackColor = Color.FromArgb(0xFF000000|colorcode );

Upvotes: 0

Jackson Pope
Jackson Pope

Reputation: 14660

Given that you cannot generate a truly unique integer to represent a string because of the difference in the size of the spaces they can represent, you could try:

uint noA = (unit)myString.GetHashCode() / 255; 
uint opaque = noA + 0xFF000000; 
rectangleBackColor = Color.FromArgb(opaque);

This should generate a (fairly) unique value for each string based on the hash code, with a the alpha component set to 255. Clearly, this can only generate 2^24 different values, and hence is not truly unique.

Edit: It should be noted this has exactly the same problem as your version but ignores the lowest 8 bits instead of the highest ones.

Upvotes: 2

fulmicoton
fulmicoton

Reputation: 15968

Hash is not unique in the first place. If you're not convinced, just consider how many more strings there is than hashcode. To begin with, hash code themselves are strings! Which means that if you were to attribute a different hash code to each strings, you would run out of hash code after going through all hash code.

Two strings having a same hashcode are called a collision. For a good hashcode, you can consider that the probability for two innocent strings to be in 1/#{size of your hash space}.

Another nice property, is that you expect any truncation of your hashcode to behave like that as well. Truncating your hash code is actually correct practise.

You will get for two given names a collision probability of around 1/16M. If you have N-strings, however, you might encounter what is called the birthday problem. The probability of observing at least 1 collision is much much greater. Somewhere near than N^2 / 16M.

Upvotes: 1

Nir
Nir

Reputation: 29614

You can't generate unique colors for strings:

The RGB space has 24bits or 2^24-1 unique values (total of 16777215 colors).

The following code will print 16777220 unique strings (5 more than the number of colors):

for(int i=0; i<16777220 ; ++i) Console.WriteLine(i.ToString());

So, if you take all the strings generated by the progam above and give then colors you must have at least 5 strings with repeating colors.

By the way, GetHashCode does not return unique values, just uniformly distributed, repeat the proof above with 32 bits (you will need to make i in the for loop uint and change the number to more than 4294967295, but those are the only changes) and you discover you can't get a unique value for every string in a 32bit value (or in any other fixed size value).

Your method is pretty good and repeat colors will probably be rare.

Upvotes: 2

Related Questions