Index: src/OFDictionary.m
==================================================================
--- src/OFDictionary.m
+++ src/OFDictionary.m
@@ -208,17 +208,33 @@
 		    exceptionWithClass: [self class]];
 
 	return [self initWithKeysAndObjects: key, object, nil];
 }
 
-- initWithObjects: (OFArray*)objects
-	  forKeys: (OFArray*)keys
+- initWithObjects: (OFArray*)objects_
+	  forKeys: (OFArray*)keys_
 {
-	Class c = [self class];
-	[self release];
-	@throw [OFNotImplementedException exceptionWithClass: c
-						    selector: _cmd];
+	id *objects, *keys;
+	size_t count;
+
+	@try {
+		count = [objects_ count];
+
+		if (count != [keys_ count])
+			@throw [OFInvalidArgumentException
+			    exceptionWithClass: [self class]];
+
+		objects = [objects_ objects];
+		keys = [keys_ objects];
+	} @catch (id e) {
+		[self release];
+		@throw e;
+	}
+
+	return [self initWithObjects: objects
+			     forKeys: keys
+			       count: count];
 }
 
 - initWithObjects: (id const*)objects
 	  forKeys: (id const*)keys
 	    count: (size_t)count

Index: src/OFDictionary_hashtable.h
==================================================================
--- src/OFDictionary_hashtable.h
+++ src/OFDictionary_hashtable.h
@@ -14,56 +14,13 @@
  * file.
  */
 
 #import "OFDictionary.h"
 
-struct of_dictionary_hashtable_bucket
-{
-	id key, object;
-	uint32_t hash;
-};
+@class OFMapTable;
+@class OFMapTableEnumerator;
 
 @interface OFDictionary_hashtable: OFDictionary
 {
-	struct of_dictionary_hashtable_bucket **data;
-	uint32_t size;
-	size_t count;
-}
-
-#if defined(OF_SET_M) || defined(OF_COUNTED_SET_M) || \
-    defined(OF_SET_HASHTABLE_M) || defined(OF_COUNTED_SET_HASHTABLE_M)
-- OF_initWithDictionary: (OFDictionary*)dictionary
-	       copyKeys: (BOOL)copyKeys;
-#endif
-@end
-
-@interface OFDictionaryEnumerator_hashtable: OFEnumerator
-{
-	OFDictionary_hashtable *dictionary;
-	struct of_dictionary_hashtable_bucket **data;
-	uint32_t size;
-	unsigned long mutations;
-	unsigned long *mutationsPtr;
-	uint32_t pos;
-}
-
-- initWithDictionary: (OFDictionary_hashtable*)dictionary
-		data: (struct of_dictionary_hashtable_bucket**)data
-		size: (uint32_t)size
-    mutationsPointer: (unsigned long*)mutationsPtr;
-@end
-
-@interface OFDictionaryKeyEnumerator_hashtable: OFDictionaryEnumerator_hashtable
-@end
-
-@interface OFDictionaryObjectEnumerator_hashtable:
-    OFDictionaryEnumerator_hashtable
-@end
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-extern struct of_dictionary_hashtable_bucket
-    of_dictionary_hashtable_deleted_bucket;
-#ifdef __cplusplus
-}
-#endif
+	OFMapTable *mapTable;
+}
+@end

Index: src/OFDictionary_hashtable.m
==================================================================
--- src/OFDictionary_hashtable.m
+++ src/OFDictionary_hashtable.m
@@ -14,95 +14,84 @@
  * file.
  */
 
 #include "config.h"
 
-#include <string.h>
-
 #include <assert.h>
 
 #import "OFDictionary_hashtable.h"
 #import "OFMutableDictionary_hashtable.h"
-#import "OFEnumerator.h"
+#import "OFMapTable.h"
 #import "OFArray.h"
 #import "OFString.h"
 #import "OFXMLElement.h"
 
 #import "OFEnumerationMutationException.h"
 #import "OFInvalidArgumentException.h"
 #import "OFInvalidFormatException.h"
 #import "OFNotImplementedException.h"
-#import "OFOutOfRangeException.h"
-
-#import "autorelease.h"
-#import "macros.h"
-
-struct of_dictionary_hashtable_bucket
-    of_dictionary_hashtable_deleted_bucket = {};
-#define DELETED &of_dictionary_hashtable_deleted_bucket
-
-@implementation OFDictionary_hashtable
-- init
-{
-	self = [super init];
-
-	@try {
-		data = [self allocMemoryWithSize: sizeof(*data)];
-		size = 1;
-		data[0] = NULL;
-	} @catch (id e) {
-		[self release];
-		@throw e;
-	}
-
-	return self;
-}
-
-- OF_initWithDictionary: (OFDictionary*)dictionary
-	       copyKeys: (BOOL)copyKeys
-{
-	self = [super init];
-
-	@try {
-		uint32_t i;
-		OFDictionary_hashtable *hashtable;
-
-		if (![dictionary isKindOfClass:
-		    [OFDictionary_hashtable class]] &&
-		    ![dictionary isKindOfClass:
-		    [OFMutableDictionary_hashtable class]])
-			@throw [OFInvalidArgumentException
-			    exceptionWithClass: [self class]
-				      selector: _cmd];
-
-		hashtable = (OFDictionary_hashtable*)dictionary;
-
-		data = [self allocMemoryWithSize: sizeof(*data)
-					   count: hashtable->size];
-
-		for (i = 0; i < hashtable->size; i++)
-			data[i] = NULL;
-
-		size = hashtable->size;
-		count = hashtable->count;
-
-		for (i = 0; i < size; i++) {
-			struct of_dictionary_hashtable_bucket *bucket;
-
-			if (hashtable->data[i] == NULL ||
-			    hashtable->data[i] == DELETED)
-				continue;
-
-			bucket = [self allocMemoryWithSize: sizeof(*bucket)];
-			bucket->key = (copyKeys
-			    ? [hashtable->data[i]->key copy]
-			    : [hashtable->data[i]->key retain]);
-			bucket->object = [hashtable->data[i]->object retain];
-			bucket->hash = hashtable->data[i]->hash;
-
-			data[i] = bucket;
-		}
+
+#import "autorelease.h"
+
+static void*
+copy(void *value)
+{
+	return [(id)value copy];
+}
+
+static void*
+retain(void *value)
+{
+	return [(id)value retain];
+}
+
+static void
+release(void *value)
+{
+	[(id)value release];
+}
+
+static uint32_t
+hash(void *value)
+{
+	return [(id)value hash];
+}
+
+static BOOL
+equal(void *value1, void *value2)
+{
+	return [(id)value1 isEqual: (id)value2];
+}
+
+static of_map_table_functions_t keyFunctions = {
+	.retain = copy,
+	.release = release,
+	.hash = hash,
+	.equal = equal
+};
+static of_map_table_functions_t valueFunctions = {
+	.retain = retain,
+	.release = release,
+	.hash = hash,
+	.equal = equal
+};
+
+@implementation OFDictionary_hashtable
+- init
+{
+	return [self initWithCapacity: 0];
+}
+
+- initWithCapacity: (size_t)capacity
+{
+	self = [super init];
+
+	@try {
+		mapTable = [[OFMapTable alloc]
+		    initWithKeyFunctions: keyFunctions
+			  valueFunctions: valueFunctions
+				capacity: capacity];
 	} @catch (id e) {
 		[self release];
 		@throw e;
 	}
 
@@ -109,87 +98,52 @@
 	return self;
 }
 
 - initWithDictionary: (OFDictionary*)dictionary
 {
+	size_t count;
+
 	if (dictionary == nil)
 		return [self init];
 
 	if ([dictionary class] == [OFDictionary_hashtable class] ||
-	    [dictionary class] == [OFMutableDictionary_hashtable class])
-		return [self OF_initWithDictionary: dictionary
-					  copyKeys: YES];
+	    [dictionary class] == [OFMutableDictionary_hashtable class]) {
+		self = [super init];
 
-	self = [super init];
+		@try {
+			OFDictionary_hashtable *dictionary_ =
+			    (OFDictionary_hashtable*)dictionary;
+
+			mapTable = [dictionary_->mapTable copy];
+		} @catch (id e) {
+			[self release];
+			@throw e;
+		}
+
+		return self;
+	}
 
 	@try {
-		void *pool;
-		OFEnumerator *enumerator;
-		id key;
-		uint32_t i, newSize;
-
-		if (dictionary == nil)
-			@throw [OFInvalidArgumentException
-			    exceptionWithClass: [self class]];
-
 		count = [dictionary count];
-
-		if (count > UINT32_MAX)
-			@throw [OFOutOfRangeException
-			    exceptionWithClass: [self class]];
-
-		for (newSize = 1; newSize < count; newSize <<= 1);
-		if (count * 4 / newSize >= 3)
-			newSize <<= 1;
-
-		if (newSize == 0)
-			@throw [OFOutOfRangeException
-			    exceptionWithClass: [self class]];
-
-		data = [self allocMemoryWithSize: sizeof(*data)
-					   count: newSize];
-
-		for (i = 0; i < newSize; i++)
-			data[i] = NULL;
-
-		size = newSize;
-
-		pool = objc_autoreleasePoolPush();
-
-		enumerator = [dictionary keyEnumerator];
-		while ((key = [enumerator nextObject]) != nil) {
-			uint32_t hash, last;
-			struct of_dictionary_hashtable_bucket *bucket;
-			id object;
-
-			hash = [key hash];
-			last = size;
-
-			for (i = hash & (size - 1); i < last && data[i] != NULL;
-			    i++);
-
-			/* In case the last bucket is already used */
-			if (i >= last) {
-				last = hash & (size - 1);
-
-				for (i = 0; i < last && data[i] != NULL; i++);
-			}
-
-			if (data[i] != NULL)
-				@throw [OFOutOfRangeException
-				    exceptionWithClass: [self class]];
-
-			bucket = [self allocMemoryWithSize: sizeof(*bucket)];
-
-			object = [dictionary objectForKey: key];
-
-			bucket->key = [key copy];
-			bucket->object = [object retain];
-			bucket->hash = hash;
-
-			data[i] = bucket;
-		}
+	} @catch (id e) {
+		[self release];
+		@throw e;
+	}
+
+	self = [self initWithCapacity: count];
+
+	@try {
+		void *pool = objc_autoreleasePoolPush();
+		OFEnumerator *keyEnumerator, *objectEnumerator;
+		id key, object;
+
+		keyEnumerator = [dictionary keyEnumerator];
+		objectEnumerator = [dictionary objectEnumerator];
+		while ((key = [keyEnumerator nextObject]) != nil &&
+		    (object = [objectEnumerator nextObject]) != nil)
+			[mapTable setValue: object
+				    forKey: key];
 
 		objc_autoreleasePoolPop(pool);
 	} @catch (id e) {
 		[self release];
 		@throw e;
@@ -199,167 +153,35 @@
 }
 
 - initWithObject: (id)object
 	  forKey: (id)key
 {
-	self = [super init];
+	self = [self initWithCapacity: 1];
 
 	@try {
-		uint32_t i;
-		struct of_dictionary_hashtable_bucket *bucket;
-
-		if (key == nil || object == nil)
-			@throw [OFInvalidArgumentException
-			    exceptionWithClass: [self class]
-				      selector: _cmd];
-
-		data = [self allocMemoryWithSize: sizeof(*data)
-					   count: 2];
-
-		size = 2;
-		for (i = 0; i < size; i++)
-			data[i] = NULL;
-
-		i = [key hash] & 1;
-
-		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
-		bucket->key = [key copy];
-		bucket->object = [object retain];
-		bucket->hash = [key hash];
-
-		data[i] = bucket;
-		count = 1;
+		[mapTable setValue: object
+			    forKey: key];
 	} @catch (id e) {
 		[self release];
 		@throw e;
 	}
 
 	return self;
 }
 
-- initWithObjects: (OFArray*)objects
-	  forKeys: (OFArray*)keys
-{
-	id ret;
-
-	@try {
-		if ([objects count] != [keys count])
-			@throw [OFInvalidArgumentException
-			    exceptionWithClass: [self class]];
-
-		ret = [self initWithObjects: [objects objects]
-				    forKeys: [keys objects]
-				      count: [objects count]];
-	} @catch (id e) {
-		[self release];
-		@throw e;
-	}
-
-	return ret;
-}
-
 - initWithObjects: (id const*)objects
 	  forKeys: (id const*)keys
-	    count: (size_t)count_
+	    count: (size_t)count
 {
-	self = [super init];
+	self = [self initWithCapacity: count];
 
 	@try {
-		uint32_t i, j, newSize;
-
-		count = count_;
-
-		if (count > UINT32_MAX)
-			@throw [OFOutOfRangeException
-			    exceptionWithClass: [self class]];
-
-		for (newSize = 1; newSize < count; newSize <<= 1);
-		if (count * 4 / newSize >= 3)
-			newSize <<= 1;
-
-		if (newSize == 0)
-			@throw [OFOutOfRangeException
-			    exceptionWithClass: [self class]];
-
-		data = [self allocMemoryWithSize: sizeof(*data)
-					   count: newSize];
-
-		for (j = 0; j < newSize; j++)
-			data[j] = NULL;
-
-		size = newSize;
-
-		for (i = 0; i < count; i++) {
-			uint32_t hash, last;
-
-			if (keys[i] == nil || objects[i] == nil)
-				@throw [OFInvalidArgumentException
-				    exceptionWithClass: [self class]];
-
-			hash = [keys[i] hash];
-			last = size;
-
-			for (j = hash & (size - 1); j < last && data[j] != NULL;
-			    j++)
-				if ([data[j]->key isEqual: keys[i]])
-					break;
-
-			/* In case the last bucket is already used */
-			if (j >= last) {
-				last = hash & (size - 1);
-
-				for (j = 0; j < last && data[j] != NULL; j++)
-					if ([data[j]->key isEqual: keys[i]])
-						break;
-			}
-
-			/* Key not in dictionary */
-			if (j >= last || data[j] == NULL ||
-			    ![data[j]->key isEqual: keys[i]]) {
-				struct of_dictionary_hashtable_bucket *bucket;
-				id key;
-
-				last = size;
-
-				j = hash & (size - 1);
-				for (; j < last && data[j] != NULL; j++);
-
-				/* In case the last bucket is already used */
-				if (j >= last) {
-					last = hash & (size - 1);
-
-					for (j = 0; j < last && data[j] != NULL;
-					    j++);
-				}
-
-				if (j >= last)
-					@throw [OFOutOfRangeException
-					    exceptionWithClass: [self class]];
-
-				bucket =
-				    [self allocMemoryWithSize: sizeof(*bucket)];
-				key = [keys[i] copy];
-
-				bucket->key = key;
-				bucket->object = [objects[i] retain];
-				bucket->hash = hash;
-
-				data[j] = bucket;
-
-				continue;
-			}
-
-			/*
-			 * The key is already in the dictionary. However, we
-			 * just replace it so that the programmer gets the same
-			 * behavior as if he'd call setObject:forKey: for each
-			 * key/object pair.
-			 */
-			[objects[i] retain];
-			[data[j]->object release];
-			data[j]->object = objects[i];
-		}
+		size_t i;
+
+		for (i = 0; i < count; i++)
+			[mapTable setValue: objects[i]
+				    forKey: keys[i]];
 	} @catch (id e) {
 		[self release];
 		@throw e;
 	}
 
@@ -370,14 +192,13 @@
     arguments: (va_list)arguments
 {
 	self = [super init];
 
 	@try {
-		id key, object;
-		uint32_t i, j, hash, newSize;
 		va_list argumentsCopy;
-		struct of_dictionary_hashtable_bucket *bucket;
+		id key, object;
+		size_t i, count;
 
 		va_copy(argumentsCopy, arguments);
 
 		if (firstKey == nil)
 			@throw [OFInvalidArgumentException
@@ -393,110 +214,29 @@
 
 		count = 1;
 		for (; va_arg(argumentsCopy, id) != nil; count++);
 		count >>= 1;
 
-		if (count > UINT32_MAX)
-			@throw [OFOutOfRangeException
-			    exceptionWithClass: [self class]];
-
-		for (newSize = 1; newSize < count; newSize <<= 1);
-		if (count * 4 / newSize >= 3)
-			newSize <<= 1;
-
-		if (newSize == 0)
-			@throw [OFOutOfRangeException
-			    exceptionWithClass: [self class]];
-
-		data = [self allocMemoryWithSize: sizeof(*data)
-					   count: newSize];
-
-		for (j = 0; j < newSize; j++)
-			data[j] = NULL;
-
-		size = newSize;
-
-		/* Add first key / object pair */
-		hash = [key hash];
-		j = hash & (size - 1);
-
-		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
-		bucket->key = [key copy];
-		bucket->object = [object retain];
-		bucket->hash = hash;
-
-		data[j] = bucket;
+		mapTable = [[OFMapTable alloc]
+		    initWithKeyFunctions: keyFunctions
+			  valueFunctions: valueFunctions
+				capacity: count];
+
+		[mapTable setValue: object
+			    forKey: key];
 
 		for (i = 1; i < count; i++) {
-			uint32_t last;
-
 			key = va_arg(arguments, id);
 			object = va_arg(arguments, id);
 
 			if (key == nil || object == nil)
 				@throw [OFInvalidArgumentException
 				    exceptionWithClass: [self class]
 					      selector: _cmd];
 
-			hash = [key hash];
-			last = size;
-
-			for (j = hash & (size - 1); j < last && data[j] != NULL;
-			    j++)
-				if ([data[j]->key isEqual: key])
-					break;
-
-			/* In case the last bucket is already used */
-			if (j >= last) {
-				last = hash & (size - 1);
-
-				for (j = 0; j < last && data[j] != NULL; j++)
-					if ([data[j]->key isEqual: key])
-						break;
-			}
-
-			/* Key not in dictionary */
-			if (j >= last || data[j] == NULL ||
-			    ![data[j]->key isEqual: key]) {
-				last = size;
-
-				j = hash & (size - 1);
-				for (; j < last && data[j] != NULL; j++);
-
-				/* In case the last bucket is already used */
-				if (j >= last) {
-					last = hash & (size - 1);
-
-					for (j = 0; j < last && data[j] != NULL;
-					    j++);
-				}
-
-				if (j >= last)
-					@throw [OFOutOfRangeException
-					    exceptionWithClass: [self class]];
-
-				bucket =
-				    [self allocMemoryWithSize: sizeof(*bucket)];
-				bucket->key = [key copy];
-				bucket->object = [object retain];
-				bucket->hash = hash;
-
-				data[j] = bucket;
-
-				continue;
-			}
-
-			/*
-			 * The key is already in the dictionary. However, we
-			 * just replace it so that the programmer gets the same
-			 * behavior as if he'd call setObject:forKey: for each
-			 * key/object pair.
-			 */
-			[object retain];
-			[data[j]->object release];
-			data[j]->object = object;
-			count--;
+			[mapTable setValue: object
+				    forKey: key];
 		}
 	} @catch (id e) {
 		[self release];
 		@throw e;
 	}
@@ -504,34 +244,31 @@
 	return self;
 }
 
 - initWithSerialization: (OFXMLElement*)element
 {
+	self = [super init];
+
 	@try {
 		void *pool = objc_autoreleasePoolPush();
-		OFMutableDictionary *dictionary;
 		OFArray *keys, *objects;
 		OFEnumerator *keyEnumerator, *objectEnumerator;
 		OFXMLElement *keyElement, *objectElement;
 
-		if ((![[element name] isEqual: @"OFDictionary"] &&
-		    ![[element name] isEqual: @"OFMutableDictionary"]) ||
-		    ![[element namespace] isEqual: OF_SERIALIZATION_NS])
-			@throw [OFInvalidArgumentException
-			    exceptionWithClass: [self class]
-				      selector: _cmd];
-
-		dictionary = [OFMutableDictionary dictionary];
-
 		keys = [element elementsForName: @"key"
 				      namespace: OF_SERIALIZATION_NS];
 		objects = [element elementsForName: @"object"
 					 namespace: OF_SERIALIZATION_NS];
 
 		if ([keys count] != [objects count])
 			@throw [OFInvalidFormatException
 			    exceptionWithClass: [self class]];
+
+		mapTable = [[OFMapTable alloc]
+		    initWithKeyFunctions: keyFunctions
+			  valueFunctions: valueFunctions
+				capacity: [keys count]];
 
 		keyEnumerator = [keys objectEnumerator];
 		objectEnumerator = [objects objectEnumerator];
 		while ((keyElement = [keyEnumerator nextObject]) != nil &&
 		    (objectElement = [objectEnumerator nextObject]) != nil) {
@@ -545,18 +282,16 @@
 
 			if (key == nil || object == nil)
 				@throw [OFInvalidFormatException
 				    exceptionWithClass: [self class]];
 
-			[dictionary setObject: [object objectByDeserializing]
-				       forKey: [key objectByDeserializing]];
+			[mapTable setValue: [object objectByDeserializing]
+				    forKey: [key objectByDeserializing]];
 
 			objc_autoreleasePoolPop(pool2);
 		}
 
-		self = [self initWithDictionary: dictionary];
-
 		objc_autoreleasePoolPop(pool);
 	} @catch (id e) {
 		[self release];
 		@throw e;
 	}
@@ -564,114 +299,67 @@
 	return self;
 }
 
 - (id)objectForKey: (id)key
 {
-	uint32_t i, hash, last;
-
-	if (key == nil)
-		@throw [OFInvalidArgumentException
-		    exceptionWithClass: [self class]
-			      selector: _cmd];
-
-	hash = [key hash];
-	last = size;
-
-	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
-		if (data[i] == DELETED)
-			continue;
-
-		if ([data[i]->key isEqual: key])
-			return data[i]->object;
-	}
-
-	if (i < last)
-		return nil;
-
-	/* In case the last bucket is already used */
-	last = hash & (size - 1);
-
-	for (i = 0; i < last && data[i] != NULL; i++) {
-		if (data[i] == DELETED)
-			continue;
-
-		if ([data[i]->key isEqual: key])
-			return data[i]->object;
-	}
-
-	return nil;
+	return [mapTable valueForKey: key];
 }
 
 - (size_t)count
 {
-	return count;
+	return [mapTable count];
 }
 
 - (BOOL)isEqual: (id)dictionary
 {
-	uint32_t i;
+	OFDictionary_hashtable *dictionary_;
 
 	if ([self class] != [OFDictionary_hashtable class] &&
 	    [self class] != [OFMutableDictionary_hashtable class])
 		return [super isEqual: dictionary];
 
-	if ([dictionary count] != count)
-		return NO;
-
-	for (i = 0; i < size; i++)
-		if (data[i] != NULL && data[i] != DELETED &&
-		    ![[dictionary objectForKey: data[i]->key]
-		    isEqual: data[i]->object])
-			return NO;
-
-	return YES;
+	dictionary_ = (OFDictionary_hashtable*)dictionary;
+
+	return [dictionary_->mapTable isEqual: mapTable];
 }
 
 - (BOOL)containsObject: (id)object
 {
-	uint32_t i;
-
-	if (object == nil || count == 0)
-		return NO;
-
-	for (i = 0; i < size; i++)
-		if (data[i] != NULL && data[i] != DELETED &&
-		    [data[i]->object isEqual: object])
-			return YES;
-
-	return NO;
+	return [mapTable containsValue: object];
 }
 
 - (BOOL)containsObjectIdenticalTo: (id)object
 {
-	uint32_t i;
-
-	if (object == nil || count == 0)
-		return NO;
-
-	for (i = 0; i < size; i++)
-		if (data[i] != NULL && data[i] != DELETED &&
-		    data[i]->object == object)
-			return YES;
-
-	return NO;
+	return [mapTable containsValueIdenticalTo: object];
 }
 
 - (OFArray*)allKeys
 {
 	OFArray *ret;
-	id *keys = [self allocMemoryWithSize: sizeof(*keys)
-				       count: count];
-	size_t i, j;
-
-	for (i = j = 0; i < size; i++)
-		if (data[i] != NULL && data[i] != DELETED)
-			keys[j++] = data[i]->key;
-
-	assert(j == count);
+	id *keys;
+	size_t count;
+
+	count = [mapTable count];
+	keys = [self allocMemoryWithSize: sizeof(*keys)
+				   count: count];
 
 	@try {
+		void *pool = objc_autoreleasePoolPush();
+		OFMapTableEnumerator *enumerator;
+		id key;
+		size_t i;
+
+		i = 0;
+		enumerator = [mapTable keyEnumerator];
+		while ((key = [enumerator nextValue]) != nil) {
+			assert(i < count);
+
+			keys[i++] = key;
+		}
+
+		objc_autoreleasePoolPop(pool);
+
 		ret = [OFArray arrayWithObjects: keys
 					  count: count];
 	} @finally {
 		[self freeMemory: keys];
 	}
@@ -680,21 +368,33 @@
 }
 
 - (OFArray*)allObjects
 {
 	OFArray *ret;
-	id *objects = [self allocMemoryWithSize: sizeof(*objects)
-					  count: count];
-	size_t i, j;
-
-	for (i = j = 0; i < size; i++)
-		if (data[i] != NULL && data[i] != DELETED)
-			objects[j++] = data[i]->object;
-
-	assert(j == count);
+	id *objects;
+	size_t count;
+
+	count = [mapTable count];
+	objects = [self allocMemoryWithSize: sizeof(*objects)
+				      count: count];
 
 	@try {
+		void *pool = objc_autoreleasePoolPush();
+		OFMapTableEnumerator *enumerator;
+		id object;
+		size_t i;
+
+		i = 0;
+		enumerator = [mapTable valueEnumerator];
+		while ((object = [enumerator nextValue]) != nil) {
+			assert(i < count);
+
+			objects[i++] = object;
+		}
+
+		objc_autoreleasePoolPop(pool);
+
 		ret = [OFArray arrayWithObjects: objects
 					  count: count];
 	} @finally {
 		[self freeMemory: objects];
 	}
@@ -702,156 +402,55 @@
 	return ret;
 }
 
 - (OFEnumerator*)keyEnumerator
 {
-	return [[[OFDictionaryKeyEnumerator_hashtable alloc]
-	    initWithDictionary: self
-			  data: data
-			  size: size
-	      mutationsPointer: NULL] autorelease];
+	return [[[OFMapTableEnumeratorWrapper alloc]
+	    initWithEnumerator: [mapTable keyEnumerator]
+			object: self] autorelease];
 }
 
 - (OFEnumerator*)objectEnumerator
 {
-	return [[[OFDictionaryObjectEnumerator_hashtable alloc]
-	    initWithDictionary: self
-			  data: data
-			  size: size
-	      mutationsPointer: NULL] autorelease];
+	return [[[OFMapTableEnumeratorWrapper alloc]
+	    initWithEnumerator: [mapTable valueEnumerator]
+			object: self] autorelease];
 }
 
 - (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
 			   objects: (id*)objects
 			     count: (int)count_
 {
-	int i;
-
-	for (i = 0; i < count_; i++) {
-		for (; state->state < size && (data[state->state] == NULL ||
-		    data[state->state] == DELETED); state->state++);
-
-		if (state->state < size) {
-			objects[i] = data[state->state]->key;
-			state->state++;
-		} else
-			break;
-	}
-
-	state->itemsPtr = objects;
-	state->mutationsPtr = (unsigned long*)self;
-
-	return i;
+	return [mapTable countByEnumeratingWithState: state
+					     objects: objects
+					       count: count_];
 }
 
 #ifdef OF_HAVE_BLOCKS
 - (void)enumerateKeysAndObjectsUsingBlock:
     (of_dictionary_enumeration_block_t)block
 {
-	size_t i;
-	BOOL stop = NO;
-
-	for (i = 0; i < size && !stop; i++)
-		if (data[i] != NULL && data[i] != DELETED)
-			block(data[i]->key, data[i]->object, &stop);
+	@try {
+		[mapTable enumerateKeysAndValuesUsingBlock:
+		    ^ (void *key, void *value, BOOL *stop) {
+			block(key, value, stop);
+		}];
+	} @catch (OFEnumerationMutationException *e) {
+		@throw [OFEnumerationMutationException
+		    exceptionWithClass: [self class]
+				object: self];
+	}
 }
 #endif
 
 - (void)dealloc
 {
-	uint32_t i;
-
-	for (i = 0; i < size; i++) {
-		if (data[i] != NULL && data[i] != DELETED) {
-			[data[i]->key release];
-			[data[i]->object release];
-		}
-	}
+	[mapTable dealloc];
 
 	[super dealloc];
 }
 
 - (uint32_t)hash
 {
-	uint32_t i, hash = 0;
-
-	for (i = 0; i < size; i++) {
-		if (data[i] != NULL && data[i] != DELETED) {
-			hash += data[i]->hash;
-			hash += [data[i]->object hash];
-		}
-	}
-
-	return hash;
-}
-@end
-
-@implementation OFDictionaryEnumerator_hashtable
-- initWithDictionary: (OFDictionary_hashtable*)dictionary_
-		data: (struct of_dictionary_hashtable_bucket**)data_
-		size: (uint32_t)size_
-    mutationsPointer: (unsigned long*)mutationsPtr_
-{
-	self = [super init];
-
-	dictionary = [dictionary_ retain];
-	data = data_;
-	size = size_;
-	mutations = (mutationsPtr_ != NULL ? *mutationsPtr_ : 0);
-	mutationsPtr = mutationsPtr_;
-
-	return self;
-}
-
-- (void)dealloc
-{
-	[dictionary release];
-
-	[super dealloc];
-}
-
-- (void)reset
-{
-	if (mutationsPtr != NULL && *mutationsPtr != mutations)
-		@throw [OFEnumerationMutationException
-		    exceptionWithClass: [dictionary class]
-				object: dictionary];
-
-	pos = 0;
-}
-@end
-
-@implementation OFDictionaryObjectEnumerator_hashtable
-- (id)nextObject
-{
-	if (mutationsPtr != NULL && *mutationsPtr != mutations)
-		@throw [OFEnumerationMutationException
-		    exceptionWithClass: [dictionary class]
-				object: dictionary];
-
-	for (; pos < size && (data[pos] == NULL ||
-	    data[pos] == DELETED); pos++);
-
-	if (pos < size)
-		return data[pos++]->object;
-	else
-		return nil;
-}
-@end
-
-@implementation OFDictionaryKeyEnumerator_hashtable
-- (id)nextObject
-{
-	if (mutationsPtr != NULL && *mutationsPtr != mutations)
-		@throw [OFEnumerationMutationException
-		    exceptionWithClass: [dictionary class]
-				object: dictionary];
-
-	for (; pos < size && (data[pos] == NULL ||
-	    data[pos] == DELETED); pos++);
-
-	if (pos < size)
-		return data[pos++]->key;
-	else
-		return nil;
+	return [mapTable hash];
 }
 @end

Index: src/OFMutableArray_adjacent.m
==================================================================
--- src/OFMutableArray_adjacent.m
+++ src/OFMutableArray_adjacent.m
@@ -311,14 +311,14 @@
 - (void)enumerateObjectsUsingBlock: (of_array_enumeration_block_t)block
 {
 	id *objects = [array cArray];
 	size_t i, count = [array count];
 	BOOL stop = NO;
-	unsigned long mutations2 = mutations;
+	unsigned long mutations_ = mutations;
 
 	for (i = 0; i < count && !stop; i++) {
-		if (mutations != mutations2)
+		if (mutations != mutations_)
 			@throw [OFEnumerationMutationException
 			    exceptionWithClass: [self class]
 					object: self];
 
 		block(objects[i], i, &stop);
@@ -328,16 +328,16 @@
 - (void)replaceObjectsUsingBlock: (of_array_replace_block_t)block
 {
 	id *objects = [array cArray];
 	size_t i, count = [array count];
 	BOOL stop = NO;
-	unsigned long mutations2 = mutations;
+	unsigned long mutations_ = mutations;
 
 	for (i = 0; i < count && !stop; i++) {
 		id newObject;
 
-		if (mutations != mutations2)
+		if (mutations != mutations_)
 			@throw [OFEnumerationMutationException
 			    exceptionWithClass: [self class]
 					object: self];
 
 		newObject = block(objects[i], i, &stop);

Index: src/OFMutableDictionary_hashtable.h
==================================================================
--- src/OFMutableDictionary_hashtable.h
+++ src/OFMutableDictionary_hashtable.h
@@ -13,21 +13,13 @@
  * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
  * file.
  */
 
 #import "OFDictionary.h"
+
+@class OFMapTable;
 
 @interface OFMutableDictionary_hashtable: OFMutableDictionary
 {
-	struct of_dictionary_hashtable_bucket **data;
-	uint32_t size;
-	size_t count;
-	unsigned long mutations;
-}
-
-#if defined(OF_SET_HASHTABLE_M) || defined(OF_MUTABLE_SET_HASHTABLE_M) || \
-    defined(OF_COUNTED_SET_HASHTABLE_M)
-- (void)OF_setObject: (id)object
-	      forKey: (id)key
-	     copyKey: (BOOL)copyKey;
-#endif
+	OFMapTable *mapTable;
+}
 @end

Index: src/OFMutableDictionary_hashtable.m
==================================================================
--- src/OFMutableDictionary_hashtable.m
+++ src/OFMutableDictionary_hashtable.m
@@ -18,319 +18,53 @@
 
 #include <string.h>
 
 #import "OFMutableDictionary_hashtable.h"
 #import "OFDictionary_hashtable.h"
+#import "OFMapTable.h"
 
 #import "OFEnumerationMutationException.h"
 #import "OFInvalidArgumentException.h"
 #import "OFOutOfRangeException.h"
 
 #import "macros.h"
 
-#define DELETED &of_dictionary_hashtable_deleted_bucket
-
-static Class dictionary = Nil;
-
 @implementation OFMutableDictionary_hashtable
 + (void)initialize
 {
-	if (self == [OFMutableDictionary_hashtable class]) {
-		dictionary = [OFDictionary_hashtable class];
-		[self inheritMethodsFromClass: dictionary];
-	}
-}
-
-- (void)OF_resizeForCount: (size_t)newCount
-{
-	size_t fullness = newCount * 4 / size;
-	struct of_dictionary_hashtable_bucket **newData;
-	uint32_t i, newSize;
-
-	if (newCount > UINT32_MAX)
-		@throw [OFOutOfRangeException exceptionWithClass: [self class]];
-
-	if (fullness >= 3)
-		newSize = size << 1;
-	else if (fullness <= 1)
-		newSize = size >> 1;
-	else
-		return;
-
-	if (newSize == 0)
-		@throw [OFOutOfRangeException exceptionWithClass: [self class]];
-
-	newData = [self allocMemoryWithSize: sizeof(*newData)
-				      count: newSize];
-
-	for (i = 0; i < newSize; i++)
-		newData[i] = NULL;
-
-	for (i = 0; i < size; i++) {
-		if (data[i] != NULL && data[i] != DELETED) {
-			uint32_t j, last;
-
-			last = newSize;
-
-			j = data[i]->hash & (newSize - 1);
-			for (; j < last && newData[j] != NULL; j++);
-
-			/* In case the last bucket is already used */
-			if (j >= last) {
-				last = data[i]->hash & (newSize - 1);
-
-				for (j = 0; j < last &&
-				    newData[j] != NULL; j++);
-			}
-
-			if (j >= last) {
-				[self freeMemory: newData];
-				@throw [OFOutOfRangeException
-				    exceptionWithClass: [self class]];
-			}
-
-			newData[j] = data[i];
-		}
-	}
-
-	[self freeMemory: data];
-	data = newData;
-	size = newSize;
-}
-
-- (void)OF_setObject: (id)object
-	      forKey: (id)key
-	     copyKey: (BOOL)copyKey
-{
-	uint32_t i, hash, last;
-	id old;
-
-	if (key == nil || object == nil)
-		@throw [OFInvalidArgumentException
-		    exceptionWithClass: [self class]
-			      selector: _cmd];
-
-	hash = [key hash];
-	last = size;
-
-	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
-		if (data[i] == DELETED)
-			continue;
-
-		if ([data[i]->key isEqual: key])
-			break;
-	}
-
-	/* In case the last bucket is already used */
-	if (i >= last) {
-		last = hash & (size - 1);
-
-		for (i = 0; i < last && data[i] != NULL; i++) {
-			if (data[i] == DELETED)
-				continue;
-
-			if ([data[i]->key isEqual: key])
-				break;
-		}
-	}
-
-	/* Key not in dictionary */
-	if (i >= last || data[i] == NULL || data[i] == DELETED ||
-	    ![data[i]->key isEqual: key]) {
-		struct of_dictionary_hashtable_bucket *bucket;
-
-		[self OF_resizeForCount: count + 1];
-
-		mutations++;
-		last = size;
-
-		for (i = hash & (size - 1); i < last && data[i] != NULL &&
-		    data[i] != DELETED; i++);
-
-		/* In case the last bucket is already used */
-		if (i >= last) {
-			last = hash & (size - 1);
-
-			for (i = 0; i < last && data[i] != NULL &&
-			    data[i] != DELETED; i++);
-		}
-
-		if (i >= last)
-			@throw [OFOutOfRangeException
-			    exceptionWithClass: [self class]];
-
-		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
-
-		if (copyKey) {
-			@try {
-				bucket->key = [key copy];
-			} @catch (id e) {
-				[self freeMemory: bucket];
-				@throw e;
-			}
-		} else
-			bucket->key = [key retain];
-
-		bucket->object = [object retain];
-		bucket->hash = hash;
-
-		data[i] = bucket;
-		count++;
-
-		return;
-	}
-
-	old = data[i]->object;
-	data[i]->object = [object retain];
-	[old release];
+	if (self == [OFMutableDictionary_hashtable class])
+		[self inheritMethodsFromClass: [OFDictionary_hashtable class]];
 }
 
 - (void)setObject: (id)object
 	   forKey: (id)key
 {
-	[self OF_setObject: object
-		    forKey: key
-		   copyKey: YES];
+	[mapTable setValue: object
+		    forKey: key];
 }
 
 - (void)removeObjectForKey: (id)key
 {
-	uint32_t i, hash, last;
-
-	if (key == nil)
-		@throw [OFInvalidArgumentException
-		    exceptionWithClass: [self class]
-			      selector: _cmd];
-
-	hash = [key hash];
-	last = size;
-
-	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
-		if (data[i] == DELETED)
-			continue;
-
-		if ([data[i]->key isEqual: key]) {
-			[data[i]->key release];
-			[data[i]->object release];
-			[self freeMemory: data[i]];
-			data[i] = DELETED;
-
-			count--;
-			mutations++;
-			[self OF_resizeForCount: count];
-
-			return;
-		}
-	}
-
-	if (i < last)
-		return;
-
-	/* In case the last bucket is already used */
-	last = hash & (size - 1);
-
-	for (i = 0; i < last && data[i] != NULL; i++) {
-		if (data[i] == DELETED)
-			continue;
-
-		if ([data[i]->key isEqual: key]) {
-			[data[i]->key release];
-			[data[i]->object release];
-			[self freeMemory: data[i]];
-			data[i] = DELETED;
-
-			count--;
-			mutations++;
-			[self OF_resizeForCount: count];
-
-			return;
-		}
-	}
-}
-
-- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
-			   objects: (id*)objects
-			     count: (int)count_
-{
-	const SEL selector =
-	    @selector(countByEnumeratingWithState:objects:count:);
-	int (*imp)(id, SEL, of_fast_enumeration_state_t*, id*, int) =
-	    (int(*)(id, SEL, of_fast_enumeration_state_t*, id*, int))
-	    [dictionary instanceMethodForSelector: selector];
-
-	int ret = imp(self, selector, state, objects, count_);
-
-	state->mutationsPtr = &mutations;
-
-	return ret;
-}
-
-- (OFEnumerator*)objectEnumerator
-{
-	return [[[OFDictionaryObjectEnumerator_hashtable alloc]
-	    initWithDictionary: (OFDictionary_hashtable*)self
-			  data: data
-			  size: size
-	      mutationsPointer: &mutations] autorelease];
-}
-
-- (OFEnumerator*)keyEnumerator
-{
-	return [[[OFDictionaryKeyEnumerator_hashtable alloc]
-	    initWithDictionary: (OFDictionary_hashtable*)self
-			  data: data
-			  size: size
-	      mutationsPointer: &mutations] autorelease];
+	[mapTable removeValueForKey: key];
 }
 
 #ifdef OF_HAVE_BLOCKS
-- (void)enumerateKeysAndObjectsUsingBlock:
-    (of_dictionary_enumeration_block_t)block
-{
-	size_t i;
-	BOOL stop = NO;
-	unsigned long mutations2 = mutations;
-
-	for (i = 0; i < size && !stop; i++) {
-		if (mutations != mutations2)
-			@throw [OFEnumerationMutationException
-			    exceptionWithClass: [self class]
-					object: self];
-
-		if (data[i] != NULL && data[i] != DELETED)
-			block(data[i]->key, data[i]->object, &stop);
-	}
-}
-
 - (void)replaceObjectsUsingBlock: (of_dictionary_replace_block_t)block
 {
-	size_t i;
-	BOOL stop = NO;
-	unsigned long mutations2 = mutations;
-
-	for (i = 0; i < size && !stop; i++) {
-		if (mutations != mutations2)
-			@throw [OFEnumerationMutationException
-			    exceptionWithClass: [self class]
-					object: self];
-
-		if (data[i] != NULL && data[i] != DELETED) {
-			id new = block(data[i]->key, data[i]->object, &stop);
-
-			if (new == nil)
-				@throw [OFInvalidArgumentException
-				    exceptionWithClass: [self class]
-					      selector: _cmd];
-
-			[new retain];
-			[data[i]->object release];
-			data[i]->object = new;
-		}
+	@try {
+		[mapTable replaceValuesUsingBlock:
+		    ^ void* (void *key, void *value, BOOL *stop) {
+			return block(key, value, stop);
+		}];
+	} @catch (OFEnumerationMutationException *e) {
+		@throw [OFEnumerationMutationException
+		    exceptionWithClass: [self class]
+				object: self];
 	}
 }
 #endif
 
 - (void)makeImmutable
 {
 	object_setClass(self, [OFDictionary_hashtable class]);
 }
 @end

Index: tests/OFDictionaryTests.m
==================================================================
--- tests/OFDictionaryTests.m
+++ tests/OFDictionaryTests.m
@@ -97,11 +97,11 @@
 #ifdef OF_HAVE_FAST_ENUMERATION
 	size_t i = 0;
 	BOOL ok = YES;
 
 	for (OFString *key in dict) {
-		if (i > 1 || ![key isEqual: keys[1 - i]]) {
+		if (i > 1 || ![key isEqual: keys[i]]) {
 			ok = NO;
 			break;
 		}
 
 		[dict setObject: [dict objectForKey: key]
@@ -130,11 +130,11 @@
 		__block size_t i = 0;
 		__block BOOL ok = YES;
 
 		[dict enumerateKeysAndObjectsUsingBlock:
 		    ^ (id key, id obj, BOOL *stop) {
-			if (i > 1 || ![key isEqual: keys[1 - i]]) {
+			if (i > 1 || ![key isEqual: keys[i]]) {
 				ok = NO;
 				*stop = YES;
 				return;
 			}
 
@@ -180,11 +180,11 @@
 			return @"val1";
 		if ([key isEqual: keys[1]])
 			return @"val2";
 
 		return nil;
-	    }] description] isEqual: @"{\n\tkey2 = val2;\n\tkey1 = val1;\n}"])
+	    }] description] isEqual: @"{\n\tkey1 = val1;\n\tkey2 = val2;\n}"])
 
 	TEST(@"-[filteredDictionaryUsingBlock:]",
 	    [[[dict filteredDictionaryUsingBlock: ^ BOOL (id key, id obj) {
 		return ([key isEqual: keys[0]] ?  YES : NO);
 	    }] description] isEqual: @"{\n\tkey1 = value_1;\n}"])

Index: tests/OFJSONTests.m
==================================================================
--- tests/OFJSONTests.m
+++ tests/OFJSONTests.m
@@ -47,11 +47,11 @@
 	    nil];
 
 	TEST(@"-[JSONValue #1]", [[s JSONValue] isEqual: d])
 
 	TEST(@"-[JSONRepresentation]", [[d JSONRepresentation] isEqual:
-	    @"{\"foo\":\"ba\\r\",\"x\":[0.5,15,null,\"foo\",false]}"])
+	    @"{\"x\":[0.5,15,null,\"foo\",false],\"foo\":\"ba\\r\"}"])
 
 	EXPECT_EXCEPTION(@"-[JSONValue #2]", OFInvalidJSONException,
 	    [@"{" JSONValue])
 	EXPECT_EXCEPTION(@"-[JSONValue #3]", OFInvalidJSONException,
 	    [@"]" JSONValue])