Menu
I'm working on an electronic project with a microcontroller which is programmed in C.
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.
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.
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.
Any idea/opinion would be really appreciated.
Thanks in advance.
478
If we hash the string twice, we may derive a hash value for an arbitrary table size up to 65536. The second time the string is hashed, one is added to the first character. Then the two 8-bit hash values are concatenated together to form a 16-bit hash value.
But a good general “rule of thumb” is: The hash table should be an array with length about 1.3 times the maximum number of keys that will actually be in the table, and. Size of hash table array should be a prime number.
The most commonly used method for hashing integers is called modular hashing: we choose the array size M to be prime, and, for any positive integer key k, compute the remainder when dividing k by M. This function is very easy to compute (k % M, in Java), and is effective in dispersing the keys evenly between 0 and M-1.
The 32-bit long hash value is a hexadecimal number of 8 characters. MD4 is a Message Digest Algorithm developed by Ronald L. Rivest from RSA Data Security, Inc. Currently it's considered insecure, but it's very fast on 32-bit mashines and it's used for calculating EDonkey 2000 hashes in the EDonkey p2p network.
Simply use 16 MSB of actual id. It's dumb but with your details it will work.
157
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
