CODEWITHSUNDEEP
algorithmhashhashmap
LodeRunner
LodeRunner

Reputation: 8403

Generating a unique hash for a custom structure?

I need to build a hash (as an unsigned 32-bit integer) for an object that encapsulate this data.

Entry {
    uint8 r;
    uint8 g;
    uint8 b;
    bool empty;
    uint8 count;
}

The hash must be unique for every instance, except if the instances are equal. Two instances are equal if and only if:

AND

The hash will be used in hashmaps and other containers so it might be called very often. The hash generation needs to be fast.

I thought about CCCERRRGGGBBB, where:

But that number is way out of range.

Any thoughts?

Upvotes: 0

Views: 102

Answers (1)

Jean-Bernard Pellerin
Jean-Bernard Pellerin

Reputation: 12670

You're going to have a tough time encoding 33 bits of information into 32 bits

if (empty == false)
  return count ~ r ~ g ~ b
else
  return count ~ 0

You get one overlap, which is when empty is false and r,g,b are all 0 - this will be the same hash as when empty is true and r,g,b are 0

Without further assumptions this is the best that can be done.

Upvotes: 2

Related Questions