diff --git a/libcxx/benchmarks/GenerateInput.h b/libcxx/benchmarks/GenerateInput.h
--- a/libcxx/benchmarks/GenerateInput.h
+++ b/libcxx/benchmarks/GenerateInput.h
@@ -111,6 +111,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());
diff --git a/libcxx/benchmarks/unordered_set_operations.bench.cpp b/libcxx/benchmarks/unordered_set_operations.bench.cpp
--- a/libcxx/benchmarks/unordered_set_operations.bench.cpp
+++ b/libcxx/benchmarks/unordered_set_operations.bench.cpp
@@ -178,6 +178,17 @@
 BENCHMARK_CAPTURE(BM_InsertValueRehash, unordered_set_string, 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
 // ---------------------------------------------------------------------------//
@@ -259,6 +270,15 @@
 BENCHMARK_CAPTURE(BM_FindRehash, unordered_set_string, 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
 // ---------------------------------------------------------------------------//
diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table
--- a/libcxx/include/__hash_table
+++ b/libcxx/include/__hash_table
@@ -1623,10 +1623,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;
             }
         }
@@ -1835,7 +1837,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;
             }
         }