Hashing Pointers

For as long as I’ve understood object-oriented programming, I’ve had an ambivalent relationship with C++. On the one hand, it promised the low-level control and performance of C, but, on the other, it also had many pitfalls that did not exist in other high-level managed languages like Java. I would often find myself in a position where I wouldn’t be sure exactly what the compiler would do under-the-hood. For example, when passing around objects by value would the compiler be “smart” enough to know that it can rip out the guts of an object instead of making an expensive copy? Granted, much of my uncomfortableness could have been remedied by a better understanding of the language specification. But why should I have to read an ~800 page specification just to understand what the compiler is allowed to do? The template engine and the STL are incredibly powerful, but it can make code just as verbose as Java, one of Java’s primary criticisms. Therefore, I found myself gravitating toward more “purely” object-oriented languages, like Java, when a project fit with that type of abstraction, and falling back to C when I needed absolute control and speed.

A couple years ago, around the time when compilers started having full support for C++11, I started a project that was tightly coupled to the LLVM codebase, which was written in C++. Therefore, I slowly started to learn about C++11’s features. I now completely agree with Stroustrup: It’s best to think of C++11 like a completely new language. Features like move semantics give the programmer complete control over when the compiler is able to move the guts of objects. The new auto type deduction keyword gets rid of a significant amount of verbosity, and makes work with complex templates much easier. Coupled with the new decltype keyword, refactoring object member variable types becomes a breeze. STL threads now make porting concurrent code much easier. That’s not to mention syntactic sugar like ranged for statements, constructor inheritance, and casting keywords. And C++ finally has lambdas! C++11 seems to be a bigger leap forward from C++03 than even Java 1.5 (with its addition of generics) was to its predecessor.

As an example, I recently needed an unordered hash map where the keys were all pointers. For example,

std::unordered_map<char*,bool> foo;

I wanted the keys to be hashed based upon the memory addresses of the character pointers, not the actual strings. This is similar to Java’s concept of an IdentityHashMap. Unfortunately, the STL does not have a built-in hash function for pointers. So I created one thusly:

/* for SIZE_MAX and UINTPTR_MAX: */
#include <cstdint>
namespace hashutils {
  /* hash any pointer */
  template<typename T>
  struct PointerHash {
    inline size_t operator()(const T* pointer) const {
      auto addr = reinterpret_cast<uintptr_t>(pointer);
#if SIZE_MAX < UINTPTR_MAX
      /* size_t is not large enough to hold the pointer's memory address */
      addr %= SIZE_MAX; /* truncate the address so it is small enough to fit in a size_t */
#endif
      return addr;
    }
  };
}

Note that I am using auto here to reduce verbosity, since it is evident that addr is a uintptr_t from the righthand side of the assignment. The hashutils::PointerHash object allows me to do this:

std::unordered_map<char*,bool,hashutils::PointerHash<char>> foo;

The neat part is that C++11 has a new using keyword that essentially lets me generically alias that definition:

template<typename K,typename V>
using unordered_pointer_map = std::unordered_map<K,V,hashutils::PointerHash<typename std::remove_pointer<K>::type>>;

unordered_pointer_map<char*,bool> foo;

Note the use of std::remove_pointer<_>, a great new STL template that gets the base type of a pointer.

In another instance, I wanted to have a hash map where the keys were pointers, but the hash was based off of the dereferenced version of the keys. This can be useful, e.g., if you need to hash a bunch of objects that are stored on the heap, or whose memory is managed outside of the current scope. This, too, was easy to implement:

namespace hashutils {
  template<typename T>
  inline size_t hash(const T& v) {
    return std::hash<T>()(v);
  }

  /* hash based off of a pointer dereference */
  template<typename T>
  struct PointerDereferenceHash {
    inline size_t operator()(const T& pointer) const {
      return hash(*pointer);
    }
  };

  /* equality based off of pointer dereference */
  template<typename T>
  struct PointerDereferenceEqualTo {
    inline bool operator()(const T& lhs, const T& rhs) const {
      return *lhs == *rhs;
    }
  };

  template<typename K,typename V>
  using unordered_pointer_dereference_map = std::unordered_map<K,V,PointerDereferenceHash<K>,PointerDereferenceEqualTo<K>>;
}

Note that, through the magic of the C++ template engine, this code supports keys that are pure pointers as well as C++11’s new smart pointers.

As another example of the afforementioned auto keyword and ranged for statements, this is how easy it is in C++11 to hash an entire collection (e.g., a std::vector or std::set):

namespace hashutils {
  class HashCombiner {
  private:
    size_t h;
  public:
    HashCombiner() : h(0) {}
    template <class T>
    inline HashCombiner& operator<<(const T& obj) {
      /* adapted from boost::hash_combine */
      h ^= hash(obj) + 0x9e3779b9 + (h << 6) + (h >> 2);
      return *this;
    }
    operator size_t() const { return h; }
  };

  /* hash any container */
  template<typename T>
  struct ContainerHash {
    size_t operator()(const T& v) const {
      HashCombiner h;
      for(const auto& e : v) {
        h << e;
      }
      return h;
    }
  };
}

Then, to make all sets hashable (and thereby valid to be used as keys in a map), simply add this:

namespace std {
  template<typename... T>
  struct hash<set<T...>> : hashutils::ContainerHash<set<T...>> {};
}

I realize that this post is a collection of rather mundane code snippets that are nowhere near a comprehensive representation of the new language features. Nevertheless, I hope that they will give you as much hope and excitement as they have given me, and perhaps inspire you to (re)visit this “new” language called C++11.