Index: libcxx/benchmarks/GenerateInput.h
===================================================================
--- libcxx/benchmarks/GenerateInput.h
+++ libcxx/benchmarks/GenerateInput.h
@@ -119,6 +119,16 @@
     return inputs;
 }
 
+inline std::vector<std::string> getPrefixedRandomStringInputs(size_t N) {
+    std::vector<std::string> inputs;
+    constexpr int kSuffixLength = 32;
+    const std::string prefix = getRandomString(1024 - kSuffixLength);
+    for (size_t i=0; i < N; ++i) {
+        inputs.push_back(prefix + getRandomString(kSuffixLength));
+    }
+    return inputs;
+}
+
 inline std::vector<std::string> getSortedStringInputs(size_t N) {
     std::vector<std::string> inputs = getRandomStringInputs(N);
     std::sort(inputs.begin(), inputs.end());
Index: libcxx/benchmarks/unordered_set_operations.bench.cpp
===================================================================
--- libcxx/benchmarks/unordered_set_operations.bench.cpp
+++ libcxx/benchmarks/unordered_set_operations.bench.cpp
@@ -202,6 +202,17 @@
     std::unordered_set<std::string>{},
     getRandomStringInputs)->Arg(TestNumInputs);
 
+// Prefixed String //
+BENCHMARK_CAPTURE(BM_InsertValue,
+    unordered_set_prefixed_string,
+    std::unordered_set<std::string>{},
+    getPrefixedRandomStringInputs)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_InsertValueRehash,
+    unordered_set_prefixed_string,
+    std::unordered_set<std::string>{},
+    getPrefixedRandomStringInputs)->Arg(TestNumInputs);
+
 //----------------------------------------------------------------------------//
 //                         BM_Find
 // ---------------------------------------------------------------------------//
@@ -287,6 +298,17 @@
     std::unordered_set<std::string>{},
     getRandomStringInputs)->Arg(TestNumInputs);
 
+// Prefixed String //
+BENCHMARK_CAPTURE(BM_Find,
+    unordered_set_prefixed_string,
+    std::unordered_set<std::string>{},
+    getPrefixedRandomStringInputs)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_FindRehash,
+    unordered_set_prefixed_string,
+    std::unordered_set<std::string>{},
+    getPrefixedRandomStringInputs)->Arg(TestNumInputs);
+
 //----------------------------------------------------------------------------//
 //                         BM_Rehash
 // ---------------------------------------------------------------------------//
@@ -310,6 +332,10 @@
     unordered_set_string,
     std::unordered_set<std::string>{},
     getRandomStringInputs)->Arg(TestNumInputs);
+BENCHMARK_CAPTURE(BM_InsertDuplicate,
+    unordered_set_prefixed_string,
+    std::unordered_set<std::string>{},
+    getPrefixedRandomStringInputs)->Arg(TestNumInputs);
 
 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
     unordered_set_int,
@@ -319,6 +345,10 @@
     unordered_set_string,
     std::unordered_set<std::string>{},
     getRandomStringInputs)->Arg(TestNumInputs);
+BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
+    unordered_set_prefixed_string,
+    std::unordered_set<std::string>{},
+    getPrefixedRandomStringInputs)->Arg(TestNumInputs);
 
 BENCHMARK_CAPTURE(BM_InsertDuplicate,
     unordered_set_int_insert_arg,
Index: libcxx/include/__hash_table
===================================================================
--- libcxx/include/__hash_table
+++ libcxx/include/__hash_table
@@ -1809,10 +1809,12 @@
         if (__ndptr != nullptr)
         {
             for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
-                                             std::__constrain_hash(__ndptr->__hash(), __bc) == __chash;
+                    (__ndptr->__hash() == __hash ||
+                     std::__constrain_hash(__ndptr->__hash(), __bc) == __chash);
                                                      __ndptr = __ndptr->__next_)
             {
-                if (key_eq()(__ndptr->__upcast()->__value_, __value))
+                if ((__ndptr->__hash() == __hash) &&
+                    key_eq()(__ndptr->__upcast()->__value_, __value))
                     return __ndptr;
             }
         }
@@ -2024,7 +2026,8 @@
                 (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
                                                            __nd = __nd->__next_)
             {
-                if (key_eq()(__nd->__upcast()->__value_, __k))
+                if ((__nd->__hash() == __hash) &&
+                    key_eq()(__nd->__upcast()->__value_, __k))
                     goto __done;
             }
         }