diff --git a/src/google/protobuf/map.h b/src/google/protobuf/map.h
index cb3ec47..34916f4 100644
--- a/src/google/protobuf/map.h
+++ b/src/google/protobuf/map.h
@@ -414,6 +414,172 @@
 
 inline size_t SpaceUsedInValues(const void*) { return 0; }
 
+// Base class for all Map instantiations.
+// This class holds all the data and provides the basic functionality shared
+// among all instantiations.
+// Having an untyped base class helps generic consumers (like the table-driven
+// parser) by having non-template code that can handle all instantiations.
+class PROTOBUF_EXPORT UntypedMapBase {
+  using Allocator = internal::MapAllocator<void*>;
+
+ public:
+  using size_type = size_t;
+
+  explicit constexpr UntypedMapBase(Arena* arena)
+      : num_elements_(0),
+        num_buckets_(internal::kGlobalEmptyTableSize),
+        seed_(0),
+        index_of_first_non_null_(internal::kGlobalEmptyTableSize),
+        table_(const_cast<TableEntryPtr*>(internal::kGlobalEmptyTable)),
+        alloc_(arena) {}
+
+  UntypedMapBase(const UntypedMapBase&) = delete;
+  UntypedMapBase& operator=(const UntypedMapBase&) = delete;
+
+ protected:
+  enum { kMinTableSize = 8 };
+
+ public:
+  Arena* arena() const { return this->alloc_.arena(); }
+
+  void Swap(UntypedMapBase* other) {
+    std::swap(num_elements_, other->num_elements_);
+    std::swap(num_buckets_, other->num_buckets_);
+    std::swap(seed_, other->seed_);
+    std::swap(index_of_first_non_null_, other->index_of_first_non_null_);
+    std::swap(table_, other->table_);
+    std::swap(alloc_, other->alloc_);
+  }
+
+  static size_type max_size() {
+    return static_cast<size_type>(1) << (sizeof(void**) >= 8 ? 60 : 28);
+  }
+  size_type size() const { return num_elements_; }
+  bool empty() const { return size() == 0; }
+
+ protected:
+  friend class TcParser;
+
+  struct NodeAndBucket {
+    NodeBase* node;
+    size_type bucket;
+  };
+
+  // Returns whether we should insert after the head of the list. For
+  // non-optimized builds, we randomly decide whether to insert right at the
+  // head of the list or just after the head. This helps add a little bit of
+  // non-determinism to the map ordering.
+  bool ShouldInsertAfterHead(void* node) {
+#ifdef NDEBUG
+    (void)node;
+    return false;
+#else
+    // Doing modulo with a prime mixes the bits more.
+    return (reinterpret_cast<uintptr_t>(node) ^ seed_) % 13 > 6;
+#endif
+  }
+
+  // Helper for InsertUnique.  Handles the case where bucket b is a
+  // not-too-long linked list.
+  void InsertUniqueInList(size_type b, NodeBase* node) {
+    if (!TableEntryIsEmpty(b) && ShouldInsertAfterHead(node)) {
+      auto* first = TableEntryToNode(table_[b]);
+      node->next = first->next;
+      first->next = node;
+    } else {
+      node->next = TableEntryToNode(table_[b]);
+      table_[b] = NodeToTableEntry(node);
+    }
+  }
+
+  bool TableEntryIsEmpty(size_type b) const {
+    return internal::TableEntryIsEmpty(table_[b]);
+  }
+  bool TableEntryIsNonEmptyList(size_type b) const {
+    return internal::TableEntryIsNonEmptyList(table_[b]);
+  }
+  bool TableEntryIsTree(size_type b) const {
+    return internal::TableEntryIsTree(table_[b]);
+  }
+  bool TableEntryIsList(size_type b) const {
+    return internal::TableEntryIsList(table_[b]);
+  }
+
+  // Return whether table_[b] is a linked list that seems awfully long.
+  // Requires table_[b] to point to a non-empty linked list.
+  bool TableEntryIsTooLong(size_type b) {
+    return internal::TableEntryIsTooLong(TableEntryToNode(table_[b]));
+  }
+
+  // Return a power of two no less than max(kMinTableSize, n).
+  // Assumes either n < kMinTableSize or n is a power of two.
+  size_type TableSize(size_type n) {
+    return n < static_cast<size_type>(kMinTableSize)
+               ? static_cast<size_type>(kMinTableSize)
+               : n;
+  }
+
+  template <typename T>
+  using AllocFor = absl::allocator_traits<Allocator>::template rebind_alloc<T>;
+
+  // Alignment of the nodes is the same as alignment of NodeBase.
+  NodeBase* AllocNode(size_t node_size) {
+    PROTOBUF_ASSUME(node_size % sizeof(NodeBase) == 0);
+    return AllocFor<NodeBase>(alloc_).allocate(node_size / sizeof(NodeBase));
+  }
+
+  void DeallocNode(NodeBase* node, size_t node_size) {
+    PROTOBUF_ASSUME(node_size % sizeof(NodeBase) == 0);
+    AllocFor<NodeBase>(alloc_).deallocate(node, node_size / sizeof(NodeBase));
+  }
+
+  void DeleteTable(TableEntryPtr* table, size_type n) {
+    AllocFor<TableEntryPtr>(alloc_).deallocate(table, n);
+  }
+
+  TableEntryPtr* CreateEmptyTable(size_type n) {
+    GOOGLE_ABSL_DCHECK_GE(n, size_type{kMinTableSize});
+    GOOGLE_ABSL_DCHECK_EQ(n & (n - 1), 0u);
+    TableEntryPtr* result = AllocFor<TableEntryPtr>(alloc_).allocate(n);
+    memset(result, 0, n * sizeof(result[0]));
+    return result;
+  }
+
+  // Return a randomish value.
+  size_type Seed() const {
+    // We get a little bit of randomness from the address of the map. The
+    // lower bits are not very random, due to alignment, so we discard them
+    // and shift the higher bits into their place.
+    size_type s = reinterpret_cast<uintptr_t>(this) >> 4;
+#if !defined(GOOGLE_PROTOBUF_NO_RDTSC)
+#if defined(__APPLE__)
+    // Use a commpage-based fast time function on Apple environments (MacOS,
+    // iOS, tvOS, watchOS, etc).
+    s += mach_absolute_time();
+#elif defined(__x86_64__) && defined(__GNUC__)
+    uint32_t hi, lo;
+    asm volatile("rdtsc" : "=a"(lo), "=d"(hi));
+    s += ((static_cast<uint64_t>(hi) << 32) | lo);
+#elif defined(__aarch64__) && defined(__GNUC__)
+    // There is no rdtsc on ARMv8. CNTVCT_EL0 is the virtual counter of the
+    // system timer. It runs at a different frequency than the CPU's, but is
+    // the best source of time-based entropy we get.
+    uint64_t virtual_timer_value;
+    asm volatile("mrs %0, cntvct_el0" : "=r"(virtual_timer_value));
+    s += virtual_timer_value;
+#endif
+#endif  // !defined(GOOGLE_PROTOBUF_NO_RDTSC)
+    return s;
+  }
+
+  size_type num_elements_;
+  size_type num_buckets_;
+  size_type seed_;
+  size_type index_of_first_non_null_;
+  TableEntryPtr* table_;  // an array with num_buckets_ entries
+  Allocator alloc_;
+};
+
 // The value might be of different signedness, so use memcpy to extract it.
 template <typename T, std::enable_if_t<std::is_integral<T>::value, int> = 0>
 T ReadKey(const void* ptr) {
@@ -427,30 +593,42 @@
   return *reinterpret_cast<const T*>(ptr);
 }
 
+// KeyMapBase is a chaining hash map with the additional feature that some
+// buckets can be converted to use an ordered container.  This ensures O(lg n)
+// bounds on find, insert, and erase, while avoiding the overheads of ordered
+// containers most of the time.
+//
+// The implementation doesn't need the full generality of unordered_map,
+// and it doesn't have it.  More bells and whistles can be added as needed.
+// Some implementation details:
+// 1. The number of buckets is a power of two.
+// 2. As is typical for hash_map and such, the Keys and Values are always
+//    stored in linked list nodes.  Pointers to elements are never invalidated
+//    until the element is deleted.
+// 3. The trees' payload type is pointer to linked-list node.  Tree-converting
+//    a bucket doesn't copy Key-Value pairs.
+// 4. Once we've tree-converted a bucket, it is never converted back unless the
+//    bucket is completely emptied out. Note that the items a tree contains may
+//    wind up assigned to trees or lists upon a rehash.
+// 5. Mutations to a map do not invalidate the map's iterators, pointers to
+//    elements, or references to elements.
+// 6. Except for erase(iterator), any non-const method can reorder iterators.
+// 7. Uses KeyForTree<Key> when using the Tree representation, which
+//    is either `uint64_t` if `Key` is an integer, or
+//    `reference_wrapper<const Key>` otherwise. This avoids unnecessary copies
+//    of string keys, for example.
+
 template <typename Key>
-class KeyMapBase {
-  using Allocator = internal::MapAllocator<void*>;
+class KeyMapBase : public UntypedMapBase {
   static_assert(!std::is_signed<Key>::value || !std::is_integral<Key>::value,
                 "");
 
  public:
-  using size_type = size_t;
   using hasher = typename TransparentSupport<Key>::hash;
 
-  explicit constexpr KeyMapBase(Arena* arena)
-      : num_elements_(0),
-        num_buckets_(internal::kGlobalEmptyTableSize),
-        seed_(0),
-        index_of_first_non_null_(internal::kGlobalEmptyTableSize),
-        table_(const_cast<TableEntryPtr*>(internal::kGlobalEmptyTable)),
-        alloc_(arena) {}
-
-  KeyMapBase(const KeyMapBase&) = delete;
-  KeyMapBase& operator=(const KeyMapBase&) = delete;
+  using UntypedMapBase::UntypedMapBase;
 
  protected:
-  enum { kMinTableSize = 8 };
-
   struct KeyNode : NodeBase {
     static constexpr size_t kOffset = sizeof(NodeBase);
     decltype(auto) key() const {
@@ -509,20 +687,21 @@
       bucket_index_ = 0;
     }
 
-    friend bool operator==(const KeyIteratorBase& a, const KeyIteratorBase& b) {
-      return a.node_ == b.node_;
-    }
-    friend bool operator!=(const KeyIteratorBase& a, const KeyIteratorBase& b) {
-      return a.node_ != b.node_;
+    // The definition of operator== is handled by the derived type. If we were
+    // to do it in this class it would allow comparing iterators of different
+    // map types.
+    bool Equals(const KeyIteratorBase& other) const {
+      return node_ == other.node_;
     }
 
-    KeyIteratorBase& operator++() {
+    // The definition of operator++ is handled in the derived type. We would not
+    // be able to return the right type from here.
+    void PlusPlus() {
       if (node_->next == nullptr) {
         SearchFrom(bucket_index_ + 1);
       } else {
         node_ = static_cast<KeyNode*>(node_->next);
       }
-      return *this;
     }
 
     KeyNode* node_;
@@ -531,25 +710,8 @@
   };
 
  public:
-  Arena* arena() const { return this->alloc_.arena(); }
-
-  void Swap(KeyMapBase* other) {
-    std::swap(num_elements_, other->num_elements_);
-    std::swap(num_buckets_, other->num_buckets_);
-    std::swap(seed_, other->seed_);
-    std::swap(index_of_first_non_null_, other->index_of_first_non_null_);
-    std::swap(table_, other->table_);
-    std::swap(alloc_, other->alloc_);
-  }
-
   hasher hash_function() const { return {}; }
 
-  static size_type max_size() {
-    return static_cast<size_type>(1) << (sizeof(void**) >= 8 ? 60 : 28);
-  }
-  size_type size() const { return num_elements_; }
-  bool empty() const { return size() == 0; }
-
  protected:
   PROTOBUF_NOINLINE void erase_no_destroy(size_type b, KeyNode* node) {
     TreeIterator tree_it;
@@ -581,10 +743,6 @@
     }
   }
 
-  struct NodeAndBucket {
-    NodeBase* node;
-    size_type bucket;
-  };
   // TODO(sbenza): We can reduce duplication by coercing `K` to a common type.
   // Eg, for string keys we can coerce to string_view. Otherwise, we instantiate
   // this with all the different `char[N]` of the caller.
@@ -640,33 +798,6 @@
     }
   }
 
-  // Returns whether we should insert after the head of the list. For
-  // non-optimized builds, we randomly decide whether to insert right at the
-  // head of the list or just after the head. This helps add a little bit of
-  // non-determinism to the map ordering.
-  bool ShouldInsertAfterHead(void* node) {
-#ifdef NDEBUG
-    (void)node;
-    return false;
-#else
-    // Doing modulo with a prime mixes the bits more.
-    return (reinterpret_cast<uintptr_t>(node) ^ seed_) % 13 > 6;
-#endif
-  }
-
-  // Helper for InsertUnique.  Handles the case where bucket b is a
-  // not-too-long linked list.
-  void InsertUniqueInList(size_type b, KeyNode* node) {
-    if (!TableEntryIsEmpty(b) && ShouldInsertAfterHead(node)) {
-      auto* first = TableEntryToNode(table_[b]);
-      node->next = first->next;
-      first->next = node;
-    } else {
-      node->next = TableEntryToNode(table_[b]);
-      table_[b] = NodeToTableEntry(node);
-    }
-  }
-
   // Helper for InsertUnique.  Handles the case where bucket b points to a
   // Tree.
   void InsertUniqueInTree(size_type b, KeyNode* node) {
@@ -747,7 +878,7 @@
         TransferTree(TableEntryToTree<Tree>(old_table[i]));
       }
     }
-    Dealloc<TableEntryPtr>(old_table, old_table_size);
+    DeleteTable(old_table, old_table_size);
   }
 
   // Transfer all nodes in the list `node` into `this`.
@@ -766,19 +897,6 @@
     TransferList(static_cast<KeyNode*>(node));
   }
 
-  bool TableEntryIsEmpty(size_type b) const {
-    return internal::TableEntryIsEmpty(table_[b]);
-  }
-  bool TableEntryIsNonEmptyList(size_type b) const {
-    return internal::TableEntryIsNonEmptyList(table_[b]);
-  }
-  bool TableEntryIsTree(size_type b) const {
-    return internal::TableEntryIsTree(table_[b]);
-  }
-  bool TableEntryIsList(size_type b) const {
-    return internal::TableEntryIsList(table_[b]);
-  }
-
   void TreeConvert(size_type b) {
     GOOGLE_ABSL_DCHECK(!TableEntryIsTree(b));
     Tree* tree =
@@ -812,12 +930,6 @@
     return count;
   }
 
-  // Return whether table_[b] is a linked list that seems awfully long.
-  // Requires table_[b] to point to a non-empty linked list.
-  bool TableEntryIsTooLong(size_type b) {
-    return internal::TableEntryIsTooLong(TableEntryToNode(table_[b]));
-  }
-
   template <typename K>
   size_type BucketNumber(const K& k) const {
     // We xor the hash value against the random seed so that we effectively
@@ -831,69 +943,12 @@
     return ((kPhi * h) >> 32) & (num_buckets_ - 1);
   }
 
-  // Return a power of two no less than max(kMinTableSize, n).
-  // Assumes either n < kMinTableSize or n is a power of two.
-  size_type TableSize(size_type n) {
-    return n < static_cast<size_type>(kMinTableSize)
-               ? static_cast<size_type>(kMinTableSize)
-               : n;
-  }
-
-  // Use alloc_ to allocate an array of n objects of type U.
-  template <typename U>
-  U* Alloc(size_type n) {
-    using alloc_type = typename Allocator::template rebind<U>::other;
-    return alloc_type(alloc_).allocate(n);
-  }
-
-  // Use alloc_ to deallocate an array of n objects of type U.
-  template <typename U>
-  void Dealloc(U* t, size_type n) {
-    using alloc_type = typename Allocator::template rebind<U>::other;
-    alloc_type(alloc_).deallocate(t, n);
-  }
-
   void DestroyTree(Tree* tree) {
     if (alloc_.arena() == nullptr) {
       delete tree;
     }
   }
 
-  TableEntryPtr* CreateEmptyTable(size_type n) {
-    GOOGLE_ABSL_DCHECK(n >= kMinTableSize);
-    GOOGLE_ABSL_DCHECK_EQ(n & (n - 1), 0u);
-    TableEntryPtr* result = Alloc<TableEntryPtr>(n);
-    memset(result, 0, n * sizeof(result[0]));
-    return result;
-  }
-
-  // Return a randomish value.
-  size_type Seed() const {
-    // We get a little bit of randomness from the address of the map. The
-    // lower bits are not very random, due to alignment, so we discard them
-    // and shift the higher bits into their place.
-    size_type s = reinterpret_cast<uintptr_t>(this) >> 4;
-#if !defined(GOOGLE_PROTOBUF_NO_RDTSC)
-#if defined(__APPLE__)
-    // Use a commpage-based fast time function on Apple environments (MacOS,
-    // iOS, tvOS, watchOS, etc).
-    s += mach_absolute_time();
-#elif defined(__x86_64__) && defined(__GNUC__)
-    uint32_t hi, lo;
-    asm volatile("rdtsc" : "=a"(lo), "=d"(hi));
-    s += ((static_cast<uint64_t>(hi) << 32) | lo);
-#elif defined(__aarch64__) && defined(__GNUC__)
-    // There is no rdtsc on ARMv8. CNTVCT_EL0 is the virtual counter of the
-    // system timer. It runs at a different frequency than the CPU's, but is
-    // the best source of time-based entropy we get.
-    uint64_t virtual_timer_value;
-    asm volatile("mrs %0, cntvct_el0" : "=r"(virtual_timer_value));
-    s += virtual_timer_value;
-#endif
-#endif  // !defined(GOOGLE_PROTOBUF_NO_RDTSC)
-    return s;
-  }
-
   // Assumes node_ and m_ are correct and non-null, but other fields may be
   // stale.  Fix them as needed.  Then return true iff node_ points to a
   // Node in a list.  If false is returned then *it is modified to be
@@ -922,13 +977,6 @@
     bucket_index = res.bucket;
     return TableEntryIsList(bucket_index);
   }
-
-  size_type num_elements_;
-  size_type num_buckets_;
-  size_type seed_;
-  size_type index_of_first_non_null_;
-  TableEntryPtr* table_;  // an array with num_buckets_ entries
-  Allocator alloc_;
 };
 
 }  // namespace internal
@@ -981,7 +1029,9 @@
 // Map's interface is similar to std::unordered_map, except that Map is not
 // designed to play well with exceptions.
 template <typename Key, typename T>
-class Map {
+class Map : private internal::KeyMapBase<internal::KeyForBase<Key>> {
+  using Base = typename Map::KeyMapBase;
+
  public:
   using key_type = Key;
   using mapped_type = T;
@@ -996,8 +1046,8 @@
   using size_type = size_t;
   using hasher = typename internal::TransparentSupport<Key>::hash;
 
-  constexpr Map() : elements_(nullptr) { StaticValidityCheck(); }
-  explicit Map(Arena* arena) : elements_(arena) { StaticValidityCheck(); }
+  constexpr Map() : Base(nullptr) { StaticValidityCheck(); }
+  explicit Map(Arena* arena) : Base(arena) { StaticValidityCheck(); }
 
   Map(const Map& other) : Map() { insert(other.begin(), other.end()); }
 
@@ -1029,6 +1079,12 @@
     // Fail-safe in case we miss calling this in a constructor.  Note: this one
     // won't trigger for leaked maps that never get destructed.
     StaticValidityCheck();
+
+    if (this->alloc_.arena() == nullptr &&
+        this->num_buckets_ != internal::kGlobalEmptyTableSize) {
+      clear();
+      this->DeleteTable(this->table_, this->num_buckets_);
+    }
   }
 
  private:
@@ -1082,272 +1138,14 @@
   using RequiresNotInit =
       typename std::enable_if<!std::is_same<P, init_type>::value, int>::type;
 
-  using Allocator = internal::MapAllocator<void*>;
-
-  // InnerMap is a generic hash-based map.  It doesn't contain any
-  // protocol-buffer-specific logic.  It is a chaining hash map with the
-  // additional feature that some buckets can be converted to use an ordered
-  // container.  This ensures O(lg n) bounds on find, insert, and erase, while
-  // avoiding the overheads of ordered containers most of the time.
-  //
-  // The implementation doesn't need the full generality of unordered_map,
-  // and it doesn't have it.  More bells and whistles can be added as needed.
-  // Some implementation details:
-  // 1. The hash function has type hasher and the equality function
-  //    equal_to<Key>.  We inherit from hasher to save space
-  //    (empty-base-class optimization).
-  // 2. The number of buckets is a power of two.
-  // 3. Buckets are converted to trees in pairs: if we convert bucket b then
-  //    buckets b and b^1 will share a tree.  Invariant: buckets b and b^1 have
-  //    the same non-null value iff they are sharing a tree.  (An alternative
-  //    implementation strategy would be to have a tag bit per bucket.)
-  // 4. As is typical for hash_map and such, the Keys and Values are always
-  //    stored in linked list nodes.  Pointers to elements are never invalidated
-  //    until the element is deleted.
-  // 5. The trees' payload type is pointer to linked-list node.  Tree-converting
-  //    a bucket doesn't copy Key-Value pairs.
-  // 6. Once we've tree-converted a bucket, it is never converted back. However,
-  //    the items a tree contains may wind up assigned to trees or lists upon a
-  //    rehash.
-  // 7. The code requires no C++ features from C++14 or later.
-  // 8. Mutations to a map do not invalidate the map's iterators, pointers to
-  //    elements, or references to elements.
-  // 9. Except for erase(iterator), any non-const method can reorder iterators.
-  // 10. InnerMap uses KeyForTree<Key> when using the Tree representation, which
-  //    is either `Key`, if Key is a scalar, or `reference_wrapper<const Key>`
-  //    otherwise. This avoids unnecessary copies of string keys, for example.
-  class InnerMap : public internal::KeyMapBase<internal::KeyForBase<Key>> {
-   public:
-    explicit constexpr InnerMap(Arena* arena) : InnerMap::KeyMapBase(arena) {}
-
-    InnerMap(const InnerMap&) = delete;
-    InnerMap& operator=(const InnerMap&) = delete;
-
-    ~InnerMap() {
-      if (this->alloc_.arena() == nullptr &&
-          this->num_buckets_ != internal::kGlobalEmptyTableSize) {
-        clear();
-        this->template Dealloc<TableEntryPtr>(this->table_, this->num_buckets_);
-      }
-    }
-
-   private:
-    // Linked-list nodes, as one would expect for a chaining hash table.
-    struct Node : InnerMap::KeyMapBase::KeyNode {
-      value_type kv;
-    };
-
-    using Tree = internal::TreeForMap<Key>;
-    using TreeIterator = typename Tree::iterator;
-
-    static Node* NodeFromTreeIterator(TreeIterator it) {
-      static_assert(PROTOBUF_FIELD_OFFSET(Node, kv.first) ==
-                        InnerMap::KeyMapBase::KeyNode::kOffset,
-                    "");
-      return static_cast<Node*>(it->second);
-    }
-
-    using TableEntryPtr = internal::TableEntryPtr;
-
-    // iterator and const_iterator are instantiations of iterator_base.
-    template <typename KeyValueType>
-    class iterator_base : public InnerMap::KeyMapBase::KeyIteratorBase {
-      using Base = typename InnerMap::KeyMapBase::KeyIteratorBase;
-
-     public:
-      using reference = KeyValueType&;
-      using pointer = KeyValueType*;
-
-      using Base::Base;
-      iterator_base() = default;
-      // Any iterator_base can convert to any other.  This is overkill, and we
-      // rely on the enclosing class to use it wisely.  The standard "iterator
-      // can convert to const_iterator" is OK but the reverse direction is not.
-      iterator_base(const Base& base) : Base(base) {}  // NOLINT
-
-      reference operator*() const {
-        return static_cast<Node*>(this->node_)->kv;
-      }
-      pointer operator->() const { return &(operator*()); }
-    };
-
-   public:
-    using iterator = iterator_base<value_type>;
-    using const_iterator = iterator_base<const value_type>;
-
-    iterator begin() { return iterator(this); }
-    iterator end() { return iterator(); }
-    const_iterator begin() const { return const_iterator(this); }
-    const_iterator end() const { return const_iterator(); }
-
-    void clear() {
-      for (size_type b = 0; b < this->num_buckets_; b++) {
-        internal::NodeBase* node;
-        if (this->TableEntryIsNonEmptyList(b)) {
-          node = internal::TableEntryToNode(this->table_[b]);
-          this->table_[b] = TableEntryPtr{};
-        } else if (this->TableEntryIsTree(b)) {
-          Tree* tree = internal::TableEntryToTree<Tree>(this->table_[b]);
-          this->table_[b] = TableEntryPtr{};
-          node = NodeFromTreeIterator(tree->begin());
-          this->DestroyTree(tree);
-        } else {
-          continue;
-        }
-        do {
-          auto* next = node->next;
-          DestroyNode(static_cast<Node*>(node));
-          node = next;
-        } while (node != nullptr);
-      }
-      this->num_elements_ = 0;
-      this->index_of_first_non_null_ = this->num_buckets_;
-    }
-
-    template <typename K>
-    iterator find(const K& k) {
-      auto res = this->FindHelper(k);
-      return iterator(static_cast<Node*>(res.node), this, res.bucket);
-    }
-
-    template <typename K>
-    const_iterator find(const K& k) const {
-      auto res = this->FindHelper(k);
-      return const_iterator(static_cast<Node*>(res.node), this, res.bucket);
-    }
-
-    // Inserts a new element into the container if there is no element with the
-    // key in the container.
-    // The new element is:
-    //  (1) Constructed in-place with the given args, if mapped_type is not
-    //      arena constructible.
-    //  (2) Constructed in-place with the arena and then assigned with a
-    //      mapped_type temporary constructed with the given args, otherwise.
-    template <typename K, typename... Args>
-    std::pair<iterator, bool> try_emplace(K&& k, Args&&... args) {
-      return ArenaAwareTryEmplace(Arena::is_arena_constructable<mapped_type>(),
-                                  std::forward<K>(k),
-                                  std::forward<Args>(args)...);
-    }
-
-    // Inserts the key into the map, if not present. In that case, the value
-    // will be value initialized.
-    template <typename K>
-    std::pair<iterator, bool> insert(K&& k) {
-      return try_emplace(std::forward<K>(k));
-    }
-
-    template <typename K>
-    value_type& operator[](K&& k) {
-      return *try_emplace(std::forward<K>(k)).first;
-    }
-
-    void erase(iterator it) {
-      GOOGLE_ABSL_DCHECK_EQ(it.m_, this);
-      auto* node = static_cast<Node*>(it.node_);
-      this->erase_no_destroy(it.bucket_index_, node);
-      DestroyNode(node);
-    }
-
-    size_t SpaceUsedInternal() const {
-      return internal::SpaceUsedInTable<Key>(this->table_, this->num_buckets_,
-                                             this->num_elements_, sizeof(Node));
-    }
-
-   private:
-    template <typename K, typename... Args>
-    std::pair<iterator, bool> TryEmplaceInternal(K&& k, Args&&... args) {
-      auto p = this->FindHelper(k);
-      // Case 1: key was already present.
-      if (p.node != nullptr)
-        return std::make_pair(
-            iterator(static_cast<Node*>(p.node), this, p.bucket), false);
-      // Case 2: insert.
-      if (this->ResizeIfLoadIsOutOfRange(this->num_elements_ + 1)) {
-        p = this->FindHelper(k);
-      }
-      const size_type b = p.bucket;  // bucket number
-      // If K is not key_type, make the conversion to key_type explicit.
-      using TypeToInit = typename std::conditional<
-          std::is_same<typename std::decay<K>::type, key_type>::value, K&&,
-          key_type>::type;
-      Node* node = this->template Alloc<Node>(1);
-      // Even when arena is nullptr, CreateInArenaStorage is still used to
-      // ensure the arena of submessage will be consistent.
-      Arena::CreateInArenaStorage(const_cast<Key*>(&node->kv.first),
-                                  this->alloc_.arena(),
-                                  static_cast<TypeToInit>(std::forward<K>(k)));
-      // Note: if `T` is arena constructible, `Args` needs to be empty.
-      Arena::CreateInArenaStorage(&node->kv.second, this->alloc_.arena(),
-                                  std::forward<Args>(args)...);
-
-      this->InsertUnique(b, node);
-      ++this->num_elements_;
-      return std::make_pair(iterator(node, this, b), true);
-    }
-
-    // A helper function to perform an assignment of `mapped_type`.
-    // If the first argument is true, then it is a regular assignment.
-    // Otherwise, we first create a temporary and then perform an assignment.
-    template <typename V>
-    static void AssignMapped(std::true_type, mapped_type& mapped, V&& v) {
-      mapped = std::forward<V>(v);
-    }
-    template <typename... Args>
-    static void AssignMapped(std::false_type, mapped_type& mapped,
-                             Args&&... args) {
-      mapped = mapped_type(std::forward<Args>(args)...);
-    }
-
-    // Case 1: `mapped_type` is arena constructible. A temporary object is
-    // created and then (if `Args` are not empty) assigned to a mapped value
-    // that was created with the arena.
-    template <typename K>
-    std::pair<iterator, bool> ArenaAwareTryEmplace(std::true_type, K&& k) {
-      // case 1.1: "default" constructed (e.g. from arena only).
-      return TryEmplaceInternal(std::forward<K>(k));
-    }
-    template <typename K, typename... Args>
-    std::pair<iterator, bool> ArenaAwareTryEmplace(std::true_type, K&& k,
-                                                   Args&&... args) {
-      // case 1.2: "default" constructed + copy/move assignment
-      auto p = TryEmplaceInternal(std::forward<K>(k));
-      if (p.second) {
-        AssignMapped(std::is_same<void(typename std::decay<Args>::type...),
-                                  void(mapped_type)>(),
-                     p.first->second, std::forward<Args>(args)...);
-      }
-      return p;
-    }
-    // Case 2: `mapped_type` is not arena constructible. Using in-place
-    // construction.
-    template <typename... Args>
-    std::pair<iterator, bool> ArenaAwareTryEmplace(std::false_type,
-                                                   Args&&... args) {
-      return TryEmplaceInternal(std::forward<Args>(args)...);
-    }
-
-    void DestroyNode(Node* node) {
-      if (this->alloc_.arena() == nullptr) {
-        node->kv.first.~key_type();
-        node->kv.second.~mapped_type();
-        this->Dealloc(node, 1);
-      }
-    }
-
-    friend class Arena;
-    using InternalArenaConstructable_ = void;
-    using DestructorSkippable_ = void;
-  };  // end of class InnerMap
-
   template <typename LookupKey>
   using key_arg = typename internal::TransparentSupport<
       key_type>::template key_arg<LookupKey>;
 
  public:
   // Iterators
-  class const_iterator {
-    using InnerIt = typename InnerMap::const_iterator;
+  class const_iterator : private Base::KeyIteratorBase {
+    using BaseIt = typename Base::KeyIteratorBase;
 
    public:
     using iterator_category = std::forward_iterator_tag;
@@ -1357,34 +1155,37 @@
     using reference = const value_type&;
 
     const_iterator() {}
-    explicit const_iterator(const InnerIt& it) : it_(it) {}
+    const_iterator(const const_iterator&) = default;
+    const_iterator& operator=(const const_iterator&) = default;
 
-    const_reference operator*() const { return *it_; }
-    const_pointer operator->() const { return &(operator*()); }
+    reference operator*() const { return static_cast<Node*>(this->node_)->kv; }
+    pointer operator->() const { return &(operator*()); }
 
     const_iterator& operator++() {
-      ++it_;
+      this->PlusPlus();
       return *this;
     }
     const_iterator operator++(int) {
       auto copy = *this;
-      ++*this;
+      this->PlusPlus();
       return copy;
     }
 
     friend bool operator==(const const_iterator& a, const const_iterator& b) {
-      return a.it_ == b.it_;
+      return a.Equals(b);
     }
     friend bool operator!=(const const_iterator& a, const const_iterator& b) {
-      return !(a == b);
+      return !a.Equals(b);
     }
 
    private:
-    InnerIt it_;
+    using BaseIt::BaseIt;
+    explicit const_iterator(const BaseIt& base) : BaseIt(base) {}
+    friend class Map;
   };
 
-  class iterator {
-    using InnerIt = typename InnerMap::iterator;
+  class iterator : private Base::KeyIteratorBase {
+    using BaseIt = typename Base::KeyIteratorBase;
 
    public:
     using iterator_category = std::forward_iterator_tag;
@@ -1394,60 +1195,60 @@
     using reference = value_type&;
 
     iterator() {}
-    explicit iterator(const InnerIt& it) : it_(it) {}
+    iterator(const iterator&) = default;
+    iterator& operator=(const iterator&) = default;
 
-    reference operator*() const { return *it_; }
+    reference operator*() const { return static_cast<Node*>(this->node_)->kv; }
     pointer operator->() const { return &(operator*()); }
 
     iterator& operator++() {
-      ++it_;
+      this->PlusPlus();
       return *this;
     }
     iterator operator++(int) {
       auto copy = *this;
-      ++*this;
+      this->PlusPlus();
       return copy;
     }
 
     // Allow implicit conversion to const_iterator.
     operator const_iterator() const {  // NOLINT(runtime/explicit)
-      return const_iterator(typename InnerMap::const_iterator(it_));
+      return const_iterator(static_cast<const BaseIt&>(*this));
     }
 
     friend bool operator==(const iterator& a, const iterator& b) {
-      return a.it_ == b.it_;
+      return a.Equals(b);
     }
     friend bool operator!=(const iterator& a, const iterator& b) {
-      return !(a == b);
+      return !a.Equals(b);
     }
 
    private:
+    using BaseIt::BaseIt;
     friend class Map;
-
-    InnerIt it_;
   };
 
-  iterator begin() { return iterator(elements_.begin()); }
-  iterator end() { return iterator(elements_.end()); }
-  const_iterator begin() const { return const_iterator(elements_.begin()); }
-  const_iterator end() const { return const_iterator(elements_.end()); }
+  iterator begin() { return iterator(this); }
+  iterator end() { return iterator(); }
+  const_iterator begin() const { return const_iterator(this); }
+  const_iterator end() const { return const_iterator(); }
   const_iterator cbegin() const { return begin(); }
   const_iterator cend() const { return end(); }
 
-  size_type size() const { return elements_.size(); }
-  bool empty() const { return size() == 0; }
+  using Base::empty;
+  using Base::size;
 
   // Element access
   template <typename K = key_type>
   T& operator[](const key_arg<K>& key) {
-    return elements_[key].second;
+    return try_emplace(key).first->second;
   }
   template <
       typename K = key_type,
       // Disable for integral types to reduce code bloat.
       typename = typename std::enable_if<!std::is_integral<K>::value>::type>
   T& operator[](key_arg<K>&& key) {
-    return elements_[std::forward<K>(key)].second;
+    return try_emplace(std::forward<K>(key)).first->second;
   }
 
   template <typename K = key_type>
@@ -1472,11 +1273,12 @@
 
   template <typename K = key_type>
   const_iterator find(const key_arg<K>& key) const {
-    return const_iterator(elements_.find(key));
+    return const_cast<Map*>(this)->find(key);
   }
   template <typename K = key_type>
   iterator find(const key_arg<K>& key) {
-    return iterator(elements_.find(key));
+    auto res = this->FindHelper(key);
+    return iterator(static_cast<Node*>(res.node), this, res.bucket);
   }
 
   template <typename K = key_type>
@@ -1510,9 +1312,16 @@
   // insert
   template <typename K, typename... Args>
   std::pair<iterator, bool> try_emplace(K&& k, Args&&... args) {
-    auto p =
-        elements_.try_emplace(std::forward<K>(k), std::forward<Args>(args)...);
-    return std::pair<iterator, bool>(iterator(p.first), p.second);
+    // Inserts a new element into the container if there is no element with the
+    // key in the container.
+    // The new element is:
+    //  (1) Constructed in-place with the given args, if mapped_type is not
+    //      arena constructible.
+    //  (2) Constructed in-place with the arena and then assigned with a
+    //      mapped_type temporary constructed with the given args, otherwise.
+    return ArenaAwareTryEmplace(Arena::is_arena_constructable<mapped_type>(),
+                                std::forward<K>(k),
+                                std::forward<Args>(args)...);
   }
   std::pair<iterator, bool> insert(init_type&& value) {
     return try_emplace(std::move(value.first), std::move(value.second));
@@ -1553,17 +1362,45 @@
       return 1;
     }
   }
+
   iterator erase(iterator pos) {
-    iterator i = pos++;
-    elements_.erase(i.it_);
-    return pos;
+    auto next = std::next(pos);
+    GOOGLE_ABSL_DCHECK_EQ(pos.m_, static_cast<Base*>(this));
+    auto* node = static_cast<Node*>(pos.node_);
+    this->erase_no_destroy(pos.bucket_index_, node);
+    DestroyNode(node);
+    return next;
   }
+
   void erase(iterator first, iterator last) {
     while (first != last) {
       first = erase(first);
     }
   }
-  void clear() { elements_.clear(); }
+
+  void clear() {
+    for (size_type b = 0; b < this->num_buckets_; b++) {
+      internal::NodeBase* node;
+      if (this->TableEntryIsNonEmptyList(b)) {
+        node = internal::TableEntryToNode(this->table_[b]);
+        this->table_[b] = TableEntryPtr{};
+      } else if (this->TableEntryIsTree(b)) {
+        Tree* tree = internal::TableEntryToTree<Tree>(this->table_[b]);
+        this->table_[b] = TableEntryPtr{};
+        node = NodeFromTreeIterator(tree->begin());
+        this->DestroyTree(tree);
+      } else {
+        continue;
+      }
+      do {
+        auto* next = node->next;
+        DestroyNode(static_cast<Node*>(node));
+        node = next;
+      } while (node != nullptr);
+    }
+    this->num_elements_ = 0;
+    this->index_of_first_non_null_ = this->num_buckets_;
+  }
 
   // Assign
   Map& operator=(const Map& other) {
@@ -1587,19 +1424,48 @@
     }
   }
 
-  void InternalSwap(Map* other) { elements_.Swap(&other->elements_); }
+  void InternalSwap(Map* other) { this->Swap(other); }
 
   hasher hash_function() const { return {}; }
 
   size_t SpaceUsedExcludingSelfLong() const {
     if (empty()) return 0;
-    return elements_.SpaceUsedInternal() + internal::SpaceUsedInValues(this);
+    return SpaceUsedInternal() + internal::SpaceUsedInValues(this);
   }
 
  private:
   struct Rank1 {};
   struct Rank0 : Rank1 {};
 
+  // Linked-list nodes, as one would expect for a chaining hash table.
+  struct Node : Base::KeyNode {
+    value_type kv;
+  };
+
+  using Tree = internal::TreeForMap<Key>;
+  using TreeIterator = typename Tree::iterator;
+  using TableEntryPtr = internal::TableEntryPtr;
+
+  static Node* NodeFromTreeIterator(TreeIterator it) {
+    static_assert(
+        PROTOBUF_FIELD_OFFSET(Node, kv.first) == Base::KeyNode::kOffset, "");
+    static_assert(alignof(Node) == alignof(internal::NodeBase), "");
+    return static_cast<Node*>(it->second);
+  }
+
+  void DestroyNode(Node* node) {
+    if (this->alloc_.arena() == nullptr) {
+      node->kv.first.~key_type();
+      node->kv.second.~mapped_type();
+      this->DeallocNode(node, sizeof(Node));
+    }
+  }
+
+  size_t SpaceUsedInternal() const {
+    return internal::SpaceUsedInTable<Key>(this->table_, this->num_buckets_,
+                                           this->num_elements_, sizeof(Node));
+  }
+
   // We try to construct `init_type` from `Args` with a fall back to
   // `value_type`. The latter is less desired as it unconditionally makes a copy
   // of `value_type::first`.
@@ -1614,10 +1480,85 @@
     return insert(value_type(std::forward<Args>(args)...));
   }
 
-  Arena* arena() const { return elements_.arena(); }
-  InnerMap elements_;
+  template <typename K, typename... Args>
+  std::pair<iterator, bool> TryEmplaceInternal(K&& k, Args&&... args) {
+    auto p = this->FindHelper(k);
+    // Case 1: key was already present.
+    if (p.node != nullptr)
+      return std::make_pair(
+          iterator(static_cast<Node*>(p.node), this, p.bucket), false);
+    // Case 2: insert.
+    if (this->ResizeIfLoadIsOutOfRange(this->num_elements_ + 1)) {
+      p = this->FindHelper(k);
+    }
+    const size_type b = p.bucket;  // bucket number
+    // If K is not key_type, make the conversion to key_type explicit.
+    using TypeToInit = typename std::conditional<
+        std::is_same<typename std::decay<K>::type, key_type>::value, K&&,
+        key_type>::type;
+    Node* node = static_cast<Node*>(this->AllocNode(sizeof(Node)));
+    // Even when arena is nullptr, CreateInArenaStorage is still used to
+    // ensure the arena of submessage will be consistent. Otherwise,
+    // submessage may have its own arena when message-owned arena is enabled.
+    // Note: This only works if `Key` is not arena constructible.
+    Arena::CreateInArenaStorage(const_cast<Key*>(&node->kv.first),
+                                this->alloc_.arena(),
+                                static_cast<TypeToInit>(std::forward<K>(k)));
+    // Note: if `T` is arena constructible, `Args` needs to be empty.
+    Arena::CreateInArenaStorage(&node->kv.second, this->alloc_.arena(),
+                                std::forward<Args>(args)...);
+
+    this->InsertUnique(b, node);
+    ++this->num_elements_;
+    return std::make_pair(iterator(node, this, b), true);
+  }
+
+  // A helper function to perform an assignment of `mapped_type`.
+  // If the first argument is true, then it is a regular assignment.
+  // Otherwise, we first create a temporary and then perform an assignment.
+  template <typename V>
+  static void AssignMapped(std::true_type, mapped_type& mapped, V&& v) {
+    mapped = std::forward<V>(v);
+  }
+  template <typename... Args>
+  static void AssignMapped(std::false_type, mapped_type& mapped,
+                           Args&&... args) {
+    mapped = mapped_type(std::forward<Args>(args)...);
+  }
+
+  // Case 1: `mapped_type` is arena constructible. A temporary object is
+  // created and then (if `Args` are not empty) assigned to a mapped value
+  // that was created with the arena.
+  template <typename K>
+  std::pair<iterator, bool> ArenaAwareTryEmplace(std::true_type, K&& k) {
+    // case 1.1: "default" constructed (e.g. from arena only).
+    return TryEmplaceInternal(std::forward<K>(k));
+  }
+  template <typename K, typename... Args>
+  std::pair<iterator, bool> ArenaAwareTryEmplace(std::true_type, K&& k,
+                                                 Args&&... args) {
+    // case 1.2: "default" constructed + copy/move assignment
+    auto p = TryEmplaceInternal(std::forward<K>(k));
+    if (p.second) {
+      AssignMapped(std::is_same<void(typename std::decay<Args>::type...),
+                                void(mapped_type)>(),
+                   p.first->second, std::forward<Args>(args)...);
+    }
+    return p;
+  }
+  // Case 2: `mapped_type` is not arena constructible. Using in-place
+  // construction.
+  template <typename... Args>
+  std::pair<iterator, bool> ArenaAwareTryEmplace(std::false_type,
+                                                 Args&&... args) {
+    return TryEmplaceInternal(std::forward<Args>(args)...);
+  }
+
+  using Base::arena;
 
   friend class Arena;
+  template <typename, typename>
+  friend class internal::TypeDefinedMapFieldBase;
   using InternalArenaConstructable_ = void;
   using DestructorSkippable_ = void;
   template <typename Derived, typename K, typename V,