diff --git a/build/Android.common.mk b/build/Android.common.mk
index 64f0de4..3932b74 100644
--- a/build/Android.common.mk
+++ b/build/Android.common.mk
@@ -41,6 +41,7 @@
 	src/dex_instruction.cc \
 	src/dex_verifier.cc \
 	src/heap.cc \
+	src/intern_table.cc \
 	src/jni_compiler.cc \
 	src/jni_internal.cc \
 	src/mark_stack.cc \
@@ -83,6 +84,7 @@
 	src/dex_cache_test.cc \
 	src/dex_file_test.cc \
 	src/dex_instruction_visitor_test.cc \
+	src/intern_table_test.cc \
 	src/jni_compiler_test.cc.arm \
 	src/object_test.cc \
 	src/runtime_test.cc \
diff --git a/src/class_linker.cc b/src/class_linker.cc
index 1bfa009..e1dcbf8 100644
--- a/src/class_linker.cc
+++ b/src/class_linker.cc
@@ -186,19 +186,22 @@
   init_done_ = true;
 }
 
-void ClassLinker::VisitRoots(RootVistor* root_visitor, void* arg) {
+void ClassLinker::VisitRoots(Heap::RootVistor* root_visitor, void* arg) {
   root_visitor(class_roots_, arg);
 
   for (size_t i = 0; i < dex_caches_.size(); i++) {
       root_visitor(dex_caches_[i], arg);
   }
 
-  // TODO: acquire classes_lock_
-  typedef Table::const_iterator It; // TODO: C++0x auto
-  for (It it = classes_.begin(), end = classes_.end(); it != end; ++it) {
-      root_visitor(it->second, arg);
+  {
+    MutexLock mu(classes_lock_);
+    typedef Table::const_iterator It; // TODO: C++0x auto
+    for (It it = classes_.begin(), end = classes_.end(); it != end; ++it) {
+        root_visitor(it->second, arg);
+    }
   }
-  // TODO: release classes_lock_
+
+  intern_table_.VisitRoots(root_visitor, arg);
 
   root_visitor(array_interfaces_, arg);
 }
@@ -736,15 +739,14 @@
 }
 
 bool ClassLinker::InsertClass(Class* klass) {
-  // TODO: acquire classes_lock_
+  MutexLock mu(classes_lock_);
   const StringPiece& key = klass->GetDescriptor();
   Table::iterator it = classes_.insert(std::make_pair(key, klass));
   return ((*it).second == klass);
-  // TODO: release classes_lock_
 }
 
 Class* ClassLinker::LookupClass(const StringPiece& descriptor, ClassLoader* class_loader) {
-  // TODO: acquire classes_lock_
+  MutexLock mu(classes_lock_);
   typedef Table::const_iterator It; // TODO: C++0x auto
   for (It it = classes_.find(descriptor), end = classes_.end(); it != end; ++it) {
     Class* klass = it->second;
@@ -753,7 +755,6 @@
     }
   }
   return NULL;
-  // TODO: release classes_lock_
 }
 
 bool ClassLinker::InitializeClass(Class* klass) {
@@ -963,7 +964,7 @@
 
 bool ClassLinker::InitializeSuperClass(Class* klass) {
   CHECK(klass != NULL);
-  // TODO: assert klass lock is acquired
+  MutexLock mu(classes_lock_);
   if (!klass->IsInterface() && klass->HasSuperClass()) {
     Class* super_class = klass->GetSuperClass();
     if (super_class->GetStatus() != Class::kStatusInitialized) {
@@ -1536,10 +1537,9 @@
   const DexFile::StringId& string_id = dex_file.GetStringId(string_idx);
   int32_t utf16_length = dex_file.GetStringLength(string_id);
   const char* utf8_data = dex_file.GetStringData(string_id);
-  String* new_string = String::AllocFromModifiedUtf8(utf16_length, utf8_data);
-  // TODO: intern the new string
-  referring->GetDexCache()->SetResolvedString(string_idx, new_string);
-  return new_string;
+  String* string = intern_table_.Intern(utf16_length, utf8_data);
+  referring->GetDexCache()->SetResolvedString(string_idx, string);
+  return string;
 }
 
 }  // namespace art
diff --git a/src/class_linker.h b/src/class_linker.h
index 70d268d..15bd054 100644
--- a/src/class_linker.h
+++ b/src/class_linker.h
@@ -7,11 +7,14 @@
 #include <utility>
 #include <vector>
 
-#include "heap.h"
-#include "macros.h"
 #include "dex_file.h"
-#include "thread.h"
+#include "heap.h"
+#include "intern_table.h"
+#include "macros.h"
 #include "object.h"
+#include "thread.h"
+#include "unordered_map.h"
+
 #include "gtest/gtest.h"
 
 namespace art {
@@ -34,24 +37,14 @@
 
   bool InitializeClass(Class* klass);
 
-  Class* LookupClass(const StringPiece& descriptor, ClassLoader* class_loader);
-
-  Class* ResolveClass(const Class* referring,
-                      uint32_t class_idx,
-                      const DexFile& dex_file);
-
-  String* ResolveString(const Class* referring,
-                        uint32_t string_idx,
-                        const DexFile& dex_file);
-
   void RegisterDexFile(const DexFile* dex_file);
 
-  // TODO replace with heap interface
-  typedef void (RootVistor)(Object* root, void* arg);
-  void VisitRoots(RootVistor* root_visitor, void* arg);
+  void VisitRoots(Heap::RootVistor* root_visitor, void* arg);
 
  private:
-  ClassLinker() {}
+  ClassLinker() {
+    classes_lock_ = Mutex::Create("ClassLinker::Lock");
+  }
 
   void Init(const std::vector<DexFile*>& boot_class_path_);
 
@@ -104,6 +97,16 @@
                   Class* klass,
                   Method* dst);
 
+  Class* ResolveClass(const Class* referring,
+                      uint32_t class_idx,
+                      const DexFile& dex_file);
+
+  String* ResolveString(const Class* referring,
+                        uint32_t string_idx,
+                        const DexFile& dex_file);
+
+  Class* LookupClass(const StringPiece& descriptor, ClassLoader* class_loader);
+
   // Inserts a class into the class table.  Returns true if the class
   // was inserted.
   bool InsertClass(Class* klass);
@@ -149,14 +152,11 @@
   // multimap from String::descriptor_ to Class* instances. Results
   // should be compared for a matching Class::descriptor_ and
   // Class::class_loader_.
-  // TODO: unordered_multimap
-  typedef std::multimap<const StringPiece, Class*> Table;
-
+  typedef std::tr1::unordered_multimap<StringPiece, Class*> Table;
   Table classes_;
-
   Mutex* classes_lock_;
 
-  // TODO: classpath
+  InternTable intern_table_;
 
   // indexes into class_roots_
   enum ClassRoot {
diff --git a/src/class_linker_test.cc b/src/class_linker_test.cc
index a9c3e50..5951c0b 100644
--- a/src/class_linker_test.cc
+++ b/src/class_linker_test.cc
@@ -4,6 +4,7 @@
 #include "class_linker.h"
 #include "dex_file.h"
 #include "heap.h"
+
 #include "gtest/gtest.h"
 
 namespace art {
diff --git a/src/dex_file.cc b/src/dex_file.cc
index 35e98db..90893cb 100644
--- a/src/dex_file.cc
+++ b/src/dex_file.cc
@@ -34,7 +34,9 @@
       return ClassPathEntry(dex_file, dex_class_def);
     }
   }
-  return ClassPathEntry(NULL, NULL);
+  // TODO remove reinterpret_cast when issue with -std=gnu++0x host issue resolved
+  return ClassPathEntry(reinterpret_cast<const DexFile*>(NULL),
+                        reinterpret_cast<const DexFile::ClassDef*>(NULL));
 }
 
 DexFile::Closer::~Closer() {}
diff --git a/src/heap.h b/src/heap.h
index 1059fd7..f8a5d23 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -23,6 +23,8 @@
 
   static const size_t kMaximumSize = 64 * MB;
 
+  typedef void (RootVistor)(Object* root, void* arg);
+
   static bool Init() {
     return Init(kStartupSize, kMaximumSize);
   }
diff --git a/src/intern_table.cc b/src/intern_table.cc
new file mode 100644
index 0000000..31749fd
--- /dev/null
+++ b/src/intern_table.cc
@@ -0,0 +1,40 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+
+#include "intern_table.h"
+
+#include "scoped_ptr.h"
+
+namespace art {
+
+InternTable::InternTable() {
+  intern_table_lock_ = Mutex::Create("InternTable::Lock");
+}
+
+void InternTable::VisitRoots(Heap::RootVistor* root_visitor, void* arg) {
+  MutexLock mu(intern_table_lock_);
+  typedef Table::const_iterator It; // TODO: C++0x auto
+  for (It it = intern_table_.begin(), end = intern_table_.end(); it != end; ++it) {
+      root_visitor(it->second, arg);
+  }
+}
+
+String* InternTable::Intern(int32_t utf16_length, const char* utf8_data_in) {
+  scoped_ptr<uint16_t> utf16_data_out(new uint16_t[utf16_length]);
+  String::ConvertModifiedUtf8ToUtf16(utf16_data_out.get(), utf8_data_in);
+  int32_t hash_code = String::ComputeUtf16Hash(utf16_data_out.get(), utf16_length);
+  {
+    MutexLock mu(intern_table_lock_);
+    typedef Table::const_iterator It; // TODO: C++0x auto
+    for (It it = intern_table_.find(hash_code), end = intern_table_.end(); it != end; ++it) {
+      String* string = it->second;
+      if (string->Equals(utf16_data_out.get(), 0, utf16_length)) {
+        return string;
+      }
+    }
+    String* new_string = String::AllocFromUtf16(utf16_length, utf16_data_out.get(), hash_code);
+    intern_table_.insert(std::make_pair(hash_code, new_string));
+    return new_string;
+  }
+}
+
+}  // namespace art
diff --git a/src/intern_table.h b/src/intern_table.h
new file mode 100644
index 0000000..61da28b
--- /dev/null
+++ b/src/intern_table.h
@@ -0,0 +1,27 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+
+#ifndef ART_SRC_INTERN_TABLE_H_
+#define ART_SRC_INTERN_TABLE_H_
+
+#include "unordered_map.h"
+
+#include "heap.h"
+#include "object.h"
+
+namespace art {
+
+class InternTable {
+ public:
+  InternTable();
+  String* Intern(int32_t utf16_length, const char* utf8_data);
+  void VisitRoots(Heap::RootVistor* root_visitor, void* arg);
+
+ private:
+  typedef std::tr1::unordered_multimap<int32_t, String*> Table;
+  Table intern_table_;
+  Mutex* intern_table_lock_;
+};
+
+}  // namespace art
+
+#endif  // ART_SRC_CLASS_LINKER_H_
diff --git a/src/intern_table_test.cc b/src/intern_table_test.cc
new file mode 100644
index 0000000..daae841
--- /dev/null
+++ b/src/intern_table_test.cc
@@ -0,0 +1,31 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+
+#include "intern_table.h"
+
+#include "common_test.h"
+#include "object.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+class InternTableTest : public RuntimeTest {};
+
+TEST_F(InternTableTest, Intern) {
+  InternTable intern_table;
+  String* foo_1 = intern_table.Intern(3, "foo");
+  String* foo_2 = intern_table.Intern(3, "foo");
+  String* foo_3 = String::AllocFromAscii("foo");
+  String* bar = intern_table.Intern(3, "bar");
+  EXPECT_TRUE(foo_1->Equals("foo"));
+  EXPECT_TRUE(foo_2->Equals("foo"));
+  EXPECT_TRUE(foo_3->Equals("foo"));
+  EXPECT_TRUE(foo_1 != NULL);
+  EXPECT_TRUE(foo_2 != NULL);
+  EXPECT_EQ(foo_1, foo_2);
+  EXPECT_NE(foo_1, bar);
+  EXPECT_NE(foo_2, bar);
+  EXPECT_NE(foo_3, bar);
+}
+
+}  // namespace art
diff --git a/src/object.h b/src/object.h
index 0e0728d..33db15e 100644
--- a/src/object.h
+++ b/src/object.h
@@ -1096,7 +1096,7 @@
     return GetChars()[i];
   }
 
-  void  SetChar(uint32_t i, uint16_t ch) {
+  void SetChar(uint32_t i, uint16_t ch) {
     CHECK_LT(i, GetLength());
     GetChars()[i] = ch;
   }
@@ -1111,33 +1111,34 @@
     return array_;
   }
 
-  uint32_t GetHashCode() const {
+  int32_t GetHashCode() const {
     return hash_code_;
   }
 
-  uint32_t GetOffset() const {
+  int32_t GetOffset() const {
+    DCHECK_LE(0, offset_);
     return offset_;
   }
 
-  uint32_t GetLength() const {
+  int32_t GetLength() const {
+    DCHECK_LE(0, count_);
     return count_;
   }
 
-  uint16_t CharAt(uint32_t index) const {
+  uint16_t CharAt(int32_t index) const {
     return GetCharArray()->GetChar(index + GetOffset());
   }
 
-  static String* AllocFromUtf16(Class* java_lang_String,
-                                Class* char_array,
-                                int32_t utf16_length,
-                                uint16_t* utf16_data_in) {
-    String* string = Alloc(java_lang_String, char_array, utf16_length);
+  static String* AllocFromUtf16(int32_t utf16_length,
+                                uint16_t* utf16_data_in,
+                                int32_t hash_code) {
+    String* string = Alloc(GetJavaLangString(), GetCharArrayClass(), utf16_length);
     uint16_t* utf16_data_out = string->array_->GetChars();
     // TODO use 16-bit wide memset variant
     for (int i = 0; i < utf16_length; i++ ) {
         utf16_data_out[i] = utf16_data_in[i];
     }
-    string->hash_code_ = ComputeUtf16Hash(utf16_data_out, utf16_length);
+    string->hash_code_ = hash_code;
     return string;
   }
 
@@ -1155,17 +1156,16 @@
   // Creates a String of the given ASCII characters. It is an error to call this
   // using non-ASCII characters as this function assumes one char per byte.
   static String* AllocFromAscii(const char* ascii_data_in) {
-    DCHECK(java_lang_String_ != NULL);
-    DCHECK(char_array_ != NULL);
-    return AllocFromModifiedUtf8(java_lang_String_,
-                                 char_array_,
+    return AllocFromModifiedUtf8(GetJavaLangString(),
+                                 GetCharArrayClass(),
                                  strlen(ascii_data_in),
                                  ascii_data_in);
   }
 
   static String* AllocFromModifiedUtf8(int32_t utf16_length,
                                        const char* utf8_data_in) {
-    return AllocFromModifiedUtf8(java_lang_String_, char_array_, utf16_length, utf8_data_in);
+    return AllocFromModifiedUtf8(GetJavaLangString(), GetCharArrayClass(),
+                                 utf16_length, utf8_data_in);
   }
 
   static void InitClasses(Class* java_lang_String, Class* char_array);
@@ -1253,13 +1253,13 @@
   static int32_t ComputeUtf16Hash(const uint16_t* string_data, size_t string_length) {
     int32_t hash = 0;
     while (string_length--) {
-        hash = hash * 31 + *string_data++;
+      hash = hash * 31 + *string_data++;
     }
     return hash;
   }
 
   bool Equals(const char* modified_utf8) const {
-    for (size_t i = 0; i < GetLength(); ++i) {
+    for (int32_t i = 0; i < GetLength(); ++i) {
       uint16_t ch = GetUtf16FromUtf8(&modified_utf8);
       if (ch == '\0' || ch != CharAt(i)) {
         return false;
@@ -1274,10 +1274,11 @@
   }
 
   bool Equals(const String* that) const {
+    // TODO short circuit on hash_code_
     if (this->GetLength() != that->GetLength()) {
       return false;
     }
-    for (size_t i = 0; i < that->GetLength(); ++i) {
+    for (int32_t i = 0; i < that->GetLength(); ++i) {
       if (this->CharAt(i) != that->CharAt(i)) {
         return false;
       }
@@ -1285,15 +1286,36 @@
     return true;
   }
 
+  bool Equals(const uint16_t* that_chars, int32_t that_offset, int32_t that_length) const {
+    if (this->GetLength() != that_length) {
+      return false;
+    }
+    for (int32_t i = 0; i < that_length; ++i) {
+      if (this->CharAt(i) != that_chars[that_offset + i]) {
+        return false;
+      }
+    }
+    return true;
+  }
+
  private:
   // Field order required by test "ValidateFieldOrderOfJavaCppUnionClasses".
   CharArray* array_;
 
-  uint32_t hash_code_;
+  int32_t hash_code_;
 
-  uint32_t offset_;
+  int32_t offset_;
 
-  uint32_t count_;
+  int32_t count_;
+
+  static Class* GetJavaLangString() {
+    DCHECK(java_lang_String_ != NULL);
+    return java_lang_String_;
+  }
+  static Class* GetCharArrayClass() {
+    DCHECK(char_array_ != NULL);
+    return char_array_;
+  }
 
   static Class* java_lang_String_;
   static Class* char_array_;
diff --git a/src/object_test.cc b/src/object_test.cc
index 18e8e77..2d32ad0 100644
--- a/src/object_test.cc
+++ b/src/object_test.cc
@@ -16,12 +16,12 @@
 
 class ObjectTest : public RuntimeTest {
  protected:
-  void AssertString(size_t length,
+  void AssertString(int32_t length,
                     const char* utf8_in,
                     const char* utf16_expected_le,
-                    uint32_t hash_expected) {
+                    int32_t hash_expected) {
     uint16_t utf16_expected[length];
-    for (size_t i = 0; i < length; i++) {
+    for (int32_t i = 0; i < length; i++) {
       uint16_t ch = (((utf16_expected_le[i*2 + 0] & 0xff) << 8) |
                      ((utf16_expected_le[i*2 + 1] & 0xff) << 0));
       utf16_expected[i] = ch;
@@ -32,8 +32,8 @@
     ASSERT_TRUE(string->GetCharArray() != NULL);
     ASSERT_TRUE(string->GetCharArray()->GetChars() != NULL);
     // strlen is necessary because the 1-character string "\0" is interpreted as ""
-    ASSERT_TRUE(string->Equals(utf8_in) || length != strlen(utf8_in));
-    for (size_t i = 0; i < length; i++) {
+    ASSERT_TRUE(string->Equals(utf8_in) || length != static_cast<int32_t>(strlen(utf8_in)));
+    for (int32_t i = 0; i < length; i++) {
       EXPECT_EQ(utf16_expected[i], string->GetCharArray()->GetChar(i));
     }
     EXPECT_EQ(hash_expected, string->GetHashCode());
diff --git a/src/unordered_map.h b/src/unordered_map.h
new file mode 100644
index 0000000..66613c6
--- /dev/null
+++ b/src/unordered_map.h
@@ -0,0 +1,37 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+
+#ifndef ART_SRC_CLASS_UNORDERED_MAP_H_
+#define ART_SRC_CLASS_UNORDERED_MAP_H_
+
+#include "stringpiece.h"
+
+#ifdef __ANDROID__
+#include <unordered_map>
+#else
+#include <tr1/unordered_map>
+#endif
+
+namespace std {
+#ifndef __ANDROID__
+namespace tr1 {
+#endif
+template<>
+struct hash<art::StringPiece> {
+ public:
+  size_t operator()(const art::StringPiece& string_piece) const {
+    size_t string_size = string_piece.size();
+    const char* string_data = string_piece.data();
+    // this is the java.lang.String hashcode for convenience, not interoperability
+    size_t hash = 0;
+    while (string_size--) {
+      hash = hash * 31 + *string_data++;
+    }
+    return hash;
+  }
+};
+#ifndef __ANDROID__
+}  // namespace tr1
+#endif
+}  // namespace std
+
+#endif  // ART_SRC_CLASS_UNORDERED_MAP_H_
diff --git a/src/zip_archive.cc b/src/zip_archive.cc
index 09dc3d4..a615321 100644
--- a/src/zip_archive.cc
+++ b/src/zip_archive.cc
@@ -310,7 +310,7 @@
 
 ZipEntry* ZipArchive::Find(const char* name) {
   DCHECK(name != NULL);
-  std::map<StringPiece, const uint8_t*>::const_iterator it = dir_entries_.find(name);
+  DirEntries::const_iterator it = dir_entries_.find(name);
   if (it == dir_entries_.end()) {
     return NULL;
   }
diff --git a/src/zip_archive.h b/src/zip_archive.h
index 9eb2948..858afe09 100644
--- a/src/zip_archive.h
+++ b/src/zip_archive.h
@@ -26,6 +26,7 @@
 #include "logging.h"
 #include "scoped_ptr.h"
 #include "stringpiece.h"
+#include "unordered_map.h"
 
 namespace art {
 
@@ -183,8 +184,8 @@
   uint16_t num_entries_;
   off_t dir_offset_;
   scoped_ptr<MemMap> dir_map_;
-  // TODO: unordered map
-  std::map<StringPiece, const uint8_t*> dir_entries_;
+  typedef std::tr1::unordered_map<StringPiece, const uint8_t*> DirEntries;
+  DirEntries dir_entries_;
 
   friend class ZipEntry;
 };