Add `HashSet<>::{Put,PutWithHash}()`.

And use it to speed up virtual method linking a bit.

Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Bug: 181943478
Change-Id: I03e931f9290d14daba07438338f9718c3b2f014f
diff --git a/libartbase/base/hash_set.h b/libartbase/base/hash_set.h
index 568d9f4..37bc5aa 100644
--- a/libartbase/base/hash_set.h
+++ b/libartbase/base/hash_set.h
@@ -529,6 +529,27 @@
     return std::make_pair(iterator(this, index), find_failed);
   }
 
+  // Insert an element known not to be in the `HashSet<>`.
+  void Put(const T& element) {
+    return PutWithHash(element, hashfn_(element));
+  }
+  void Put(T&& element) {
+    return PutWithHash(std::move(element), hashfn_(element));
+  }
+
+  template <typename U, typename = typename std::enable_if<std::is_convertible<U, T>::value>::type>
+  void PutWithHash(U&& element, size_t hash) {
+    DCHECK_EQ(hash, hashfn_(element));
+    if (num_elements_ >= elements_until_expand_) {
+      Expand();
+      DCHECK_LT(num_elements_, elements_until_expand_);
+    }
+    auto find_fail_fn = [](size_t index) { return index; };
+    size_t index = FindIndexImpl</*kCanFind=*/ false>(element, hash, find_fail_fn);
+    data_[index] = std::forward<U>(element);
+    ++num_elements_;
+  }
+
   void swap(HashSet& other) {
     // Use argument-dependent lookup with fall-back to std::swap() for function objects.
     using std::swap;
@@ -685,7 +706,7 @@
   }
 
   // Find the hash table slot for an element, or return an empty slot index if not found.
-  template <typename K, typename FailFn>
+  template <bool kCanFind = true, typename K, typename FailFn>
   size_t FindIndexImpl(const K& element, size_t hash, FailFn fail_fn) const {
     DCHECK_NE(NumBuckets(), 0u);
     DCHECK_EQ(hashfn_(element), hash);
@@ -695,7 +716,9 @@
       if (emptyfn_.IsEmpty(slot)) {
         return fail_fn(index);
       }
-      if (pred_(slot, element)) {
+      if (!kCanFind) {
+        DCHECK(!pred_(slot, element));
+      } else if (pred_(slot, element)) {
         return index;
       }
       index = NextIndex(index);
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index 0878667..aa779f3 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -7816,8 +7816,9 @@
   DCHECK_GE(super_vtable_length, mirror::Object::kVTableLength);
   for (uint32_t i = 0; i != mirror::Object::kVTableLength; ++i) {
     size_t hash = class_linker_->object_virtual_method_hashes_[i];
-    bool inserted = super_vtable_signatures.InsertWithHash(i, hash).second;
-    DCHECK(inserted);  // No duplicate signatures in `java.lang.Object`.
+    // There are no duplicate signatures in `java.lang.Object`, so use `HashSet<>::PutWithHash()`.
+    // This avoids equality comparison for the three `java.lang.Object.wait()` overloads.
+    super_vtable_signatures.PutWithHash(i, hash);
   }
   // Insert the remaining indexes, check for duplicate signatures.
   if (super_vtable_length > mirror::Object::kVTableLength) {