What is the fastest hash function for pointers?

Question

Hash table based containers are very fast associative array (e.g. `unordered_map`, `unordered_set`). Their performance is highly dependent on that hash function used to create an index for each entry. As hash tables grow, elements are rehashed again and again. Pointers are simple type, basically a 4/8 byte value that uniquely identify an object. The problem is that using an address as a result of the hash function is not efficient due to several LSB being zero. Example: ``` struct MyVoidPointerHash { size_t operator()(const void* val) const { return (size_t)val; } }; ``` A faster implementation is to lose a few bits: ``` struct MyVoidPointerHash2 { size_t operator()(const void* val) const { return ((size_t)val) >> 3; // 3 on 64 bit, 1 on 32 bit } }; ``` The latter produced 10-20% performance increase on a large application that uses hash sets and maps with tens of thousands of elements that are frequently built and cleared. Can someone offer a better scheme for hashing pointers? The f…

Accepted Answer

After letting this question lay for a while, I'll post my best hash function for pointers so far:

```
template<typename Tval>
struct MyTemplatePointerHash1 {
    size_t operator()(const Tval* val) const {
        static const size_t shift = (size_t)log2(1 + sizeof(Tval));
        return (size_t)(val) >> shift;
    }
};
```

It's high performing for various block sizes. If someone has a better function, I'll change the accepted answer.

What is the fastest hash function for pointers?

Solution

Problem