diff --git a/oatdump/oatdump.cc b/oatdump/oatdump.cc
index dca048f..cdf48c3 100644
--- a/oatdump/oatdump.cc
+++ b/oatdump/oatdump.cc
@@ -520,8 +520,9 @@
         LOG(WARNING) << "Failed to open dex file '" << oat_dex_file->GetDexFileLocation()
             << "': " << error_msg;
       } else {
+        const char* descriptor = m->GetDeclaringClassDescriptor();
         const DexFile::ClassDef* class_def =
-            dex_file->FindClassDef(m->GetDeclaringClassDescriptor());
+            dex_file->FindClassDef(descriptor, ComputeModifiedUtf8Hash(descriptor));
         if (class_def != nullptr) {
           uint16_t class_def_index = dex_file->GetIndexForClassDef(*class_def);
           const OatFile::OatClass oat_class = oat_dex_file->GetOatClass(class_def_index);
diff --git a/runtime/base/hash_map.h b/runtime/base/hash_map.h
new file mode 100644
index 0000000..c0f903f
--- /dev/null
+++ b/runtime/base/hash_map.h
@@ -0,0 +1,60 @@
+/*
+ * 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_MAP_H_
+#define ART_RUNTIME_BASE_HASH_MAP_H_
+
+#include <utility>
+
+#include "hash_set.h"
+
+namespace art {
+
+template <typename Fn>
+class HashMapWrapper {
+ public:
+  // Hash function.
+  template <class Key, class Value>
+  size_t operator()(const std::pair<Key, Value>& pair) const {
+    return fn_(pair.first);
+  }
+  template <class Key>
+  size_t operator()(const Key& key) const {
+    return fn_(key);
+  }
+  template <class Key, class Value>
+  bool operator()(const std::pair<Key, Value>& a, const std::pair<Key, Value>& b) const {
+    return fn_(a.first, b.first);
+  }
+  template <class Key, class Value, class Element>
+  bool operator()(const std::pair<Key, Value>& a, const Element& element) const {
+    return fn_(a.first, element);
+  }
+
+ private:
+  Fn fn_;
+};
+
+template <class Key, class Value, class EmptyFn = DefaultEmptyFn<Key>,
+    class HashFn = std::hash<Key>, class Pred = std::equal_to<Key>,
+    class Alloc = std::allocator<std::pair<Key, Value>>>
+class HashMap : public HashSet<std::pair<Key, Value>, EmptyFn, HashMapWrapper<HashFn>,
+                               HashMapWrapper<Pred>, Alloc> {
+};
+
+}  // namespace art
+
+#endif  // ART_RUNTIME_BASE_HASH_MAP_H_
diff --git a/runtime/base/hash_set_test.cc b/runtime/base/hash_set_test.cc
index 885fc06..5f498d9 100644
--- a/runtime/base/hash_set_test.cc
+++ b/runtime/base/hash_set_test.cc
@@ -22,12 +22,11 @@
 #include <unordered_set>
 
 #include "common_runtime_test.h"
-#include "utils.h"
+#include "hash_map.h"
 
 namespace art {
 
-class IsEmptyFnString {
- public:
+struct IsEmptyFnString {
   void MakeEmpty(std::string& item) const {
     item.clear();
   }
@@ -200,4 +199,25 @@
   }
 }
 
+struct IsEmptyStringPair {
+  void MakeEmpty(std::pair<std::string, int>& pair) const {
+    pair.first.clear();
+  }
+  bool IsEmpty(const std::pair<std::string, int>& pair) const {
+    return pair.first.empty();
+  }
+};
+
+TEST_F(HashSetTest, TestHashMap) {
+  HashMap<std::string, int, IsEmptyStringPair> hash_map;
+  hash_map.Insert(std::make_pair(std::string("abcd"), 123));
+  hash_map.Insert(std::make_pair(std::string("abcd"), 124));
+  hash_map.Insert(std::make_pair(std::string("bags"), 444));
+  auto it = hash_map.Find(std::string("abcd"));
+  ASSERT_EQ(it->second, 123);
+  hash_map.Erase(it);
+  it = hash_map.Find(std::string("abcd"));
+  ASSERT_EQ(it->second, 124);
+}
+
 }  // namespace art
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index fecea89..fb90b91 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -147,15 +147,6 @@
   VlogClassInitializationFailure(klass);
 }
 
-static size_t Hash(const char* s) {
-  // This is the java.lang.String hashcode for convenience, not interoperability.
-  size_t hash = 0;
-  for (; *s != '\0'; ++s) {
-    hash = hash * 31 + *s;
-  }
-  return hash;
-}
-
 // Gap between two fields in object layout.
 struct FieldGap {
   uint32_t start_offset;  // The offset from the start of the object.
@@ -2010,7 +2001,8 @@
     }
     CHECK(h_class->IsRetired());
     // Get the updated class from class table.
-    klass = LookupClass(self, descriptor, h_class.Get()->GetClassLoader());
+    klass = LookupClass(self, descriptor, ComputeModifiedUtf8Hash(descriptor),
+                        h_class.Get()->GetClassLoader());
   }
 
   // Wait for the class if it has not already been linked.
@@ -2043,22 +2035,20 @@
 typedef std::pair<const DexFile*, const DexFile::ClassDef*> ClassPathEntry;
 
 // Search a collection of DexFiles for a descriptor
-static ClassPathEntry FindInClassPath(const char* descriptor,
-                                      const std::vector<const DexFile*>& class_path) {
-  for (size_t i = 0; i != class_path.size(); ++i) {
-    const DexFile* dex_file = class_path[i];
-    const DexFile::ClassDef* dex_class_def = dex_file->FindClassDef(descriptor);
+ClassPathEntry FindInClassPath(const char* descriptor,
+                               size_t hash, const std::vector<const DexFile*>& class_path) {
+  for (const DexFile* dex_file : class_path) {
+    const DexFile::ClassDef* dex_class_def = dex_file->FindClassDef(descriptor, hash);
     if (dex_class_def != nullptr) {
       return ClassPathEntry(dex_file, dex_class_def);
     }
   }
-  // TODO: remove reinterpret_cast when issue with -std=gnu++0x host issue resolved
-  return ClassPathEntry(static_cast<const DexFile*>(nullptr),
-                        static_cast<const DexFile::ClassDef*>(nullptr));
+  return ClassPathEntry(nullptr, nullptr);
 }
 
 mirror::Class* ClassLinker::FindClassInPathClassLoader(ScopedObjectAccessAlreadyRunnable& soa,
                                                        Thread* self, const char* descriptor,
+                                                       size_t hash,
                                                        Handle<mirror::ClassLoader> class_loader) {
   if (class_loader->GetClass() !=
       soa.Decode<mirror::Class*>(WellKnownClasses::dalvik_system_PathClassLoader) ||
@@ -2066,14 +2056,14 @@
           soa.Decode<mirror::Class*>(WellKnownClasses::java_lang_BootClassLoader)) {
     return nullptr;
   }
-  ClassPathEntry pair = FindInClassPath(descriptor, boot_class_path_);
+  ClassPathEntry pair = FindInClassPath(descriptor, hash, boot_class_path_);
   // Check if this would be found in the parent boot class loader.
   if (pair.second != nullptr) {
-    mirror::Class* klass = LookupClass(self, descriptor, nullptr);
+    mirror::Class* klass = LookupClass(self, descriptor, hash, nullptr);
     if (klass != nullptr) {
       return EnsureResolved(self, descriptor, klass);
     }
-    klass = DefineClass(self, descriptor, NullHandle<mirror::ClassLoader>(), *pair.first,
+    klass = DefineClass(self, descriptor, hash, NullHandle<mirror::ClassLoader>(), *pair.first,
                         *pair.second);
     if (klass != nullptr) {
       return klass;
@@ -2121,11 +2111,11 @@
               break;
             }
             for (const DexFile* cp_dex_file : *dex_files) {
-              const DexFile::ClassDef* dex_class_def = cp_dex_file->FindClassDef(descriptor);
+              const DexFile::ClassDef* dex_class_def = cp_dex_file->FindClassDef(descriptor, hash);
               if (dex_class_def != nullptr) {
                 RegisterDexFile(*cp_dex_file);
-                mirror::Class* klass =
-                    DefineClass(self, descriptor, class_loader, *cp_dex_file, *dex_class_def);
+                mirror::Class* klass = DefineClass(self, descriptor, hash, class_loader,
+                                                   *cp_dex_file, *dex_class_def);
                 if (klass == nullptr) {
                   CHECK(self->IsExceptionPending()) << descriptor;
                   self->ClearException();
@@ -2152,19 +2142,20 @@
     // for primitive classes that aren't backed by dex files.
     return FindPrimitiveClass(descriptor[0]);
   }
+  const size_t hash = ComputeModifiedUtf8Hash(descriptor);
   // Find the class in the loaded classes table.
-  mirror::Class* klass = LookupClass(self, descriptor, class_loader.Get());
+  mirror::Class* klass = LookupClass(self, descriptor, hash, class_loader.Get());
   if (klass != nullptr) {
     return EnsureResolved(self, descriptor, klass);
   }
   // Class is not yet loaded.
   if (descriptor[0] == '[') {
-    return CreateArrayClass(self, descriptor, class_loader);
+    return CreateArrayClass(self, descriptor, hash, class_loader);
   } else if (class_loader.Get() == nullptr) {
     // The boot class loader, search the boot class path.
-    ClassPathEntry pair = FindInClassPath(descriptor, boot_class_path_);
+    ClassPathEntry pair = FindInClassPath(descriptor, hash, boot_class_path_);
     if (pair.second != nullptr) {
-      return DefineClass(self, descriptor, NullHandle<mirror::ClassLoader>(), *pair.first,
+      return DefineClass(self, descriptor, hash, NullHandle<mirror::ClassLoader>(), *pair.first,
                          *pair.second);
     } else {
       // The boot class loader is searched ahead of the application class loader, failures are
@@ -2177,16 +2168,16 @@
   } else if (Runtime::Current()->UseCompileTimeClassPath()) {
     // First try with the bootstrap class loader.
     if (class_loader.Get() != nullptr) {
-      klass = LookupClass(self, descriptor, nullptr);
+      klass = LookupClass(self, descriptor, hash, nullptr);
       if (klass != nullptr) {
         return EnsureResolved(self, descriptor, klass);
       }
     }
     // If the lookup failed search the boot class path. We don't perform a recursive call to avoid
     // a NoClassDefFoundError being allocated.
-    ClassPathEntry pair = FindInClassPath(descriptor, boot_class_path_);
+    ClassPathEntry pair = FindInClassPath(descriptor, hash, boot_class_path_);
     if (pair.second != nullptr) {
-      return DefineClass(self, descriptor, NullHandle<mirror::ClassLoader>(), *pair.first,
+      return DefineClass(self, descriptor, hash, NullHandle<mirror::ClassLoader>(), *pair.first,
                          *pair.second);
     }
     // Next try the compile time class path.
@@ -2197,9 +2188,9 @@
                                             soa.AddLocalReference<jobject>(class_loader.Get()));
       class_path = &Runtime::Current()->GetCompileTimeClassPath(jclass_loader.get());
     }
-    pair = FindInClassPath(descriptor, *class_path);
+    pair = FindInClassPath(descriptor, hash, *class_path);
     if (pair.second != nullptr) {
-      return DefineClass(self, descriptor, class_loader, *pair.first, *pair.second);
+      return DefineClass(self, descriptor, hash, class_loader, *pair.first, *pair.second);
     } else {
       // Use the pre-allocated NCDFE at compile time to avoid wasting time constructing exceptions.
       mirror::Throwable* pre_allocated = Runtime::Current()->GetPreAllocatedNoClassDefFoundError();
@@ -2208,7 +2199,8 @@
     }
   } else {
     ScopedObjectAccessUnchecked soa(self);
-    mirror::Class* cp_klass = FindClassInPathClassLoader(soa, self, descriptor, class_loader);
+    mirror::Class* cp_klass = FindClassInPathClassLoader(soa, self, descriptor, hash,
+                                                         class_loader);
     if (cp_klass != nullptr) {
       return cp_klass;
     }
@@ -2245,13 +2237,12 @@
   UNREACHABLE();
 }
 
-mirror::Class* ClassLinker::DefineClass(Thread* self, const char* descriptor,
+mirror::Class* ClassLinker::DefineClass(Thread* self, const char* descriptor, size_t hash,
                                         Handle<mirror::ClassLoader> class_loader,
                                         const DexFile& dex_file,
                                         const DexFile::ClassDef& dex_class_def) {
   StackHandleScope<3> hs(self);
   auto klass = hs.NewHandle<mirror::Class>(nullptr);
-  bool should_allocate = false;
 
   // Load the class from the dex file.
   if (UNLIKELY(!init_done_)) {
@@ -2270,14 +2261,10 @@
       klass.Assign(GetClassRoot(kJavaLangReflectArtField));
     } else if (strcmp(descriptor, "Ljava/lang/reflect/ArtMethod;") == 0) {
       klass.Assign(GetClassRoot(kJavaLangReflectArtMethod));
-    } else {
-      should_allocate = true;
     }
-  } else {
-    should_allocate = true;
   }
 
-  if (should_allocate) {
+  if (klass.Get() == nullptr) {
     // Allocate a class with the status of not ready.
     // Interface object should get the right size here. Regular class will
     // figure out the right size later and be replaced with one of the right
@@ -2302,7 +2289,7 @@
   klass->SetClinitThreadId(self->GetTid());
 
   // Add the newly loaded class to the loaded classes table.
-  mirror::Class* existing = InsertClass(descriptor, klass.Get(), Hash(descriptor));
+  mirror::Class* existing = InsertClass(descriptor, klass.Get(), hash);
   if (existing != nullptr) {
     // We failed to insert because we raced with another thread. Calling EnsureResolved may cause
     // this thread to block.
@@ -3106,7 +3093,8 @@
   primitive_class->SetPrimitiveType(type);
   primitive_class->SetStatus(mirror::Class::kStatusInitialized, self);
   const char* descriptor = Primitive::Descriptor(type);
-  mirror::Class* existing = InsertClass(descriptor, primitive_class, Hash(descriptor));
+  mirror::Class* existing = InsertClass(descriptor, primitive_class,
+                                        ComputeModifiedUtf8Hash(descriptor));
   CHECK(existing == nullptr) << "InitPrimitiveClass(" << type << ") failed";
   return primitive_class;
 }
@@ -3124,7 +3112,7 @@
 // array class; that always comes from the base element class.
 //
 // Returns nullptr with an exception raised on failure.
-mirror::Class* ClassLinker::CreateArrayClass(Thread* self, const char* descriptor,
+mirror::Class* ClassLinker::CreateArrayClass(Thread* self, const char* descriptor, size_t hash,
                                              Handle<mirror::ClassLoader> class_loader) {
   // Identify the underlying component type
   CHECK_EQ('[', descriptor[0]);
@@ -3134,7 +3122,8 @@
   if (component_type.Get() == nullptr) {
     DCHECK(self->IsExceptionPending());
     // We need to accept erroneous classes as component types.
-    component_type.Assign(LookupClass(self, descriptor + 1, class_loader.Get()));
+    const size_t component_hash = ComputeModifiedUtf8Hash(descriptor + 1);
+    component_type.Assign(LookupClass(self, descriptor + 1, component_hash, class_loader.Get()));
     if (component_type.Get() == nullptr) {
       DCHECK(self->IsExceptionPending());
       return nullptr;
@@ -3164,7 +3153,7 @@
   // class to the hash table --- necessary because of possible races with
   // other threads.)
   if (class_loader.Get() != component_type->GetClassLoader()) {
-    mirror::Class* new_class = LookupClass(self, descriptor, component_type->GetClassLoader());
+    mirror::Class* new_class = LookupClass(self, descriptor, hash, component_type->GetClassLoader());
     if (new_class != nullptr) {
       return new_class;
     }
@@ -3253,7 +3242,7 @@
 
   new_class->SetAccessFlags(access_flags);
 
-  mirror::Class* existing = InsertClass(descriptor, new_class.Get(), Hash(descriptor));
+  mirror::Class* existing = InsertClass(descriptor, new_class.Get(), hash);
   if (existing == nullptr) {
     return new_class.Get();
   }
@@ -3330,21 +3319,18 @@
 mirror::Class* ClassLinker::UpdateClass(const char* descriptor, mirror::Class* klass,
                                         size_t hash) {
   WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-  mirror::Class* existing =
-      LookupClassFromTableLocked(descriptor, klass->GetClassLoader(), hash);
-
-  if (existing == nullptr) {
+  auto existing_it = class_table_.FindWithHash(std::make_pair(descriptor, klass->GetClassLoader()),
+                                               hash);
+  if (existing_it == class_table_.end()) {
     CHECK(klass->IsProxyClass());
     return nullptr;
   }
 
+  mirror::Class* existing = existing_it->Read();
   CHECK_NE(existing, klass) << descriptor;
   CHECK(!existing->IsResolved()) << descriptor;
   CHECK_EQ(klass->GetStatus(), mirror::Class::kStatusResolving) << descriptor;
 
-  auto it = class_table_.FindWithHash(GcRoot<mirror::Class>(klass), hash);
-  CHECK(it != class_table_.end());
-
   CHECK(!klass->IsTemp()) << descriptor;
   if (kIsDebugBuild && klass->GetClassLoader() == nullptr &&
       dex_cache_image_class_lookup_required_) {
@@ -3358,7 +3344,7 @@
   VerifyObject(klass);
 
   // Update the element in the hash set.
-  *it = GcRoot<mirror::Class>(klass);
+  *existing_it = GcRoot<mirror::Class>(klass);
   if (log_new_class_table_roots_) {
     new_class_roots_.push_back(GcRoot<mirror::Class>(klass));
   }
@@ -3382,9 +3368,8 @@
   return false;
 }
 
-mirror::Class* ClassLinker::LookupClass(Thread* self, const char* descriptor,
+mirror::Class* ClassLinker::LookupClass(Thread* self, const char* descriptor, size_t hash,
                                         mirror::ClassLoader* class_loader) {
-  size_t hash = Hash(descriptor);
   {
     ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
     mirror::Class* result = LookupClassFromTableLocked(descriptor, class_loader, hash);
@@ -3451,7 +3436,7 @@
       if (klass != nullptr) {
         DCHECK(klass->GetClassLoader() == nullptr);
         const char* descriptor = klass->GetDescriptor(&temp);
-        size_t hash = Hash(descriptor);
+        size_t hash = ComputeModifiedUtf8Hash(descriptor);
         mirror::Class* existing = LookupClassFromTableLocked(descriptor, nullptr, hash);
         if (existing != nullptr) {
           CHECK_EQ(existing, klass) << PrettyClassAndClassLoader(existing) << " != "
@@ -3952,7 +3937,8 @@
     CHECK_EQ(klass.Get()->GetThrows(),
              soa.Decode<mirror::ObjectArray<mirror::ObjectArray<mirror::Class>>*>(throws));
   }
-  mirror::Class* existing = InsertClass(descriptor.c_str(), klass.Get(), Hash(descriptor.c_str()));
+  mirror::Class* existing = InsertClass(descriptor.c_str(), klass.Get(),
+                                        ComputeModifiedUtf8Hash(descriptor.c_str()));
   CHECK(existing == nullptr);
   return klass.Get();
 }
@@ -4499,7 +4485,8 @@
 
     FixupTemporaryDeclaringClass(klass.Get(), new_class_h.Get());
 
-    mirror::Class* existing = UpdateClass(descriptor, new_class_h.Get(), Hash(descriptor));
+    mirror::Class* existing = UpdateClass(descriptor, new_class_h.Get(),
+                                          ComputeModifiedUtf8Hash(descriptor));
     CHECK(existing == nullptr || existing == klass.Get());
 
     // This will notify waiters on temp class that saw the not yet resolved class in the
@@ -4695,7 +4682,7 @@
   void Add(uint32_t virtual_method_index) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     mirror::ArtMethod* local_method = klass_->GetVirtualMethodDuringLinking(virtual_method_index);
     const char* name = local_method->GetName();
-    uint32_t hash = Hash(name);
+    uint32_t hash = ComputeModifiedUtf8Hash(name);
     uint32_t index = hash % hash_size_;
     // Linear probe until we have an empty slot.
     while (hash_table_[index] != invalid_index_) {
@@ -4708,7 +4695,7 @@
   uint32_t FindAndRemove(MethodNameAndSignatureComparator* comparator)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     const char* name = comparator->GetName();
-    uint32_t hash = Hash(name);
+    uint32_t hash = ComputeModifiedUtf8Hash(name);
     size_t index = hash % hash_size_;
     while (true) {
       const uint32_t value = hash_table_[index];
@@ -5888,7 +5875,7 @@
 std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& root)
     const {
   std::string temp;
-  return Hash(root.Read()->GetDescriptor(&temp));
+  return ComputeModifiedUtf8Hash(root.Read()->GetDescriptor(&temp));
 }
 
 bool ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& a,
@@ -5902,7 +5889,7 @@
 
 std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(
     const std::pair<const char*, mirror::ClassLoader*>& element) const {
-  return Hash(element.first);
+  return ComputeModifiedUtf8Hash(element.first);
 }
 
 bool ClassLinker::ClassDescriptorHashEquals::operator()(
@@ -5919,7 +5906,7 @@
 }
 
 std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(const char* descriptor) const {
-  return Hash(descriptor);
+  return ComputeModifiedUtf8Hash(descriptor);
 }
 
 }  // namespace art
diff --git a/runtime/class_linker.h b/runtime/class_linker.h
index 7b2ba43..385f135 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -117,9 +117,10 @@
                            Handle<mirror::ClassLoader> class_loader)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  // Find a class in the path class loader, loading it if necessary.
+  // Find a class in the path class loader, loading it if necessary. Hash function is supposed to
+  // be ComputeModifiedUtf8Hash(descriptor).
   mirror::Class* FindClassInPathClassLoader(ScopedObjectAccessAlreadyRunnable& soa,
-                                            Thread* self, const char* descriptor,
+                                            Thread* self, const char* descriptor, size_t hash,
                                             Handle<mirror::ClassLoader> class_loader)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
@@ -138,14 +139,14 @@
   }
 
   // Define a new a class based on a ClassDef from a DexFile
-  mirror::Class* DefineClass(Thread* self, const char* descriptor,
+  mirror::Class* DefineClass(Thread* self, const char* descriptor, size_t hash,
                              Handle<mirror::ClassLoader> class_loader,
                              const DexFile& dex_file, const DexFile::ClassDef& dex_class_def)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   // 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,
+  mirror::Class* LookupClass(Thread* self, const char* descriptor, size_t hash,
                              mirror::ClassLoader* class_loader)
       LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
@@ -499,7 +500,7 @@
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
 
-  mirror::Class* CreateArrayClass(Thread* self, const char* descriptor,
+  mirror::Class* CreateArrayClass(Thread* self, const char* descriptor, size_t hash,
                                   Handle<mirror::ClassLoader> class_loader)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
diff --git a/runtime/dex_file.cc b/runtime/dex_file.cc
index 16bc33f..3d4184b 100644
--- a/runtime/dex_file.cc
+++ b/runtime/dex_file.cc
@@ -419,11 +419,12 @@
   return atoi(version);
 }
 
-const DexFile::ClassDef* DexFile::FindClassDef(const char* descriptor) const {
+const DexFile::ClassDef* DexFile::FindClassDef(const char* descriptor, size_t hash) const {
+  DCHECK_EQ(ComputeModifiedUtf8Hash(descriptor), hash);
   // If we have an index lookup the descriptor via that as its constant time to search.
   Index* index = class_def_index_.LoadSequentiallyConsistent();
   if (index != nullptr) {
-    auto it = index->find(descriptor);
+    auto it = index->FindWithHash(descriptor, hash);
     return (it == index->end()) ? nullptr : it->second;
   }
   // Fast path for rate no class defs case.
@@ -455,11 +456,11 @@
     // Are we the ones moving the miss count past the max? Sanity check the index doesn't exist.
     CHECK(class_def_index_.LoadSequentiallyConsistent() == nullptr);
     // Build the index.
-    index = new Index(num_class_defs);
+    index = new Index();
     for (uint32_t i = 0; i < num_class_defs;  ++i) {
       const ClassDef& class_def = GetClassDef(i);
       const char* class_descriptor = GetClassDescriptor(class_def);
-      index->insert(std::make_pair(class_descriptor, &class_def));
+      index->Insert(std::make_pair(class_descriptor, &class_def));
     }
     // Sanity check the index still doesn't exist, only 1 thread should build it.
     CHECK(class_def_index_.LoadSequentiallyConsistent() == nullptr);
diff --git a/runtime/dex_file.h b/runtime/dex_file.h
index 8ced664..a71ca42 100644
--- a/runtime/dex_file.h
+++ b/runtime/dex_file.h
@@ -22,6 +22,7 @@
 #include <unordered_map>
 #include <vector>
 
+#include "base/hash_map.h"
 #include "base/logging.h"
 #include "base/mutex.h"  // For Locks::mutator_lock_.
 #include "base/value_object.h"
@@ -649,8 +650,9 @@
     return StringByTypeIdx(class_def.class_idx_);
   }
 
-  // Looks up a class definition by its class descriptor.
-  const ClassDef* FindClassDef(const char* descriptor) const;
+  // Looks up a class definition by its class descriptor. Hash must be
+  // ComputeModifiedUtf8Hash(descriptor).
+  const ClassDef* FindClassDef(const char* descriptor, size_t hash) const;
 
   // Looks up a class definition by its type index.
   const ClassDef* FindClassDef(uint16_t type_idx) const;
@@ -986,17 +988,30 @@
   // Number of misses finding a class def from a descriptor.
   mutable Atomic<uint32_t> find_class_def_misses_;
 
+  struct UTF16EmptyFn {
+    void MakeEmpty(std::pair<const char*, const ClassDef*>& pair) const {
+      pair.first = nullptr;
+      pair.second = nullptr;
+    }
+    bool IsEmpty(const std::pair<const char*, const ClassDef*>& pair) const {
+      if (pair.first == nullptr) {
+        DCHECK(pair.second == nullptr);
+        return true;
+      }
+      return false;
+    }
+  };
   struct UTF16HashCmp {
     // Hash function.
     size_t operator()(const char* key) const {
-      return ComputeUtf8Hash(key);
+      return ComputeModifiedUtf8Hash(key);
     }
     // std::equal function.
     bool operator()(const char* a, const char* b) const {
       return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(a, b) == 0;
     }
   };
-  typedef std::unordered_map<const char*, const ClassDef*, UTF16HashCmp, UTF16HashCmp> Index;
+  typedef HashMap<const char*, const ClassDef*, UTF16EmptyFn, UTF16HashCmp, UTF16HashCmp> Index;
   mutable Atomic<Index*> class_def_index_;
 };
 std::ostream& operator<<(std::ostream& os, const DexFile& dex_file);
diff --git a/runtime/native/dalvik_system_DexFile.cc b/runtime/native/dalvik_system_DexFile.cc
index 012e03e..f37312e 100644
--- a/runtime/native/dalvik_system_DexFile.cc
+++ b/runtime/native/dalvik_system_DexFile.cc
@@ -185,9 +185,9 @@
     return NULL;
   }
   const std::string descriptor(DotToDescriptor(class_name.c_str()));
-
+  const size_t hash(ComputeModifiedUtf8Hash(descriptor.c_str()));
   for (const DexFile* dex_file : *dex_files) {
-    const DexFile::ClassDef* dex_class_def = dex_file->FindClassDef(descriptor.c_str());
+    const DexFile::ClassDef* dex_class_def = dex_file->FindClassDef(descriptor.c_str(), hash);
     if (dex_class_def != nullptr) {
       ScopedObjectAccess soa(env);
       ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
@@ -195,7 +195,7 @@
       StackHandleScope<1> hs(soa.Self());
       Handle<mirror::ClassLoader> class_loader(
           hs.NewHandle(soa.Decode<mirror::ClassLoader*>(javaLoader)));
-      mirror::Class* result = class_linker->DefineClass(soa.Self(), descriptor.c_str(),
+      mirror::Class* result = class_linker->DefineClass(soa.Self(), descriptor.c_str(), hash,
                                                         class_loader, *dex_file, *dex_class_def);
       if (result != nullptr) {
         VLOG(class_linker) << "DexFile_defineClassNative returning " << result
diff --git a/runtime/native/dalvik_system_VMRuntime.cc b/runtime/native/dalvik_system_VMRuntime.cc
index fdba43e..f6e2b21 100644
--- a/runtime/native/dalvik_system_VMRuntime.cc
+++ b/runtime/native/dalvik_system_VMRuntime.cc
@@ -262,7 +262,7 @@
   if (class_name[1] == '\0') {
     klass = linker->FindPrimitiveClass(class_name[0]);
   } else {
-    klass = linker->LookupClass(self, class_name, NULL);
+    klass = linker->LookupClass(self, class_name, ComputeModifiedUtf8Hash(class_name), NULL);
   }
   if (klass == NULL) {
     return;
diff --git a/runtime/native/java_lang_VMClassLoader.cc b/runtime/native/java_lang_VMClassLoader.cc
index 45563d2..35932e0 100644
--- a/runtime/native/java_lang_VMClassLoader.cc
+++ b/runtime/native/java_lang_VMClassLoader.cc
@@ -36,14 +36,16 @@
   }
   ClassLinker* cl = Runtime::Current()->GetClassLinker();
   std::string descriptor(DotToDescriptor(name.c_str()));
-  mirror::Class* c = cl->LookupClass(soa.Self(), descriptor.c_str(), loader);
+  const size_t descriptor_hash = ComputeModifiedUtf8Hash(descriptor.c_str());
+  mirror::Class* c = cl->LookupClass(soa.Self(), descriptor.c_str(), descriptor_hash, loader);
   if (c != nullptr && c->IsResolved()) {
     return soa.AddLocalReference<jclass>(c);
   }
   if (loader != nullptr) {
     // Try the common case.
     StackHandleScope<1> hs(soa.Self());
-    c = cl->FindClassInPathClassLoader(soa, soa.Self(), descriptor.c_str(), hs.NewHandle(loader));
+    c = cl->FindClassInPathClassLoader(soa, soa.Self(), descriptor.c_str(), descriptor_hash,
+                                       hs.NewHandle(loader));
     if (c != nullptr) {
       return soa.AddLocalReference<jclass>(c);
     }
diff --git a/runtime/utf.cc b/runtime/utf.cc
index 735815d..05b847b 100644
--- a/runtime/utf.cc
+++ b/runtime/utf.cc
@@ -85,10 +85,10 @@
   return static_cast<int32_t>(hash);
 }
 
-int32_t ComputeUtf8Hash(const char* chars) {
-  uint32_t hash = 0;
+size_t ComputeModifiedUtf8Hash(const char* chars) {
+  size_t hash = 0;
   while (*chars != '\0') {
-    hash = hash * 31 + GetUtf16FromUtf8(&chars);
+    hash = hash * 31 + *chars++;
   }
   return static_cast<int32_t>(hash);
 }
diff --git a/runtime/utf.h b/runtime/utf.h
index a09db9d..b55227b 100644
--- a/runtime/utf.h
+++ b/runtime/utf.h
@@ -79,8 +79,9 @@
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 int32_t ComputeUtf16Hash(const uint16_t* chars, size_t char_count);
 
-// Compute a hash code of a UTF-8 string.
-int32_t ComputeUtf8Hash(const char* chars);
+// Compute a hash code of a modified UTF-8 string. Not the standard java hash since it returns a
+// size_t and hashes individual chars instead of codepoint words.
+size_t ComputeModifiedUtf8Hash(const char* chars);
 
 /*
  * Retrieve the next UTF-16 character from a UTF-8 string.
diff --git a/runtime/verifier/reg_type_cache.cc b/runtime/verifier/reg_type_cache.cc
index 7c40945..1dfbe51 100644
--- a/runtime/verifier/reg_type_cache.cc
+++ b/runtime/verifier/reg_type_cache.cc
@@ -148,7 +148,8 @@
   if (can_load_classes_) {
     klass = class_linker->FindClass(self, descriptor, class_loader);
   } else {
-    klass = class_linker->LookupClass(self, descriptor, loader);
+    klass = class_linker->LookupClass(self, descriptor, ComputeModifiedUtf8Hash(descriptor),
+                                      loader);
     if (klass != nullptr && !klass->IsLoaded()) {
       // We found the class but without it being loaded its not safe for use.
       klass = nullptr;