title: Hash algorithm in C to map 16 byte-values to 2 byte-values
body: <p>I'm working on an electronic project with a microcontroller which is programmed in C.</p>
  
  <p>I need to store some IDs and its associated information in a flash memory (SD). These IDs are 16 bytes long so there are 2^128 possible values. Although they are 16 bytes, only 50000 (unique) values will be used. It's physically impossible to store all the possible (2^128) IDs in a SD.</p>
  
  <p>I could store only the 50000 used values but then I would have to traverse all (at worst) of them to find the one I need. Besides, it would have to be computed a 16-byte values comparison for each of them which makes it to be quite slow.</p>
  
  <p>So I think I would need some kind of (hash?) function that maps the 2^128 values to 50000 (map 16 bytes to 2 bytes). It's obvious that some of the original values will map to the same value/index. The idea is that when I get an ID, I apply a hash function which gives me an index between 0 and ~50000 (0-65535). With that index I can directly access the SD sector(s) in which the ID and its associated info is stored. As I have pointed out, that index will refer to a position of memory where various IDs will coexist due to some different IDs getting mapped to the same index value. I would have to find the correct ID but it would cost only a few comparison instead of the 50000 original ones.</p>
  
  <p>Any idea/opinion would be really appreciated.</p>
  
  <p>Thanks in advance.</p>