diff --git a/src/objects.cc b/src/objects.cc
index 0f8dca3..118c489 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -1351,6 +1351,8 @@
 Object* JSObject::AddConstantFunctionProperty(String* name,
                                               JSFunction* function,
                                               PropertyAttributes attributes) {
+  ASSERT(!Heap::InNewSpace(function));
+
   // Allocate new instance descriptors with (name, function) added
   ConstantFunctionDescriptor d(name, function, attributes);
   Object* new_descriptors =
@@ -1437,7 +1439,7 @@
     // Ensure the descriptor array does not get too big.
     if (map()->instance_descriptors()->number_of_descriptors() <
         DescriptorArray::kMaxNumberOfDescriptors) {
-      if (value->IsJSFunction()) {
+      if (value->IsJSFunction() && !Heap::InNewSpace(value)) {
         return AddConstantFunctionProperty(name,
                                            JSFunction::cast(value),
                                            attributes);
@@ -3254,7 +3256,8 @@
     return Heap::empty_descriptor_array();
   }
   // Allocate the array of keys.
-  Object* array = Heap::AllocateFixedArray(ToKeyIndex(number_of_descriptors));
+  Object* array =
+      Heap::AllocateFixedArray(ToKeyIndex(number_of_descriptors));
   if (array->IsFailure()) return array;
   // Do not use DescriptorArray::cast on incomplete object.
   FixedArray* result = FixedArray::cast(array);
@@ -6831,43 +6834,36 @@
 
 
 template<typename Shape, typename Key>
-Object* HashTable<Shape, Key>::Allocate(
-    int at_least_space_for) {
+Object* HashTable<Shape, Key>::Allocate(int at_least_space_for) {
   int capacity = RoundUpToPowerOf2(at_least_space_for);
-  if (capacity < 4) capacity = 4;  // Guarantee min capacity.
+  if (capacity < 4) {
+    capacity = 4;  // Guarantee min capacity.
+  } else if (capacity > HashTable::kMaxCapacity) {
+    return Failure::OutOfMemoryException();
+  }
+
   Object* obj = Heap::AllocateHashTable(EntryToIndex(capacity));
   if (!obj->IsFailure()) {
     HashTable::cast(obj)->SetNumberOfElements(0);
+    HashTable::cast(obj)->SetNumberOfDeletedElements(0);
     HashTable::cast(obj)->SetCapacity(capacity);
   }
   return obj;
 }
 
 
-
-// Find entry for key otherwise return -1.
+// Find entry for key otherwise return kNotFound.
 template<typename Shape, typename Key>
 int HashTable<Shape, Key>::FindEntry(Key key) {
-  uint32_t nof = NumberOfElements();
-  if (nof == 0) return kNotFound;  // Bail out if empty.
-
   uint32_t capacity = Capacity();
-  uint32_t hash = Shape::Hash(key);
-  uint32_t entry = GetProbe(hash, 0, capacity);
-
-  Object* element = KeyAt(entry);
-  uint32_t passed_elements = 0;
-  if (!element->IsNull()) {
-    if (!element->IsUndefined() && Shape::IsMatch(key, element)) return entry;
-    if (++passed_elements == nof) return kNotFound;
-  }
-  for (uint32_t i = 1; !element->IsUndefined(); i++) {
-    entry = GetProbe(hash, i, capacity);
-    element = KeyAt(entry);
-    if (!element->IsNull()) {
-      if (!element->IsUndefined() && Shape::IsMatch(key, element)) return entry;
-      if (++passed_elements == nof) return kNotFound;
-    }
+  uint32_t entry = FirstProbe(Shape::Hash(key), capacity);
+  uint32_t count = 1;
+  // EnsureCapacity will guarantee the hash table is never full.
+  while (true) {
+    Object* element = KeyAt(entry);
+    if (element->IsUndefined()) break;  // Empty entry.
+    if (!element->IsNull() && Shape::IsMatch(key, element)) return entry;
+    entry = NextProbe(entry, count++, capacity);
   }
   return kNotFound;
 }
@@ -6877,8 +6873,12 @@
 Object* HashTable<Shape, Key>::EnsureCapacity(int n, Key key) {
   int capacity = Capacity();
   int nof = NumberOfElements() + n;
-  // Make sure 50% is free
-  if (nof + (nof >> 1) <= capacity) return this;
+  int nod = NumberOfDeletedElements();
+  // Return if:
+  //   50% is still free after adding n elements and
+  //   at most 50% of the free elements are deleted elements.
+  if ((nof + (nof >> 1) <= capacity) &&
+      (nod <= (capacity - nof) >> 1)) return this;
 
   Object* obj = Allocate(nof * 2);
   if (obj->IsFailure()) return obj;
@@ -6905,21 +6905,23 @@
     }
   }
   table->SetNumberOfElements(NumberOfElements());
+  table->SetNumberOfDeletedElements(0);
   return table;
 }
 
 
+
 template<typename Shape, typename Key>
 uint32_t HashTable<Shape, Key>::FindInsertionEntry(uint32_t hash) {
   uint32_t capacity = Capacity();
-  uint32_t entry = GetProbe(hash, 0, capacity);
-  Object* element = KeyAt(entry);
-
-  for (uint32_t i = 1; !(element->IsUndefined() || element->IsNull()); i++) {
-    entry = GetProbe(hash, i, capacity);
-    element = KeyAt(entry);
+  uint32_t entry = FirstProbe(hash, capacity);
+  uint32_t count = 1;
+  // EnsureCapacity will guarantee the hash table is never full.
+  while (true) {
+    Object* element = KeyAt(entry);
+    if (element->IsUndefined() || element->IsNull()) break;
+    entry = NextProbe(entry, count++, capacity);
   }
-
   return entry;
 }
 
@@ -6998,6 +7000,10 @@
 template
 int Dictionary<StringDictionaryShape, String*>::NumberOfEnumElements();
 
+template
+int HashTable<NumberDictionaryShape, uint32_t>::FindEntry(uint32_t);
+
+
 // Collates undefined and unexisting elements below limit from position
 // zero of the elements. The object stays in Dictionary mode.
 Object* JSObject::PrepareSlowElementsForSort(uint32_t limit) {
@@ -7700,7 +7706,7 @@
   }
 
   // Update the number of elements.
-  SetNumberOfElements(NumberOfElements() - removed_entries);
+  ElementsRemoved(removed_entries);
 }
 
 
@@ -7962,7 +7968,10 @@
       PropertyType type = DetailsAt(i).type();
       ASSERT(type != FIELD);
       instance_descriptor_length++;
-      if (type == NORMAL && !value->IsJSFunction()) number_of_fields += 1;
+      if (type == NORMAL &&
+          (!value->IsJSFunction() || Heap::InNewSpace(value))) {
+        number_of_fields += 1;
+      }
     }
   }
 
@@ -7993,7 +8002,7 @@
       PropertyDetails details = DetailsAt(i);
       PropertyType type = details.type();
 
-      if (value->IsJSFunction()) {
+      if (value->IsJSFunction() && !Heap::InNewSpace(value)) {
         ConstantFunctionDescriptor d(String::cast(key),
                                      JSFunction::cast(value),
                                      details.attributes(),