Add folly::hasher support for floating point types

Summary:
Move `folly::hasher` closer to feature parity with `std::hash`.
This is in order to replace some instances of `folly::hash::hash_combine(...)` with `folly::Hash()(...)` (`std::hash` is the identity for integers, which makes it an unsafe default for more sophisticated hash data structures, including open-addressing hash tables).

The implementation is similar to `libstdc++`'s implementation, in that we handle separately the `0` case, because `0` and `-0` have different binary representations but are equal according to `operator==`, and hash the bytes otherwise. It is probably a little faster than `libstdc++`'s implementation, that delegates a out-of-line Murmur hash routine for arbitrary buffers, while this uses a minimal inlineable machine word hashing routine.

Reviewed By: yfeldblum

Differential Revision: D6410713

fbshipit-source-id: 86d9e4ed8da04fffe283949825852e539ec7d5cf

diff --git a/folly/hash/Hash.h b/folly/hash/Hash.h
index 5253975a4a8f70998a88dc604bdf8fae8c1e7058..8f0743dea541f2d1d64b1c92065161b21e8c0515 100644 (file)
--- a/folly/hash/Hash.h
+++ b/folly/hash/Hash.h
@@ -371,11 +371,12 @@ inline uint32_t hsieh_hash32_str(const std::string& str) {
 } // namespace hash
 
 namespace detail {
 } // namespace hash
 
 namespace detail {

+

 struct integral_hasher {
   template <typename I>
   size_t operator()(I const& i) const {
 struct integral_hasher {
   template <typename I>
   size_t operator()(I const& i) const {

-    static_assert(sizeof(I) <= 8, "input type is too wide");
-    if (sizeof(I) <= 4) { // the branch taken is known at compile time
+    static_assert(sizeof(I) <= 8, "Input type is too wide");
+    /* constexpr */ if (sizeof(I) <= 4) {

       auto const i32 = static_cast<int32_t>(i); // impl accident: sign-extends
       auto const u32 = static_cast<uint32_t>(i32);
       return static_cast<size_t>(hash::jenkins_rev_mix32(u32));
       auto const i32 = static_cast<int32_t>(i); // impl accident: sign-extends
       auto const u32 = static_cast<uint32_t>(i32);
       return static_cast<size_t>(hash::jenkins_rev_mix32(u32));


@@ -385,6 +386,28 @@ struct integral_hasher {
     }
   }
 };
     }
   }
 };

+
+struct float_hasher {
+  template <typename F>
+  size_t operator()(F const& f) const {
+    static_assert(sizeof(F) <= 8, "Input type is too wide");
+
+    if (f == F{}) { // Ensure 0 and -0 get the same hash.
+      return 0;
+    }
+
+    /* constexpr */ if (sizeof(F) <= 4) {
+      uint32_t u32 = 0;
+      memcpy(&u32, &f, sizeof(F));
+      return static_cast<size_t>(hash::jenkins_rev_mix32(u32));
+    } else {
+      uint64_t u64 = 0;
+      memcpy(&u64, &f, sizeof(F));
+      return static_cast<size_t>(hash::twang_mix64(u64));
+    }
+  }
+};
+

 } // namespace detail
 
 template <class Key, class Enable = void>
 } // namespace detail
 
 template <class Key, class Enable = void>


@@ -443,6 +466,12 @@ struct hasher<signed char> : detail::integral_hasher {};
 template <> // char is a different type from both signed char and unsigned char
 struct hasher<char> : detail::integral_hasher {};
 
 template <> // char is a different type from both signed char and unsigned char
 struct hasher<char> : detail::integral_hasher {};
 

+template <>
+struct hasher<float> : detail::float_hasher {};
+
+template <>
+struct hasher<double> : detail::float_hasher {};
+

 template <> struct hasher<std::string> {
   size_t operator()(const std::string& key) const {
     return static_cast<size_t>(
 template <> struct hasher<std::string> {
   size_t operator()(const std::string& key) const {
     return static_cast<size_t>(

diff --git a/folly/hash/test/HashTest.cpp b/folly/hash/test/HashTest.cpp
index 68627002607204669c279df08d2adbe1328e9186..f0eb6b85718b4085d78c23dd9d927c1ec701764f 100644 (file)
--- a/folly/hash/test/HashTest.cpp
+++ b/folly/hash/test/HashTest.cpp
@@ -217,6 +217,24 @@ TEST(Hash, integral_types) {
   EXPECT_EQ(24, hashes.size());
 }
 
   EXPECT_EQ(24, hashes.size());
 }
 

+TEST(Hash, float_types) {
+  folly::Hash hasher;
+
+  EXPECT_EQ(hasher(0.0f), hasher(-0.0f));
+  EXPECT_EQ(hasher(0.0), hasher(-0.0));
+
+  // Basically just confirms that things compile ok.
+  std::unordered_set<size_t> hashes;
+  hashes.insert(hasher(0.0f));
+  hashes.insert(hasher(0.1f));
+  hashes.insert(hasher(0.2));
+  hashes.insert(hasher(0.2f));
+  hashes.insert(hasher(-0.3));
+  hashes.insert(hasher(-0.3f));
+
+  EXPECT_EQ(6, hashes.size());
+}
+

 // Not a full hasher since only handles one type
 class TestHasher {
  public:
 // Not a full hasher since only handles one type
 class TestHasher {
  public: