Index: src/OFDictionary.h
==================================================================
--- src/OFDictionary.h
+++ src/OFDictionary.h
@@ -180,5 +180,7 @@
 @interface OFDictionaryKeyEnumerator: OFDictionaryEnumerator
 @end
 /// \endcond
 
 #import "OFMutableDictionary.h"
+
+extern const int of_dictionary_deleted_bucket;

Index: src/OFDictionary.m
==================================================================
--- src/OFDictionary.m
+++ src/OFDictionary.m
@@ -17,12 +17,15 @@
 #import "OFEnumerator.h"
 #import "OFArray.h"
 #import "OFAutoreleasePool.h"
 #import "OFExceptions.h"
 #import "macros.h"
+
+const int of_dictionary_deleted_bucket;
 
 #define BUCKET_SIZE sizeof(struct of_dictionary_bucket)
+#define DELETED (id)&of_dictionary_deleted_bucket
 
 @implementation OFDictionary
 + dictionary;
 {
 	return [[[self alloc] init] autorelease];
@@ -113,11 +116,11 @@
 	count = dict->count;
 
 	for (i = 0; i < size; i++) {
 		OFObject <OFCopying> *key;
 
-		if (dict->data[i].key == nil) {
+		if (dict->data[i].key == nil || dict->data[i].key == DELETED) {
 			data[i].key = nil;
 			continue;
 		}
 
 		@try {
@@ -200,34 +203,44 @@
 		@throw e;
 	}
 	memset(data, 0, size * BUCKET_SIZE);
 
 	for (i = 0; i < count; i++) {
-		uint32_t j, hash;
-
-		hash = [keys_carray[i] hash];
-
-		for (j = hash & (size - 1); j < size && data[j].key != nil &&
-		    ![data[j].key isEqual: keys_carray[i]]; j++);
-
-		/* In case the last bucket is already used */
-		if (j >= size)
-			for (j = 0; j < size && data[j].key != nil &&
-			    ![data[j].key isEqual: keys_carray[i]]; j++);
-
-		/* Key not in dictionary */
-		if (j >= size || ![data[j].key isEqual: keys_carray[i]]) {
-			OFObject <OFCopying> *key;
-
-			j = hash & (size - 1);
-			for (; j < size && data[j].key != nil; j++);
-
-			/* In case the last bucket is already used */
-			if (j >= size)
-				for (j = 0; j < size && data[j].key != nil;
-				    j++);
-			if (j >= size) {
+		uint32_t j, hash, last;
+
+		hash = [keys_carray[i] hash];
+		last = size;
+
+		for (j = hash & (size - 1); j < last && data[j].key != nil &&
+		    ![data[j].key isEqual: keys_carray[i]]; j++);
+
+		/* In case the last bucket is already used */
+		if (j >= last) {
+			last = hash & (size - 1);
+
+			for (j = 0; j < last && data[j].key != nil &&
+			    ![data[j].key isEqual: keys_carray[i]]; j++);
+		}
+
+		/* Key not in dictionary */
+		if (j >= last || ![data[j].key isEqual: keys_carray[i]]) {
+			OFObject <OFCopying> *key;
+
+			last = size;
+
+			j = hash & (size - 1);
+			for (; j < last && data[j].key != nil; j++);
+
+			/* In case the last bucket is already used */
+			if (j >= last) {
+				last = hash & (size - 1);
+
+				for (j = 0; j < last && data[j].key != nil;
+				    j++);
+			}
+
+			if (j >= last) {
 				Class c = isa;
 				[self dealloc];
 				@throw [OFOutOfRangeException newWithClass: c];
 			}
 
@@ -328,21 +341,21 @@
 	}
 	memset(data, 0, size * BUCKET_SIZE);
 
 	if (key == nil)
 		return self;
-	else if ((obj = va_arg(args, OFObject*)) == nil) {
+
+	if ((obj = va_arg(args, OFObject*)) == nil) {
 		Class c = isa;
 		[self dealloc];
 		@throw [OFInvalidArgumentException newWithClass: c
 						       selector: _cmd];
 	}
 
 	/* Add first key / object pair */
 	hash = [key hash];
-
-	for (j = hash & (size - 1); j < size && data[j].key != nil; j++);
+	j = hash & (size - 1);
 
 	@try {
 		key = [key copy];
 	} @catch (OFException *e) {
 		[self dealloc];
@@ -360,10 +373,12 @@
 	data[j].key = key;
 	data[j].object = obj;
 	data[j].hash = hash;
 
 	for (i = 1; i < count; i++) {
+		size_t last;
+
 		key = va_arg(args, OFObject <OFCopying>*);
 		obj = va_arg(args, OFObject*);
 
 		if (key == nil || obj == nil) {
 			Class c = isa;
@@ -371,29 +386,39 @@
 			@throw [OFInvalidArgumentException newWithClass: c
 							       selector: _cmd];
 		}
 
 		hash = [key hash];
+		last = size;
 
-		for (j = hash & (size - 1); j < size && data[j].key != nil &&
+		for (j = hash & (size - 1); j < last && data[j].key != nil &&
 		    ![data[j].key isEqual: key]; j++);
 
 		/* In case the last bucket is already used */
-		if (j >= size)
-			for (j = 0; j < size && data[j].key != nil &&
+		if (j >= last) {
+			last = hash & (size - 1);
+
+			for (j = 0; j < last && data[j].key != nil &&
 			    ![data[j].key isEqual: key]; j++);
+		}
 
 		/* Key not in dictionary */
-		if (j >= size || ![data[j].key isEqual: key]) {
+		if (j >= last || ![data[j].key isEqual: key]) {
+			last = size;
+
 			j = hash & (size - 1);
-			for (; j < size && data[j].key != nil; j++);
+			for (; j < last && data[j].key != nil; j++);
 
 			/* In case the last bucket is already used */
-			if (j >= size)
-				for (j = 0; j < size && data[j].key != nil;
+			if (j >= last) {
+				last = hash & (size - 1);
+
+				for (j = 0; j < last && data[j].key != nil;
 				    j++);
-			if (j >= size) {
+			}
+
+			if (j >= last) {
 				Class c = isa;
 				[self dealloc];
 				@throw [OFOutOfRangeException newWithClass: c];
 			}
 
@@ -445,31 +470,37 @@
 	return self;
 }
 
 - (id)objectForKey: (OFObject <OFCopying>*)key
 {
-	uint32_t i, hash;
+	uint32_t i, hash, last;
 
 	if (key == nil)
 		@throw [OFInvalidArgumentException newWithClass: isa
 						       selector: _cmd];
 
 	hash = [key hash];
+	last = size;
 
-	for (i = hash & (size - 1); i < size && data[i].key != nil &&
-	    ![data[i].key isEqual: key]; i++);
+	for (i = hash & (size - 1); i < last && data[i].key != nil &&
+	    (data[i].key == DELETED || ![data[i].key isEqual: key]); i++);
 
-	if (i < size && data[i].key == nil)
+	if (i < last && (data[i].key == nil || data[i].key == DELETED))
 		return nil;
 
 	/* In case the last bucket is already used */
-	if (i >= size)
-		for (i = 0; i < size && data[i].key != nil &&
-		    ![data[i].key isEqual: key]; i++);
+	if (i >= last) {
+		last = hash & (size - 1);
+
+		for (i = 0; i < last && data[i].key != nil &&
+		    (data[i].key == DELETED || ![data[i].key isEqual: key]);
+		    i++);
+	}
 
 	/* Key not in dictionary */
-	if (i >= size || ![data[i].key isEqual: key])
+	if (i >= last || data[i].key == nil || data[i].key == DELETED ||
+	    ![data[i].key isEqual: key])
 		return nil;
 
 	return [[data[i].object retain] autorelease];
 }
 
@@ -494,11 +525,11 @@
 
 	if ([dict count] != count)
 		return NO;
 
 	for (i = 0; i < size; i++)
-		if (data[i].key != nil &&
+		if (data[i].key != nil && data[i].key != DELETED &&
 		    ![[dict objectForKey: data[i].key] isEqual: data[i].object])
 			return NO;
 
 	return YES;
 }
@@ -508,12 +539,12 @@
 			     count: (int)count_
 {
 	size_t i;
 
 	for (i = 0; i < count_; i++) {
-		for (; state->state < size && data[state->state].key == nil;
-		    state->state++);
+		for (; state->state < size && (data[state->state].key == nil ||
+		    data[state->state].key == DELETED); state->state++);
 
 		if (state->state < size) {
 			objects[i] = data[state->state].key;
 			state->state++;
 		} else
@@ -545,11 +576,11 @@
 - (void)dealloc
 {
 	size_t i;
 
 	for (i = 0; i < size; i++) {
-		if (data[i].key != nil) {
+		if (data[i].key != nil && data[i].key != DELETED) {
 			[data[i].key release];
 			[data[i].object release];
 		}
 	}
 
@@ -562,11 +593,11 @@
 	uint32_t hash;
 
 	OF_HASH_INIT(hash);
 
 	for (i = 0; i < size; i++) {
-		if (data[i].key != nil) {
+		if (data[i].key != nil && data[i].key != DELETED) {
 			uint32_t kh = [data[i].key hash];
 
 			OF_HASH_ADD(hash, kh >> 24);
 			OF_HASH_ADD(hash, (kh >> 16) & 0xFF);
 			OF_HASH_ADD(hash, (kh >> 8) & 0xFF);
@@ -616,11 +647,12 @@
 - (id)nextObject
 {
 	if (mutations_ptr != NULL && *mutations_ptr != mutations)
 		@throw [OFEnumerationMutationException newWithClass: isa];
 
-	for (; pos < size && data[pos].key == nil; pos++);
+	for (; pos < size && (data[pos].key == nil ||
+	    data[pos].key == DELETED); pos++);
 
 	if (pos < size)
 		return data[pos++].object;
 	else
 		return nil;
@@ -631,14 +663,15 @@
 - (id)nextObject
 {
 	if (mutations_ptr != NULL && *mutations_ptr != mutations)
 		@throw [OFEnumerationMutationException newWithClass: isa];
 
-	for (; pos < size && data[pos].key == nil; pos++);
+	for (; pos < size && (data[pos].key == nil ||
+	    data[pos].key == DELETED); pos++);
 
 	if (pos < size)
 		return data[pos++].key;
 	else
 		return nil;
 }
 @end
 /// \endcond

Index: src/OFMutableDictionary.m
==================================================================
--- src/OFMutableDictionary.m
+++ src/OFMutableDictionary.m
@@ -16,10 +16,11 @@
 #import "OFMutableDictionary.h"
 #import "OFExceptions.h"
 #import "macros.h"
 
 #define BUCKET_SIZE sizeof(struct of_dictionary_bucket)
+#define DELETED (id)&of_dictionary_deleted_bucket
 
 static OF_INLINE void
 resize(id self, Class isa, size_t count, struct of_dictionary_bucket **data,
     size_t *size)
 {
@@ -41,19 +42,27 @@
 	newdata = [self allocMemoryForNItems: newsize
 				    withSize: BUCKET_SIZE];
 	memset(newdata, 0, newsize * BUCKET_SIZE);
 
 	for (i = 0; i < *size; i++) {
-		if ((*data)[i].key != nil) {
-			uint32_t j = (*data)[i].hash & (newsize - 1);
-			for (; j < newsize && newdata[j].key != nil; j++);
+		if ((*data)[i].key != nil && (*data)[i].key != DELETED) {
+			uint32_t j, last;
+
+			last = newsize;
+
+			j = (*data)[i].hash & (newsize - 1);
+			for (; j < last && newdata[j].key != nil; j++);
 
 			/* In case the last bucket is already used */
-			if (j >= newsize)
-				for (j = 0; j < newsize &&
+			if (j >= last) {
+				last = (*data)[i].hash & (newsize - 1);
+
+				for (j = 0; j < last &&
 				    newdata[j].key != nil; i++);
-			if (j >= newsize)
+			}
+
+			if (j >= last)
 				@throw [OFOutOfRangeException
 				    newWithClass: [self class]];
 
 			newdata[j].key = (*data)[i].key;
 			newdata[j].object = (*data)[i].object;
@@ -68,39 +77,51 @@
 
 @implementation OFMutableDictionary
 - setObject: (OFObject*)obj
      forKey: (OFObject <OFCopying>*)key
 {
-	uint32_t i, hash;
+	uint32_t i, hash, last;
 
 	if (key == nil || obj == nil)
 		@throw [OFInvalidArgumentException newWithClass: isa
 						       selector: _cmd];
 
 	hash = [key hash];
+	last = size;
 
-	for (i = hash & (size - 1); i < size && data[i].key != nil &&
-	    ![data[i].key isEqual: key]; i++);
+	for (i = hash & (size - 1); i < last && data[i].key != nil &&
+	    (data[i].key == DELETED || ![data[i].key isEqual: key]); i++);
 
 	/* In case the last bucket is already used */
-	if (i >= size)
-		for (i = 0; i < size && data[i].key != nil &&
-		    ![data[i].key isEqual: key]; i++);
+	if (i >= last) {
+		last = hash & (size - 1);
+
+		for (i = 0; i < last && data[i].key != nil &&
+		    (data[i].key == DELETED || ![data[i].key isEqual: key]);
+		    i++);
+	}
 
 	/* Key not in dictionary */
-	if (i >= size || ![data[i].key isEqual: key]) {
+	if (i >= last || data[i].key == nil || data[i].key == DELETED ||
+	    ![data[i].key isEqual: key]) {
 		resize(self, isa, count + 1, &data, &size);
 
 		mutations++;
+		last = size;
 
-		i = hash & (size - 1);
-		for (; i < size && data[i].key != nil; i++);
+		for (i = hash & (size - 1); i < last && data[i].key != nil &&
+		    data[i].key != DELETED; i++);
 
 		/* In case the last bucket is already used */
-		if (i >= size)
-			for (i = 0; i < size && data[i].key != nil; i++);
-		if (i >= size)
+		if (i >= last) {
+			last = hash & (size - 1);
+
+			for (i = 0; i < last && data[i].key != nil &&
+			    data[i].key != DELETED; i++);
+		}
+
+		if (i >= last)
 			@throw [OFOutOfRangeException newWithClass: isa];
 
 		key = [key copy];
 		@try {
 			[obj retain];
@@ -124,36 +145,43 @@
 	return self;
 }
 
 - removeObjectForKey: (OFObject*)key
 {
-	uint32_t i, hash;
+	uint32_t i, hash, last;
 
 	if (key == nil)
 		@throw [OFInvalidArgumentException newWithClass: isa
 						       selector: _cmd];
 
 	hash = [key hash];
+	last = size;
 
-	for (i = hash & (size - 1); i < size && data[i].key != nil &&
-	    ![data[i].key isEqual: key]; i++);
+	for (i = hash & (size - 1); i < last && data[i].key != nil &&
+	    (data[i].key == DELETED || ![data[i].key isEqual: key]); i++);
 
-	if (i < size && data[i].key == nil)
+	if (i < last && (data[i].key == nil || data[i].key == DELETED ||
+	    ![data[i].key isEqual: key]))
 		return self;
 
 	/* In case the last bucket is already used */
-	if (i >= size)
-		for (i = 0; i < size && data[i].key != nil &&
-		    ![data[i].key isEqual: key]; i++);
+	if (i >= last) {
+		last = hash & (size - 1);
+
+		for (i = 0; i < last && data[i].key != nil &&
+		    (data[i].key == DELETED || ![data[i].key isEqual: key]);
+		    i++);
+	}
 
 	/* Key not in dictionary */
-	if (i >= size || ![data[i].key isEqual: key])
+	if (i >= last || data[i].key == nil || data[i].key == DELETED ||
+	    ![data[i].key isEqual: key])
 		return self;
 
 	[data[i].key release];
 	[data[i].object release];
-	data[i].key = nil;
+	data[i].key = DELETED;
 
 	count--;
 	mutations++;
 	resize(self, isa, count, &data, &size);
 
@@ -170,12 +198,12 @@
 			     count: (int)count_
 {
 	size_t i;
 
 	for (i = 0; i < count_; i++) {
-		for (; state->state < size && data[state->state].key == nil;
-		    state->state++);
+		for (; state->state < size && (data[state->state].key == nil ||
+		    data[state->state].key == DELETED); state->state++);
 
 		if (state->state < size) {
 			objects[i] = data[state->state].key;
 			state->state++;
 		} else