Which is the fastest hashing method … and has O(1) complexity?
Well, the fastest hash might be just taking the first eight bytes of our data to produce a hash. But that is likely to create lots of collisions where the first eight bytes are the same, such as “Edinburgh123” and “Edinburgh99”. A stronger method is to sample bytes, and merge these into a 64-byte hash. The complexity is then O(1), as it doesn’t matter how much data we have, as we just have to sample bytes at certain locations.
One method of sampling bytes is he o1hash and which was created by Wang Yi. Overall is a quick-and-dirty approach and which can be used within fast hash tables. For this we can have any size of data object, and then we just sample the bytes at given location, and produce a hash value for our lookup.
Overall o1hash samples the first, middle and last four bytes in order to produce the hash. These are merged to produce a 64-bit hash, by converting the values into an unsigned integer, and then adding the first and last value, and then multiplying by the middle value:
first=first four bytes of key;
middle=middle four bytes of key;
last=last four bytes of key;
hash= (uint64_t)(first+last)*middle;A collision is not difficult to create, as we just have to make sure that the first four bytes, the middle four bytes and the last four bytes are the…
