Hashing a 48-bit key into a 16-bit value

Question

I am working with devices that receive very small packets of data. A device is uniquely identified by a 48-bit key. When the device receives an individual packet, it needs to read the packet and determine if the packet was meant for that device. Sounds simple, but the packet has enough space for only a 16-bit key.

The communication protocol cannot be changed. I cannot make use of multiple packets or any other fields in the packet. Basically I need to store this 48-bit identifier in a 16-bit field. Obviously there will be collisions with any solution.

I was considering either sending the lower 16 bits of the original key or hashing it. What's the best way to do this while minimizing the collisions?

PS: Actually it looks like the first three bytes of the original key is always the same, so this problem just got reduced to shoving a 24-bit key into a 16 bit key, still pretty bad though.

PPS: Collisions are not catastrophic. The device can recover but it is expensive.

Answer 1

Ask the manufacturer about any patterns in the generation of this number. It's quite likely that some of these 24 bits identify the production batch or the part of the world to ship to, making they the prime candidates for being trimmed out.

Make it clear in the request that you are aware and accept that they can change numbering policy anytime without notice. This should make them more likely to give the information.

Answer 2

The only thing that can help you in this situation is if you have devices less than or equal 2^16. here you need to have hash table that maps each 24-bit key to unique 16-bit key . So while sending the packet send 16-bit key and while retrieving check for your keys mapped value in the hash table. You can also hard code the 16-bit key values for direct comparisons. But if you have more than 2^16 devices then according to pigeon hole principle you will have 2 or more devices with same 16-bit key then you cannot be sure which device the packet is meant for.

Pseudo Code for Sending & receiving packet:-

Send(BigKey,Data) {

  // get 16-bit key from 24-bit one
  SmallKey = HashMap.getValue(BigKey);
  Packet = SmallKey + Data ;

}

Receive(Packet) {

  (Key,Data) = split(Packet);

   // get devices 16-bit key
   SmallKey = HashMap.getValue(MyKey);

   if(SmallKey==Key)
      Process(Data)
   else Error("Invalid Packet");

}

Note:- Hash map can be created using red-black trees,b-tree etc. which do lookup in O(logn). which is good enough for your application here.