sillykeys.m

#import <Foundation/Foundation.h>

static const char *alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

NSString *badKey(int idx) {
    char *buffer = malloc(4096);
    memset(buffer, 'A', 4096 * sizeof(char));
    //NSString hashes the beginning, middle, and end of long strings, so we want our keys to differ only in other places.
    //-isEqual: also compares from front to back, so to exaggerate the problem, I placed the differences in the keys about 3/4 of the way through the string
    buffer[3072] = alphabet[arc4random_uniform(52)];
    buffer[3073] = alphabet[arc4random_uniform(52)];
    buffer[3074] = alphabet[arc4random_uniform(52)];
    buffer[3075] = alphabet[arc4random_uniform(52)];
    buffer[3076] = alphabet[arc4random_uniform(52)];
    buffer[3077] = alphabet[arc4random_uniform(52)];
    buffer[3078] = alphabet[arc4random_uniform(52)];
    buffer[4095] = '\0';
    NSString *key = [NSString stringWithUTF8String:buffer];
    free(buffer);
    return key;
}

NSString *goodIshKey(int idx) {
    char *buffer = malloc(4096 + idx);
    memset(buffer, 'A', (4096 + idx) * sizeof(char));
    buffer[3072] = alphabet[arc4random_uniform(52)];
    buffer[3073] = alphabet[arc4random_uniform(52)];
    buffer[3074] = alphabet[arc4random_uniform(52)];
    buffer[3075] = alphabet[arc4random_uniform(52)];
    buffer[3076] = alphabet[arc4random_uniform(52)];
    buffer[3077] = alphabet[arc4random_uniform(52)];
    buffer[3078] = alphabet[arc4random_uniform(52)];
    buffer[4095 + idx] = '\0';
    NSString *key = [NSString stringWithUTF8String:buffer];
    free(buffer);
    return key;
}

#define BAD 1

int main() {
    NSMutableArray *keys = [NSMutableArray array];
#if BAD
    for (int i = 0; i < 1000; i++) {
        [keys addObject:badKey(i)];
    }
#else
    for (int i = 0; i < 1000; i++) {
        [keys addObject:goodIshKey(i)];
    }
#endif
    NSDictionary *dict = [[NSDictionary alloc] initWithObjects:keys forKeys:keys];
    NSDate *date = [NSDate date];
    for (int i = 0; i < 10; i++) {
        for (NSString *key in keys) {
            [dict objectForKey:key];
        }
    }
    NSTimeInterval elapsed = -[date timeIntervalSinceNow];
    NSLog(@"%f s to do 10,000 lookups", elapsed);
    return 0;
}

10,000 lookups...?

Heh, yeah, didn't update the comment when I updated the code. Oh well.