diff --git a/src/class_linker.cc b/src/class_linker.cc
index 567415c..423bd72 100644
--- a/src/class_linker.cc
+++ b/src/class_linker.cc
@@ -2674,12 +2674,12 @@
 }
 
 void ClassLinker::ConstructFieldMap(const DexFile& dex_file, const DexFile::ClassDef& dex_class_def,
-                                    Class* c, std::map<uint32_t, Field*>& field_map) {
+                                    Class* c, SafeMap<uint32_t, Field*>& field_map) {
   const ClassLoader* cl = c->GetClassLoader();
   const byte* class_data = dex_file.GetClassData(dex_class_def);
   ClassDataItemIterator it(dex_file, class_data);
   for (size_t i = 0; it.HasNextStaticField(); i++, it.Next()) {
-    field_map[i] = ResolveField(dex_file, it.GetMemberIndex(), c->GetDexCache(), cl, true);
+    field_map.Put(i, ResolveField(dex_file, it.GetMemberIndex(), c->GetDexCache(), cl, true));
   }
 }
 
@@ -2701,10 +2701,10 @@
 
   if (it.HasNext()) {
     // We reordered the fields, so we need to be able to map the field indexes to the right fields.
-    std::map<uint32_t, Field*> field_map;
+    SafeMap<uint32_t, Field*> field_map;
     ConstructFieldMap(dex_file, *dex_class_def, klass, field_map);
     for (size_t i = 0; it.HasNext(); i++, it.Next()) {
-      it.ReadValueToField(field_map[i]);
+      it.ReadValueToField(field_map.Get(i));
     }
     return true;
   }
diff --git a/src/class_linker.h b/src/class_linker.h
index 86b02ad..a8fa01d 100644
--- a/src/class_linker.h
+++ b/src/class_linker.h
@@ -17,7 +17,6 @@
 #ifndef ART_SRC_CLASS_LINKER_H_
 #define ART_SRC_CLASS_LINKER_H_
 
-#include <map>
 #include <string>
 #include <utility>
 #include <vector>
@@ -30,6 +29,7 @@
 #include "mutex.h"
 #include "oat_file.h"
 #include "object.h"
+#include "safe_map.h"
 #include "stack_indirect_reference_table.h"
 
 namespace art {
@@ -342,7 +342,7 @@
   void AppendToBootClassPath(const DexFile& dex_file, SirtRef<DexCache>& dex_cache);
 
   void ConstructFieldMap(const DexFile& dex_file, const DexFile::ClassDef& dex_class_def,
-                         Class* c, std::map<uint32_t, Field*>& field_map);
+                         Class* c, SafeMap<uint32_t, Field*>& field_map);
 
   size_t SizeOfClass(const DexFile& dex_file,
                      const DexFile::ClassDef& dex_class_def);
diff --git a/src/compiler.cc b/src/compiler.cc
index 7369535..0a88cff 100644
--- a/src/compiler.cc
+++ b/src/compiler.cc
@@ -1215,7 +1215,7 @@
       CompiledClass* compiled_class = GetCompiledClass(ref);
       if (compiled_class == NULL) {
         compiled_class = new CompiledClass(status);
-        compiled_classes_[ref] = compiled_class;
+        compiled_classes_.Put(ref, compiled_class);
       } else {
         DCHECK_EQ(status, compiled_class->GetStatus());
       }
@@ -1301,6 +1301,14 @@
   ForAll(&context, 0, dex_file.NumClassDefs(), Compiler::CompileClass, thread_count_);
 }
 
+static std::string MakeInvokeStubKey(bool is_static, const char* shorty) {
+  std::string key(shorty);
+  if (is_static) {
+    key += "$";  // Must not be a shorty type character.
+  }
+  return key;
+}
+
 void Compiler::CompileMethod(const DexFile::CodeItem* code_item, uint32_t access_flags,
                              uint32_t method_idx, const ClassLoader* class_loader,
                              const DexFile& dex_file) {
@@ -1326,33 +1334,30 @@
     MethodReference ref(&dex_file, method_idx);
     CHECK(GetCompiledMethod(ref) == NULL) << PrettyMethod(method_idx, dex_file);
     MutexLock mu(compiled_methods_lock_);
-    compiled_methods_[ref] = compiled_method;
+    compiled_methods_.Put(ref, compiled_method);
     DCHECK(GetCompiledMethod(ref) != NULL) << PrettyMethod(method_idx, dex_file);
   }
 
   uint32_t shorty_len;
   const char* shorty = dex_file.GetMethodShorty(dex_file.GetMethodId(method_idx), &shorty_len);
   bool is_static = (access_flags & kAccStatic) != 0;
-  const CompiledInvokeStub* compiled_invoke_stub = FindInvokeStub(is_static, shorty);
+  std::string key(MakeInvokeStubKey(is_static, shorty));
+  const CompiledInvokeStub* compiled_invoke_stub = FindInvokeStub(key);
   if (compiled_invoke_stub == NULL) {
     compiled_invoke_stub = (*create_invoke_stub_)(*this, is_static, shorty, shorty_len);
     CHECK(compiled_invoke_stub != NULL);
-    InsertInvokeStub(is_static, shorty, compiled_invoke_stub);
+    InsertInvokeStub(key, compiled_invoke_stub);
   }
   CHECK(!Thread::Current()->IsExceptionPending()) << PrettyMethod(method_idx, dex_file);
 }
 
-static std::string MakeInvokeStubKey(bool is_static, const char* shorty) {
-  std::string key(shorty);
-  if (is_static) {
-    key += "$";  // Must not be a shorty type character.
-  }
-  return key;
+const CompiledInvokeStub* Compiler::FindInvokeStub(bool is_static, const char* shorty) const {
+  const std::string key(MakeInvokeStubKey(is_static, shorty));
+  return FindInvokeStub(key);
 }
 
-const CompiledInvokeStub* Compiler::FindInvokeStub(bool is_static, const char* shorty) const {
+const CompiledInvokeStub* Compiler::FindInvokeStub(const std::string& key) const {
   MutexLock mu(compiled_invoke_stubs_lock_);
-  const std::string key(MakeInvokeStubKey(is_static, shorty));
   InvokeStubTable::const_iterator it = compiled_invoke_stubs_.find(key);
   if (it == compiled_invoke_stubs_.end()) {
     return NULL;
@@ -1362,11 +1367,16 @@
   }
 }
 
-void Compiler::InsertInvokeStub(bool is_static, const char* shorty,
+void Compiler::InsertInvokeStub(const std::string& key,
                                 const CompiledInvokeStub* compiled_invoke_stub) {
   MutexLock mu(compiled_invoke_stubs_lock_);
-  std::string key(MakeInvokeStubKey(is_static, shorty));
-  compiled_invoke_stubs_[key] = compiled_invoke_stub;
+  InvokeStubTable::iterator it = compiled_invoke_stubs_.find(key);
+  if (it != compiled_invoke_stubs_.end()) {
+    // Someone else won the race.
+    delete compiled_invoke_stub;
+  } else {
+    compiled_invoke_stubs_.Put(key, compiled_invoke_stub);
+  }
 }
 
 CompiledClass* Compiler::GetCompiledClass(ClassReference ref) const {
diff --git a/src/compiler.h b/src/compiler.h
index cb6023b..9b8a3ab 100644
--- a/src/compiler.h
+++ b/src/compiler.h
@@ -17,7 +17,6 @@
 #ifndef ART_SRC_COMPILER_H_
 #define ART_SRC_COMPILER_H_
 
-#include <map>
 #include <set>
 #include <string>
 #include <vector>
@@ -32,6 +31,7 @@
 #include "oat_file.h"
 #include "object.h"
 #include "runtime.h"
+#include "safe_map.h"
 
 namespace art {
 
@@ -92,6 +92,7 @@
   CompiledMethod* GetCompiledMethod(MethodReference ref) const;
 
   const CompiledInvokeStub* FindInvokeStub(bool is_static, const char* shorty) const;
+  const CompiledInvokeStub* FindInvokeStub(const std::string& key) const;
 
   // Callbacks from OAT/ART compiler to see what runtime checks must be generated
 
@@ -274,25 +275,24 @@
   void SetGcMapsDexFile(const ClassLoader* class_loader, const DexFile& dex_file);
   void SetGcMapsMethod(const DexFile& dex_file, Method* method);
 
-  void InsertInvokeStub(bool is_static, const char* shorty,
-                        const CompiledInvokeStub* compiled_invoke_stub);
+  void InsertInvokeStub(const std::string& key, const CompiledInvokeStub* compiled_invoke_stub);
 
   std::vector<const PatchInformation*> code_to_patch_;
   std::vector<const PatchInformation*> methods_to_patch_;
 
   InstructionSet instruction_set_;
 
-  typedef std::map<const ClassReference, CompiledClass*> ClassTable;
+  typedef SafeMap<const ClassReference, CompiledClass*> ClassTable;
   // All class references that this compiler has compiled
   mutable Mutex compiled_classes_lock_;
   ClassTable compiled_classes_;
 
-  typedef std::map<const MethodReference, CompiledMethod*> MethodTable;
+  typedef SafeMap<const MethodReference, CompiledMethod*> MethodTable;
   // All method references that this compiler has compiled
   mutable Mutex compiled_methods_lock_;
   MethodTable compiled_methods_;
 
-  typedef std::map<std::string, const CompiledInvokeStub*> InvokeStubTable;
+  typedef SafeMap<std::string, const CompiledInvokeStub*> InvokeStubTable;
   // Invocation stubs created to allow invocation of the compiled methods
   mutable Mutex compiled_invoke_stubs_lock_;
   InvokeStubTable compiled_invoke_stubs_;
diff --git a/src/compiler/CompilerIR.h b/src/compiler/CompilerIR.h
index 0fc26de..88593bd 100644
--- a/src/compiler/CompilerIR.h
+++ b/src/compiler/CompilerIR.h
@@ -17,10 +17,12 @@
 #ifndef ART_SRC_COMPILER_COMPILER_IR_H_
 #define ART_SRC_COMPILER_COMPILER_IR_H_
 
+#include <vector>
+
 #include "codegen/Optimizer.h"
 #include "CompilerUtility.h"
-#include <vector>
 #include "oat_compilation_unit.h"
+#include "safe_map.h"
 
 namespace art {
 
@@ -519,8 +521,8 @@
     const u2* insns;
     u4 insnsSize;
     bool disableDataflow; // Skip dataflow analysis if possible
-    std::map<unsigned int, BasicBlock*> blockMap; // findBlock lookup cache
-    std::map<unsigned int, LIR*> boundaryMap; // boundary lookup cache
+    SafeMap<unsigned int, BasicBlock*> blockMap; // findBlock lookup cache
+    SafeMap<unsigned int, LIR*> boundaryMap; // boundary lookup cache
     int defCount;         // Used to estimate number of SSA names
 
     // If non-empty, apply optimizer/debug flags only to matching methods.
diff --git a/src/compiler/Frontend.cc b/src/compiler/Frontend.cc
index 309bcf8..dbaf323 100644
--- a/src/compiler/Frontend.cc
+++ b/src/compiler/Frontend.cc
@@ -136,8 +136,7 @@
     bottomBlock->lastMIRInsn = origBlock->lastMIRInsn;
 
     /* Add it to the quick lookup cache */
-    cUnit->blockMap.insert(std::make_pair(bottomBlock->startOffset,
-                                          bottomBlock));
+    cUnit->blockMap.Put(bottomBlock->startOffset, bottomBlock);
 
     /* Handle the taken path */
     bottomBlock->taken = origBlock->taken;
@@ -211,7 +210,7 @@
     GrowableList* blockList = &cUnit->blockList;
     BasicBlock* bb;
     unsigned int i;
-    std::map<unsigned int, BasicBlock*>::iterator it;
+    SafeMap<unsigned int, BasicBlock*>::iterator it;
 
     it = cUnit->blockMap.find(codeOffset);
     if (it != cUnit->blockMap.end()) {
@@ -239,7 +238,7 @@
     bb = oatNewBB(cUnit, kDalvikByteCode, cUnit->numBlocks++);
     oatInsertGrowableList(cUnit, &cUnit->blockList, (intptr_t) bb);
     bb->startOffset = codeOffset;
-    cUnit->blockMap.insert(std::make_pair(bb->startOffset, bb));
+    cUnit->blockMap.Put(bb->startOffset, bb);
     return bb;
 }
 
@@ -853,7 +852,7 @@
     curBlock->startOffset = 0;
     oatInsertGrowableList(cUnit.get(), &cUnit->blockList, (intptr_t) curBlock);
     /* Add first block to the fast lookup cache */
-    cUnit->blockMap.insert(std::make_pair(curBlock->startOffset, curBlock));
+    cUnit->blockMap.Put(curBlock->startOffset, curBlock);
     entryBlock->fallThrough = curBlock;
     oatInsertGrowableList(cUnit.get(), curBlock->predecessors,
                           (intptr_t)entryBlock);
diff --git a/src/compiler/codegen/CodegenUtil.cc b/src/compiler/codegen/CodegenUtil.cc
index 00e78ec..777cf57 100644
--- a/src/compiler/codegen/CodegenUtil.cc
+++ b/src/compiler/codegen/CodegenUtil.cc
@@ -857,7 +857,7 @@
  */
 LIR* insertCaseLabel(CompilationUnit* cUnit, int vaddr, int keyVal)
 {
-    std::map<unsigned int, LIR*>::iterator it;
+    SafeMap<unsigned int, LIR*>::iterator it;
     it = cUnit->boundaryMap.find(vaddr);
     if (it == cUnit->boundaryMap.end()) {
         LOG(FATAL) << "Error: didn't find vaddr 0x" << std::hex << vaddr;
diff --git a/src/compiler/codegen/MethodCodegenDriver.cc b/src/compiler/codegen/MethodCodegenDriver.cc
index 0b8a19d..dd47359 100644
--- a/src/compiler/codegen/MethodCodegenDriver.cc
+++ b/src/compiler/codegen/MethodCodegenDriver.cc
@@ -883,8 +883,7 @@
            oatGetDalvikDisassembly(cUnit, mir->dalvikInsn, "") : NULL;
         boundaryLIR = newLIR1(cUnit, kPseudoDalvikByteCodeBoundary,
                               (intptr_t) instStr);
-        cUnit->boundaryMap.insert(std::make_pair(mir->offset,
-                                 (LIR*)boundaryLIR));
+        cUnit->boundaryMap.Overwrite(mir->offset, boundaryLIR);
         /* Remember the first LIR for this block */
         if (headLIR == NULL) {
             headLIR = boundaryLIR;
diff --git a/src/compiler/codegen/arm/Thumb2/Gen.cc b/src/compiler/codegen/arm/Thumb2/Gen.cc
index fa51266..5451d57 100644
--- a/src/compiler/codegen/arm/Thumb2/Gen.cc
+++ b/src/compiler/codegen/arm/Thumb2/Gen.cc
@@ -133,8 +133,7 @@
        oatGetDalvikDisassembly(cUnit, mir->dalvikInsn, "") : NULL;
     boundaryLIR = newLIR1(cUnit, kPseudoDalvikByteCodeBoundary,
                           (intptr_t) instStr);
-    cUnit->boundaryMap.insert(std::make_pair(mir->offset,
-                             (LIR*)boundaryLIR));
+    cUnit->boundaryMap.Put(mir->offset, boundaryLIR);
     /* Don't generate the SSA annotation unless verbose mode is on */
     if (cUnit->printMe && mir->ssaRep) {
         char* ssaString = oatGetSSAString(cUnit, mir->ssaRep);
diff --git a/src/compiler_llvm/inferred_reg_category_map.h b/src/compiler_llvm/inferred_reg_category_map.h
index f056274..14bc052 100644
--- a/src/compiler_llvm/inferred_reg_category_map.h
+++ b/src/compiler_llvm/inferred_reg_category_map.h
@@ -21,7 +21,8 @@
 
 #include <stdint.h>
 #include <vector>
-#include <map>
+
+#include "safe_map.h"
 
 namespace art {
 namespace compiler_llvm {
@@ -31,8 +32,7 @@
  private:
   class RegCategoryLine {
    private:
-    // TODO: Use hashmap (unordered_map).
-    typedef std::map<uint16_t, uint8_t> Table;
+    typedef SafeMap<uint16_t, uint8_t> Table;
     Table reg_category_line_;
 
    public:
diff --git a/src/debugger.cc b/src/debugger.cc
index 553bfc7..fe9bc49 100644
--- a/src/debugger.cc
+++ b/src/debugger.cc
@@ -25,9 +25,10 @@
 #include "dex_verifier.h" // For Instruction.
 #include "oat/runtime/context.h"
 #include "object_utils.h"
+#include "safe_map.h"
+#include "scoped_thread_list_lock.h"
 #include "ScopedLocalRef.h"
 #include "ScopedPrimitiveArray.h"
-#include "scoped_thread_list_lock.h"
 #include "space.h"
 #include "stack_indirect_reference_table.h"
 #include "thread_list.h"
@@ -58,7 +59,7 @@
     }
     JDWP::ObjectId id = static_cast<JDWP::ObjectId>(reinterpret_cast<uintptr_t>(o));
     MutexLock mu(lock_);
-    map_[id] = o;
+    map_.Overwrite(id, o);
     return id;
   }
 
@@ -79,14 +80,14 @@
     }
 
     MutexLock mu(lock_);
-    typedef std::map<JDWP::ObjectId, Object*>::iterator It; // C++0x auto
+    typedef SafeMap<JDWP::ObjectId, Object*>::iterator It; // C++0x auto
     It it = map_.find(id);
     return (it != map_.end()) ? reinterpret_cast<T>(it->second) : reinterpret_cast<T>(kInvalidId);
   }
 
   void VisitRoots(Heap::RootVisitor* visitor, void* arg) {
     MutexLock mu(lock_);
-    typedef std::map<JDWP::ObjectId, Object*>::iterator It; // C++0x auto
+    typedef SafeMap<JDWP::ObjectId, Object*>::iterator It; // C++0x auto
     for (It it = map_.begin(); it != map_.end(); ++it) {
       visitor(it->second, arg);
     }
@@ -94,7 +95,7 @@
 
  private:
   Mutex lock_;
-  std::map<JDWP::ObjectId, Object*> map_;
+  SafeMap<JDWP::ObjectId, Object*> map_;
 };
 
 struct AllocRecordStackTraceElement {
diff --git a/src/dex_file.cc b/src/dex_file.cc
index 6168f9e..a054849 100644
--- a/src/dex_file.cc
+++ b/src/dex_file.cc
@@ -25,9 +25,6 @@
 #include <sys/mman.h>
 #include <sys/stat.h>
 
-#include <map>
-
-#include "UniquePtr.h"
 #include "class_linker.h"
 #include "dex_file_verifier.h"
 #include "globals.h"
@@ -35,8 +32,10 @@
 #include "logging.h"
 #include "object.h"
 #include "os.h"
+#include "safe_map.h"
 #include "stringprintf.h"
 #include "thread.h"
+#include "UniquePtr.h"
 #include "utf.h"
 #include "utils.h"
 #include "zip_archive.h"
@@ -331,7 +330,7 @@
   for (size_t i = 0; i < NumClassDefs(); ++i) {
     const ClassDef& class_def = GetClassDef(i);
     const char* descriptor = GetClassDescriptor(class_def);
-    index_[descriptor] = i;
+    index_.Put(descriptor, i);
   }
 }
 
diff --git a/src/dex_file.h b/src/dex_file.h
index 02d0b27..2f315a9 100644
--- a/src/dex_file.h
+++ b/src/dex_file.h
@@ -17,17 +17,17 @@
 #ifndef ART_SRC_DEX_FILE_H_
 #define ART_SRC_DEX_FILE_H_
 
-#include <map>
 #include <string>
 #include <vector>
 
-#include "UniquePtr.h"
 #include "globals.h"
 #include "jni.h"
 #include "logging.h"
 #include "mem_map.h"
 #include "mutex.h"
+#include "safe_map.h"
 #include "stringpiece.h"
+#include "UniquePtr.h"
 #include "utils.h"
 
 namespace art {
@@ -847,7 +847,7 @@
       void* context, const byte* stream, LocalInfo* local_in_reg) const;
 
   // The index of descriptors to class definition indexes (as opposed to type id indexes)
-  typedef std::map<const StringPiece, uint32_t> Index;
+  typedef SafeMap<const StringPiece, uint32_t> Index;
   Index index_;
 
   // The base address of the memory mapping.
diff --git a/src/dex_file_verifier.cc b/src/dex_file_verifier.cc
index af9d4bb..b8df696 100644
--- a/src/dex_file_verifier.cc
+++ b/src/dex_file_verifier.cc
@@ -16,12 +16,11 @@
 
 #include "dex_file_verifier.h"
 
-#include <map>
-
-#include "UniquePtr.h"
 #include "leb128.h"
 #include "object.h"
+#include "safe_map.h"
 #include "stringprintf.h"
+#include "UniquePtr.h"
 #include "zip_archive.h"
 
 namespace art {
@@ -1117,7 +1116,7 @@
     }
 
     if (IsDataSectionType(type)) {
-      offset_to_type_map_.insert(std::make_pair(aligned_offset, type));
+      offset_to_type_map_.Put(aligned_offset, type);
     }
 
     aligned_offset = reinterpret_cast<uint32_t>(ptr_) - reinterpret_cast<uint32_t>(begin_);
@@ -1289,7 +1288,7 @@
 }
 
 bool DexFileVerifier::CheckOffsetToTypeMap(uint32_t offset, uint16_t type) {
-  typedef std::map<uint32_t, uint16_t>::iterator It; // TODO: C++0x auto
+  typedef SafeMap<uint32_t, uint16_t>::iterator It; // TODO: C++0x auto
   It it = offset_to_type_map_.find(offset);
   if (it == offset_to_type_map_.end()) {
     LOG(ERROR) << StringPrintf("No data map entry found @ %x; expected %x", offset, type);
diff --git a/src/dex_file_verifier.h b/src/dex_file_verifier.h
index 58b5984..5538d4a 100644
--- a/src/dex_file_verifier.h
+++ b/src/dex_file_verifier.h
@@ -17,9 +17,8 @@
 #ifndef ART_SRC_DEX_FILE_VERIFIER_H_
 #define ART_SRC_DEX_FILE_VERIFIER_H_
 
-#include <map>
-
 #include "dex_file.h"
+#include "safe_map.h"
 
 namespace art {
 
@@ -88,7 +87,7 @@
   size_t size_;
   const DexFile::Header* header_;
 
-  std::map<uint32_t, uint16_t> offset_to_type_map_;
+  SafeMap<uint32_t, uint16_t> offset_to_type_map_;
   const byte* ptr_;
   const void* previous_item_;
 };
diff --git a/src/dex_verifier.cc b/src/dex_verifier.cc
index 91d6ccd..4f523fa 100644
--- a/src/dex_verifier.cc
+++ b/src/dex_verifier.cc
@@ -901,7 +901,7 @@
         break;
     }
     if (interesting) {
-      pc_to_register_line_[i] = new RegisterLine(registers_size, verifier);
+      pc_to_register_line_.Put(i, new RegisterLine(registers_size, verifier));
     }
   }
 }
@@ -4035,12 +4035,12 @@
 
 void DexVerifier::SetGcMap(Compiler::MethodReference ref, const std::vector<uint8_t>& gc_map) {
   MutexLock mu(*gc_maps_lock_);
-  const std::vector<uint8_t>* existing_gc_map = GetGcMap(ref);
-  if (existing_gc_map != NULL) {
-    CHECK(*existing_gc_map == gc_map);
-    delete existing_gc_map;
+  GcMapTable::iterator it = gc_maps_->find(ref);
+  if (it != gc_maps_->end()) {
+    delete it->second;
+    gc_maps_->erase(it);
   }
-  (*gc_maps_)[ref] = &gc_map;
+  gc_maps_->Put(ref, &gc_map);
   CHECK(GetGcMap(ref) != NULL);
 }
 
diff --git a/src/dex_verifier.h b/src/dex_verifier.h
index 043e4f9..75de207 100644
--- a/src/dex_verifier.h
+++ b/src/dex_verifier.h
@@ -19,7 +19,6 @@
 
 #include <deque>
 #include <limits>
-#include <map>
 #include <set>
 #include <vector>
 
@@ -29,6 +28,7 @@
 #include "dex_instruction.h"
 #include "macros.h"
 #include "object.h"
+#include "safe_map.h"
 #include "stl_util.h"
 #include "UniquePtr.h"
 
@@ -774,16 +774,16 @@
  private:
 
   void CopyRegToLockDepth(size_t dst, size_t src) {
-    if (reg_to_lock_depths_.count(src) > 0) {
-      uint32_t depths = reg_to_lock_depths_[src];
-      reg_to_lock_depths_[dst] = depths;
+    SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(src);
+    if (it != reg_to_lock_depths_.end()) {
+      reg_to_lock_depths_.Put(dst, it->second);
     }
   }
 
   bool IsSetLockDepth(size_t reg, size_t depth) {
-    if (reg_to_lock_depths_.count(reg) > 0) {
-      uint32_t depths = reg_to_lock_depths_[reg];
-      return (depths & (1 << depth)) != 0;
+    SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(reg);
+    if (it != reg_to_lock_depths_.end()) {
+      return (it->second & (1 << depth)) != 0;
     } else {
       return false;
     }
@@ -792,25 +792,24 @@
   void SetRegToLockDepth(size_t reg, size_t depth) {
     CHECK_LT(depth, 32u);
     DCHECK(!IsSetLockDepth(reg, depth));
-    uint32_t depths;
-    if (reg_to_lock_depths_.count(reg) > 0) {
-      depths = reg_to_lock_depths_[reg];
-      depths = depths | (1 << depth);
+    SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(reg);
+    if (it == reg_to_lock_depths_.end()) {
+      reg_to_lock_depths_.Put(reg, 1 << depth);
     } else {
-      depths = 1 << depth;
+      it->second |= (1 << depth);
     }
-    reg_to_lock_depths_[reg] = depths;
   }
 
   void ClearRegToLockDepth(size_t reg, size_t depth) {
     CHECK_LT(depth, 32u);
     DCHECK(IsSetLockDepth(reg, depth));
-    uint32_t depths = reg_to_lock_depths_[reg];
-    depths = depths ^ (1 << depth);
+    SafeMap<uint32_t, uint32_t>::iterator it = reg_to_lock_depths_.find(reg);
+    DCHECK(it != reg_to_lock_depths_.end());
+    uint32_t depths = it->second ^ (1 << depth);
     if (depths != 0) {
-      reg_to_lock_depths_[reg] = depths;
+      it->second = depths;
     } else {
-      reg_to_lock_depths_.erase(reg);
+      reg_to_lock_depths_.erase(it);
     }
   }
 
@@ -834,7 +833,7 @@
   // A map from register to a bit vector of indices into the monitors_ stack. As we pop the monitor
   // stack we verify that monitor-enter/exit are correctly nested. That is, if there was a
   // monitor-enter on v5 and then on v6, we expect the monitor-exit to be on v6 then on v5
-  std::map<uint32_t, uint32_t> reg_to_lock_depths_;
+  SafeMap<uint32_t, uint32_t> reg_to_lock_depths_;
 };
 std::ostream& operator<<(std::ostream& os, const RegisterLine& rhs);
 
@@ -870,9 +869,8 @@
   }
 
  private:
-  // TODO: Use hashmap (unordered_map).
-  typedef std::map<int32_t, RegisterLine*> Table;
   // Map from a dex pc to the register status associated with it
+  typedef SafeMap<int32_t, RegisterLine*> Table;
   Table pc_to_register_line_;
 
   // Number of registers we track for each instruction. This is equal to the method's declared
@@ -1306,15 +1304,15 @@
   }
 
   // All the GC maps that the verifier has created
-  typedef std::map<const Compiler::MethodReference, const std::vector<uint8_t>*> GcMapTable;
+  typedef SafeMap<const Compiler::MethodReference, const std::vector<uint8_t>*> GcMapTable;
   static Mutex* gc_maps_lock_;
   static GcMapTable* gc_maps_;
   static void SetGcMap(Compiler::MethodReference ref, const std::vector<uint8_t>& gc_map);
 
 #if defined(ART_USE_LLVM_COMPILER)
   // All the inferred register category maps that the verifier has created
-  typedef std::map<const Compiler::MethodReference,
-                   const compiler_llvm::InferredRegCategoryMap*> InferredRegCategoryMapTable;
+  typedef SafeMap<const Compiler::MethodReference,
+                  const compiler_llvm::InferredRegCategoryMap*> InferredRegCategoryMapTable;
   static Mutex* inferred_reg_category_maps_lock_;
   static InferredRegCategoryMapTable* inferred_reg_category_maps_;
   static void SetInferredRegCategoryMap(Compiler::MethodReference ref,
diff --git a/src/hprof/hprof.cc b/src/hprof/hprof.cc
index b118b5c..d6771d0 100644
--- a/src/hprof/hprof.cc
+++ b/src/hprof/hprof.cc
@@ -649,10 +649,13 @@
 }
 
 HprofStringId Hprof::LookupStringId(std::string string) {
-  if (strings_.find(string) == strings_.end()) {
-    strings_[string] = next_string_id_++;
+  StringMapIterator it = strings_.find(string);
+  if (it != strings_.end()) {
+    return it->second;
   }
-  return strings_[string];
+  HprofStringId id = next_string_id_++;
+  strings_.Put(string, id);
+  return id;
 }
 
 int Hprof::DumpStrings() {
diff --git a/src/hprof/hprof.h b/src/hprof/hprof.h
index c4a0dd3..bcdbef8 100644
--- a/src/hprof/hprof.h
+++ b/src/hprof/hprof.h
@@ -18,12 +18,12 @@
 
 #include <stdio.h>
 
-#include <map>
 #include <set>
 
 #include "file.h"
 #include "globals.h"
 #include "object.h"
+#include "safe_map.h"
 #include "thread_list.h"
 
 namespace art {
@@ -80,8 +80,8 @@
 typedef HprofId HprofClassObjectId;
 typedef std::set<Class*> ClassSet;
 typedef std::set<Class*>::iterator ClassSetIterator;
-typedef std::map<std::string, size_t> StringMap;
-typedef std::map<std::string, size_t>::iterator StringMapIterator;
+typedef SafeMap<std::string, size_t> StringMap;
+typedef SafeMap<std::string, size_t>::iterator StringMapIterator;
 
 enum HprofBasicType {
   hprof_basic_object = 2,
diff --git a/src/image_writer.h b/src/image_writer.h
index f62bea1..5f78863 100644
--- a/src/image_writer.h
+++ b/src/image_writer.h
@@ -20,7 +20,6 @@
 #include <stdint.h>
 
 #include <cstddef>
-#include <map>
 #include <set>
 #include <string>
 
@@ -30,6 +29,7 @@
 #include "oat_file.h"
 #include "object.h"
 #include "os.h"
+#include "safe_map.h"
 #include "space.h"
 #include "UniquePtr.h"
 
@@ -65,7 +65,7 @@
     DCHECK(object != NULL);
     DCHECK_NE(offset, 0U);
     DCHECK(!IsImageOffsetAssigned(object));
-    offsets_[object] = offset;
+    offsets_.Put(object, offset);
   }
 
   size_t IsImageOffsetAssigned(const Object* object) const {
@@ -142,7 +142,7 @@
   void PatchOatCodeAndMethods(const Compiler& compiler);
   void SetPatchLocation(const Compiler::PatchInformation* patch, uint32_t value);
 
-  std::map<const Object*, size_t> offsets_;
+  SafeMap<const Object*, size_t> offsets_;
 
   // oat file with code for this image
   OatFile* oat_file_;
diff --git a/src/intern_table.h b/src/intern_table.h
index bb8e031..58d87d0 100644
--- a/src/intern_table.h
+++ b/src/intern_table.h
@@ -18,11 +18,11 @@
 #define ART_SRC_INTERN_TABLE_H_
 
 #include <iosfwd>
-#include <map>
 
 #include "heap.h"
 #include "mutex.h"
 #include "object.h"
+#include "safe_map.h"
 
 namespace art {
 
diff --git a/src/jni_internal.cc b/src/jni_internal.cc
index e192ce8..1e27604 100644
--- a/src/jni_internal.cc
+++ b/src/jni_internal.cc
@@ -20,12 +20,9 @@
 #include <sys/mman.h>
 
 #include <cstdarg>
-#include <map>
 #include <utility>
 #include <vector>
 
-#include "ScopedLocalRef.h"
-#include "UniquePtr.h"
 #include "class_linker.h"
 #include "class_loader.h"
 #include "jni.h"
@@ -33,10 +30,13 @@
 #include "object.h"
 #include "object_utils.h"
 #include "runtime.h"
+#include "safe_map.h"
 #include "scoped_jni_thread_state.h"
+#include "ScopedLocalRef.h"
 #include "stl_util.h"
 #include "stringpiece.h"
 #include "thread.h"
+#include "UniquePtr.h"
 
 namespace art {
 
@@ -665,7 +665,7 @@
   }
 
   void Put(const std::string& path, SharedLibrary* library) {
-    libraries_[path] = library;
+    libraries_.Put(path, library);
   }
 
   // See section 11.3 "Linking Native Methods" of the JNI spec.
@@ -698,9 +698,9 @@
   }
 
  private:
-  typedef std::map<std::string, SharedLibrary*>::iterator It; // TODO: C++0x auto
+  typedef SafeMap<std::string, SharedLibrary*>::iterator It; // TODO: C++0x auto
 
-  std::map<std::string, SharedLibrary*> libraries_;
+  SafeMap<std::string, SharedLibrary*> libraries_;
 };
 
 JValue InvokeWithJValues(JNIEnv* public_env, jobject obj, jmethodID mid, jvalue* args) {
diff --git a/src/oat_file.cc b/src/oat_file.cc
index 261fd60..7196222 100644
--- a/src/oat_file.cc
+++ b/src/oat_file.cc
@@ -177,11 +177,11 @@
     oat += (sizeof(*methods_offsets_pointer) * header->class_defs_size_);
     CHECK_LE(oat, map->End()) << GetLocation();
 
-    oat_dex_files_[dex_file_location] = new OatDexFile(this,
-                                                       dex_file_location,
-                                                       dex_file_checksum,
-                                                       dex_file_pointer,
-                                                       methods_offsets_pointer);
+    oat_dex_files_.Put(dex_file_location, new OatDexFile(this,
+                                                         dex_file_location,
+                                                         dex_file_checksum,
+                                                         dex_file_pointer,
+                                                         methods_offsets_pointer));
   }
 
 #if !defined(ART_USE_LLVM_COMPILER)
diff --git a/src/oat_file.h b/src/oat_file.h
index 0bd9d33..0b1ebac 100644
--- a/src/oat_file.h
+++ b/src/oat_file.h
@@ -315,7 +315,7 @@
   // backing memory map for oat file
   UniquePtr<MemMap> mem_map_;
 
-  typedef std::map<std::string, const OatDexFile*> Table;
+  typedef SafeMap<std::string, const OatDexFile*> Table;
   Table oat_dex_files_;
 
 #if defined(ART_USE_LLVM_COMPILER)
diff --git a/src/oat_writer.cc b/src/oat_writer.cc
index f08aa8d..2ccf207 100644
--- a/src/oat_writer.cc
+++ b/src/oat_writer.cc
@@ -16,16 +16,17 @@
 
 #include "oat_writer.h"
 
+#include <zlib.h>
+
 #include "class_linker.h"
 #include "class_loader.h"
 #include "elf_image.h"
 #include "file.h"
 #include "os.h"
+#include "safe_map.h"
 #include "space.h"
 #include "stl_util.h"
 
-#include <zlib.h>
-
 namespace art {
 
 bool OatWriter::Create(File* file,
@@ -286,11 +287,11 @@
       code_offset = offset + sizeof(code_size) + thumb_offset;
 
       // Deduplicate code arrays
-      std::map<const std::vector<uint8_t>*, uint32_t>::iterator code_iter = code_offsets_.find(&code);
+      SafeMap<const std::vector<uint8_t>*, uint32_t>::iterator code_iter = code_offsets_.find(&code);
       if (code_iter != code_offsets_.end()) {
         code_offset = code_iter->second;
       } else {
-        code_offsets_.insert(std::pair<const std::vector<uint8_t>*, uint32_t>(&code, code_offset));
+        code_offsets_.Put(&code, code_offset);
         offset += sizeof(code_size);  // code size is prepended before code
         offset += code_size;
         oat_header_->UpdateChecksum(&code[0], code_size);
@@ -304,11 +305,11 @@
       mapping_table_offset = (mapping_table_size == 0) ? 0 : offset;
 
       // Deduplicate mapping tables
-      std::map<const std::vector<uint32_t>*, uint32_t>::iterator mapping_iter = mapping_table_offsets_.find(&mapping_table);
+      SafeMap<const std::vector<uint32_t>*, uint32_t>::iterator mapping_iter = mapping_table_offsets_.find(&mapping_table);
       if (mapping_iter != mapping_table_offsets_.end()) {
         mapping_table_offset = mapping_iter->second;
       } else {
-        mapping_table_offsets_.insert(std::pair<const std::vector<uint32_t>*, uint32_t>(&mapping_table, mapping_table_offset));
+        mapping_table_offsets_.Put(&mapping_table, mapping_table_offset);
         offset += mapping_table_size;
         oat_header_->UpdateChecksum(&mapping_table[0], mapping_table_size);
       }
@@ -318,11 +319,11 @@
       vmap_table_offset = (vmap_table_size == 0) ? 0 : offset;
 
       // Deduplicate vmap tables
-      std::map<const std::vector<uint16_t>*, uint32_t>::iterator vmap_iter = vmap_table_offsets_.find(&vmap_table);
+      SafeMap<const std::vector<uint16_t>*, uint32_t>::iterator vmap_iter = vmap_table_offsets_.find(&vmap_table);
       if (vmap_iter != vmap_table_offsets_.end()) {
         vmap_table_offset = vmap_iter->second;
       } else {
-        vmap_table_offsets_.insert(std::pair<const std::vector<uint16_t>*, uint32_t>(&vmap_table, vmap_table_offset));
+        vmap_table_offsets_.Put(&vmap_table, vmap_table_offset);
         offset += vmap_table_size;
         oat_header_->UpdateChecksum(&vmap_table[0], vmap_table_size);
       }
@@ -342,11 +343,11 @@
 #endif
 
       // Deduplicate GC maps
-      std::map<const std::vector<uint8_t>*, uint32_t>::iterator gc_map_iter = gc_map_offsets_.find(&gc_map);
+      SafeMap<const std::vector<uint8_t>*, uint32_t>::iterator gc_map_iter = gc_map_offsets_.find(&gc_map);
       if (gc_map_iter != gc_map_offsets_.end()) {
         gc_map_offset = gc_map_iter->second;
       } else {
-        gc_map_offsets_.insert(std::pair<const std::vector<uint8_t>*, uint32_t>(&gc_map, gc_map_offset));
+        gc_map_offsets_.Put(&gc_map, gc_map_offset);
         offset += gc_map_size;
         oat_header_->UpdateChecksum(&gc_map[0], gc_map_size);
       }
@@ -368,11 +369,11 @@
       invoke_stub_offset = offset + sizeof(invoke_stub_size);
 
       // Deduplicate invoke stubs
-      std::map<const std::vector<uint8_t>*, uint32_t>::iterator stub_iter = code_offsets_.find(&invoke_stub);
+      SafeMap<const std::vector<uint8_t>*, uint32_t>::iterator stub_iter = code_offsets_.find(&invoke_stub);
       if (stub_iter != code_offsets_.end()) {
         invoke_stub_offset = stub_iter->second;
       } else {
-        code_offsets_.insert(std::pair<const std::vector<uint8_t>*, uint32_t>(&invoke_stub, invoke_stub_offset));
+        code_offsets_.Put(&invoke_stub, invoke_stub_offset);
         offset += sizeof(invoke_stub_size);  // invoke stub size is prepended before code
         offset += invoke_stub_size;
         oat_header_->UpdateChecksum(&invoke_stub[0], invoke_stub_size);
@@ -627,7 +628,7 @@
 
       // Deduplicate code arrays
       size_t offset = code_offset + sizeof(code_size) + compiled_method->CodeDelta();
-      std::map<const std::vector<uint8_t>*, uint32_t>::iterator code_iter = code_offsets_.find(&code);
+      SafeMap<const std::vector<uint8_t>*, uint32_t>::iterator code_iter = code_offsets_.find(&code);
       if (code_iter != code_offsets_.end() && offset != method_offsets.code_offset_) {
         DCHECK(code_iter->second == method_offsets.code_offset_) << PrettyMethod(method_idx, dex_file);
       } else {
@@ -653,7 +654,7 @@
       size_t mapping_table_size = mapping_table.size() * sizeof(mapping_table[0]);
 
       // Deduplicate mapping tables
-      std::map<const std::vector<uint32_t>*, uint32_t>::iterator mapping_iter =
+      SafeMap<const std::vector<uint32_t>*, uint32_t>::iterator mapping_iter =
           mapping_table_offsets_.find(&mapping_table);
       if (mapping_iter != mapping_table_offsets_.end() &&
           code_offset != method_offsets.mapping_table_offset_) {
@@ -676,7 +677,7 @@
       size_t vmap_table_size = vmap_table.size() * sizeof(vmap_table[0]);
 
       // Deduplicate vmap tables
-      std::map<const std::vector<uint16_t>*, uint32_t>::iterator vmap_iter =
+      SafeMap<const std::vector<uint16_t>*, uint32_t>::iterator vmap_iter =
           vmap_table_offsets_.find(&vmap_table);
       if (vmap_iter != vmap_table_offsets_.end() &&
           code_offset != method_offsets.vmap_table_offset_) {
@@ -699,7 +700,7 @@
       size_t gc_map_size = gc_map.size() * sizeof(gc_map[0]);
 
       // Deduplicate GC maps
-      std::map<const std::vector<uint8_t>*, uint32_t>::iterator gc_map_iter =
+      SafeMap<const std::vector<uint8_t>*, uint32_t>::iterator gc_map_iter =
           gc_map_offsets_.find(&gc_map);
       if (gc_map_iter != gc_map_offsets_.end() &&
           code_offset != method_offsets.gc_map_offset_) {
@@ -743,7 +744,7 @@
 
       // Deduplicate invoke stubs
       size_t offset = code_offset + sizeof(invoke_stub_size);
-      std::map<const std::vector<uint8_t>*, uint32_t>::iterator stub_iter =
+      SafeMap<const std::vector<uint8_t>*, uint32_t>::iterator stub_iter =
           code_offsets_.find(&invoke_stub);
       if (stub_iter != code_offsets_.end() && offset != method_offsets.invoke_stub_offset_) {
         DCHECK(stub_iter->second == method_offsets.invoke_stub_offset_) << PrettyMethod(method_idx, dex_file);
diff --git a/src/oat_writer.h b/src/oat_writer.h
index e0d257f..956475c 100644
--- a/src/oat_writer.h
+++ b/src/oat_writer.h
@@ -21,13 +21,14 @@
 
 #include <cstddef>
 
-#include "UniquePtr.h"
 #include "compiler.h"
 #include "dex_cache.h"
 #include "mem_map.h"
 #include "oat.h"
 #include "object.h"
 #include "os.h"
+#include "safe_map.h"
+#include "UniquePtr.h"
 
 namespace art {
 
@@ -203,10 +204,10 @@
   };
 
   // code mappings for deduplication
-  std::map<const std::vector<uint8_t>*, uint32_t, MapCompare<std::vector<uint8_t> > > code_offsets_;
-  std::map<const std::vector<uint16_t>*, uint32_t, MapCompare<std::vector<uint16_t> > > vmap_table_offsets_;
-  std::map<const std::vector<uint32_t>*, uint32_t, MapCompare<std::vector<uint32_t> > > mapping_table_offsets_;
-  std::map<const std::vector<uint8_t>*, uint32_t, MapCompare<std::vector<uint8_t> > > gc_map_offsets_;
+  SafeMap<const std::vector<uint8_t>*, uint32_t, MapCompare<std::vector<uint8_t> > > code_offsets_;
+  SafeMap<const std::vector<uint16_t>*, uint32_t, MapCompare<std::vector<uint16_t> > > vmap_table_offsets_;
+  SafeMap<const std::vector<uint32_t>*, uint32_t, MapCompare<std::vector<uint32_t> > > mapping_table_offsets_;
+  SafeMap<const std::vector<uint8_t>*, uint32_t, MapCompare<std::vector<uint8_t> > > gc_map_offsets_;
 
   DISALLOW_COPY_AND_ASSIGN(OatWriter);
 };
diff --git a/src/oatdump.cc b/src/oatdump.cc
index 6680b57..93eb9a1 100644
--- a/src/oatdump.cc
+++ b/src/oatdump.cc
@@ -19,7 +19,6 @@
 
 #include <fstream>
 #include <iostream>
-#include <map>
 #include <string>
 #include <vector>
 
@@ -33,6 +32,7 @@
 #include "object_utils.h"
 #include "os.h"
 #include "runtime.h"
+#include "safe_map.h"
 #include "space.h"
 #include "stringpiece.h"
 
@@ -901,35 +901,35 @@
         size_t dex_instruction_bytes = code_item->insns_size_in_code_units_ * 2;
         state->stats_.dex_instruction_bytes += dex_instruction_bytes;
 
-        bool first_occurance;
-        size_t gc_map_bytes = state->ComputeOatSize(method->GetGcMapRaw(), &first_occurance);
-        if (first_occurance) {
+        bool first_occurrence;
+        size_t gc_map_bytes = state->ComputeOatSize(method->GetGcMapRaw(), &first_occurrence);
+        if (first_occurrence) {
           state->stats_.gc_map_bytes += gc_map_bytes;
         }
 
         size_t pc_mapping_table_bytes =
-            state->ComputeOatSize(method->GetMappingTableRaw(), &first_occurance);
-        if (first_occurance) {
+            state->ComputeOatSize(method->GetMappingTableRaw(), &first_occurrence);
+        if (first_occurrence) {
           state->stats_.pc_mapping_table_bytes += pc_mapping_table_bytes;
         }
 
         size_t vmap_table_bytes =
-            state->ComputeOatSize(method->GetVmapTableRaw(), &first_occurance);
-        if (first_occurance) {
+            state->ComputeOatSize(method->GetVmapTableRaw(), &first_occurrence);
+        if (first_occurrence) {
           state->stats_.vmap_table_bytes += vmap_table_bytes;
         }
 
         // TODO: compute invoke stub using length from oat file.
         size_t invoke_stub_size = state->ComputeOatSize(
-            reinterpret_cast<const void*>(method->GetInvokeStub()), &first_occurance);
-        if (first_occurance) {
+            reinterpret_cast<const void*>(method->GetInvokeStub()), &first_occurrence);
+        if (first_occurrence) {
           state->stats_.native_to_managed_code_bytes += invoke_stub_size;
         }
         const void* oat_code_begin = state->GetOatCodeBegin(method);
         const void* oat_code_end = state->GetOatCodeEnd(method);
         uint32_t oat_code_size = state->GetOatCodeSize(method);
-        state->ComputeOatSize(oat_code_begin, &first_occurance);
-        if (first_occurance) {
+        state->ComputeOatSize(oat_code_begin, &first_occurrence);
+        if (first_occurrence) {
           state->stats_.managed_code_bytes += oat_code_size;
           if (method->IsConstructor()) {
             if (method->IsStatic()) {
@@ -955,9 +955,7 @@
         state->stats_.ComputeOutliers(total_size, expansion, method);
       }
     }
-    std::string descriptor(ClassHelper(obj_class).GetDescriptor());
-    state->stats_.descriptor_to_bytes[descriptor] += object_bytes;
-    state->stats_.descriptor_to_count[descriptor] += 1;
+    state->stats_.Update(ClassHelper(obj_class).GetDescriptor(), object_bytes);
 
     state->os_ << summary << std::flush;
   }
@@ -965,12 +963,12 @@
   std::set<const void*> already_seen_;
   // Compute the size of the given data within the oat file and whether this is the first time
   // this data has been requested
-  size_t ComputeOatSize(const void* oat_data, bool* first_occurance) {
+  size_t ComputeOatSize(const void* oat_data, bool* first_occurrence) {
     if (already_seen_.count(oat_data) == 0) {
-      *first_occurance = true;
+      *first_occurrence = true;
       already_seen_.insert(oat_data);
     } else {
-      *first_occurance = false;
+      *first_occurrence = false;
     }
     return oat_dumper_->ComputeSize(oat_data);
   }
@@ -1020,11 +1018,23 @@
           vmap_table_bytes(0),
           dex_instruction_bytes(0) {}
 
-    typedef std::map<std::string, size_t> TableBytes;
-    TableBytes descriptor_to_bytes;
+    struct SizeAndCount {
+      SizeAndCount(size_t bytes, size_t count) : bytes(bytes), count(count) {}
+      size_t bytes;
+      size_t count;
+    };
+    typedef SafeMap<std::string, SizeAndCount> SizeAndCountTable;
+    SizeAndCountTable sizes_and_counts;
 
-    typedef std::map<std::string, size_t> TableCount;
-    TableCount descriptor_to_count;
+    void Update(const std::string& descriptor, size_t object_bytes) {
+      SizeAndCountTable::iterator it = sizes_and_counts.find(descriptor);
+      if (it != sizes_and_counts.end()) {
+        it->second.bytes += object_bytes;
+        it->second.count += 1;
+      } else {
+        sizes_and_counts.Put(descriptor, SizeAndCount(object_bytes, 1));
+      }
+    }
 
     double PercentOfOatBytes(size_t size) {
       return (static_cast<double>(size) / static_cast<double>(oat_file_bytes)) * 100;
@@ -1158,21 +1168,18 @@
 
       CHECK_EQ(file_bytes, header_bytes + object_bytes + alignment_bytes);
 
-      os << "\tobject_bytes = sum of descriptor_to_bytes values below:\n";
+      os << "\tobject_bytes breakdown:\n";
       size_t object_bytes_total = 0;
-      typedef TableBytes::const_iterator It;  // TODO: C++0x auto
-      for (It it = descriptor_to_bytes.begin(), end = descriptor_to_bytes.end(); it != end; ++it) {
+      typedef SizeAndCountTable::const_iterator It;  // TODO: C++0x auto
+      for (It it = sizes_and_counts.begin(), end = sizes_and_counts.end(); it != end; ++it) {
         const std::string& descriptor(it->first);
-        size_t bytes = it->second;
-        size_t count = descriptor_to_count[descriptor];
-        double average = static_cast<double>(bytes) / static_cast<double>(count);
-        double percent = PercentOfObjectBytes(bytes);
+        double average = static_cast<double>(it->second.bytes) / static_cast<double>(it->second.count);
+        double percent = PercentOfObjectBytes(it->second.bytes);
         os << StringPrintf("\t%32s %8zd bytes %6zd instances "
-                           "(%3.0f bytes/instance) %2.0f%% of object_bytes\n",
-                           descriptor.c_str(), bytes, count,
+                           "(%4.0f bytes/instance) %2.0f%% of object_bytes\n",
+                           descriptor.c_str(), it->second.bytes, it->second.count,
                            average, percent);
-
-        object_bytes_total += bytes;
+        object_bytes_total += it->second.bytes;
       }
       os << std::endl << std::flush;
       CHECK_EQ(object_bytes, object_bytes_total);
diff --git a/src/runtime.cc b/src/runtime.cc
index d16ee78..06c4020 100644
--- a/src/runtime.cc
+++ b/src/runtime.cc
@@ -1049,7 +1049,7 @@
 void Runtime::SetCompileTimeClassPath(const ClassLoader* class_loader, std::vector<const DexFile*>& class_path) {
   CHECK(!IsStarted());
   use_compile_time_class_path_ = true;
-  compile_time_class_paths_[class_loader] = class_path;
+  compile_time_class_paths_.Put(class_loader, class_path);
 }
 
 }  // namespace art
diff --git a/src/runtime.h b/src/runtime.h
index b8fe35a..0dea763 100644
--- a/src/runtime.h
+++ b/src/runtime.h
@@ -17,21 +17,20 @@
 #ifndef ART_SRC_RUNTIME_H_
 #define ART_SRC_RUNTIME_H_
 
+#include <jni.h>
 #include <stdio.h>
 
 #include <iosfwd>
-#include <map>
 #include <string>
 #include <utility>
 #include <vector>
 
-#include <jni.h>
-
+#include "globals.h"
 #include "heap.h"
 #include "instruction_set.h"
-#include "globals.h"
 #include "macros.h"
 #include "runtime_stats.h"
+#include "safe_map.h"
 #include "stringpiece.h"
 
 namespace art {
@@ -329,7 +328,7 @@
   size_t method_trace_file_size_;
   Trace* tracer_;
 
-  typedef std::map<const ClassLoader*, std::vector<const DexFile*> > CompileTimeClassPaths;
+  typedef SafeMap<const ClassLoader*, std::vector<const DexFile*> > CompileTimeClassPaths;
   CompileTimeClassPaths compile_time_class_paths_;
   bool use_compile_time_class_path_;
 
diff --git a/src/safe_map.h b/src/safe_map.h
new file mode 100644
index 0000000..1544181
--- /dev/null
+++ b/src/safe_map.h
@@ -0,0 +1,82 @@
+#ifndef ART_SRC_SAFE_MAP_H_
+#define ART_SRC_SAFE_MAP_H_
+
+#include <map>
+
+#include "logging.h"
+
+namespace art {
+
+// Equivalent to std::map, but without operator[] and its bug-prone semantics (in particular,
+// the implicit insertion of a default-constructed value on failed lookups).
+template <typename K, typename V, typename Comparator = std::less<K> >
+class SafeMap {
+ private:
+  typedef SafeMap<K, V, Comparator> Self;
+
+ public:
+  typedef typename ::std::map<K, V, Comparator>::iterator iterator;
+  typedef typename ::std::map<K, V, Comparator>::const_iterator const_iterator;
+  typedef typename ::std::map<K, V, Comparator>::size_type size_type;
+  typedef typename ::std::map<K, V, Comparator>::value_type value_type;
+
+  Self& operator=(const Self& rhs) { map_ = rhs.map_; return *this; }
+
+  iterator begin() { return map_.begin(); }
+  const_iterator begin() const { return map_.begin(); }
+  iterator end() { return map_.end(); }
+  const_iterator end() const { return map_.end(); }
+
+  bool empty() const { return map_.empty(); }
+  size_type size() const { return map_.size(); }
+
+  void clear() { return map_.clear(); }
+  void erase(iterator it) { map_.erase(it); }
+  size_type erase(const K& k) { return map_.erase(k); }
+
+  iterator find(const K& k) { return map_.find(k); }
+  const_iterator find(const K& k) const { return map_.find(k); }
+
+  size_type count(const K& k) const { return map_.count(k); }
+
+  // Note that unlike std::map's operator[], this doesn't return a reference to the value.
+  V Get(const K& k) {
+    iterator it = map_.find(k);
+    DCHECK(it != map_.end());
+    return it->second;
+  }
+
+  // Used to insert a new mapping.
+  void Put(const K& k, const V& v) {
+    std::pair<iterator, bool> result = map_.insert(std::make_pair(k, v));
+    DCHECK(result.second); // Check we didn't accidentally overwrite an existing value.
+  }
+
+  // Used to insert a new mapping or overwrite an existing mapping. Note that if the value type
+  // of this container is a pointer, any overwritten pointer will be lost and if this container
+  // was the owner, you have a leak.
+  void Overwrite(const K& k, const V& v) {
+    map_.insert(std::make_pair(k, v));
+  }
+
+  bool Equals(const Self& rhs) const {
+    return map_ == rhs.map_;
+  }
+
+ private:
+  ::std::map<K, V, Comparator> map_;
+};
+
+template <typename K, typename V, typename Comparator>
+bool operator==(const SafeMap<K, V, Comparator>& lhs, const SafeMap<K, V, Comparator>& rhs) {
+  return lhs.Equals(rhs);
+}
+
+template <typename K, typename V, typename Comparator>
+bool operator!=(const SafeMap<K, V, Comparator>& lhs, const SafeMap<K, V, Comparator>& rhs) {
+  return !(lhs == rhs);
+}
+
+}  // namespace art
+
+#endif  // ART_SRC_SAFE_MAP_H_
diff --git a/src/trace.cc b/src/trace.cc
index 3278830..588979b 100644
--- a/src/trace.cc
+++ b/src/trace.cc
@@ -164,7 +164,7 @@
 }
 
 void Trace::AddSavedCodeToMap(const Method* method, const void* code) {
-  saved_code_map_.insert(std::make_pair(method, code));
+  saved_code_map_.Put(method, code);
 }
 
 void Trace::RemoveSavedCodeFromMap(const Method* method) {
@@ -172,7 +172,7 @@
 }
 
 const void* Trace::GetSavedCodeFromMap(const Method* method) {
-  typedef std::map<const Method*, const void*>::const_iterator It; // TODO: C++0x auto
+  typedef SafeMap<const Method*, const void*>::const_iterator It; // TODO: C++0x auto
   It it = saved_code_map_.find(method);
   if (it == saved_code_map_.end()) {
     return NULL;
@@ -355,7 +355,7 @@
 void Trace::LogMethodTraceEvent(Thread* self, const Method* method, Trace::TraceEvent event) {
   if (thread_clock_base_map_.find(self) == thread_clock_base_map_.end()) {
     uint64_t time = ThreadCpuMicroTime();
-    thread_clock_base_map_.insert(std::make_pair(self, time));
+    thread_clock_base_map_.Put(self, time);
   }
 
   // Advance cur_offset_ atomically.
diff --git a/src/trace.h b/src/trace.h
index 8dbf924..bcf7f0a 100644
--- a/src/trace.h
+++ b/src/trace.h
@@ -17,7 +17,6 @@
 #ifndef ART_SRC_TRACE_H_
 #define ART_SRC_TRACE_H_
 
-#include <map>
 #include <ostream>
 #include <set>
 #include <string>
@@ -25,6 +24,7 @@
 #include "file.h"
 #include "globals.h"
 #include "macros.h"
+#include "safe_map.h"
 #include "UniquePtr.h"
 
 namespace art {
@@ -90,13 +90,13 @@
   void DumpThreadList(std::ostream& os);
 
   // Maps a method to its original code pointer.
-  std::map<const Method*, const void*> saved_code_map_;
+  SafeMap<const Method*, const void*> saved_code_map_;
 
   // Set of methods visited by the profiler.
   std::set<const Method*> visited_methods_;
 
   // Maps a thread to its clock base.
-  std::map<Thread*, uint64_t> thread_clock_base_map_;
+  SafeMap<Thread*, uint64_t> thread_clock_base_map_;
 
   // File to write trace data out to, NULL if direct to ddms.
   UniquePtr<File> trace_file_;
diff --git a/src/zip_archive.cc b/src/zip_archive.cc
index fd7086f..5e6b4eb 100644
--- a/src/zip_archive.cc
+++ b/src/zip_archive.cc
@@ -466,10 +466,7 @@
 
     // add the CDE filename to the hash table
     const char* name = reinterpret_cast<const char*>(ptr + kCDELen);
-    bool success = dir_entries_.insert(std::make_pair(StringPiece(name, filename_len), ptr)).second;
-    if (!success) {
-        return false;
-    }
+    dir_entries_.Put(StringPiece(name, filename_len), ptr);
     ptr += kCDELen + filename_len + extra_len + comment_len;
     if (ptr > cd_ptr + cd_length) {
       LOG(WARNING) << "Zip: bad CD advance "
diff --git a/src/zip_archive.h b/src/zip_archive.h
index 4f95284..3889fcb 100644
--- a/src/zip_archive.h
+++ b/src/zip_archive.h
@@ -21,12 +21,11 @@
 #include <sys/mman.h>
 #include <zlib.h>
 
-#include <map>
-
 #include "file.h"
 #include "globals.h"
 #include "logging.h"
 #include "mem_map.h"
+#include "safe_map.h"
 #include "stringpiece.h"
 #include "UniquePtr.h"
 
@@ -120,7 +119,7 @@
   uint16_t num_entries_;
   off_t dir_offset_;
   UniquePtr<MemMap> dir_map_;
-  typedef std::map<StringPiece, const byte*> DirEntries;
+  typedef SafeMap<StringPiece, const byte*> DirEntries;
   DirEntries dir_entries_;
 
   friend class ZipEntry;