diff --git a/quiche/common/http/http_header_block.cc b/quiche/common/http/http_header_block.cc
index f6c6169..914c0de 100644
--- a/quiche/common/http/http_header_block.cc
+++ b/quiche/common/http/http_header_block.cc
@@ -156,9 +156,7 @@
   if (lookup_result_ == block_->map_.end()) {
     QUICHE_DVLOG(1) << "Inserting: (" << key_ << ", " << value << ")";
     lookup_result_ =
-        block_->map_
-            .emplace(std::make_pair(
-                key_, HeaderValue(storage, key_, storage->Write(value))))
+        block_->map_.try_emplace(key_, storage, key_, storage->Write(value))
             .first;
   } else {
     QUICHE_DVLOG(1) << "Updating key: " << key_ << " with value: " << value;
@@ -325,8 +323,7 @@
 void HttpHeaderBlock::AppendHeader(const absl::string_view key,
                                    const absl::string_view value) {
   auto backed_key = WriteKey(key);
-  map_.emplace(std::make_pair(
-      backed_key, HeaderValue(&storage_, backed_key, storage_.Write(value))));
+  map_.try_emplace(backed_key, &storage_, backed_key, storage_.Write(value));
 }
 
 absl::string_view HttpHeaderBlock::WriteKey(const absl::string_view key) {
diff --git a/quiche/common/quiche_linked_hash_map.h b/quiche/common/quiche_linked_hash_map.h
index 25c70fb..3932844 100644
--- a/quiche/common/quiche_linked_hash_map.h
+++ b/quiche/common/quiche_linked_hash_map.h
@@ -188,17 +188,13 @@
   size_type size() const { return map_.size(); }
 
   template <typename... Args>
-  std::pair<iterator, bool> emplace(Args&&... args) {
-    ListType node_donor;
-    auto node_pos =
-        node_donor.emplace(node_donor.end(), std::forward<Args>(args)...);
-    const auto& k = node_pos->first;
-    auto ins = map_.insert({k, node_pos});
-    if (!ins.second) {
-      return {ins.first->second, false};
-    }
-    list_.splice(list_.end(), node_donor, node_pos);
-    return {ins.first->second, true};
+  std::pair<iterator, bool> try_emplace(const key_type& key, Args&&... args) {
+    return TryEmplaceInternal(key, std::forward<Args>(args)...);
+  }
+
+  template <typename... Args>
+  std::pair<iterator, bool> try_emplace(key_type&& key, Args&&... args) {
+    return TryEmplaceInternal(std::move(key), std::forward<Args>(args)...);
   }
 
   void swap(QuicheLinkedHashMap& other) {
@@ -225,6 +221,23 @@
     return {list_iter, true};
   }
 
+  template <typename K, typename... Args>
+  std::pair<iterator, bool> TryEmplaceInternal(K&& key, Args&&... args) {
+    auto insert_result = map_.try_emplace(std::forward<K>(key));
+
+    if (!insert_result.second) {
+      return {insert_result.first->second, false};
+    }
+
+    auto list_iter =
+        list_.emplace(list_.end(), std::piecewise_construct,
+                      std::forward_as_tuple(std::forward<K>(key)),
+                      std::forward_as_tuple(std::forward<Args>(args)...));
+
+    insert_result.first->second = list_iter;
+    return {list_iter, true};
+  }
+
   // The map component, used for speedy lookups
   MapType map_;
 
diff --git a/quiche/common/quiche_linked_hash_map_test.cc b/quiche/common/quiche_linked_hash_map_test.cc
index 1a3aa79..98a731a 100644
--- a/quiche/common/quiche_linked_hash_map_test.cc
+++ b/quiche/common/quiche_linked_hash_map_test.cc
@@ -30,15 +30,14 @@
               UnorderedElementsAre(Pair(2, Pointee(12)), Pair(3, Pointee(13))));
 }
 
-TEST(LinkedHashMapTest, CanEmplaceMoveOnly) {
+TEST(LinkedHashMapTest, CanTryEmplaceMoveOnly) {
   QuicheLinkedHashMap<int, std::unique_ptr<int>> m;
   struct Data {
     int k, v;
   };
   const Data data[] = {{1, 123}, {3, 345}, {2, 234}, {4, 456}};
   for (const auto& kv : data) {
-    m.emplace(std::piecewise_construct, std::make_tuple(kv.k),
-              std::make_tuple(new int{kv.v}));
+    m.try_emplace(kv.k, std::make_unique<int>(kv.v));
   }
   EXPECT_TRUE(m.contains(2));
   auto found = m.find(2);
@@ -55,15 +54,14 @@
   int x;
 };
 
-TEST(LinkedHashMapTest, CanEmplaceNoMoveNoCopy) {
+TEST(LinkedHashMapTest, CanTryEmplaceNoMoveNoCopy) {
   QuicheLinkedHashMap<int, NoCopy> m;
   struct Data {
     int k, v;
   };
   const Data data[] = {{1, 123}, {3, 345}, {2, 234}, {4, 456}};
   for (const auto& kv : data) {
-    m.emplace(std::piecewise_construct, std::make_tuple(kv.k),
-              std::make_tuple(kv.v));
+    m.try_emplace(kv.k, kv.v);
   }
   EXPECT_TRUE(m.contains(2));
   auto found = m.find(2);
diff --git a/quiche/quic/core/quic_lru_cache.h b/quiche/quic/core/quic_lru_cache.h
index eb9c553..b85944d 100644
--- a/quiche/quic/core/quic_lru_cache.h
+++ b/quiche/quic/core/quic_lru_cache.h
@@ -56,7 +56,7 @@
     if (it != cache_.end()) {
       cache_.erase(it);
     }
-    cache_.emplace(key, std::move(value));
+    cache_.try_emplace(key, std::move(value));
 
     if (cache_.size() > capacity_) {
       cache_.pop_front();
@@ -72,7 +72,7 @@
 
     std::unique_ptr<V> value = std::move(iter->second);
     cache_.erase(iter);
-    auto result = cache_.emplace(key, std::move(value));
+    auto result = cache_.try_emplace(key, std::move(value));
     QUICHE_DCHECK(result.second);
     return result.first;
   }