diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index fdfd94c..ff41736 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -29,6 +29,7 @@
   GetMethodSignature \
   Instrumentation \
   Interfaces \
+  Lookup \
   Main \
   MultiDex \
   MultiDexModifiedSecondary \
@@ -78,6 +79,7 @@
 ART_GTEST_reflection_test_DEX_DEPS := Main NonStaticLeafMethods StaticLeafMethods
 ART_GTEST_stub_test_DEX_DEPS := AllFields
 ART_GTEST_transaction_test_DEX_DEPS := Transaction
+ART_GTEST_type_lookup_table_test_DEX_DEPS := Lookup
 
 # The elf writer test has dependencies on core.oat.
 ART_GTEST_elf_writer_test_HOST_DEPS := $(HOST_CORE_IMAGE_default_no-pic_64) $(HOST_CORE_IMAGE_default_no-pic_32)
@@ -220,6 +222,7 @@
   runtime/reference_table_test.cc \
   runtime/thread_pool_test.cc \
   runtime/transaction_test.cc \
+  runtime/type_lookup_table_test.cc \
   runtime/utf_test.cc \
   runtime/utils_test.cc \
   runtime/verifier/method_verifier_test.cc \
diff --git a/compiler/oat_writer.cc b/compiler/oat_writer.cc
index dcb23bf..c7b8884 100644
--- a/compiler/oat_writer.cc
+++ b/compiler/oat_writer.cc
@@ -33,6 +33,7 @@
 #include "driver/compiler_options.h"
 #include "gc/space/image_space.h"
 #include "gc/space/space.h"
+#include "handle_scope-inl.h"
 #include "image_writer.h"
 #include "linker/relative_patcher.h"
 #include "mirror/array.h"
@@ -44,7 +45,7 @@
 #include "output_stream.h"
 #include "safe_map.h"
 #include "scoped_thread_state_change.h"
-#include "handle_scope-inl.h"
+#include "type_lookup_table.h"
 #include "utils/dex_cache_arrays_layout-inl.h"
 #include "verifier/method_verifier.h"
 
@@ -107,6 +108,9 @@
     size_oat_class_status_(0),
     size_oat_class_method_bitmaps_(0),
     size_oat_class_method_offsets_(0),
+    size_oat_lookup_table_alignment_(0),
+    size_oat_lookup_table_offset_(0),
+    size_oat_lookup_table_(0),
     method_offset_map_() {
   CHECK(key_value_store != nullptr);
 
@@ -129,6 +133,10 @@
     offset = InitDexFiles(offset);
   }
   {
+    TimingLogger::ScopedTiming split("InitLookupTables", timings);
+    offset = InitLookupTables(offset);
+  }
+  {
     TimingLogger::ScopedTiming split("InitOatClasses", timings);
     offset = InitOatClasses(offset);
   }
@@ -322,7 +330,8 @@
     return true;
   }
 
-  bool VisitMethod(size_t class_def_method_index ATTRIBUTE_UNUSED, const ClassDataItemIterator& it) {
+  bool VisitMethod(size_t class_def_method_index ATTRIBUTE_UNUSED,
+                   const ClassDataItemIterator& it) {
     // Fill in the compiled_methods_ array for methods that have a
     // CompiledMethod. We track the number of non-null entries in
     // num_non_null_compiled_methods_ since we only want to allocate
@@ -1043,11 +1052,29 @@
     oat_dex_files_[i]->dex_file_offset_ = offset;
 
     const DexFile* dex_file = (*dex_files_)[i];
+
+    // Initialize type lookup table
+    oat_dex_files_[i]->lookup_table_ = dex_file->GetTypeLookupTable();
+
     offset += dex_file->GetHeader().file_size_;
   }
   return offset;
 }
 
+size_t OatWriter::InitLookupTables(size_t offset) {
+  for (OatDexFile* oat_dex_file : oat_dex_files_) {
+    if (oat_dex_file->lookup_table_ != nullptr) {
+      uint32_t aligned_offset = RoundUp(offset, 4);
+      oat_dex_file->lookup_table_offset_ = aligned_offset;
+      size_oat_lookup_table_alignment_ += aligned_offset - offset;
+      offset = aligned_offset + oat_dex_file->lookup_table_->RawDataLength();
+    } else {
+      oat_dex_file->lookup_table_offset_ = 0;
+    }
+  }
+  return offset;
+}
+
 size_t OatWriter::InitOatClasses(size_t offset) {
   // calculate the offsets within OatDexFiles to OatClasses
   InitOatClassesMethodVisitor visitor(this, offset);
@@ -1256,6 +1283,9 @@
     DO_STAT(size_oat_class_status_);
     DO_STAT(size_oat_class_method_bitmaps_);
     DO_STAT(size_oat_class_method_offsets_);
+    DO_STAT(size_oat_lookup_table_alignment_);
+    DO_STAT(size_oat_lookup_table_offset_);
+    DO_STAT(size_oat_lookup_table_);
     #undef DO_STAT
 
     VLOG(compiler) << "size_total=" << PrettySize(size_total) << " (" << size_total << "B)"; \
@@ -1309,6 +1339,9 @@
     }
     size_dex_file_ += dex_file->GetHeader().file_size_;
   }
+  if (!WriteLookupTables(out, file_offset)) {
+    return false;
+  }
   for (size_t i = 0; i != oat_classes_.size(); ++i) {
     if (!oat_classes_[i]->Write(this, out, file_offset)) {
       PLOG(ERROR) << "Failed to write oat methods information to " << out->GetLocation();
@@ -1318,6 +1351,35 @@
   return true;
 }
 
+bool OatWriter::WriteLookupTables(OutputStream* out, const size_t file_offset) {
+  for (size_t i = 0; i < oat_dex_files_.size(); ++i) {
+    const uint32_t lookup_table_offset = oat_dex_files_[i]->lookup_table_offset_;
+    const TypeLookupTable* table = oat_dex_files_[i]->lookup_table_;
+    DCHECK_EQ(lookup_table_offset == 0, table == nullptr);
+    if (lookup_table_offset == 0) {
+      continue;
+    }
+    const uint32_t expected_offset = file_offset + lookup_table_offset;
+    off_t actual_offset = out->Seek(expected_offset, kSeekSet);
+    if (static_cast<uint32_t>(actual_offset) != expected_offset) {
+      const DexFile* dex_file = (*dex_files_)[i];
+      PLOG(ERROR) << "Failed to seek to lookup table section. Actual: " << actual_offset
+                  << " Expected: " << expected_offset << " File: " << dex_file->GetLocation();
+      return false;
+    }
+    if (table != nullptr) {
+      if (!out->WriteFully(table->RawData(), table->RawDataLength())) {
+        const DexFile* dex_file = (*dex_files_)[i];
+        PLOG(ERROR) << "Failed to write lookup table for " << dex_file->GetLocation()
+                    << " to " << out->GetLocation();
+        return false;
+      }
+      size_oat_lookup_table_ += table->RawDataLength();
+    }
+  }
+  return true;
+}
+
 size_t OatWriter::WriteMaps(OutputStream* out, const size_t file_offset, size_t relative_offset) {
   #define VISIT(VisitorType)                                              \
     do {                                                                  \
@@ -1425,6 +1487,7 @@
   dex_file_location_data_ = reinterpret_cast<const uint8_t*>(location.data());
   dex_file_location_checksum_ = dex_file.GetLocationChecksum();
   dex_file_offset_ = 0;
+  lookup_table_offset_ = 0;
   methods_offsets_.resize(dex_file.NumClassDefs());
 }
 
@@ -1433,6 +1496,7 @@
           + dex_file_location_size_
           + sizeof(dex_file_location_checksum_)
           + sizeof(dex_file_offset_)
+          + sizeof(lookup_table_offset_)
           + (sizeof(methods_offsets_[0]) * methods_offsets_.size());
 }
 
@@ -1441,6 +1505,10 @@
   oat_header->UpdateChecksum(dex_file_location_data_, dex_file_location_size_);
   oat_header->UpdateChecksum(&dex_file_location_checksum_, sizeof(dex_file_location_checksum_));
   oat_header->UpdateChecksum(&dex_file_offset_, sizeof(dex_file_offset_));
+  oat_header->UpdateChecksum(&lookup_table_offset_, sizeof(lookup_table_offset_));
+  if (lookup_table_ != nullptr) {
+    oat_header->UpdateChecksum(lookup_table_->RawData(), lookup_table_->RawDataLength());
+  }
   oat_header->UpdateChecksum(&methods_offsets_[0],
                             sizeof(methods_offsets_[0]) * methods_offsets_.size());
 }
@@ -1469,6 +1537,11 @@
     return false;
   }
   oat_writer->size_oat_dex_file_offset_ += sizeof(dex_file_offset_);
+  if (!out->WriteFully(&lookup_table_offset_, sizeof(lookup_table_offset_))) {
+    PLOG(ERROR) << "Failed to write lookup table offset to " << out->GetLocation();
+    return false;
+  }
+  oat_writer->size_oat_lookup_table_offset_ += sizeof(lookup_table_offset_);
   if (!out->WriteFully(&methods_offsets_[0],
                       sizeof(methods_offsets_[0]) * methods_offsets_.size())) {
     PLOG(ERROR) << "Failed to write methods offsets to " << out->GetLocation();
diff --git a/compiler/oat_writer.h b/compiler/oat_writer.h
index d6cb65b..f2fe048 100644
--- a/compiler/oat_writer.h
+++ b/compiler/oat_writer.h
@@ -24,8 +24,8 @@
 #include "linker/relative_patcher.h"  // For linker::RelativePatcherTargetProvider.
 #include "mem_map.h"
 #include "method_reference.h"
-#include "oat.h"
 #include "mirror/class.h"
+#include "oat.h"
 #include "safe_map.h"
 
 namespace art {
@@ -36,6 +36,7 @@
 class ImageWriter;
 class OutputStream;
 class TimingLogger;
+class TypeLookupTable;
 
 // OatHeader         variable length with count of D OatDexFiles
 //
@@ -49,6 +50,11 @@
 // ...
 // Dex[D]
 //
+// TypeLookupTable[0] one descriptor to class def index hash table for each OatDexFile.
+// TypeLookupTable[1]
+// ...
+// TypeLookupTable[D]
+//
 // OatClass[0]       one variable sized OatClass for each of C DexFile::ClassDefs
 // OatClass[1]       contains OatClass entries with class status, offsets to code, etc.
 // ...
@@ -168,6 +174,7 @@
 
   size_t InitOatHeader();
   size_t InitOatDexFiles(size_t offset);
+  size_t InitLookupTables(size_t offset);
   size_t InitDexFiles(size_t offset);
   size_t InitOatClasses(size_t offset);
   size_t InitOatMaps(size_t offset);
@@ -177,6 +184,7 @@
       SHARED_REQUIRES(Locks::mutator_lock_);
 
   bool WriteTables(OutputStream* out, const size_t file_offset);
+  bool WriteLookupTables(OutputStream* out, const size_t file_offset);
   size_t WriteMaps(OutputStream* out, const size_t file_offset, size_t relative_offset);
   size_t WriteCode(OutputStream* out, const size_t file_offset, size_t relative_offset);
   size_t WriteCodeDexFiles(OutputStream* out, const size_t file_offset, size_t relative_offset);
@@ -199,6 +207,8 @@
     const uint8_t* dex_file_location_data_;
     uint32_t dex_file_location_checksum_;
     uint32_t dex_file_offset_;
+    uint32_t lookup_table_offset_;
+    TypeLookupTable* lookup_table_;  // Owned by the dex file.
     std::vector<uint32_t> methods_offsets_;
 
    private:
@@ -333,6 +343,9 @@
   uint32_t size_oat_class_status_;
   uint32_t size_oat_class_method_bitmaps_;
   uint32_t size_oat_class_method_offsets_;
+  uint32_t size_oat_lookup_table_alignment_;
+  uint32_t size_oat_lookup_table_offset_;
+  uint32_t size_oat_lookup_table_;
 
   std::unique_ptr<linker::RelativePatcher> relative_patcher_;
 
diff --git a/dex2oat/dex2oat.cc b/dex2oat/dex2oat.cc
index 384b879..af0bb65 100644
--- a/dex2oat/dex2oat.cc
+++ b/dex2oat/dex2oat.cc
@@ -1410,6 +1410,7 @@
       ScopedObjectAccess soa(self);
       dex_caches_.push_back(soa.AddLocalReference<jobject>(
           class_linker->RegisterDexFile(*dex_file, Runtime::Current()->GetLinearAlloc())));
+      dex_file->CreateTypeLookupTable();
     }
 
     // If we use a swap file, ensure we are above the threshold to make it necessary.
diff --git a/runtime/Android.mk b/runtime/Android.mk
index 09d7311..1fdffe3 100644
--- a/runtime/Android.mk
+++ b/runtime/Android.mk
@@ -47,6 +47,7 @@
   dex_file_verifier.cc \
   dex_instruction.cc \
   elf_file.cc \
+  fault_handler.cc \
   gc/allocation_record.cc \
   gc/allocator/dlmalloc.cc \
   gc/allocator/rosalloc.cc \
@@ -162,6 +163,7 @@
   os_linux.cc \
   parsed_options.cc \
   primitive.cc \
+  profiler.cc \
   quick_exception_handler.cc \
   quick/inline_method_analyser.cc \
   reference_table.cc \
@@ -176,8 +178,7 @@
   thread_pool.cc \
   trace.cc \
   transaction.cc \
-  profiler.cc \
-  fault_handler.cc \
+  type_lookup_table.cc \
   utf.cc \
   utils.cc \
   verifier/dex_gc_map.cc \
diff --git a/runtime/dex_file.cc b/runtime/dex_file.cc
index ae62e2b..b3ca6ac 100644
--- a/runtime/dex_file.cc
+++ b/runtime/dex_file.cc
@@ -37,6 +37,7 @@
 #include "dex_file-inl.h"
 #include "dex_file_verifier.h"
 #include "globals.h"
+#include "handle_scope-inl.h"
 #include "leb128.h"
 #include "mirror/field.h"
 #include "mirror/method.h"
@@ -44,8 +45,8 @@
 #include "os.h"
 #include "reflection.h"
 #include "safe_map.h"
-#include "handle_scope-inl.h"
 #include "thread.h"
+#include "type_lookup_table.h"
 #include "utf-inl.h"
 #include "utils.h"
 #include "well_known_classes.h"
@@ -414,11 +415,19 @@
       method_ids_(reinterpret_cast<const MethodId*>(base + header_->method_ids_off_)),
       proto_ids_(reinterpret_cast<const ProtoId*>(base + header_->proto_ids_off_)),
       class_defs_(reinterpret_cast<const ClassDef*>(base + header_->class_defs_off_)),
-      find_class_def_misses_(0),
-      class_def_index_(nullptr),
       oat_dex_file_(oat_dex_file) {
   CHECK(begin_ != nullptr) << GetLocation();
   CHECK_GT(size_, 0U) << GetLocation();
+  const uint8_t* lookup_data = (oat_dex_file != nullptr)
+      ? oat_dex_file->GetLookupTableData()
+      : nullptr;
+  if (lookup_data != nullptr) {
+    if (lookup_data + TypeLookupTable::RawDataLength(*this) > oat_dex_file->GetOatFile()->End()) {
+      LOG(WARNING) << "found truncated lookup table in " << GetLocation();
+    } else {
+      lookup_table_.reset(TypeLookupTable::Open(lookup_data, *this));
+    }
+  }
 }
 
 DexFile::~DexFile() {
@@ -426,8 +435,6 @@
   // that's only called after DetachCurrentThread, which means there's no JNIEnv. We could
   // re-attach, but cleaning up these global references is not obviously useful. It's not as if
   // the global reference table is otherwise empty!
-  // Remove the index if one were created.
-  delete class_def_index_.LoadRelaxed();
 }
 
 bool DexFile::Init(std::string* error_msg) {
@@ -477,51 +484,26 @@
 
 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->FindWithHash(descriptor, hash);
-    return (it == index->end()) ? nullptr : it->second;
+  if (LIKELY(lookup_table_ != nullptr)) {
+    const uint32_t class_def_idx = lookup_table_->Lookup(descriptor, hash);
+    return (class_def_idx != DexFile::kDexNoIndex) ? &GetClassDef(class_def_idx) : nullptr;
   }
+
   // Fast path for rate no class defs case.
-  uint32_t num_class_defs = NumClassDefs();
+  const uint32_t num_class_defs = NumClassDefs();
   if (num_class_defs == 0) {
     return nullptr;
   }
-  // Search for class def with 2 binary searches and then a linear search.
-  const StringId* string_id = FindStringId(descriptor);
-  if (string_id != nullptr) {
-    const TypeId* type_id = FindTypeId(GetIndexForStringId(*string_id));
-    if (type_id != nullptr) {
-      uint16_t type_idx = GetIndexForTypeId(*type_id);
-      for (size_t i = 0; i < num_class_defs; ++i) {
-        const ClassDef& class_def = GetClassDef(i);
-        if (class_def.class_idx_ == type_idx) {
-          return &class_def;
-        }
+  const TypeId* type_id = FindTypeId(descriptor);
+  if (type_id != nullptr) {
+    uint16_t type_idx = GetIndexForTypeId(*type_id);
+    for (size_t i = 0; i < num_class_defs; ++i) {
+      const ClassDef& class_def = GetClassDef(i);
+      if (class_def.class_idx_ == type_idx) {
+        return &class_def;
       }
     }
   }
-  // A miss. If we've had kMaxFailedDexClassDefLookups misses then build an index to speed things
-  // up. This isn't done eagerly at construction as construction is not performed in multi-threaded
-  // sections of tools like dex2oat. If we're lazy we hopefully increase the chance of balancing
-  // out which thread builds the index.
-  const uint32_t kMaxFailedDexClassDefLookups = 100;
-  uint32_t old_misses = find_class_def_misses_.FetchAndAddSequentiallyConsistent(1);
-  if (old_misses == kMaxFailedDexClassDefLookups) {
-    // 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();
-    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));
-    }
-    // Sanity check the index still doesn't exist, only 1 thread should build it.
-    CHECK(class_def_index_.LoadSequentiallyConsistent() == nullptr);
-    class_def_index_.StoreSequentiallyConsistent(index);
-  }
   return nullptr;
 }
 
@@ -625,6 +607,26 @@
   return nullptr;
 }
 
+const DexFile::TypeId* DexFile::FindTypeId(const char* string) const {
+  int32_t lo = 0;
+  int32_t hi = NumTypeIds() - 1;
+  while (hi >= lo) {
+    int32_t mid = (hi + lo) / 2;
+    const TypeId& type_id = GetTypeId(mid);
+    const DexFile::StringId& str_id = GetStringId(type_id.descriptor_idx_);
+    const char* str = GetStringData(str_id);
+    int compare = CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(string, str);
+    if (compare > 0) {
+      lo = mid + 1;
+    } else if (compare < 0) {
+      hi = mid - 1;
+    } else {
+      return &type_id;
+    }
+  }
+  return nullptr;
+}
+
 const DexFile::StringId* DexFile::FindStringId(const uint16_t* string, size_t length) const {
   int32_t lo = 0;
   int32_t hi = NumStringIds() - 1;
@@ -697,6 +699,10 @@
   return nullptr;
 }
 
+void DexFile::CreateTypeLookupTable() const {
+  lookup_table_.reset(TypeLookupTable::Create(*this));
+}
+
 // Given a signature place the type ids into the given vector
 bool DexFile::CreateTypeList(const StringPiece& signature, uint16_t* return_type_idx,
                              std::vector<uint16_t>* param_type_idxs) const {
diff --git a/runtime/dex_file.h b/runtime/dex_file.h
index 47e5c12..e7877b2 100644
--- a/runtime/dex_file.h
+++ b/runtime/dex_file.h
@@ -51,6 +51,7 @@
 class Signature;
 template<class T> class Handle;
 class StringPiece;
+class TypeLookupTable;
 class ZipArchive;
 
 // TODO: move all of the macro functionality into the DexCache class.
@@ -532,6 +533,8 @@
   // Looks up a string id for a given modified utf8 string.
   const StringId* FindStringId(const char* string) const;
 
+  const TypeId* FindTypeId(const char* string) const;
+
   // Looks up a string id for a given utf16 string.
   const StringId* FindStringId(const uint16_t* string, size_t length) const;
 
@@ -1139,6 +1142,12 @@
     return oat_dex_file_;
   }
 
+  TypeLookupTable* GetTypeLookupTable() const {
+    return lookup_table_.get();
+  }
+
+  void CreateTypeLookupTable() const;
+
  private:
   // Opens a .dex file
   static std::unique_ptr<const DexFile> OpenFile(int fd, const char* location,
@@ -1237,44 +1246,11 @@
   // Points to the base of the class definition list.
   const ClassDef* const class_defs_;
 
-  // 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 ComputeModifiedUtf8Hash(key);
-    }
-    // std::equal function.
-    bool operator()(const char* a, const char* b) const {
-      return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(a, b) == 0;
-    }
-  };
-  using Index = HashMap<const char*,
-                        const ClassDef*,
-                        UTF16EmptyFn,
-                        UTF16HashCmp,
-                        UTF16HashCmp,
-                        std::allocator<std::pair<const char*, const ClassDef*>>>;
-  mutable Atomic<Index*> class_def_index_;
-
   // If this dex file was loaded from an oat file, oat_dex_file_ contains a
   // pointer to the OatDexFile it was loaded from. Otherwise oat_dex_file_ is
   // null.
   const OatDexFile* oat_dex_file_;
+  mutable std::unique_ptr<TypeLookupTable> lookup_table_;
 
   friend class DexFileVerifierTest;
 };
diff --git a/runtime/oat.h b/runtime/oat.h
index 276e7f3..5b780c3 100644
--- a/runtime/oat.h
+++ b/runtime/oat.h
@@ -31,7 +31,7 @@
 class PACKED(4) OatHeader {
  public:
   static constexpr uint8_t kOatMagic[] = { 'o', 'a', 't', '\n' };
-  static constexpr uint8_t kOatVersion[] = { '0', '7', '2', '\0' };
+  static constexpr uint8_t kOatVersion[] = { '0', '7', '3', '\0' };
 
   static constexpr const char* kImageLocationKey = "image-location";
   static constexpr const char* kDex2OatCmdLineKey = "dex2oat-cmdline";
diff --git a/runtime/oat_file.cc b/runtime/oat_file.cc
index a162a4e..680f4ac 100644
--- a/runtime/oat_file.cc
+++ b/runtime/oat_file.cc
@@ -547,6 +547,25 @@
       return false;
     }
     const DexFile::Header* header = reinterpret_cast<const DexFile::Header*>(dex_file_pointer);
+
+    if (UNLIKELY(oat > End())) {
+      *error_msg = StringPrintf("In oat file '%s' found OatDexFile #%zd for '%s' with truncated "
+                                "lookup table offset", GetLocation().c_str(), i,
+                                dex_file_location.c_str());
+      return false;
+    }
+    uint32_t lookup_table_offset = *reinterpret_cast<const uint32_t*>(oat);
+    oat += sizeof(lookup_table_offset);
+    if (Begin() + lookup_table_offset > End()) {
+      *error_msg = StringPrintf("In oat file '%s' found OatDexFile #%zd for '%s' with truncated "
+                                "lookup table", GetLocation().c_str(), i,
+                                dex_file_location.c_str());
+      return false;
+    }
+    const uint8_t* lookup_table_data = lookup_table_offset != 0u
+        ? Begin() + lookup_table_offset
+        : nullptr;
+
     const uint32_t* methods_offsets_pointer = reinterpret_cast<const uint32_t*>(oat);
 
     oat += (sizeof(*methods_offsets_pointer) * header->class_defs_size_);
@@ -586,6 +605,7 @@
                                               canonical_location,
                                               dex_file_checksum,
                                               dex_file_pointer,
+                                              lookup_table_data,
                                               methods_offsets_pointer,
                                               current_dex_cache_arrays);
     oat_dex_files_storage_.push_back(oat_dex_file);
@@ -709,6 +729,7 @@
                                 const std::string& canonical_dex_file_location,
                                 uint32_t dex_file_location_checksum,
                                 const uint8_t* dex_file_pointer,
+                                const uint8_t* lookup_table_data,
                                 const uint32_t* oat_class_offsets_pointer,
                                 uint8_t* dex_cache_arrays)
     : oat_file_(oat_file),
@@ -716,6 +737,7 @@
       canonical_dex_file_location_(canonical_dex_file_location),
       dex_file_location_checksum_(dex_file_location_checksum),
       dex_file_pointer_(dex_file_pointer),
+      lookup_table_data_(lookup_table_data),
       oat_class_offsets_pointer_(oat_class_offsets_pointer),
       dex_cache_arrays_(dex_cache_arrays) {}
 
diff --git a/runtime/oat_file.h b/runtime/oat_file.h
index 6acdf86..0a77654 100644
--- a/runtime/oat_file.h
+++ b/runtime/oat_file.h
@@ -400,6 +400,10 @@
     return dex_cache_arrays_;
   }
 
+  const uint8_t* GetLookupTableData() const {
+    return lookup_table_data_;
+  }
+
   ~OatDexFile();
 
  private:
@@ -408,6 +412,7 @@
              const std::string& canonical_dex_file_location,
              uint32_t dex_file_checksum,
              const uint8_t* dex_file_pointer,
+             const uint8_t* lookup_table_data,
              const uint32_t* oat_class_offsets_pointer,
              uint8_t* dex_cache_arrays);
 
@@ -416,6 +421,7 @@
   const std::string canonical_dex_file_location_;
   const uint32_t dex_file_location_checksum_;
   const uint8_t* const dex_file_pointer_;
+  const uint8_t* lookup_table_data_;
   const uint32_t* const oat_class_offsets_pointer_;
   uint8_t* const dex_cache_arrays_;
 
diff --git a/runtime/type_lookup_table.cc b/runtime/type_lookup_table.cc
new file mode 100644
index 0000000..0d40bb7
--- /dev/null
+++ b/runtime/type_lookup_table.cc
@@ -0,0 +1,131 @@
+/*
+ * Copyright (C) 2015 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 "type_lookup_table.h"
+
+#include "dex_file-inl.h"
+#include "utf-inl.h"
+#include "utils.h"
+
+#include <memory>
+#include <cstring>
+
+namespace art {
+
+static uint16_t MakeData(uint16_t class_def_idx, uint32_t hash, uint32_t mask) {
+  uint16_t hash_mask = static_cast<uint16_t>(~mask);
+  return (static_cast<uint16_t>(hash) & hash_mask) | class_def_idx;
+}
+
+TypeLookupTable::~TypeLookupTable() {
+  if (!owns_entries_) {
+    // We don't actually own the entries, don't let the unique_ptr release them.
+    entries_.release();
+  }
+}
+
+uint32_t TypeLookupTable::RawDataLength() const {
+  return RawDataLength(dex_file_);
+}
+
+uint32_t TypeLookupTable::RawDataLength(const DexFile& dex_file) {
+  return RoundUpToPowerOfTwo(dex_file.NumClassDefs()) * sizeof(Entry);
+}
+
+TypeLookupTable* TypeLookupTable::Create(const DexFile& dex_file) {
+  const uint32_t num_class_defs = dex_file.NumClassDefs();
+  return (num_class_defs == 0 || num_class_defs > std::numeric_limits<uint16_t>::max())
+      ? nullptr
+      : new TypeLookupTable(dex_file);
+}
+
+TypeLookupTable* TypeLookupTable::Open(const uint8_t* raw_data, const DexFile& dex_file) {
+  return new TypeLookupTable(raw_data, dex_file);
+}
+
+TypeLookupTable::TypeLookupTable(const DexFile& dex_file)
+    : dex_file_(dex_file),
+      mask_(RoundUpToPowerOfTwo(dex_file.NumClassDefs()) - 1),
+      entries_(new Entry[mask_ + 1]),
+      owns_entries_(true) {
+  std::vector<uint16_t> conflict_class_defs;
+  // The first stage. Put elements on their initial positions. If an initial position is already
+  // occupied then delay the insertion of the element to the second stage to reduce probing
+  // distance.
+  for (size_t i = 0; i < dex_file.NumClassDefs(); ++i) {
+    const DexFile::ClassDef& class_def = dex_file.GetClassDef(i);
+    const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
+    const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
+    const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
+    Entry entry;
+    entry.str_offset = str_id.string_data_off_;
+    entry.data = MakeData(i, hash, GetSizeMask());
+    if (!SetOnInitialPos(entry, hash)) {
+      conflict_class_defs.push_back(i);
+    }
+  }
+  // The second stage. The initial position of these elements had a collision. Put these elements
+  // into the nearest free cells and link them together by updating next_pos_delta.
+  for (uint16_t class_def_idx : conflict_class_defs) {
+    const DexFile::ClassDef& class_def = dex_file.GetClassDef(class_def_idx);
+    const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
+    const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
+    const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
+    Entry entry;
+    entry.str_offset = str_id.string_data_off_;
+    entry.data = MakeData(class_def_idx, hash, GetSizeMask());
+    Insert(entry, hash);
+  }
+}
+
+TypeLookupTable::TypeLookupTable(const uint8_t* raw_data, const DexFile& dex_file)
+    : dex_file_(dex_file),
+      mask_(RoundUpToPowerOfTwo(dex_file.NumClassDefs()) - 1),
+      entries_(reinterpret_cast<Entry*>(const_cast<uint8_t*>(raw_data))),
+      owns_entries_(false) {}
+
+bool TypeLookupTable::SetOnInitialPos(const Entry& entry, uint32_t hash) {
+  const uint32_t pos = hash & GetSizeMask();
+  if (!entries_[pos].IsEmpty()) {
+    return false;
+  }
+  entries_[pos] = entry;
+  entries_[pos].next_pos_delta = 0;
+  return true;
+}
+
+void TypeLookupTable::Insert(const Entry& entry, uint32_t hash) {
+  uint32_t pos = FindLastEntryInBucket(hash & GetSizeMask());
+  uint32_t next_pos = (pos + 1) & GetSizeMask();
+  while (!entries_[next_pos].IsEmpty()) {
+    next_pos = (next_pos + 1) & GetSizeMask();
+  }
+  const uint32_t delta = (next_pos >= pos) ? (next_pos - pos) : (next_pos + Size() - pos);
+  entries_[pos].next_pos_delta = delta;
+  entries_[next_pos] = entry;
+  entries_[next_pos].next_pos_delta = 0;
+}
+
+uint32_t TypeLookupTable::FindLastEntryInBucket(uint32_t pos) const {
+  const Entry* entry = &entries_[pos];
+  while (!entry->IsLast()) {
+    pos = (pos + entry->next_pos_delta) & GetSizeMask();
+    entry = &entries_[pos];
+  }
+  return pos;
+}
+
+}  // namespace art
diff --git a/runtime/type_lookup_table.h b/runtime/type_lookup_table.h
new file mode 100644
index 0000000..3c2295c
--- /dev/null
+++ b/runtime/type_lookup_table.h
@@ -0,0 +1,162 @@
+/*
+ * Copyright (C) 2015 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_TYPE_LOOKUP_TABLE_H_
+#define ART_RUNTIME_TYPE_LOOKUP_TABLE_H_
+
+#include "dex_file.h"
+#include "leb128.h"
+#include "utf.h"
+
+namespace art {
+
+/**
+ * TypeLookupTable used to find class_def_idx by class descriptor quickly.
+ * Implementation of TypeLookupTable is based on hash table.
+ * This class instantiated at compile time by calling Create() method and written into OAT file.
+ * At runtime, the raw data is read from memory-mapped file by calling Open() method. The table
+ * memory remains clean.
+ */
+class TypeLookupTable {
+ public:
+  ~TypeLookupTable();
+
+  // Return the number of buckets in the lookup table.
+  uint32_t Size() const {
+    return mask_ + 1;
+  }
+
+  // Method search class_def_idx by class descriptor and it's hash.
+  // If no data found then the method returns DexFile::kDexNoIndex
+  ALWAYS_INLINE uint32_t Lookup(const char* str, uint32_t hash) const {
+    uint32_t pos = hash & GetSizeMask();
+    // Thanks to special insertion algorithm, the element at position pos can be empty or start of
+    // bucket.
+    const Entry* entry = &entries_[pos];
+    while (!entry->IsEmpty()) {
+      if (CmpHashBits(entry->data, hash) && IsStringsEquals(str, entry->str_offset)) {
+        return GetClassDefIdx(entry->data);
+      }
+      if (entry->IsLast()) {
+        return DexFile::kDexNoIndex;
+      }
+      pos = (pos + entry->next_pos_delta) & GetSizeMask();
+      entry = &entries_[pos];
+    }
+    return DexFile::kDexNoIndex;
+  }
+
+  // Method creates lookup table for dex file
+  static TypeLookupTable* Create(const DexFile& dex_file);
+
+  // Method opens lookup table from binary data. Lookup table does not owns binary data.
+  static TypeLookupTable* Open(const uint8_t* raw_data, const DexFile& dex_file);
+
+  // Method returns pointer to binary data of lookup table. Used by the oat writer.
+  const uint8_t* RawData() const {
+    return reinterpret_cast<const uint8_t*>(entries_.get());
+  }
+
+  // Method returns length of binary data. Used by the oat writer.
+  uint32_t RawDataLength() const;
+
+  // Method returns length of binary data for the specified dex file.
+  static uint32_t RawDataLength(const DexFile& dex_file);
+
+ private:
+   /**
+    * To find element we need to compare strings.
+    * It is faster to compare first hashes and then strings itself.
+    * But we have no full hash of element of table. But we can use 2 ideas.
+    * 1. All minor bits of hash inside one bucket are equals.
+    * 2. If dex file contains N classes and size of hash table is 2^n (where N <= 2^n)
+    *    then 16-n bits are free. So we can encode part of element's hash into these bits.
+    * So hash of element can be divided on three parts:
+    * XXXX XXXX XXXX YYYY YZZZ ZZZZ ZZZZZ
+    * Z - a part of hash encoded in bucket (these bits of has are same for all elements in bucket) -
+    * n bits
+    * Y - a part of hash that we can write into free 16-n bits (because only n bits used to store
+    * class_def_idx)
+    * X - a part of has that we can't use without increasing increase
+    * So the data element of Entry used to store class_def_idx and part of hash of the entry.
+    */
+  struct Entry {
+    uint32_t str_offset;
+    uint16_t data;
+    uint16_t next_pos_delta;
+
+    Entry() : str_offset(0), data(0), next_pos_delta(0) {}
+
+    bool IsEmpty() const {
+      return str_offset == 0;
+    }
+
+    bool IsLast() const {
+      return next_pos_delta == 0;
+    }
+  };
+
+  // Construct from a dex file.
+  explicit TypeLookupTable(const DexFile& dex_file);
+
+  // Construct from a dex file with existing data.
+  TypeLookupTable(const uint8_t* raw_data, const DexFile& dex_file);
+
+  bool IsStringsEquals(const char* str, uint32_t str_offset) const {
+    const uint8_t* ptr = dex_file_.Begin() + str_offset;
+    // Skip string length.
+    DecodeUnsignedLeb128(&ptr);
+    return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(
+        str, reinterpret_cast<const char*>(ptr)) == 0;
+  }
+
+  // Method extracts hash bits from element's data and compare them with
+  // the corresponding bits of the specified hash
+  bool CmpHashBits(uint32_t data, uint32_t hash) const {
+    uint32_t mask = static_cast<uint16_t>(~GetSizeMask());
+    return (hash & mask) == (data & mask);
+  }
+
+  uint32_t GetClassDefIdx(uint32_t data) const {
+    return data & mask_;
+  }
+
+  uint32_t GetSizeMask() const {
+    return mask_;
+  }
+
+  // Attempt to set an entry on it's hash' slot. If there is alrady something there, return false.
+  // Otherwise return true.
+  bool SetOnInitialPos(const Entry& entry, uint32_t hash);
+
+  // Insert an entry, probes until there is an empty slot.
+  void Insert(const Entry& entry, uint32_t hash);
+
+  // Find the last entry in a chain.
+  uint32_t FindLastEntryInBucket(uint32_t cur_pos) const;
+
+  const DexFile& dex_file_;
+  const uint32_t mask_;
+  std::unique_ptr<Entry[]> entries_;
+  // owns_entries_ specifies if the lookup table owns the entries_ array.
+  const bool owns_entries_;
+
+  DISALLOW_IMPLICIT_CONSTRUCTORS(TypeLookupTable);
+};
+
+}  // namespace art
+
+#endif  // ART_RUNTIME_TYPE_LOOKUP_TABLE_H_
diff --git a/runtime/type_lookup_table_test.cc b/runtime/type_lookup_table_test.cc
new file mode 100644
index 0000000..7f500cc
--- /dev/null
+++ b/runtime/type_lookup_table_test.cc
@@ -0,0 +1,86 @@
+/*
+ * Copyright (C) 2011 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 <memory>
+
+#include "common_runtime_test.h"
+#include "dex_file-inl.h"
+#include "scoped_thread_state_change.h"
+#include "type_lookup_table.h"
+#include "utf-inl.h"
+
+namespace art {
+
+class TypeLookupTableTest : public CommonRuntimeTest {
+ public:
+  size_t kDexNoIndex = DexFile::kDexNoIndex;  // Make copy to prevent linking errors.
+};
+
+TEST_F(TypeLookupTableTest, CreateLookupTable) {
+  ScopedObjectAccess soa(Thread::Current());
+  std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup"));
+  std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file));
+  ASSERT_NE(nullptr, table.get());
+  ASSERT_NE(nullptr, table->RawData());
+  ASSERT_EQ(32U, table->RawDataLength());
+}
+
+TEST_F(TypeLookupTableTest, FindNonExistingClassWithoutCollisions) {
+  ScopedObjectAccess soa(Thread::Current());
+  std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup"));
+  std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file));
+  ASSERT_NE(nullptr, table.get());
+  const char* descriptor = "LBA;";
+  size_t hash = ComputeModifiedUtf8Hash(descriptor);
+  uint32_t class_def_idx = table->Lookup(descriptor, hash);
+  ASSERT_EQ(kDexNoIndex, class_def_idx);
+}
+
+TEST_F(TypeLookupTableTest, FindNonExistingClassWithCollisions) {
+  ScopedObjectAccess soa(Thread::Current());
+  std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup"));
+  std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file));
+  ASSERT_NE(nullptr, table.get());
+  const char* descriptor = "LDA;";
+  size_t hash = ComputeModifiedUtf8Hash(descriptor);
+  uint32_t class_def_idx = table->Lookup(descriptor, hash);
+  ASSERT_EQ(kDexNoIndex, class_def_idx);
+}
+
+TEST_F(TypeLookupTableTest, FindClassNoCollisions) {
+  ScopedObjectAccess soa(Thread::Current());
+  std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup"));
+  std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file));
+  ASSERT_NE(nullptr, table.get());
+  const char* descriptor = "LC;";
+  size_t hash = ComputeModifiedUtf8Hash(descriptor);
+  uint32_t class_def_idx = table->Lookup(descriptor, hash);
+  ASSERT_EQ(2U, class_def_idx);
+}
+
+TEST_F(TypeLookupTableTest, FindClassWithCollisions) {
+  ScopedObjectAccess soa(Thread::Current());
+  std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup"));
+  std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file));
+  ASSERT_NE(nullptr, table.get());
+  const char* descriptor = "LAB;";
+  size_t hash = ComputeModifiedUtf8Hash(descriptor);
+  uint32_t class_def_idx = table->Lookup(descriptor, hash);
+  ASSERT_EQ(1U, class_def_idx);
+}
+
+}  // namespace art
diff --git a/test/Lookup/A.java b/test/Lookup/A.java
new file mode 100644
index 0000000..666ba18
--- /dev/null
+++ b/test/Lookup/A.java
@@ -0,0 +1,17 @@
+/*
+ * Copyright (C) 2011 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.
+ */
+
+class A {}
diff --git a/test/Lookup/AB.java b/test/Lookup/AB.java
new file mode 100644
index 0000000..b231708
--- /dev/null
+++ b/test/Lookup/AB.java
@@ -0,0 +1,17 @@
+/*
+ * Copyright (C) 2011 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.
+ */
+
+class AB {}
diff --git a/test/Lookup/C.java b/test/Lookup/C.java
new file mode 100644
index 0000000..5b90069
--- /dev/null
+++ b/test/Lookup/C.java
@@ -0,0 +1,17 @@
+/*
+ * Copyright (C) 2011 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.
+ */
+
+class C {}