[libc++] Don't call key_eq in unordered_map/set rehashing routine

[itrofimow]

Summary

As of now containers key_eq might get called when rehashing happens, which is redundant for unique keys containers.

[itrofimow]

+ clang-format

[jloser]

I recommend against clang-format everywhere here. When uploading the patch, you can specify --nolint to arc so it won't complain about the lack of clang-formatting a particular changeset. The noise ratio compared with the actual content change here is high in my opinion.

[itrofimow]

In D128021#3591054, @jloser wrote:

I recommend against clang-format everywhere here. When uploading the patch, you can specify --nolint to arc so it won't complain about the lack of clang-formatting a particular changeset. The noise ratio compared with the actual content change here is high in my opinion.

Thanks for the suggestion, i definitely will follow - clang-format goes crazy with these files

[philnik]

I agree with @jloser that this is a lot of noise. Please either ignore clang-format for now or provide a patch to only reformat the parts you change here and rebase this patch. More important for now: Please provide appropriate benchmarks in libcxx/benchmarks for this if we don't have any and provide the benchmark results.

[Mordante]

Thanks for your contribution! I'll have another look after all comment have been addressed.

libcxx/include/__hash_table

863

Can you add some comment why these traits are needed? The reason is in the commit message, but not in the code.

865

Nowadays we tend to use using instead of typedef. This works for all supported compilers in C++98/C++03 mode.

868

I'm not fond of name _Traits it very generic. How about _UniqueKeys?

libcxx/include/unordered_map

1051

As an extension we add unordered_map to C++03.

[itrofimow]

cleanup, + benchmarks

[jloser]

libcxx/include/__hash_table

862

Nit: s/reduntand/redundant

868

FWIW, I personally preferred the traits class name holding a (member or type) to denote the one trait of interest: unique_keys. I don't feel too strongly, but I feel it leads to a more open design generally.

2281–2288

Question: what's the libc++ stance for something like this which could be if constexpr in C++17 or later? Is it worth writing

#if _LIBCPP_STD_VER >= 17
if constexpr
#else
if
#endif
(!UniqueKeys::Value) {

I suspect the answer is just writing if for all standards modes and just letting the compiler realize it's always a constant value now up-front.

[itrofimow]

libcxx/benchmarks/unordered_set_operations.bench.cpp

346

This is with the patch:
BM_Rehash/unordered_set_string_arg/1024 44848 ns 44846 ns 96172

This is on trunk:
BM_Rehash/unordered_set_string_arg/1024 55711 ns 55706 ns 74198

full output: https://pastebin.com/7DMcNTna

This benchmark doesn't mean there is an immense speedup in rehashing, it just shows that there is a speedup - max_load_factor(3) was used to be sure that there will be collisions and key_eq branch in rehashing would be hit. So this just measures how long it takes to compare long random strings, but with the patch we don't compare them at all.

[itrofimow]

Can some please help me with clang-format builds failing?
This is what i used to update the patch arc diff HEAD~ --update D128021 --nolint, but format build are still failing.
What should i do to fix that?

[philnik]

This looks pretty good so far, but I'd like to see a full set of benchmarks before approving. BTW it's really stupid that we have all the member function definitions out of line. It makes this diff so much larger than it needs to be.

In D128021#3593737, @itrofimow wrote:

Can some please help me with clang-format builds failing?
This is what i used to update the patch arc diff HEAD~ --update D128021 --nolint, but format build are still failing.
What should i do to fix that?

You can ignore the clang-format runner. It's just soft-failing. Your problem with the CI currently is that you've got some non-ASCII symbols in your patch. That's why Generated output fails.

libcxx/benchmarks/ContainerBenchmarks.h

143

benchmark::DoNotOptimize(c) should be more than enough. This doesn't allow the compiler to optimize anything from the container.

libcxx/benchmarks/unordered_set_operations.bench.cpp

346

Could you provide the results of a full set of input data (i.e. elements other than string and other sizes)? I don't think you cherry-picked, but having only a single data point smells like it. Since this patch also affects unordered_map, unordered_multimap and unordered_multiset I'd also like to see benchmarks for those (the multi-version are optional, but a nice to have).

libcxx/include/__hash_table

861–862

I don't think this is necessary. Just use integral_constant<bool, {true, false}> where __hash_table is used or use a NTTP instead.

2281–2288

It's definitely not worth it. This makes the code a lot less readable for a minor to non-existent improvement in compile times.

2281–2288

Could you indent this properly?

[Mordante]

One request, when you address a review comment, can you check the "done" button this makes reviewing easier.

I had a look at the changes and I'm wondering about the impact on the size of the binary. You add one template argument to "only" adjust the __rehash function. This means the __hash_table for unordered_map<K, V> and unordered_multimap<K, V> will be different after this change. Could you provide some numbers regarding how much the binary will grow when an applications uses both unordered_map<K, V> and unordered_multimap<K, V>`?

libcxx/include/__hash_table

2281–2288

Question: what's the libc++ stance for something like this which could be if constexpr in C++17 or later? Is it worth writing

#if _LIBCPP_STD_VER >= 17
if constexpr
#else
if
#endif
(!UniqueKeys::Value) {

I suspect the answer is just writing if for all standards modes and just letting the compiler realize it's always a constant value now up-front.

There's no need for the #if LIBCPP_STD_VER >= 17, if _LIBCPP_CONSTEXPR_AFTER_CXX14 (!UniqueKeys::Value) { should work.

libcxx/include/ext/hash_map

494

There's no need for std:: here.

[itrofimow]

Thank you guys for the valuable feedback. I'll get back to this near the end of the upcoming week

[itrofimow]

code review fixes

[itrofimow]

So i got some benchmarks: unordered_set_benches

And they didn't make any sense for BM_FindRehash: how could my changes affect it that much, when they don't even touch ::find?
After some profiling i found out that branch misprediction in std::equal_to increases up to x2 from ~11% to 23%, with overall mispediction being close to 4%.

Changing initial rehash in BM_FindRehash from 8 to 7 leads to this: unordered_set_benches, which is what i expected to be,
but i still have no idea what happens in original version.

libcxx/include/__hash_table

861–862

I feel like that would make __hash_table usage way less readable: is true self explanatory enough in __hash_table<Key, Hash, Eq, Alloc, true>?

libcxx/include/ext/hash_map

494

doesn't compile without it

[itrofimow]

In D128021#3593922, @Mordante wrote:

One request, when you address a review comment, can you check the "done" button this makes reviewing easier.

I had a look at the changes and I'm wondering about the impact on the size of the binary. You add one template argument to "only" adjust the __rehash function. This means the __hash_table for unordered_map<K, V> and unordered_multimap<K, V> will be different after this change. Could you provide some numbers regarding how much the binary will grow when an applications uses both unordered_map<K, V> and unordered_multimap<K, V>`?

Would this example be enough?
I could've messed up compile flags, and guidance would be appreciated if i did so

[Mordante]

In D128021#3603708, @itrofimow wrote:

In D128021#3593922, @Mordante wrote:

Would this example be enough?
I could've messed up compile flags, and guidance would be appreciated if i did so

Thanks! Can you provide the output of the size command instead of the ls command for both binaries?

[itrofimow]

In D128021#3603897, @Mordante wrote:

In D128021#3603708, @itrofimow wrote:

In D128021#3593922, @Mordante wrote:

Would this example be enough?
I could've messed up compile flags, and guidance would be appreciated if i did so

Thanks! Can you provide the output of the size command instead of the ls command for both binaries?

root@adelaide:~/tmp# size binary_size_*

 text	   data	    bss	    dec	    hex	filename
10109	    744	      8	  10861	   2a6d	binary_size_main
11334	    744	      8	  12086	   2f36	binary_size_patch

[itrofimow]

Gently pinging this

[Mordante]

In D128021#3604428, @itrofimow wrote:

In D128021#3603897, @Mordante wrote:

In D128021#3603708, @itrofimow wrote:

In D128021#3593922, @Mordante wrote:

Would this example be enough?
I could've messed up compile flags, and guidance would be appreciated if i did so

Thanks! Can you provide the output of the size command instead of the ls command for both binaries?

root@adelaide:~/tmp# size binary_size_*

 text	   data	    bss	    dec	    hex	filename
10109	    744	      8	  10861	   2a6d	binary_size_main
11334	    744	      8	  12086	   2f36	binary_size_patch

Thanks. This gives more insight. For the ls the patched version is smaller, but here patched version is bigger; which matches my expectations. I'm not happy with the 1 KB increment of the text size. This price will be paid for every type.

I want to have a closer look at this myself and see whether there's a better solution that gives the performance improvement with a smaller text size overhead.

libcxx/benchmarks/ContainerBenchmarks.h

140

Please don't use auto when the type isn't clear, same for the bucket_count.

[Mordante]

I had a look at the code and I wonder whether a different approach might be better. Instead of adding a template argument we change __rehash to two function __rehash_unique and __rehash_multi. This seems the approach already taken for other functions in the __hash_table class.

This means the public functions rehash and resize also need two versions. The other functions calling rehash are already specific for unique and multi. I think we can keep the unique key argument on these rehash functions. So I would suggest something along the lines of.

// These were rehash, keep them public and adjust the callers
_LIBCPP_INLINE_VISIBILITY void __rehash_unique(size_type __n) { __rehash<true>(__n); }
_LIBCPP_INLINE_VISIBILITY void __rehash_multi(size_type __n) { __rehash<false>(__n); }

// These were reserve, keep them public and adjust the callers
_LIBCPP_INLINE_VISIBILITY void __reserve_unique(size_type __n)
      {__rehash_unique(static_cast<size_type>(ceil(__n / max_load_factor())));}                                              
_LIBCPP_INLINE_VISIBILITY void __reserve_multi(size_type __n)
      {__rehash_multi(static_cast<size_type>(ceil(__n / max_load_factor())));}


// rename __rehash to __do_rehash and make it templated
template<class _UniqueKeys>
void __do_rehash(size_type __n);

// rename rehash to __rehash, make it private and make it templated
template<class _UniqueKeys>
void __rehash(size_type __n);

Then we can keep the templated rehashing you added but only have the template arguments on these two function instead of the entire class.

WDYT?

[itrofimow]

In D128021#3613221, @Mordante wrote:

I had a look at the code and I wonder whether a different approach might be better. Instead of adding a template argument we change __rehash to two function __rehash_unique and __rehash_multi. This seems the approach already taken for other functions in the __hash_table class.

This means the public functions rehash and resize also need two versions. The other functions calling rehash are already specific for unique and multi. I think we can keep the unique key argument on these rehash functions. So I would suggest something along the lines of.

// These were rehash, keep them public and adjust the callers
_LIBCPP_INLINE_VISIBILITY void __rehash_unique(size_type __n) { __rehash<true>(__n); }
_LIBCPP_INLINE_VISIBILITY void __rehash_multi(size_type __n) { __rehash<false>(__n); }

// These were reserve, keep them public and adjust the callers
_LIBCPP_INLINE_VISIBILITY void __reserve_unique(size_type __n)
      {__rehash_unique(static_cast<size_type>(ceil(__n / max_load_factor())));}                                              
_LIBCPP_INLINE_VISIBILITY void __reserve_multi(size_type __n)
      {__rehash_multi(static_cast<size_type>(ceil(__n / max_load_factor())));}


// rename __rehash to __do_rehash and make it templated
template<class _UniqueKeys>
void __do_rehash(size_type __n);

// rename rehash to __rehash, make it private and make it templated
template<class _UniqueKeys>
void __rehash(size_type __n);

Then we can keep the templated rehashing you added but only have the template arguments on these two function instead of the entire class.

WDYT?

If binary size is a concern i definitely like this approach more

[itrofimow]

review fixes, updated benchmarks (https://pastebin.com/raw/AF0fa9VJ)

[itrofimow]

libcxx/benchmarks/ContainerBenchmarks.h

140

Type here differs for different benchmark registrations, so it would be some decltype otherwise.

I could change bucket_count to be a size_t if you insist, but i feel like it's not only clearly size_t, but also the same type rehash takes anyway

libcxx/benchmarks/unordered_set_operations.bench.cpp

346

Strangely enough i couldn't find any unordered_map/multimap/multiset benchmarks, and i'm not sure i am familiar enough with this codebase to write a comprehensive ones from scratch

[itrofimow]

Trying to force a rebuild

[Mordante]

I think this patch is getting close to be done!

I see some small issues.
Can you provide the new binary sizes, I would like to see the overhead of this new approach.
Can you upload the patch with the complete context? Without context it's hard to validate whether the changes to unordered_set and unordered_map are correct. (I assume they are, but I want to validate.)

libcxx/benchmarks/unordered_set_operations.bench.cpp

110

This function is confusion. It's called slow, but when the sizes don't match they function bails out quickly. Else it compares all elements. Some comment would be helpful.

114

please put eq &= lhs[i] == rhs[i]; on its own line.

libcxx/include/__hash_table

1155

please us __ugly function names.

[itrofimow]

binary size after changes: https://pastebin.com/raw/z23mLN93

[Mordante]

In D128021#3627047, @itrofimow wrote:

binary size after changes: https://pastebin.com/raw/z23mLN93

 text	   data	    bss	    dec	    hex	filename
10323	    744	      8	  11075	   2b43	binary_size_main
10996	    744	      8	  11748	   2de4	binary_size_patch

Thanks! I like these numbers better! This about half of the size overhead of the previous version.
I assume the main values have changed due to rebasing, right?

[itrofimow]

In D128021#3627048, @Mordante wrote:

In D128021#3627047, @itrofimow wrote:

binary size after changes: https://pastebin.com/raw/z23mLN93

 text	   data	    bss	    dec	    hex	filename
10323	    744	      8	  11075	   2b43	binary_size_main
10996	    744	      8	  11748	   2de4	binary_size_patch

Thanks! I like these numbers better! This about half of the size overhead of the previous version.
I assume the main values have changed due to rebasing, right?

I did rebase, however i think main values changed due to me compiling on a different machine.
Not sure if i understand the size command output completely, but this time binary takes only ~150 bytes more on disk versus ~4.5Kb in the previous version

Smh about losing context - updated the patch via web interface, will fix remaining issues and upload the patch via arc this time

[itrofimow]

cr fixes

[itrofimow]

rebase on main

[Mordante]

In D128021#3627069, @itrofimow wrote:

In D128021#3627048, @Mordante wrote:

In D128021#3627047, @itrofimow wrote:

binary size after changes: https://pastebin.com/raw/z23mLN93

 text	   data	    bss	    dec	    hex	filename
10323	    744	      8	  11075	   2b43	binary_size_main
10996	    744	      8	  11748	   2de4	binary_size_patch

Thanks! I like these numbers better! This about half of the size overhead of the previous version.
I assume the main values have changed due to rebasing, right?

I did rebase, however i think main values changed due to me compiling on a different machine.
Not sure if i understand the size command output completely, but this time binary takes only ~150 bytes more on disk versus ~4.5Kb in the previous version

The size command gives more insight in the real binary size. The file on disk contains a lot of additional information, like debug information, information needed for the dynamic linker, etc.

LGTM modulo some small nits. I'll leave the final approval to @philnik.

libcxx/benchmarks/ContainerBenchmarks.h

140

I think it's good to use real types when possible.

libcxx/benchmarks/unordered_set_operations.bench.cpp

113

Thanks this clarifies it!
You could consider adding an assert that the sizes are equal.

[philnik]

LGTM.

libcxx/benchmarks/ContainerBenchmarks.h

static void BM_FindRehash(benchmark::State& st, Container c, GenInputs gen) {
     while (st.KeepRunning()) {
         for (auto it = in.data(); it != end; ++it) {
             benchmark::DoNotOptimize(&(*c.find(*it)));
         }
         benchmark::ClobberMemory();
     }
 }
 
+template <class Container, class GenInputs>
+static void BM_Rehash(benchmark::State& st, Container c, GenInputs gen) {
+    auto in = gen(st.range(0));
+    c.max_load_factor(3.0);
+    c.insert(in.begin(), in.end());
+    benchmark::DoNotOptimize(c);
+    const auto bucket_count = c.bucket_count();
+    while (st.KeepRunning()) {
+        c.rehash(bucket_count + 1);
+        c.rehash(bucket_count);
+        benchmark::ClobberMemory();
+    }
+}
+
 } // end namespace ContainerBenchmarks
 
 #endif // BENCHMARK_CONTAINER_BENCHMARKS_H

libcxx/benchmarks/unordered_set_operations.bench.cpp

 struct UInt64Hash2 {
   UInt64Hash2() = default;
   inline TEST_ALWAYS_INLINE
   std::size_t operator()(uint64_t data) const {
       return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
   }
 };
 
+// The sole purpose of this comparator is to be used in BM_Rehash, where
+// we need something slow enough to be easily noticable in benchmark results.
+// The default implementation of operator== for strings seems to be a little
+// too fast for that specific benchmark to reliably show a noticeable
+// improvement, but unoptimized bytewise comparison fits just right.
+// Early return is there just for convenience, since we only compare strings
+// of equal length in BM_Rehash.
+struct SlowStringEq {
+  SlowStringEq() = default;
+  inline TEST_ALWAYS_INLINE
+  bool operator()(const std::string& lhs, const std::string& rhs) const {
+      if (lhs.size() != rhs.size()) return false;
+
+      bool eq = true;
+      for (size_t i = 0; i < lhs.size(); ++i) {
+          eq &= lhs[i] == rhs[i];
+      }
+      return eq;
+  }
+};
+
 //----------------------------------------------------------------------------//
 //                               BM_Hash
 // ---------------------------------------------------------------------------//
 
 template <class HashFn, class GenInputs>
 void BM_Hash(benchmark::State& st, HashFn fn, GenInputs gen) {
     auto in = gen(st.range(0));
     const auto end = in.data() + in.size();
BENCHMARK_CAPTURE(BM_Find,
     std::unordered_set<std::string>{},
     getRandomStringInputs)->Arg(TestNumInputs);
 
 BENCHMARK_CAPTURE(BM_FindRehash,
     unordered_set_string,
     std::unordered_set<std::string>{},
     getRandomStringInputs)->Arg(TestNumInputs);
 
+//----------------------------------------------------------------------------//
+//                         BM_Rehash
+// ---------------------------------------------------------------------------//
+
+BENCHMARK_CAPTURE(BM_Rehash,
+    unordered_set_string_arg,
+    std::unordered_set<std::string, std::hash<std::string>, SlowStringEq>{},
+    getRandomStringInputs)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_Rehash,
+    unordered_set_int_arg,
+    std::unordered_set<int>{},
+    getRandomIntegerInputs<int>)->Arg(TestNumInputs);
+
 ///////////////////////////////////////////////////////////////////////////////
 BENCHMARK_CAPTURE(BM_InsertDuplicate,
     unordered_set_int,
     std::unordered_set<int>{},
     getRandomIntegerInputs<int>)->Arg(TestNumInputs);
 BENCHMARK_CAPTURE(BM_InsertDuplicate,
     unordered_set_string,
     std::unordered_set<std::string>{},
BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
     std::unordered_set<int>{},
     getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs);
 
 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
     unordered_set_string_arg,
     std::unordered_set<std::string>{},
     getRandomCStringInputs)->Arg(TestNumInputs);
 
 BENCHMARK_MAIN();

libcxx/include/__hash_table

 __diagnose_unordered_container_requirements(int);
 
 // This dummy overload is used so that the compiler won't emit a spurious
 // "no matching function for call to __diagnose_unordered_xxx" diagnostic
 // when the overload above causes a hard error.
 template <class _Key, class _Hash, class _Equal>
 int __diagnose_unordered_container_requirements(void*);
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 class __hash_table
 {
 public:
     typedef _Tp    value_type;
     typedef _Hash  hasher;
     typedef _Equal key_equal;
     typedef _Alloc allocator_type;
 
 private:
     typedef allocator_traits<allocator_type> __alloc_traits;
     typedef typename
       __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type
                                                                      _NodeTypes;
 public:
 
#if _LIBCPP_STD_VER > 14
     _LIBCPP_INLINE_VISIBILITY
     _NodeHandle __node_handle_extract(key_type const& __key);
     template <class _NodeHandle>
     _LIBCPP_INLINE_VISIBILITY
     _NodeHandle __node_handle_extract(const_iterator __it);
 #endif
 
     void clear() _NOEXCEPT;
-    void rehash(size_type __n);
-    _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
-        {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
+    _LIBCPP_INLINE_VISIBILITY void __rehash_unique(size_type __n) { __rehash<true>(__n); }
+    _LIBCPP_INLINE_VISIBILITY void __rehash_multi(size_type __n) { __rehash<false>(__n); }
+    _LIBCPP_INLINE_VISIBILITY void __reserve_unique(size_type __n)
+    {
+        __rehash_unique(static_cast<size_type>(ceil(__n / max_load_factor())));
+    }
+    _LIBCPP_INLINE_VISIBILITY void __reserve_multi(size_type __n)
+    {
+        __rehash_multi(static_cast<size_type>(ceil(__n / max_load_factor())));
+    }
 
     _LIBCPP_INLINE_VISIBILITY
     size_type bucket_count() const _NOEXCEPT
     {
         return __bucket_list_.get_deleter().size();
     }
 
     _LIBCPP_INLINE_VISIBILITY
#ifdef _LIBCPP_ENABLE_DEBUG_MODE
     bool __dereferenceable(const const_iterator* __i) const;
     bool __decrementable(const const_iterator* __i) const;
     bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
 
 #endif // _LIBCPP_ENABLE_DEBUG_MODE
 
 private:
-    void __rehash(size_type __n);
+    template <bool _UniqueKeys> void __rehash(size_type __n);
+    template <bool _UniqueKeys> void __do_rehash(size_type __n);
 
     template <class ..._Args>
     __node_holder __construct_node(_Args&& ...__args);
 
     template <class _First, class ..._Rest>
     __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
 
 
if (__bc != 0)
             {
                 if (key_eq()(__ndptr->__upcast()->__value_, __value))
                     return __ndptr;
             }
         }
     }
     if (size()+1 > __bc * max_load_factor() || __bc == 0)
     {
-        rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
+        __rehash_unique(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
                                      size_type(ceil(float(size() + 1) / max_load_factor()))));
     }
     return nullptr;
 }
 
 // Insert the node __nd into the container by pushing it into the right bucket,
 // and updating size(). Assumes that __nd->__hash is up-to-date, and that
 // rehashing has already occurred and that no element with the same key exists

 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(
     size_t __cp_hash, value_type& __cp_val)
 {
     size_type __bc = bucket_count();
     if (size()+1 > __bc * max_load_factor() || __bc == 0)
     {
-        rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
+        __rehash_multi(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
                        size_type(ceil(float(size() + 1) / max_load_factor()))));
         __bc = bucket_count();
     }
     size_t __chash = __constrain_hash(__cp_hash, __bc);
     __next_pointer __pn = __bucket_list_[__chash];
     if (__pn != nullptr)
     {
         for (bool __found = false; __pn->__next_ != nullptr &&
_LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
                          " referring to this unordered container");
     if (__p != end() && key_eq()(*__p, __cp->__value_))
     {
         __next_pointer __np = __p.__node_;
         __cp->__hash_ = __np->__hash();
         size_type __bc = bucket_count();
         if (size()+1 > __bc * max_load_factor() || __bc == 0)
         {
-            rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
+            __rehash_multi(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
                            size_type(ceil(float(size() + 1) / max_load_factor()))));
             __bc = bucket_count();
         }
         size_t __chash = __constrain_hash(__cp->__hash_, __bc);
         __next_pointer __pp = __bucket_list_[__chash];
         while (__pp->__next_ != __np)
             __pp = __pp->__next_;
         __cp->__next_ = __np;
if (__bc != 0)
                     goto __done;
             }
         }
     }
     {
         __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...);
         if (size()+1 > __bc * max_load_factor() || __bc == 0)
         {
-            rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
+            __rehash_unique(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
                            size_type(ceil(float(size() + 1) / max_load_factor()))));
             __bc = bucket_count();
             __chash = __constrain_hash(__hash, __bc);
         }
         // insert_after __bucket_list_[__chash], or __first_node if bucket is null
         __next_pointer __pn = __bucket_list_[__chash];
         if (__pn == nullptr)
         {
for (typename _Table::iterator __it = __source.begin();
         (void)__source.remove(__it++).release();
         __src_ptr->__hash_ = __src_hash;
         __node_insert_multi_perform(__src_ptr, __pn);
     }
 }
 #endif // _LIBCPP_STD_VER > 14
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <bool _UniqueKeys>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __n)
 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
 {
     if (__n == 1)
         __n = 2;
     else if (__n & (__n - 1))
         __n = __next_prime(__n);
     size_type __bc = bucket_count();
     if (__n > __bc)
-        __rehash(__n);
+        __do_rehash<_UniqueKeys>(__n);
     else if (__n < __bc)
     {
         __n = _VSTD::max<size_type>
               (
                   __n,
                   __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) :
                                            __next_prime(size_t(ceil(float(size()) / max_load_factor())))
               );
         if (__n < __bc)
-            __rehash(__n);
+            __do_rehash<_UniqueKeys>(__n);
     }
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <bool _UniqueKeys>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__do_rehash(size_type __nbc)
 {
     std::__debug_db_invalidate_all(this);
     __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
     __bucket_list_.reset(__nbc > 0 ?
                       __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
     __bucket_list_.get_deleter().size() = __nbc;
     if (__nbc > 0)
     {
if (__nbc > 0)
                     {
                         __bucket_list_[__chash] = __pp;
                         __pp = __cp;
                         __phash = __chash;
                     }
                     else
                     {
                         __next_pointer __np = __cp;
+                        if _LIBCPP_CONSTEXPR_AFTER_CXX14 (!_UniqueKeys)
+                        {
                             for (; __np->__next_ != nullptr &&
                                    key_eq()(__cp->__upcast()->__value_,
                                             __np->__next_->__upcast()->__value_);
                                                                __np = __np->__next_)
                                 ;
+                        }
                         __pp->__next_ = __np->__next_;
                         __np->__next_ = __bucket_list_[__chash]->__next_;
                         __bucket_list_[__chash]->__next_ = __cp;
 
                     }
                 }
             }
         }

libcxx/include/ext/hash_map

 private:
     typedef std::pair<key_type, mapped_type>                    __value_type;
     typedef __hash_map_hasher<__value_type, hasher>   __hasher;
     typedef __hash_map_equal<__value_type, key_equal> __key_equal;
     typedef typename std::__rebind_alloc_helper<
         std::allocator_traits<allocator_type>, __value_type>::type __allocator_type;
 
     typedef std::__hash_table<__value_type, __hasher,
                          __key_equal,  __allocator_type>   __table;
 
     __table __table_;
 
     typedef typename __table::__node_pointer               __node_pointer;
     typedef typename __table::__node_const_pointer         __node_const_pointer;
     typedef typename __table::__node_traits                __node_traits;
     typedef typename __table::__node_allocator             __node_allocator;
     typedef typename __table::__node                       __node;
public:
     _LIBCPP_INLINE_VISIBILITY
     size_type max_bucket_count() const {return __table_.max_bucket_count();}
 
     _LIBCPP_INLINE_VISIBILITY
     size_type elems_in_bucket(size_type __n) const
         {return __table_.bucket_size(__n);}
 
     _LIBCPP_INLINE_VISIBILITY
-    void resize(size_type __n) {__table_.rehash(__n);}
+    void resize(size_type __n) {__table_.__rehash_unique(__n);}
 
 private:
     __node_holder __construct_node(const key_type& __k);
 };
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
         size_type __n, const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
         size_type __n, const hasher& __hf, const key_equal& __eql,
         const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
         _InputIterator __first, _InputIterator __last)
 {
     insert(__first, __last);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
     insert(__first, __last);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
     insert(__first, __last);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
         const hash_map& __u)
     : __table_(__u.__table_)
 {
-    __table_.rehash(__u.bucket_count());
+    __table_.__rehash_unique(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
 {
     __node_allocator& __na = __table_.__node_alloc();
public:
     _LIBCPP_INLINE_VISIBILITY
     size_type max_bucket_count() const {return __table_.max_bucket_count();}
 
     _LIBCPP_INLINE_VISIBILITY
     size_type elems_in_bucket(size_type __n) const
         {return __table_.bucket_size(__n);}
 
     _LIBCPP_INLINE_VISIBILITY
-    void resize(size_type __n) {__table_.rehash(__n);}
+    void resize(size_type __n) {__table_.__rehash_multi(__n);}
 };
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
         size_type __n, const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
         size_type __n, const hasher& __hf, const key_equal& __eql,
         const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
         _InputIterator __first, _InputIterator __last)
 {
     insert(__first, __last);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
     insert(__first, __last);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
     insert(__first, __last);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
         const hash_multimap& __u)
     : __table_(__u.__table_)
 {
-    __table_.rehash(__u.bucket_count());
+    __table_.__rehash_multi(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 inline
 void
 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,

libcxx/include/ext/hash_set

public:
     size_type bucket_count() const {return __table_.bucket_count();}
     _LIBCPP_INLINE_VISIBILITY
     size_type max_bucket_count() const {return __table_.max_bucket_count();}
 
     _LIBCPP_INLINE_VISIBILITY
     size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
 
     _LIBCPP_INLINE_VISIBILITY
-    void resize(size_type __n) {__table_.rehash(__n);}
+    void resize(size_type __n) {__table_.__rehash_unique(__n);}
 };
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
         _InputIterator __first, _InputIterator __last)
 {
     insert(__first, __last);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
     insert(__first, __last);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
     insert(__first, __last);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
         const hash_set& __u)
     : __table_(__u.__table_)
 {
-    __table_.rehash(__u.bucket_count());
+    __table_.__rehash_unique(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 inline
 void
 hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
public:
     size_type bucket_count() const {return __table_.bucket_count();}
     _LIBCPP_INLINE_VISIBILITY
     size_type max_bucket_count() const {return __table_.max_bucket_count();}
 
     _LIBCPP_INLINE_VISIBILITY
     size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
 
     _LIBCPP_INLINE_VISIBILITY
-    void resize(size_type __n) {__table_.rehash(__n);}
+    void resize(size_type __n) {__table_.__rehash_multi(__n);}
 };
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
         size_type __n, const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
         size_type __n, const hasher& __hf, const key_equal& __eql,
         const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
         _InputIterator __first, _InputIterator __last)
 {
     insert(__first, __last);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
     insert(__first, __last);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
     insert(__first, __last);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
         const hash_multiset& __u)
     : __table_(__u.__table_)
 {
-    __table_.rehash(__u.bucket_count());
+    __table_.__rehash_multi(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 inline
 void
 hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,

libcxx/include/unordered_map

 private:
     typedef __hash_value_type<key_type, mapped_type>                          __value_type;
     typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;
     typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher>  __key_equal;
     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
                                                  __value_type>::type          __allocator_type;
 
     typedef __hash_table<__value_type, __hasher,
                          __key_equal,  __allocator_type>   __table;
 
     __table __table_;
 
     typedef typename __table::_NodeTypes                   _NodeTypes;
     typedef typename __table::__node_pointer               __node_pointer;
     typedef typename __table::__node_const_pointer         __node_const_pointer;
     typedef typename __table::__node_traits                __node_traits;
     typedef typename __table::__node_allocator             __node_allocator;
#endif
 
     _LIBCPP_INLINE_VISIBILITY
     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
     _LIBCPP_INLINE_VISIBILITY
     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
     _LIBCPP_INLINE_VISIBILITY
     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
     _LIBCPP_INLINE_VISIBILITY
-    void rehash(size_type __n) {__table_.rehash(__n);}
+    void rehash(size_type __n) {__table_.__rehash_unique(__n);}
     _LIBCPP_INLINE_VISIBILITY
-    void reserve(size_type __n) {__table_.reserve(__n);}
+    void reserve(size_type __n) {__table_.__reserve_unique(__n);}
 
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 
     bool __dereferenceable(const const_iterator* __i) const
         {return __table_.__dereferenceable(_VSTD::addressof(__i->__i_));}
     bool __decrementable(const const_iterator* __i) const
         {return __table_.__decrementable(_VSTD::addressof(__i->__i_));}
     bool __addable(const const_iterator* __i, ptrdiff_t __n) const

 #endif
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
         size_type __n, const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
         size_type __n, const hasher& __hf, const key_equal& __eql,
         const allocator_type& __a)
     : __table_(__hf, __eql, typename __table::allocator_type(__a))
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 inline
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
         const allocator_type& __a)
     : __table_(typename __table::allocator_type(__a))
 {

 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
     insert(__first, __last);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, typename __table::allocator_type(__a))
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
     insert(__first, __last);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
         const unordered_map& __u)
     : __table_(__u.__table_)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__u.bucket_count());
+    __table_.__rehash_unique(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
         const unordered_map& __u, const allocator_type& __a)
     : __table_(__u.__table_, typename __table::allocator_type(__a))
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__u.bucket_count());
+    __table_.__rehash_unique(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 inline
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(

 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
         const key_equal& __eql)
     : __table_(__hf, __eql)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
     insert(__il.begin(), __il.end());
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
         const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, typename __table::allocator_type(__a))
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
     insert(__il.begin(), __il.end());
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 inline
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
#endif // _LIBCPP_STD_VER > 17
 
     _LIBCPP_INLINE_VISIBILITY
     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
     _LIBCPP_INLINE_VISIBILITY
     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
     _LIBCPP_INLINE_VISIBILITY
     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
     _LIBCPP_INLINE_VISIBILITY
-    void rehash(size_type __n) {__table_.rehash(__n);}
+    void rehash(size_type __n) {__table_.__rehash_multi(__n);}
     _LIBCPP_INLINE_VISIBILITY
-    void reserve(size_type __n) {__table_.reserve(__n);}
+    void reserve(size_type __n) {__table_.__reserve_multi(__n);}
 
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 
     bool __dereferenceable(const const_iterator* __i) const
         {return __table_.__dereferenceable(_VSTD::addressof(__i->__i_));}
     bool __decrementable(const const_iterator* __i) const
         {return __table_.__decrementable(_VSTD::addressof(__i->__i_));}
     bool __addable(const const_iterator* __i, ptrdiff_t __n) const

 #endif
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
         size_type __n, const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
         size_type __n, const hasher& __hf, const key_equal& __eql,
         const allocator_type& __a)
     : __table_(__hf, __eql, typename __table::allocator_type(__a))
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
         _InputIterator __first, _InputIterator __last)
 {
     _VSTD::__debug_db_insert_c(this);
     insert(__first, __last);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
     insert(__first, __last);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, typename __table::allocator_type(__a))
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
     insert(__first, __last);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 inline
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
         const allocator_type& __a)
     : __table_(typename __table::allocator_type(__a))
 {
     _VSTD::__debug_db_insert_c(this);
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
         const unordered_multimap& __u)
     : __table_(__u.__table_)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__u.bucket_count());
+    __table_.__rehash_multi(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
         const unordered_multimap& __u, const allocator_type& __a)
     : __table_(__u.__table_, typename __table::allocator_type(__a))
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__u.bucket_count());
+    __table_.__rehash_multi(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 inline
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(

 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
         const key_equal& __eql)
     : __table_(__hf, __eql)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
     insert(__il.begin(), __il.end());
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
         const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, typename __table::allocator_type(__a))
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
     insert(__il.begin(), __il.end());
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 inline
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)

libcxx/include/unordered_set

#endif // _LIBCPP_STD_VER > 17
 
     _LIBCPP_INLINE_VISIBILITY
     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
     _LIBCPP_INLINE_VISIBILITY
     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
     _LIBCPP_INLINE_VISIBILITY
     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
     _LIBCPP_INLINE_VISIBILITY
-    void rehash(size_type __n) {__table_.rehash(__n);}
+    void rehash(size_type __n) {__table_.__rehash_unique(__n);}
     _LIBCPP_INLINE_VISIBILITY
-    void reserve(size_type __n) {__table_.reserve(__n);}
+    void reserve(size_type __n) {__table_.__reserve_unique(__n);}
 
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 
     bool __dereferenceable(const const_iterator* __i) const
         {return __table_.__dereferenceable(__i);}
     bool __decrementable(const const_iterator* __i) const
         {return __table_.__decrementable(__i);}
     bool __addable(const const_iterator* __i, ptrdiff_t __n) const

 #endif
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         _InputIterator __first, _InputIterator __last)
 {
     _VSTD::__debug_db_insert_c(this);
     insert(__first, __last);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
     insert(__first, __last);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
     insert(__first, __last);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 inline
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         const allocator_type& __a)
     : __table_(__a)
 {
     _VSTD::__debug_db_insert_c(this);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         const unordered_set& __u)
     : __table_(__u.__table_)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__u.bucket_count());
+    __table_.__rehash_unique(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         const unordered_set& __u, const allocator_type& __a)
     : __table_(__u.__table_, __a)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__u.bucket_count());
+    __table_.__rehash_unique(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 inline
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(

 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
         const key_equal& __eql)
     : __table_(__hf, __eql)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
     insert(__il.begin(), __il.end());
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
         const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_unique(__n);
     insert(__il.begin(), __il.end());
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 inline
 unordered_set<_Value, _Hash, _Pred, _Alloc>&
 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
#endif // _LIBCPP_STD_VER > 17
 
     _LIBCPP_INLINE_VISIBILITY
     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
     _LIBCPP_INLINE_VISIBILITY
     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
     _LIBCPP_INLINE_VISIBILITY
     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
     _LIBCPP_INLINE_VISIBILITY
-    void rehash(size_type __n) {__table_.rehash(__n);}
+    void rehash(size_type __n) {__table_.__rehash_multi(__n);}
     _LIBCPP_INLINE_VISIBILITY
-    void reserve(size_type __n) {__table_.reserve(__n);}
+    void reserve(size_type __n) {__table_.__reserve_multi(__n);}
 
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 
     bool __dereferenceable(const const_iterator* __i) const
         {return __table_.__dereferenceable(__i);}
     bool __decrementable(const const_iterator* __i) const
         {return __table_.__decrementable(__i);}
     bool __addable(const const_iterator* __i, ptrdiff_t __n) const

 #endif
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         size_type __n, const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         size_type __n, const hasher& __hf, const key_equal& __eql,
         const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         _InputIterator __first, _InputIterator __last)
 {
     _VSTD::__debug_db_insert_c(this);
     insert(__first, __last);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
     insert(__first, __last);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 template <class _InputIterator>
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         _InputIterator __first, _InputIterator __last, size_type __n,
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
     insert(__first, __last);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 inline
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         const allocator_type& __a)
     : __table_(__a)
 {
     _VSTD::__debug_db_insert_c(this);
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         const unordered_multiset& __u)
     : __table_(__u.__table_)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__u.bucket_count());
+    __table_.__rehash_multi(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         const unordered_multiset& __u, const allocator_type& __a)
     : __table_(__u.__table_, __a)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__u.bucket_count());
+    __table_.__rehash_multi(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 inline
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(

 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
         const key_equal& __eql)
     : __table_(__hf, __eql)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
     insert(__il.begin(), __il.end());
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
         const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
     _VSTD::__debug_db_insert_c(this);
-    __table_.rehash(__n);
+    __table_.__rehash_multi(__n);
     insert(__il.begin(), __il.end());
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 inline
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
         unordered_multiset&& __u)