diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 75665b6..56e95b8 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -76,6 +76,7 @@
   runtime/barrier_test.cc \
   runtime/base/bit_field_test.cc \
   runtime/base/bit_vector_test.cc \
+  runtime/base/hash_set_test.cc \
   runtime/base/hex_dump_test.cc \
   runtime/base/histogram_test.cc \
   runtime/base/mutex_test.cc \
diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc
index 2fd5a52..448888f 100644
--- a/compiler/image_writer.cc
+++ b/compiler/image_writer.cc
@@ -324,7 +324,8 @@
 
   // Remove the undesired classes from the class roots.
   for (const std::string& it : non_image_classes) {
-    class_linker->RemoveClass(it.c_str(), NULL);
+    bool result = class_linker->RemoveClass(it.c_str(), NULL);
+    DCHECK(result);
   }
 
   // Clear references to removed classes from the DexCaches.
diff --git a/runtime/base/allocator.h b/runtime/base/allocator.h
index 30f7f12..5a09c96 100644
--- a/runtime/base/allocator.h
+++ b/runtime/base/allocator.h
@@ -101,7 +101,7 @@
 
 // Tracking allocator for use with STL types, tracks how much memory is used.
 template<class T, AllocatorTag kTag>
-class TrackingAllocatorImpl {
+class TrackingAllocatorImpl : public std::allocator<T> {
  public:
   typedef typename std::allocator<T>::value_type value_type;
   typedef typename std::allocator<T>::size_type size_type;
diff --git a/runtime/base/hash_set.h b/runtime/base/hash_set.h
new file mode 100644
index 0000000..992e5b1
--- /dev/null
+++ b/runtime/base/hash_set.h
@@ -0,0 +1,407 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_BASE_HASH_SET_H_
+#define ART_RUNTIME_BASE_HASH_SET_H_
+
+#include <functional>
+#include <memory>
+#include <stdint.h>
+#include <utility>
+
+#include "logging.h"
+
+namespace art {
+
+// Returns true if an item is empty.
+template <class T>
+class DefaultEmptyFn {
+ public:
+  void MakeEmpty(T& item) const {
+    item = T();
+  }
+  bool IsEmpty(const T& item) const {
+    return item == T();
+  }
+};
+
+template <class T>
+class DefaultEmptyFn<T*> {
+ public:
+  void MakeEmpty(T*& item) const {
+    item = nullptr;
+  }
+  bool IsEmpty(const T*& item) const {
+    return item == nullptr;
+  }
+};
+
+// Low memory version of a hash set, uses less memory than std::unordered_set since elements aren't
+// boxed. Uses linear probing.
+// EmptyFn needs to implement two functions MakeEmpty(T& item) and IsEmpty(const T& item)
+template <class T, class EmptyFn = DefaultEmptyFn<T>, class HashFn = std::hash<T>,
+    class Pred = std::equal_to<T>, class Alloc = std::allocator<T>>
+class HashSet {
+ public:
+  static constexpr double kDefaultMinLoadFactor = 0.5;
+  static constexpr double kDefaultMaxLoadFactor = 0.9;
+  static constexpr size_t kMinBuckets = 1000;
+
+  class Iterator {
+   public:
+    Iterator(const Iterator&) = default;
+    Iterator(HashSet* hash_set, size_t index) : hash_set_(hash_set), index_(index) {
+    }
+    Iterator& operator=(const Iterator&) = default;
+    bool operator==(const Iterator& other) const {
+      return hash_set_ == other.hash_set_ && index_ == other.index_;
+    }
+    bool operator!=(const Iterator& other) const {
+      return !(*this == other);
+    }
+    Iterator operator++() {  // Value after modification.
+      index_ = NextNonEmptySlot(index_);
+      return *this;
+    }
+    Iterator operator++(int) {
+      Iterator temp = *this;
+      index_ = NextNonEmptySlot(index_);
+      return temp;
+    }
+    T& operator*() {
+      DCHECK(!hash_set_->IsFreeSlot(GetIndex()));
+      return hash_set_->ElementForIndex(index_);
+    }
+    const T& operator*() const {
+      DCHECK(!hash_set_->IsFreeSlot(GetIndex()));
+      return hash_set_->ElementForIndex(index_);
+    }
+    T* operator->() {
+      return &**this;
+    }
+    const T* operator->() const {
+      return &**this;
+    }
+    // TODO: Operator -- --(int)
+
+   private:
+    HashSet* hash_set_;
+    size_t index_;
+
+    size_t GetIndex() const {
+      return index_;
+    }
+    size_t NextNonEmptySlot(size_t index) const {
+      const size_t num_buckets = hash_set_->NumBuckets();
+      DCHECK_LT(index, num_buckets);
+      do {
+        ++index;
+      } while (index < num_buckets && hash_set_->IsFreeSlot(index));
+      return index;
+    }
+
+    friend class HashSet;
+  };
+
+  void Clear() {
+    DeallocateStorage();
+    AllocateStorage(1);
+    num_elements_ = 0;
+    elements_until_expand_ = 0;
+  }
+  HashSet() : num_elements_(0), num_buckets_(0), data_(nullptr),
+      min_load_factor_(kDefaultMinLoadFactor), max_load_factor_(kDefaultMaxLoadFactor) {
+    Clear();
+  }
+  HashSet(const HashSet& other) : num_elements_(0), num_buckets_(0), data_(nullptr) {
+    *this = other;
+  }
+  HashSet(HashSet&& other) : num_elements_(0), num_buckets_(0), data_(nullptr) {
+    *this = std::move(other);
+  }
+  ~HashSet() {
+    DeallocateStorage();
+  }
+  HashSet& operator=(HashSet&& other) {
+    std::swap(data_, other.data_);
+    std::swap(num_buckets_, other.num_buckets_);
+    std::swap(num_elements_, other.num_elements_);
+    std::swap(elements_until_expand_, other.elements_until_expand_);
+    std::swap(min_load_factor_, other.min_load_factor_);
+    std::swap(max_load_factor_, other.max_load_factor_);
+    return *this;
+  }
+  HashSet& operator=(const HashSet& other) {
+    DeallocateStorage();
+    AllocateStorage(other.NumBuckets());
+    for (size_t i = 0; i < num_buckets_; ++i) {
+      ElementForIndex(i) = other.data_[i];
+    }
+    num_elements_ = other.num_elements_;
+    elements_until_expand_ = other.elements_until_expand_;
+    min_load_factor_ = other.min_load_factor_;
+    max_load_factor_ = other.max_load_factor_;
+    return *this;
+  }
+  // Lower case for c++11 for each.
+  Iterator begin() {
+    Iterator ret(this, 0);
+    if (num_buckets_ != 0 && IsFreeSlot(ret.GetIndex())) {
+      ++ret;  // Skip all the empty slots.
+    }
+    return ret;
+  }
+  // Lower case for c++11 for each.
+  Iterator end() {
+    return Iterator(this, NumBuckets());
+  }
+  bool Empty() {
+    return begin() == end();
+  }
+  // Erase algorithm:
+  // Make an empty slot where the iterator is pointing.
+  // Scan fowards until we hit another empty slot.
+  // If an element inbetween doesn't rehash to the range from the current empty slot to the
+  // iterator. It must be before the empty slot, in that case we can move it to the empty slot
+  // and set the empty slot to be the location we just moved from.
+  // Relies on maintaining the invariant that there's no empty slots from the 'ideal' index of an
+  // element to its actual location/index.
+  Iterator Erase(Iterator it) {
+    // empty_index is the index that will become empty.
+    size_t empty_index = it.GetIndex();
+    DCHECK(!IsFreeSlot(empty_index));
+    size_t next_index = empty_index;
+    bool filled = false;  // True if we filled the empty index.
+    while (true) {
+      next_index = NextIndex(next_index);
+      T& next_element = ElementForIndex(next_index);
+      // If the next element is empty, we are done. Make sure to clear the current empty index.
+      if (emptyfn_.IsEmpty(next_element)) {
+        emptyfn_.MakeEmpty(ElementForIndex(empty_index));
+        break;
+      }
+      // Otherwise try to see if the next element can fill the current empty index.
+      const size_t next_hash = hashfn_(next_element);
+      // Calculate the ideal index, if it is within empty_index + 1 to next_index then there is
+      // nothing we can do.
+      size_t next_ideal_index = IndexForHash(next_hash);
+      // Loop around if needed for our check.
+      size_t unwrapped_next_index = next_index;
+      if (unwrapped_next_index < empty_index) {
+        unwrapped_next_index += NumBuckets();
+      }
+      // Loop around if needed for our check.
+      size_t unwrapped_next_ideal_index = next_ideal_index;
+      if (unwrapped_next_ideal_index < empty_index) {
+        unwrapped_next_ideal_index += NumBuckets();
+      }
+      if (unwrapped_next_ideal_index <= empty_index ||
+          unwrapped_next_ideal_index > unwrapped_next_index) {
+        // If the target index isn't within our current range it must have been probed from before
+        // the empty index.
+        ElementForIndex(empty_index) = std::move(next_element);
+        filled = true;  // TODO: Optimize
+        empty_index = next_index;
+      }
+    }
+    --num_elements_;
+    // If we didn't fill the slot then we need go to the next non free slot.
+    if (!filled) {
+      ++it;
+    }
+    return it;
+  }
+  // Find an element, returns end() if not found.
+  // Allows custom K types, example of when this is useful.
+  // Set of Class* sorted by name, want to find a class with a name but can't allocate a dummy
+  // object in the heap for performance solution.
+  template <typename K>
+  Iterator Find(const K& element) {
+    return FindWithHash(element, hashfn_(element));
+  }
+  template <typename K>
+  Iterator FindWithHash(const K& element, size_t hash) {
+    DCHECK_EQ(hashfn_(element), hash);
+    size_t index = IndexForHash(hash);
+    while (true) {
+      T& slot = ElementForIndex(index);
+      if (emptyfn_.IsEmpty(slot)) {
+        return end();
+      }
+      if (pred_(slot, element)) {
+        return Iterator(this, index);
+      }
+      index = NextIndex(index);
+    }
+  }
+  // Insert an element, allows duplicates.
+  void Insert(const T& element) {
+    InsertWithHash(element, hashfn_(element));
+  }
+  void InsertWithHash(const T& element, size_t hash) {
+    DCHECK_EQ(hash, hashfn_(element));
+    if (num_elements_ >= elements_until_expand_) {
+      Expand();
+      DCHECK_LT(num_elements_, elements_until_expand_);
+    }
+    const size_t index = FirstAvailableSlot(IndexForHash(hash));
+    data_[index] = element;
+    ++num_elements_;
+  }
+  size_t Size() const {
+    return num_elements_;
+  }
+  void ShrinkToMaximumLoad() {
+    Resize(Size() / max_load_factor_);
+  }
+  // To distance that inserted elements were probed. Used for measuring how good hash functions
+  // are.
+  size_t TotalProbeDistance() const {
+    size_t total = 0;
+    for (size_t i = 0; i < NumBuckets(); ++i) {
+      const T& element = ElementForIndex(i);
+      if (!emptyfn_.IsEmpty(element)) {
+        size_t ideal_location = IndexForHash(hashfn_(element));
+        if (ideal_location > i) {
+          total += i + NumBuckets() - ideal_location;
+        } else {
+          total += i - ideal_location;
+        }
+      }
+    }
+    return total;
+  }
+  // Calculate the current load factor and return it.
+  double CalculateLoadFactor() const {
+    return static_cast<double>(Size()) / static_cast<double>(NumBuckets());
+  }
+  // Make sure that everything reinserts in the right spot. Returns the number of errors.
+  size_t Verify() {
+    size_t errors = 0;
+    for (size_t i = 0; i < num_buckets_; ++i) {
+      T& element = data_[i];
+      if (!emptyfn_.IsEmpty(element)) {
+        T temp;
+        emptyfn_.MakeEmpty(temp);
+        std::swap(temp, element);
+        size_t first_slot = FirstAvailableSlot(IndexForHash(hashfn_(temp)));
+        if (i != first_slot) {
+          LOG(ERROR) << "Element " << i << " should be in slot " << first_slot;
+          ++errors;
+        }
+        std::swap(temp, element);
+      }
+    }
+    return errors;
+  }
+
+ private:
+  T& ElementForIndex(size_t index) {
+    DCHECK_LT(index, NumBuckets());
+    DCHECK(data_ != nullptr);
+    return data_[index];
+  }
+  const T& ElementForIndex(size_t index) const {
+    DCHECK_LT(index, NumBuckets());
+    DCHECK(data_ != nullptr);
+    return data_[index];
+  }
+  size_t IndexForHash(size_t hash) const {
+    return hash % num_buckets_;
+  }
+  size_t NextIndex(size_t index) const {
+    if (UNLIKELY(++index >= num_buckets_)) {
+      DCHECK_EQ(index, NumBuckets());
+      return 0;
+    }
+    return index;
+  }
+  bool IsFreeSlot(size_t index) const {
+    return emptyfn_.IsEmpty(ElementForIndex(index));
+  }
+  size_t NumBuckets() const {
+    return num_buckets_;
+  }
+  // Allocate a number of buckets.
+  void AllocateStorage(size_t num_buckets) {
+    num_buckets_ = num_buckets;
+    data_ = allocfn_.allocate(num_buckets_);
+    for (size_t i = 0; i < num_buckets_; ++i) {
+      allocfn_.construct(allocfn_.address(data_[i]));
+      emptyfn_.MakeEmpty(data_[i]);
+    }
+  }
+  void DeallocateStorage() {
+    if (num_buckets_ != 0) {
+      for (size_t i = 0; i < NumBuckets(); ++i) {
+        allocfn_.destroy(allocfn_.address(data_[i]));
+      }
+      allocfn_.deallocate(data_, NumBuckets());
+      data_ = nullptr;
+      num_buckets_ = 0;
+    }
+  }
+  // Expand the set based on the load factors.
+  void Expand() {
+    size_t min_index = static_cast<size_t>(Size() / min_load_factor_);
+    if (min_index < kMinBuckets) {
+      min_index = kMinBuckets;
+    }
+    // Resize based on the minimum load factor.
+    Resize(min_index);
+    // When we hit elements_until_expand_, we are at the max load factor and must expand again.
+    elements_until_expand_ = NumBuckets() * max_load_factor_;
+  }
+  // Expand / shrink the table to the new specified size.
+  void Resize(size_t new_size) {
+    DCHECK_GE(new_size, Size());
+    T* old_data = data_;
+    size_t old_num_buckets = num_buckets_;
+    // Reinsert all of the old elements.
+    AllocateStorage(new_size);
+    for (size_t i = 0; i < old_num_buckets; ++i) {
+      T& element = old_data[i];
+      if (!emptyfn_.IsEmpty(element)) {
+        data_[FirstAvailableSlot(IndexForHash(hashfn_(element)))] = std::move(element);
+      }
+      allocfn_.destroy(allocfn_.address(element));
+    }
+    allocfn_.deallocate(old_data, old_num_buckets);
+  }
+  ALWAYS_INLINE size_t FirstAvailableSlot(size_t index) const {
+    while (!emptyfn_.IsEmpty(data_[index])) {
+      index = NextIndex(index);
+    }
+    return index;
+  }
+
+  Alloc allocfn_;  // Allocator function.
+  HashFn hashfn_;  // Hashing function.
+  EmptyFn emptyfn_;  // IsEmpty/SetEmpty function.
+  Pred pred_;  // Equals function.
+  size_t num_elements_;  // Number of inserted elements.
+  size_t num_buckets_;  // Number of hash table buckets.
+  size_t elements_until_expand_;  // Maxmimum number of elements until we expand the table.
+  T* data_;  // Backing storage.
+  double min_load_factor_;
+  double max_load_factor_;
+
+  friend class Iterator;
+};
+
+}  // namespace art
+
+#endif  // ART_RUNTIME_BASE_HASH_SET_H_
diff --git a/runtime/base/hash_set_test.cc b/runtime/base/hash_set_test.cc
new file mode 100644
index 0000000..885fc06
--- /dev/null
+++ b/runtime/base/hash_set_test.cc
@@ -0,0 +1,203 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "hash_set.h"
+
+#include <map>
+#include <sstream>
+#include <string>
+#include <unordered_set>
+
+#include "common_runtime_test.h"
+#include "utils.h"
+
+namespace art {
+
+class IsEmptyFnString {
+ public:
+  void MakeEmpty(std::string& item) const {
+    item.clear();
+  }
+  bool IsEmpty(const std::string& item) const {
+    return item.empty();
+  }
+};
+
+class HashSetTest : public CommonRuntimeTest {
+ public:
+  HashSetTest() : seed_(97421), unique_number_(0) {
+  }
+  std::string RandomString(size_t len) {
+    std::ostringstream oss;
+    for (size_t i = 0; i < len; ++i) {
+      oss << static_cast<char>('A' + PRand() % 64);
+    }
+    static_assert(' ' < 'A', "space must be less than a");
+    oss << " " << unique_number_++;  // Relies on ' ' < 'A'
+    return oss.str();
+  }
+  void SetSeed(size_t seed) {
+    seed_ = seed;
+  }
+  size_t PRand() {  // Pseudo random.
+    seed_ = seed_ * 1103515245 + 12345;
+    return seed_;
+  }
+
+ private:
+  size_t seed_;
+  size_t unique_number_;
+};
+
+TEST_F(HashSetTest, TestSmoke) {
+  HashSet<std::string, IsEmptyFnString> hash_set;
+  const std::string test_string = "hello world 1234";
+  ASSERT_TRUE(hash_set.Empty());
+  ASSERT_EQ(hash_set.Size(), 0U);
+  hash_set.Insert(test_string);
+  auto it = hash_set.Find(test_string);
+  ASSERT_EQ(*it, test_string);
+  auto after_it = hash_set.Erase(it);
+  ASSERT_TRUE(after_it == hash_set.end());
+  ASSERT_TRUE(hash_set.Empty());
+  ASSERT_EQ(hash_set.Size(), 0U);
+  it = hash_set.Find(test_string);
+  ASSERT_TRUE(it == hash_set.end());
+}
+
+TEST_F(HashSetTest, TestInsertAndErase) {
+  HashSet<std::string, IsEmptyFnString> hash_set;
+  static constexpr size_t count = 1000;
+  std::vector<std::string> strings;
+  for (size_t i = 0; i < count; ++i) {
+    // Insert a bunch of elements and make sure we can find them.
+    strings.push_back(RandomString(10));
+    hash_set.Insert(strings[i]);
+    auto it = hash_set.Find(strings[i]);
+    ASSERT_TRUE(it != hash_set.end());
+    ASSERT_EQ(*it, strings[i]);
+  }
+  ASSERT_EQ(strings.size(), hash_set.Size());
+  // Try to erase the odd strings.
+  for (size_t i = 1; i < count; i += 2) {
+    auto it = hash_set.Find(strings[i]);
+    ASSERT_TRUE(it != hash_set.end());
+    ASSERT_EQ(*it, strings[i]);
+    hash_set.Erase(it);
+  }
+  // Test removed.
+  for (size_t i = 1; i < count; i += 2) {
+    auto it = hash_set.Find(strings[i]);
+    ASSERT_TRUE(it == hash_set.end());
+  }
+  for (size_t i = 0; i < count; i += 2) {
+    auto it = hash_set.Find(strings[i]);
+    ASSERT_TRUE(it != hash_set.end());
+    ASSERT_EQ(*it, strings[i]);
+  }
+}
+
+TEST_F(HashSetTest, TestIterator) {
+  HashSet<std::string, IsEmptyFnString> hash_set;
+  ASSERT_TRUE(hash_set.begin() == hash_set.end());
+  static constexpr size_t count = 1000;
+  std::vector<std::string> strings;
+  for (size_t i = 0; i < count; ++i) {
+    // Insert a bunch of elements and make sure we can find them.
+    strings.push_back(RandomString(10));
+    hash_set.Insert(strings[i]);
+  }
+  // Make sure we visit each string exactly once.
+  std::map<std::string, size_t> found_count;
+  for (const std::string& s : hash_set) {
+    ++found_count[s];
+  }
+  for (size_t i = 0; i < count; ++i) {
+    ASSERT_EQ(found_count[strings[i]], 1U);
+  }
+  found_count.clear();
+  // Remove all the elements with iterator erase.
+  for (auto it = hash_set.begin(); it != hash_set.end();) {
+    ++found_count[*it];
+    it = hash_set.Erase(it);
+    ASSERT_EQ(hash_set.Verify(), 0U);
+  }
+  for (size_t i = 0; i < count; ++i) {
+    ASSERT_EQ(found_count[strings[i]], 1U);
+  }
+}
+
+TEST_F(HashSetTest, TestSwap) {
+  HashSet<std::string, IsEmptyFnString> hash_seta, hash_setb;
+  std::vector<std::string> strings;
+  static constexpr size_t count = 1000;
+  for (size_t i = 0; i < count; ++i) {
+    strings.push_back(RandomString(10));
+    hash_seta.Insert(strings[i]);
+  }
+  std::swap(hash_seta, hash_setb);
+  hash_seta.Insert("TEST");
+  hash_setb.Insert("TEST2");
+  for (size_t i = 0; i < count; ++i) {
+    strings.push_back(RandomString(10));
+    hash_seta.Insert(strings[i]);
+  }
+}
+
+TEST_F(HashSetTest, TestStress) {
+  HashSet<std::string, IsEmptyFnString> hash_set;
+  std::unordered_multiset<std::string> std_set;
+  std::vector<std::string> strings;
+  static constexpr size_t string_count = 2000;
+  static constexpr size_t operations = 100000;
+  static constexpr size_t target_size = 5000;
+  for (size_t i = 0; i < string_count; ++i) {
+    strings.push_back(RandomString(i % 10 + 1));
+  }
+  const size_t seed = time(nullptr);
+  SetSeed(seed);
+  LOG(INFO) << "Starting stress test with seed " << seed;
+  for (size_t i = 0; i < operations; ++i) {
+    ASSERT_EQ(hash_set.Size(), std_set.size());
+    size_t delta = std::abs(static_cast<ssize_t>(target_size) -
+                            static_cast<ssize_t>(hash_set.Size()));
+    size_t n = PRand();
+    if (n % target_size == 0) {
+      hash_set.Clear();
+      std_set.clear();
+      ASSERT_TRUE(hash_set.Empty());
+      ASSERT_TRUE(std_set.empty());
+    } else  if (n % target_size < delta) {
+      // Skew towards adding elements until we are at the desired size.
+      const std::string& s = strings[PRand() % string_count];
+      hash_set.Insert(s);
+      std_set.insert(s);
+      ASSERT_EQ(*hash_set.Find(s), *std_set.find(s));
+    } else {
+      const std::string& s = strings[PRand() % string_count];
+      auto it1 = hash_set.Find(s);
+      auto it2 = std_set.find(s);
+      ASSERT_EQ(it1 == hash_set.end(), it2 == std_set.end());
+      if (it1 != hash_set.end()) {
+        ASSERT_EQ(*it1, *it2);
+        hash_set.Erase(it1);
+        std_set.erase(it2);
+      }
+    }
+  }
+}
+
+}  // namespace art
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index eeb65f9..fecea89 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -1730,25 +1730,24 @@
 void ClassLinker::VisitClassRoots(RootCallback* callback, void* arg, VisitRootFlags flags) {
   WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
   if ((flags & kVisitRootFlagAllRoots) != 0) {
-    for (std::pair<const size_t, GcRoot<mirror::Class> >& it : class_table_) {
-      it.second.VisitRoot(callback, arg, 0, kRootStickyClass);
+    for (GcRoot<mirror::Class>& root : class_table_) {
+      root.VisitRoot(callback, arg, 0, kRootStickyClass);
+    }
+    for (GcRoot<mirror::Class>& root : pre_zygote_class_table_) {
+      root.VisitRoot(callback, arg, 0, kRootStickyClass);
     }
   } else if ((flags & kVisitRootFlagNewRoots) != 0) {
-    for (auto& pair : new_class_roots_) {
-      mirror::Class* old_ref = pair.second.Read<kWithoutReadBarrier>();
-      pair.second.VisitRoot(callback, arg, 0, kRootStickyClass);
-      mirror::Class* new_ref = pair.second.Read<kWithoutReadBarrier>();
+    for (auto& root : new_class_roots_) {
+      mirror::Class* old_ref = root.Read<kWithoutReadBarrier>();
+      root.VisitRoot(callback, arg, 0, kRootStickyClass);
+      mirror::Class* new_ref = root.Read<kWithoutReadBarrier>();
       if (UNLIKELY(new_ref != old_ref)) {
         // Uh ohes, GC moved a root in the log. Need to search the class_table and update the
         // corresponding object. This is slow, but luckily for us, this may only happen with a
         // concurrent moving GC.
-        for (auto it = class_table_.lower_bound(pair.first), end = class_table_.end();
-            it != end && it->first == pair.first; ++it) {
-          // If the class stored matches the old class, update it to the new value.
-          if (old_ref == it->second.Read<kWithoutReadBarrier>()) {
-            it->second = GcRoot<mirror::Class>(new_ref);
-          }
-        }
+        auto it = class_table_.Find(GcRoot<mirror::Class>(old_ref));
+        class_table_.Erase(it);
+        class_table_.Insert(GcRoot<mirror::Class>(new_ref));
       }
     }
   }
@@ -1806,9 +1805,13 @@
   }
   // TODO: why isn't this a ReaderMutexLock?
   WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-  for (std::pair<const size_t, GcRoot<mirror::Class> >& it : class_table_) {
-    mirror::Class* c = it.second.Read();
-    if (!visitor(c, arg)) {
+  for (GcRoot<mirror::Class>& root : class_table_) {
+    if (!visitor(root.Read(), arg)) {
+      return;
+    }
+  }
+  for (GcRoot<mirror::Class>& root : pre_zygote_class_table_) {
+    if (!visitor(root.Read(), arg)) {
       return;
     }
   }
@@ -1864,7 +1867,7 @@
       size_t class_table_size;
       {
         ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
-        class_table_size = class_table_.size();
+        class_table_size = class_table_.Size() + pre_zygote_class_table_.Size();
       }
       mirror::Class* class_type = mirror::Class::GetJavaLangClass();
       mirror::Class* array_of_class = FindArrayClass(self, &class_type);
@@ -3303,8 +3306,7 @@
     LOG(INFO) << "Loaded class " << descriptor << source;
   }
   WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-  mirror::Class* existing =
-      LookupClassFromTableLocked(descriptor, klass->GetClassLoader(), hash);
+  mirror::Class* existing = LookupClassFromTableLocked(descriptor, klass->GetClassLoader(), hash);
   if (existing != nullptr) {
     return existing;
   }
@@ -3314,13 +3316,13 @@
     // is in the image.
     existing = LookupClassFromImage(descriptor);
     if (existing != nullptr) {
-      CHECK(klass == existing);
+      CHECK_EQ(klass, existing);
     }
   }
   VerifyObject(klass);
-  class_table_.insert(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+  class_table_.InsertWithHash(GcRoot<mirror::Class>(klass), hash);
   if (log_new_class_table_roots_) {
-    new_class_roots_.push_back(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+    new_class_roots_.push_back(GcRoot<mirror::Class>(klass));
   }
   return nullptr;
 }
@@ -3340,14 +3342,8 @@
   CHECK(!existing->IsResolved()) << descriptor;
   CHECK_EQ(klass->GetStatus(), mirror::Class::kStatusResolving) << descriptor;
 
-  for (auto it = class_table_.lower_bound(hash), end = class_table_.end();
-       it != end && it->first == hash; ++it) {
-    mirror::Class* klass_from_table = it->second.Read();
-    if (klass_from_table == existing) {
-      class_table_.erase(it);
-      break;
-    }
-  }
+  auto it = class_table_.FindWithHash(GcRoot<mirror::Class>(klass), hash);
+  CHECK(it != class_table_.end());
 
   CHECK(!klass->IsTemp()) << descriptor;
   if (kIsDebugBuild && klass->GetClassLoader() == nullptr &&
@@ -3356,36 +3352,38 @@
     // is in the image.
     existing = LookupClassFromImage(descriptor);
     if (existing != nullptr) {
-      CHECK(klass == existing) << descriptor;
+      CHECK_EQ(klass, existing) << descriptor;
     }
   }
   VerifyObject(klass);
 
-  class_table_.insert(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+  // Update the element in the hash set.
+  *it = GcRoot<mirror::Class>(klass);
   if (log_new_class_table_roots_) {
-    new_class_roots_.push_back(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+    new_class_roots_.push_back(GcRoot<mirror::Class>(klass));
   }
 
   return existing;
 }
 
-bool ClassLinker::RemoveClass(const char* descriptor, const mirror::ClassLoader* class_loader) {
-  size_t hash = Hash(descriptor);
+bool ClassLinker::RemoveClass(const char* descriptor, mirror::ClassLoader* class_loader) {
   WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-  for (auto it = class_table_.lower_bound(hash), end = class_table_.end();
-       it != end && it->first == hash;
-       ++it) {
-    mirror::Class* klass = it->second.Read();
-    if (klass->GetClassLoader() == class_loader && klass->DescriptorEquals(descriptor)) {
-      class_table_.erase(it);
-      return true;
-    }
+  auto pair = std::make_pair(descriptor, class_loader);
+  auto it = class_table_.Find(pair);
+  if (it != class_table_.end()) {
+    class_table_.Erase(it);
+    return true;
+  }
+  it = pre_zygote_class_table_.Find(pair);
+  if (it != pre_zygote_class_table_.end()) {
+    pre_zygote_class_table_.Erase(it);
+    return true;
   }
   return false;
 }
 
 mirror::Class* ClassLinker::LookupClass(Thread* self, const char* descriptor,
-                                        const mirror::ClassLoader* class_loader) {
+                                        mirror::ClassLoader* class_loader) {
   size_t hash = Hash(descriptor);
   {
     ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
@@ -3415,26 +3413,17 @@
 }
 
 mirror::Class* ClassLinker::LookupClassFromTableLocked(const char* descriptor,
-                                                       const mirror::ClassLoader* class_loader,
+                                                       mirror::ClassLoader* class_loader,
                                                        size_t hash) {
-  auto end = class_table_.end();
-  for (auto it = class_table_.lower_bound(hash); it != end && it->first == hash; ++it) {
-    mirror::Class* klass = it->second.Read();
-    if (klass->GetClassLoader() == class_loader && klass->DescriptorEquals(descriptor)) {
-      if (kIsDebugBuild) {
-        // Check for duplicates in the table.
-        for (++it; it != end && it->first == hash; ++it) {
-          mirror::Class* klass2 = it->second.Read();
-          CHECK(!(klass2->GetClassLoader() == class_loader &&
-              klass2->DescriptorEquals(descriptor)))
-              << PrettyClass(klass) << " " << klass << " " << klass->GetClassLoader() << " "
-              << PrettyClass(klass2) << " " << klass2 << " " << klass2->GetClassLoader();
-        }
-      }
-      return klass;
+  auto descriptor_pair = std::make_pair(descriptor, class_loader);
+  auto it = pre_zygote_class_table_.FindWithHash(descriptor_pair, hash);
+  if (it == pre_zygote_class_table_.end()) {
+    it = class_table_.FindWithHash(descriptor_pair, hash);
+    if (it == class_table_.end()) {
+      return nullptr;
     }
   }
-  return nullptr;
+  return it->Read();
 }
 
 static mirror::ObjectArray<mirror::DexCache>* GetImageDexCaches()
@@ -3465,12 +3454,12 @@
         size_t hash = Hash(descriptor);
         mirror::Class* existing = LookupClassFromTableLocked(descriptor, nullptr, hash);
         if (existing != nullptr) {
-          CHECK(existing == klass) << PrettyClassAndClassLoader(existing) << " != "
+          CHECK_EQ(existing, klass) << PrettyClassAndClassLoader(existing) << " != "
               << PrettyClassAndClassLoader(klass);
         } else {
-          class_table_.insert(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+          class_table_.Insert(GcRoot<mirror::Class>(klass));
           if (log_new_class_table_roots_) {
-            new_class_roots_.push_back(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+            new_class_roots_.push_back(GcRoot<mirror::Class>(klass));
           }
         }
       }
@@ -3479,6 +3468,13 @@
   dex_cache_image_class_lookup_required_ = false;
 }
 
+void ClassLinker::MoveClassTableToPreZygote() {
+  WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
+  DCHECK(pre_zygote_class_table_.Empty());
+  pre_zygote_class_table_ = std::move(class_table_);
+  class_table_.Clear();
+}
+
 mirror::Class* ClassLinker::LookupClassFromImage(const char* descriptor) {
   ScopedAssertNoThreadSuspension ants(Thread::Current(), "Image class lookup");
   mirror::ObjectArray<mirror::DexCache>* dex_caches = GetImageDexCaches();
@@ -3507,14 +3503,32 @@
   if (dex_cache_image_class_lookup_required_) {
     MoveImageClassesToClassTable();
   }
-  size_t hash = Hash(descriptor);
-  ReaderMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-  for (auto it = class_table_.lower_bound(hash), end = class_table_.end();
-      it != end && it->first == hash; ++it) {
-    mirror::Class* klass = it->second.Read();
-    if (klass->DescriptorEquals(descriptor)) {
-      result.push_back(klass);
+  WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
+  while (true) {
+    auto it = class_table_.Find(descriptor);
+    if (it == class_table_.end()) {
+      break;
     }
+    result.push_back(it->Read());
+    class_table_.Erase(it);
+  }
+  for (mirror::Class* k : result) {
+    class_table_.Insert(GcRoot<mirror::Class>(k));
+  }
+  size_t pre_zygote_start = result.size();
+  // Now handle the pre zygote table.
+  // Note: This dirties the pre-zygote table but shouldn't be an issue since LookupClasses is only
+  // called from the debugger.
+  while (true) {
+    auto it = pre_zygote_class_table_.Find(descriptor);
+    if (it == pre_zygote_class_table_.end()) {
+      break;
+    }
+    result.push_back(it->Read());
+    pre_zygote_class_table_.Erase(it);
+  }
+  for (size_t i = pre_zygote_start; i < result.size(); ++i) {
+    pre_zygote_class_table_.Insert(GcRoot<mirror::Class>(result[i]));
   }
 }
 
@@ -5697,9 +5711,8 @@
   std::vector<mirror::Class*> all_classes;
   {
     ReaderMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-    for (std::pair<const size_t, GcRoot<mirror::Class> >& it : class_table_) {
-      mirror::Class* klass = it.second.Read();
-      all_classes.push_back(klass);
+    for (GcRoot<mirror::Class>& it : class_table_) {
+      all_classes.push_back(it.Read());
     }
   }
 
@@ -5793,7 +5806,8 @@
     MoveImageClassesToClassTable();
   }
   ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
-  os << "Loaded classes: " << class_table_.size() << " allocated classes\n";
+  os << "Zygote loaded classes=" << pre_zygote_class_table_.Size() << " post zygote classes="
+     << class_table_.Size() << "\n";
 }
 
 size_t ClassLinker::NumLoadedClasses() {
@@ -5801,7 +5815,8 @@
     MoveImageClassesToClassTable();
   }
   ReaderMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-  return class_table_.size();
+  // Only return non zygote classes since these are the ones which apps which care about.
+  return class_table_.Size();
 }
 
 pid_t ClassLinker::GetClassesLockOwner() {
@@ -5870,4 +5885,41 @@
   return descriptor;
 }
 
+std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& root)
+    const {
+  std::string temp;
+  return Hash(root.Read()->GetDescriptor(&temp));
+}
+
+bool ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& a,
+                                                        const GcRoot<mirror::Class>& b) {
+  if (a.Read()->GetClassLoader() != b.Read()->GetClassLoader()) {
+    return false;
+  }
+  std::string temp;
+  return a.Read()->DescriptorEquals(b.Read()->GetDescriptor(&temp));
+}
+
+std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(
+    const std::pair<const char*, mirror::ClassLoader*>& element) const {
+  return Hash(element.first);
+}
+
+bool ClassLinker::ClassDescriptorHashEquals::operator()(
+    const GcRoot<mirror::Class>& a, const std::pair<const char*, mirror::ClassLoader*>& b) {
+  if (a.Read()->GetClassLoader() != b.second) {
+    return false;
+  }
+  return a.Read()->DescriptorEquals(b.first);
+}
+
+bool ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& a,
+                                                        const char* descriptor) {
+  return a.Read()->DescriptorEquals(descriptor);
+}
+
+std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(const char* descriptor) const {
+  return Hash(descriptor);
+}
+
 }  // namespace art
diff --git a/runtime/class_linker.h b/runtime/class_linker.h
index a1cae4d..7b2ba43 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -23,6 +23,7 @@
 #include <vector>
 
 #include "base/allocator.h"
+#include "base/hash_set.h"
 #include "base/macros.h"
 #include "base/mutex.h"
 #include "dex_file.h"
@@ -145,7 +146,7 @@
   // Finds a class by its descriptor, returning NULL if it isn't wasn't loaded
   // by the given 'class_loader'.
   mirror::Class* LookupClass(Thread* self, const char* descriptor,
-                             const mirror::ClassLoader* class_loader)
+                             mirror::ClassLoader* class_loader)
       LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
@@ -158,7 +159,7 @@
 
   // General class unloading is not supported, this is used to prune
   // unwanted classes during image writing.
-  bool RemoveClass(const char* descriptor, const mirror::ClassLoader* class_loader)
+  bool RemoveClass(const char* descriptor, mirror::ClassLoader* class_loader)
       LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
@@ -458,6 +459,17 @@
     return class_roots;
   }
 
+  // Move all of the image classes into the class table for faster lookups.
+  void MoveImageClassesToClassTable()
+      LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  // Move the class table to the pre-zygote table to reduce memory usage. This works by ensuring
+  // that no more classes are ever added to the pre zygote table which makes it that the pages
+  // always remain shared dirty instead of private dirty.
+  void MoveClassTableToPreZygote()
+      LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
  private:
   const OatFile::OatMethod FindOatMethodFor(mirror::ArtMethod* method, bool* found)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
@@ -685,7 +697,7 @@
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   mirror::Class* LookupClassFromTableLocked(const char* descriptor,
-                                            const mirror::ClassLoader* class_loader,
+                                            mirror::ClassLoader* class_loader,
                                             size_t hash)
       SHARED_LOCKS_REQUIRED(Locks::classlinker_classes_lock_, Locks::mutator_lock_);
 
@@ -693,9 +705,6 @@
       LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  void MoveImageClassesToClassTable() LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
-      LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
   mirror::Class* LookupClassFromImage(const char* descriptor)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
@@ -724,15 +733,43 @@
   std::vector<GcRoot<mirror::DexCache>> dex_caches_ GUARDED_BY(dex_lock_);
   std::vector<const OatFile*> oat_files_ GUARDED_BY(dex_lock_);
 
+  class ClassDescriptorHashEquals {
+   public:
+    // Same class loader and descriptor.
+    std::size_t operator()(const GcRoot<mirror::Class>& root) const NO_THREAD_SAFETY_ANALYSIS;
+    bool operator()(const GcRoot<mirror::Class>& a, const GcRoot<mirror::Class>& b)
+        NO_THREAD_SAFETY_ANALYSIS;
+    // Same class loader and descriptor.
+    std::size_t operator()(const std::pair<const char*, mirror::ClassLoader*>& element) const
+        NO_THREAD_SAFETY_ANALYSIS;
+    bool operator()(const GcRoot<mirror::Class>& a,
+                    const std::pair<const char*, mirror::ClassLoader*>& b)
+        NO_THREAD_SAFETY_ANALYSIS;
+    // Same descriptor.
+    bool operator()(const GcRoot<mirror::Class>& a, const char* descriptor)
+        NO_THREAD_SAFETY_ANALYSIS;
+    std::size_t operator()(const char* descriptor) const NO_THREAD_SAFETY_ANALYSIS;
+  };
+  class GcRootEmptyFn {
+   public:
+    void MakeEmpty(GcRoot<mirror::Class>& item) const {
+      item = GcRoot<mirror::Class>();
+    }
+    bool IsEmpty(const GcRoot<mirror::Class>& item) const {
+      return item.IsNull();
+    }
+  };
 
-  // multimap from a string hash code of a class descriptor to
-  // mirror::Class* instances. Results should be compared for a matching
-  // Class::descriptor_ and Class::class_loader_.
-  typedef AllocationTrackingMultiMap<size_t, GcRoot<mirror::Class>, kAllocatorTagClassTable> Table;
+  // hash set which hashes class descriptor, and compares descriptors nad class loaders. Results
+  // should be compared for a matching Class descriptor and class loader.
+  typedef HashSet<GcRoot<mirror::Class>, GcRootEmptyFn, ClassDescriptorHashEquals,
+      ClassDescriptorHashEquals, TrackingAllocator<GcRoot<mirror::Class>, kAllocatorTagClassTable>>
+      Table;
   // This contains strong roots. To enable concurrent root scanning of
   // the class table, be careful to use a read barrier when accessing this.
   Table class_table_ GUARDED_BY(Locks::classlinker_classes_lock_);
-  std::vector<std::pair<size_t, GcRoot<mirror::Class>>> new_class_roots_;
+  Table pre_zygote_class_table_ GUARDED_BY(Locks::classlinker_classes_lock_);
+  std::vector<GcRoot<mirror::Class>> new_class_roots_;
 
   // Do we need to search dex caches to find image classes?
   bool dex_cache_image_class_lookup_required_;
diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc
index 06cd326..0e67978 100644
--- a/runtime/gc/heap.cc
+++ b/runtime/gc/heap.cc
@@ -1899,6 +1899,7 @@
     return;
   }
   Runtime::Current()->GetInternTable()->SwapPostZygoteWithPreZygote();
+  Runtime::Current()->GetClassLinker()->MoveClassTableToPreZygote();
   VLOG(heap) << "Starting PreZygoteFork";
   // Trim the pages at the end of the non moving space.
   non_moving_space_->Trim();
diff --git a/runtime/gc_root-inl.h b/runtime/gc_root-inl.h
index 482f7bc..a42ec08 100644
--- a/runtime/gc_root-inl.h
+++ b/runtime/gc_root-inl.h
@@ -25,7 +25,7 @@
 
 template<class MirrorType>
 template<ReadBarrierOption kReadBarrierOption>
-inline MirrorType* GcRoot<MirrorType>::Read() {
+inline MirrorType* GcRoot<MirrorType>::Read() const {
   return ReadBarrier::BarrierForRoot<MirrorType, kReadBarrierOption>(&root_);
 }
 
diff --git a/runtime/gc_root.h b/runtime/gc_root.h
index a347622..aee5586 100644
--- a/runtime/gc_root.h
+++ b/runtime/gc_root.h
@@ -27,9 +27,9 @@
 class PACKED(4) GcRoot {
  public:
   template<ReadBarrierOption kReadBarrierOption = kWithReadBarrier>
-  ALWAYS_INLINE MirrorType* Read() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  ALWAYS_INLINE MirrorType* Read() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  void VisitRoot(RootCallback* callback, void* arg, uint32_t thread_id, RootType root_type) {
+  void VisitRoot(RootCallback* callback, void* arg, uint32_t thread_id, RootType root_type) const {
     DCHECK(!IsNull());
     callback(reinterpret_cast<mirror::Object**>(&root_), arg, thread_id, root_type);
     DCHECK(!IsNull());
@@ -53,7 +53,7 @@
   }
 
  private:
-  MirrorType* root_;
+  mutable MirrorType* root_;
 };
 
 }  // namespace art
diff --git a/runtime/intern_table.cc b/runtime/intern_table.cc
index 95186c6..56a6d2c 100644
--- a/runtime/intern_table.cc
+++ b/runtime/intern_table.cc
@@ -56,13 +56,13 @@
 void InternTable::VisitRoots(RootCallback* callback, void* arg, VisitRootFlags flags) {
   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
   if ((flags & kVisitRootFlagAllRoots) != 0) {
-    strong_interns_.VisitRoots(callback, arg, flags);
+    strong_interns_.VisitRoots(callback, arg);
   } else if ((flags & kVisitRootFlagNewRoots) != 0) {
     for (auto& root : new_strong_intern_roots_) {
       mirror::String* old_ref = root.Read<kWithoutReadBarrier>();
       root.VisitRoot(callback, arg, 0, kRootInternedString);
       mirror::String* new_ref = root.Read<kWithoutReadBarrier>();
-      if (UNLIKELY(new_ref != old_ref)) {
+      if (new_ref != old_ref) {
         // The GC moved a root in the log. Need to search the strong interns and update the
         // corresponding object. This is slow, but luckily for us, this may only happen with a
         // concurrent moving GC.
@@ -71,7 +71,6 @@
       }
     }
   }
-
   if ((flags & kVisitRootFlagClearRootLog) != 0) {
     new_strong_intern_roots_.clear();
   }
@@ -190,7 +189,7 @@
     const DexFile* dex_file = dex_cache->GetDexFile();
     // Binary search the dex file for the string index.
     const DexFile::StringId* string_id = dex_file->FindStringId(utf8.c_str());
-    if (string_id != NULL) {
+    if (string_id != nullptr) {
       uint32_t string_idx = dex_file->GetIndexForStringId(*string_id);
       mirror::String* image_string = dex_cache->GetResolvedString(string_idx);
       if (image_string != NULL) {
@@ -198,7 +197,7 @@
       }
     }
   }
-  return NULL;
+  return nullptr;
 }
 
 void InternTable::AllowNewInterns() {
@@ -215,58 +214,36 @@
 }
 
 mirror::String* InternTable::Insert(mirror::String* s, bool is_strong) {
+  if (s == nullptr) {
+    return nullptr;
+  }
   Thread* self = Thread::Current();
   MutexLock mu(self, *Locks::intern_table_lock_);
-
-  DCHECK(s != NULL);
-
   while (UNLIKELY(!allow_new_interns_)) {
     new_intern_condition_.WaitHoldingLocks(self);
   }
-
-  if (is_strong) {
-    // Check the strong table for a match.
-    mirror::String* strong = LookupStrong(s);
-    if (strong != NULL) {
-      return strong;
-    }
-
-    // Check the image for a match.
-    mirror::String* image = LookupStringFromImage(s);
-    if (image != NULL) {
-      return InsertStrong(image);
-    }
-
-    // There is no match in the strong table, check the weak table.
-    mirror::String* weak = LookupWeak(s);
-    if (weak != NULL) {
-      // A match was found in the weak table. Promote to the strong table.
-      RemoveWeak(weak);
-      return InsertStrong(weak);
-    }
-
-    // No match in the strong table or the weak table. Insert into the strong
-    // table.
-    return InsertStrong(s);
-  }
-
   // Check the strong table for a match.
   mirror::String* strong = LookupStrong(s);
-  if (strong != NULL) {
+  if (strong != nullptr) {
     return strong;
   }
   // Check the image for a match.
   mirror::String* image = LookupStringFromImage(s);
-  if (image != NULL) {
-    return InsertWeak(image);
+  if (image != nullptr) {
+    return is_strong ? InsertStrong(image) : InsertWeak(image);
   }
-  // Check the weak table for a match.
+  // There is no match in the strong table, check the weak table.
   mirror::String* weak = LookupWeak(s);
-  if (weak != NULL) {
+  if (weak != nullptr) {
+    if (is_strong) {
+      // A match was found in the weak table. Promote to the strong table.
+      RemoveWeak(weak);
+      return InsertStrong(weak);
+    }
     return weak;
   }
-  // Insert into the weak table.
-  return InsertWeak(s);
+  // No match in the strong table or the weak table. Insert into the strong / weak table.
+  return is_strong ? InsertStrong(s) : InsertWeak(s);
 }
 
 mirror::String* InternTable::InternStrong(int32_t utf16_length, const char* utf8_data) {
@@ -281,16 +258,10 @@
 }
 
 mirror::String* InternTable::InternStrong(mirror::String* s) {
-  if (s == nullptr) {
-    return nullptr;
-  }
   return Insert(s, true);
 }
 
 mirror::String* InternTable::InternWeak(mirror::String* s) {
-  if (s == nullptr) {
-    return nullptr;
-  }
   return Insert(s, false);
 }
 
@@ -304,64 +275,63 @@
   weak_interns_.SweepWeaks(callback, arg);
 }
 
-std::size_t InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& root) {
+std::size_t InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& root) const {
   if (kIsDebugBuild) {
     Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
   }
-  return static_cast<size_t>(const_cast<GcRoot<mirror::String>&>(root).Read()->GetHashCode());
+  return static_cast<size_t>(root.Read()->GetHashCode());
 }
 
 bool InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& a,
-                                               const GcRoot<mirror::String>& b) {
+                                               const GcRoot<mirror::String>& b) const {
   if (kIsDebugBuild) {
     Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
   }
-  return const_cast<GcRoot<mirror::String>&>(a).Read()->Equals(
-      const_cast<GcRoot<mirror::String>&>(b).Read());
+  return a.Read()->Equals(b.Read());
 }
 
 void InternTable::Table::Remove(mirror::String* s) {
-  auto it = post_zygote_table_.find(GcRoot<mirror::String>(s));
+  auto it = post_zygote_table_.Find(GcRoot<mirror::String>(s));
   if (it != post_zygote_table_.end()) {
-    post_zygote_table_.erase(it);
+    post_zygote_table_.Erase(it);
   } else {
-    it = pre_zygote_table_.find(GcRoot<mirror::String>(s));
+    it = pre_zygote_table_.Find(GcRoot<mirror::String>(s));
     DCHECK(it != pre_zygote_table_.end());
-    pre_zygote_table_.erase(it);
+    pre_zygote_table_.Erase(it);
   }
 }
 
 mirror::String* InternTable::Table::Find(mirror::String* s) {
   Locks::intern_table_lock_->AssertHeld(Thread::Current());
-  auto it = pre_zygote_table_.find(GcRoot<mirror::String>(s));
-  if (LIKELY(it != pre_zygote_table_.end())) {
-    return const_cast<GcRoot<mirror::String>&>(*it).Read();
+  auto it = pre_zygote_table_.Find(GcRoot<mirror::String>(s));
+  if (it != pre_zygote_table_.end()) {
+    return it->Read();
   }
-  it = post_zygote_table_.find(GcRoot<mirror::String>(s));
-  if (LIKELY(it != post_zygote_table_.end())) {
-    return const_cast<GcRoot<mirror::String>&>(*it).Read();
+  it = post_zygote_table_.Find(GcRoot<mirror::String>(s));
+  if (it != post_zygote_table_.end()) {
+    return it->Read();
   }
   return nullptr;
 }
 
 void InternTable::Table::SwapPostZygoteWithPreZygote() {
-  CHECK(pre_zygote_table_.empty());
+  CHECK(pre_zygote_table_.Empty());
   std::swap(pre_zygote_table_, post_zygote_table_);
+  VLOG(heap) << "Swapping " << pre_zygote_table_.Size() << " interns to the pre zygote table";
 }
 
 void InternTable::Table::Insert(mirror::String* s) {
   // Always insert the post zygote table, this gets swapped when we create the zygote to be the
   // pre zygote table.
-  post_zygote_table_.insert(GcRoot<mirror::String>(s));
+  post_zygote_table_.Insert(GcRoot<mirror::String>(s));
 }
 
-void InternTable::Table::VisitRoots(RootCallback* callback, void* arg,
-                                    VisitRootFlags flags ATTRIBUTE_UNUSED) {
+void InternTable::Table::VisitRoots(RootCallback* callback, void* arg) {
   for (auto& intern : pre_zygote_table_) {
-    const_cast<GcRoot<mirror::String>&>(intern).VisitRoot(callback, arg, 0, kRootInternedString);
+    intern.VisitRoot(callback, arg, 0, kRootInternedString);
   }
   for (auto& intern : post_zygote_table_) {
-    const_cast<GcRoot<mirror::String>&>(intern).VisitRoot(callback, arg, 0, kRootInternedString);
+    intern.VisitRoot(callback, arg, 0, kRootInternedString);
   }
 }
 
@@ -373,16 +343,19 @@
 void InternTable::Table::SweepWeaks(UnorderedSet* set, IsMarkedCallback* callback, void* arg) {
   for (auto it = set->begin(), end = set->end(); it != end;) {
     // This does not need a read barrier because this is called by GC.
-    GcRoot<mirror::String>& root = const_cast<GcRoot<mirror::String>&>(*it);
-    mirror::Object* object = root.Read<kWithoutReadBarrier>();
+    mirror::Object* object = it->Read<kWithoutReadBarrier>();
     mirror::Object* new_object = callback(object, arg);
     if (new_object == nullptr) {
-      it = set->erase(it);
+      it = set->Erase(it);
     } else {
-      root = GcRoot<mirror::String>(new_object->AsString());
+      *it = GcRoot<mirror::String>(new_object->AsString());
       ++it;
     }
   }
 }
 
+size_t InternTable::Table::Size() const {
+  return pre_zygote_table_.Size() + post_zygote_table_.Size();
+}
+
 }  // namespace art
diff --git a/runtime/intern_table.h b/runtime/intern_table.h
index 0bff7b9..371d3f7 100644
--- a/runtime/intern_table.h
+++ b/runtime/intern_table.h
@@ -20,6 +20,7 @@
 #include <unordered_set>
 
 #include "base/allocator.h"
+#include "base/hash_set.h"
 #include "base/mutex.h"
 #include "gc_root.h"
 #include "object_callbacks.h"
@@ -98,10 +99,19 @@
  private:
   class StringHashEquals {
    public:
-    std::size_t operator()(const GcRoot<mirror::String>& root) NO_THREAD_SAFETY_ANALYSIS;
-    bool operator()(const GcRoot<mirror::String>& a, const GcRoot<mirror::String>& b)
+    std::size_t operator()(const GcRoot<mirror::String>& root) const NO_THREAD_SAFETY_ANALYSIS;
+    bool operator()(const GcRoot<mirror::String>& a, const GcRoot<mirror::String>& b) const
         NO_THREAD_SAFETY_ANALYSIS;
   };
+  class GcRootEmptyFn {
+   public:
+    void MakeEmpty(GcRoot<mirror::String>& item) const {
+      item = GcRoot<mirror::String>();
+    }
+    bool IsEmpty(const GcRoot<mirror::String>& item) const {
+      return item.IsNull();
+    }
+  };
 
   // Table which holds pre zygote and post zygote interned strings. There is one instance for
   // weak interns and strong interns.
@@ -114,19 +124,17 @@
     void Remove(mirror::String* s)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
         EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
-    void VisitRoots(RootCallback* callback, void* arg, VisitRootFlags flags)
+    void VisitRoots(RootCallback* callback, void* arg)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
         EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
     void SweepWeaks(IsMarkedCallback* callback, void* arg)
         SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
         EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
     void SwapPostZygoteWithPreZygote() EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
-    size_t Size() const EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_) {
-      return pre_zygote_table_.size() + post_zygote_table_.size();
-    }
+    size_t Size() const EXCLUSIVE_LOCKS_REQUIRED(Locks::intern_table_lock_);
 
    private:
-    typedef std::unordered_set<GcRoot<mirror::String>, StringHashEquals, StringHashEquals,
+    typedef HashSet<GcRoot<mirror::String>, GcRootEmptyFn, StringHashEquals, StringHashEquals,
         TrackingAllocator<GcRoot<mirror::String>, kAllocatorTagInternTable>> UnorderedSet;
 
     void SweepWeaks(UnorderedSet* set, IsMarkedCallback* callback, void* arg)
@@ -141,6 +149,7 @@
     UnorderedSet post_zygote_table_;
   };
 
+  // Insert if non null, otherwise return nullptr.
   mirror::String* Insert(mirror::String* s, bool is_strong)
       LOCKS_EXCLUDED(Locks::intern_table_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
diff --git a/runtime/runtime.cc b/runtime/runtime.cc
index 1cda29b..d338ad7 100644
--- a/runtime/runtime.cc
+++ b/runtime/runtime.cc
@@ -440,6 +440,7 @@
   if (IsZygote()) {
     ScopedObjectAccess soa(self);
     Runtime::Current()->GetInternTable()->AddImageStringsToTable(heap_->GetImageSpace());
+    Runtime::Current()->GetClassLinker()->MoveImageClassesToClassTable();
   }
 
   if (!IsImageDex2OatEnabled() || !Runtime::Current()->GetHeap()->HasImageSpace()) {