Index: src/OFMapTable.m
==================================================================
--- src/OFMapTable.m
+++ src/OFMapTable.m
@@ -336,21 +336,24 @@
 		if (_buckets[i] != NULL && _buckets[i] != &deleted) {
 			uint32_t j, last;
 
 			last = capacity;
 
-			j = _buckets[i]->hash & (capacity - 1);
-			for (; j < last && buckets[j] != NULL; j++);
+			for (j = _buckets[i]->hash & (capacity - 1);
+			    j < last && buckets[j] != NULL; j++);
 
 			/* In case the last bucket is already used */
 			if (j >= last) {
 				last = _buckets[i]->hash & (capacity - 1);
 
 				for (j = 0; j < last &&
 				    buckets[j] != NULL; j++);
 			}
 
+			if (j >= last)
+				@throw [OFOutOfRangeException exception];
+
 			buckets[j] = _buckets[i];
 		}
 	}
 
 	[self freeMemory: _buckets];

Index: src/runtime/class.m
==================================================================
--- src/runtime/class.m
+++ src/runtime/class.m
@@ -862,11 +862,11 @@
 		objc_unregister_class(cls->subclass_list[0]);
 
 	if (cls->info & OBJC_CLASS_INFO_LOADED)
 		call_method(cls, "unload");
 
-	objc_hashtable_set(classes, cls->name, NULL);
+	objc_hashtable_delete(classes, cls->name);
 
 	if (strcmp(class_getName(cls), "Protocol"))
 		classes_cnt--;
 
 	unregister_class(cls);
@@ -894,17 +894,21 @@
 
 	if (classes == NULL)
 		return;
 
 	for (i = 0; i < classes->size; i++) {
-		if (classes->data[i] != NULL) {
+		if (classes->data[i] != NULL &&
+		    classes->data[i] != &objc_deleted_bucket) {
 			void *cls = (Class)classes->data[i]->obj;
 
 			if (cls == Nil || (uintptr_t)cls & 1)
 				continue;
 
 			objc_unregister_class(cls);
+
+			/* The table might have been resized, so start again */
+			i = 0;
 		}
 	}
 
 	assert(classes_cnt == 0);
 

Index: src/runtime/hashtable.m
==================================================================
--- src/runtime/hashtable.m
+++ src/runtime/hashtable.m
@@ -22,10 +22,12 @@
 #include <string.h>
 
 #import "runtime.h"
 #import "runtime-private.h"
 
+struct objc_hashtable_bucket objc_deleted_bucket;
+
 uint32_t
 objc_hash_string(const void *str_)
 {
 	const char *str = str_;
 	uint32_t hash = 0;
@@ -69,74 +71,83 @@
 	if (table->data == NULL)
 		OBJC_ERROR("Not enough memory to allocate hash table!");
 
 	return table;
 }
+
+static void
+resize(struct objc_hashtable *table, uint32_t count)
+{
+	uint32_t i, fullness, nsize;
+	struct objc_hashtable_bucket **ndata;
+
+	if (count > UINT32_MAX / sizeof(*table->data) || count > UINT32_MAX / 8)
+		OBJC_ERROR("Integer overflow!");
+
+	fullness = count * 8 / table->size;
+
+	if (fullness >= 6) {
+		if (table->size > UINT32_MAX / 2)
+			nsize = table->size;
+
+		nsize = table->size * 2;
+	} else if (fullness <= 1)
+		nsize = table->size / 2;
+	else
+		return;
+
+	if ((ndata = calloc(nsize,
+	    sizeof(struct objc_hashtable_bucket*))) == NULL)
+		OBJC_ERROR("Not enough memory to insert into hash table!");
+
+	for (i = 0; i < table->size; i++) {
+		if (table->data[i] != NULL &&
+		    table->data[i] != &objc_deleted_bucket) {
+			uint32_t j, last;
+
+			last = nsize;
+
+			for (j = table->data[i]->hash & (nsize - 1);
+			    j < last && ndata[j] != NULL; j++);
+
+			if (j >= last) {
+				last = table->data[i]->hash & (nsize - 1);
+
+				for (j = 0; j < last && ndata[j] != NULL; j++);
+			}
+
+			if (j >= last)
+				OBJC_ERROR("No free bucket!");
+
+			ndata[j] = table->data[i];
+		}
+	}
+
+	free(table->data);
+	table->data = ndata;
+	table->size = nsize;
+}
 
 static void
 insert(struct objc_hashtable *table, const void *key, const void *obj)
 {
 	uint32_t i, hash, last;
 	struct objc_hashtable_bucket *bucket;
 
-	hash = table->hash(key);
-
-	if (table->count + 1 > UINT32_MAX / 4)
-		OBJC_ERROR("Integer overflow!");
-
-	if ((table->count + 1) * 4 / table->size >= 3) {
-		struct objc_hashtable_bucket **newData;
-		uint32_t newSize;
-
-		if (table->size > UINT32_MAX / 2)
-			OBJC_ERROR("Integer overflow!");
-
-		newSize = table->size * 2;
-
-		if ((newData = calloc(newSize,
-		    sizeof(struct objc_hashtable_bucket*))) == NULL)
-			OBJC_ERROR("Not enough memory to insert into hash "
-			    "table!");
-
-		for (i = 0; i < table->size; i++) {
-			if (table->data[i] != NULL) {
-				uint32_t j;
-
-				last = newSize;
-
-				for (j = table->data[i]->hash & (newSize - 1);
-				    j < last && newData[j] != NULL; j++);
-
-				if (j >= last) {
-					last = table->data[i]->hash &
-					    (newSize - 1);
-
-					for (j = 0; j < last &&
-					    newData[j] != NULL; j++);
-				}
-
-				if (j >= last)
-					OBJC_ERROR("No free bucket!");
-
-				newData[j] = table->data[i];
-			}
-		}
-
-		free(table->data);
-		table->data = newData;
-		table->size = newSize;
-	}
-
+	resize(table, table->count + 1);
+
+	hash = table->hash(key);
 	last = table->size;
 
-	for (i = hash & (table->size - 1);
-	    i < last && table->data[i] != NULL; i++);
+	for (i = hash & (table->size - 1); i < last && table->data[i] != NULL &&
+	    table->data[i] != &objc_deleted_bucket; i++);
 
 	if (i >= last) {
 		last = hash & (table->size - 1);
 
-		for (i = 0; i < last && table->data[i] != NULL; i++);
+		for (i = 0; i < last && table->data[i] != NULL &&
+		    table->data[i] != &objc_deleted_bucket; i++);
 	}
 
 	if (i >= last)
 		OBJC_ERROR("No free bucket!");
 
@@ -149,38 +160,50 @@
 
 	table->data[i] = bucket;
 	table->count++;
 }
 
-static inline int64_t
-index_for_key(struct objc_hashtable *table, const void *key)
+static inline bool
+index_for_key(struct objc_hashtable *table, const void *key, uint32_t *index)
 {
 	uint32_t i, hash;
 
 	hash = table->hash(key) & (table->size - 1);
 
-	for (i = hash; i < table->size && table->data[i] != NULL; i++)
-		if (table->equal(table->data[i]->key, key))
-			return i;
+	for (i = hash; i < table->size && table->data[i] != NULL; i++) {
+		if (table->data[i] == &objc_deleted_bucket)
+			continue;
+
+		if (table->equal(table->data[i]->key, key)) {
+			*index = i;
+			return true;
+		}
+	}
 
 	if (i < table->size)
-		return -1;
+		return false;
+
+	for (i = 0; i < hash && table->data[i] != NULL; i++) {
+		if (table->data[i] == &objc_deleted_bucket)
+			continue;
 
-	for (i = 0; i < hash && table->data[i] != NULL; i++)
-		if (table->equal(table->data[i]->key, key))
-			return i;
+		if (table->equal(table->data[i]->key, key)) {
+			*index = i;
+			return true;
+		}
+	}
 
-	return -1;
+	return false;
 }
 
 void
 objc_hashtable_set(struct objc_hashtable *table, const void *key,
     const void *obj)
 {
-	int64_t idx = index_for_key(table, key);
+	uint32_t idx;
 
-	if (idx < 0) {
+	if (!index_for_key(table, key, &idx)) {
 		insert(table, key, obj);
 		return;
 	}
 
 	table->data[idx]->obj = obj;
@@ -187,25 +210,41 @@
 }
 
 void*
 objc_hashtable_get(struct objc_hashtable *table, const void *key)
 {
-	int64_t idx = index_for_key(table, key);
+	uint32_t idx;
 
-	if (idx < 0)
+	if (!index_for_key(table, key, &idx))
 		return NULL;
 
 	return (void*)table->data[idx]->obj;
 }
+
+void
+objc_hashtable_delete(struct objc_hashtable *table, const void *key)
+{
+	uint32_t idx;
+
+	if (!index_for_key(table, key, &idx))
+		return;
+
+	free(table->data[idx]);
+	table->data[idx] = &objc_deleted_bucket;
+
+	table->count--;
+	resize(table, table->count);
+}
 
 void
 objc_hashtable_free(struct objc_hashtable *table)
 {
 	uint32_t i;
 
 	for (i = 0; i < table->size; i++)
-		if (table->data[i] != NULL)
+		if (table->data[i] != NULL &&
+		    table->data[i] != &objc_deleted_bucket)
 			free(table->data[i]);
 
 	free(table->data);
 	free(table);
 }

Index: src/runtime/runtime-private.h
==================================================================
--- src/runtime/runtime-private.h
+++ src/runtime/runtime-private.h
@@ -131,13 +131,15 @@
 extern void objc_unregister_all_classes(void);
 extern uint32_t objc_hash_string(const void*);
 extern bool objc_equal_string(const void*, const void*);
 extern struct objc_hashtable* objc_hashtable_new(uint32_t (*)(const void*),
     bool (*)(const void*, const void*), uint32_t);
+extern struct objc_hashtable_bucket objc_deleted_bucket;
 extern void objc_hashtable_set(struct objc_hashtable*, const void*,
     const void*);
 extern void* objc_hashtable_get(struct objc_hashtable*, const void*);
+extern void objc_hashtable_delete(struct objc_hashtable*, const void*);
 extern void objc_hashtable_free(struct objc_hashtable *h);
 extern void objc_register_selector(struct objc_abi_selector*);
 extern void objc_register_all_selectors(struct objc_abi_symtab*);
 extern void objc_unregister_all_selectors(void);
 extern struct objc_sparsearray* objc_sparsearray_new(void);