Case-Insensitive Dictionary Keys

On a recent project, I found myself needing a mutable dictionary whose keys were case-insensitive strings. A common solution to this problem is to normalize the case of each key before getting or setting its value:

- (id)valueForField:(NSString *)field
    return dictionary[field.lowercaseString];

- (void)setValue:(id)value forField:(NSString *)field
    dictionary[field.lowercaseString] = value;

Unfortunately, I had an additional requirement that precluded this solution: I wanted the case of keys to be preserved. That is, if I added an entry using the key @"Foo", I wanted to be able to get its value using @"foo" or @"FOO"; if I printed out the dictionary’s keys, I wanted to see the key as @"Foo".

It wasn’t readily apparent how to achieve this without dropping into CoreFoundation or subclassing NSMutableDictionary, neither of which sounded like a lot of fun. Instead, I reached for NSMutableDictionary’s more flexible cousin NSMapTable. Map tables and mutable dictionaries have nearly identical interfaces, but map tables can also:

  • Use keys that don’t conform to NSCopying
  • Weakly reference their keys and/or values
  • Store non-objects as pointers
  • Use user-defined functions for hashing, equality checking, and memory management

We can exploit this last feature to get a dictionary-like object with case-insensitive keys.

Customizing Our Map Table

We need to customize how our map table determines if two keys are equal, replacing strict string equality with case-insensitive comparison. Map tables use NSPointerFunctions objects to determine how keys and values are compared and memory-managed. Our first task is to create a pointer-functions object with case-insensitive versions of hashFunction and isEqualFunction. We’ll start by implementing these functions:

NSUInteger TWTCaseInsensitiveHash(const void *item, NSUInteger (*size)(const void *item))
    return [[(__bridge NSString *)item lowercaseString] hash];

BOOL TWTCaseInsensitiveIsEqual(const void *item1, const void *item2,  
                               NSUInteger (*size)(const void *item))
    NSString *string1 = (__bridge NSString *)item1;
    NSString *string2 = (__bridge NSString *)item2;
    return [string1 caseInsensitiveCompare:string2] == NSOrderedSame;

Next, we need to create the pointer-functions object for our keys. Besides using our case-insensitive …Hash and …IsEqual functions, our keys should be like those of NSDictionary: they should be copied on insertion, use strongly referenced memory, and otherwise behave like objects.

NSPointerFunctionsOptions options = NSPointerFunctionsCopyIn |
                                    NSPointerFunctionsStrongMemory |
NSPointerFunctions *keyFunctions = [[NSPointerFunctions alloc] initWithOptions:options];
keyFunctions.hashFunction = TWTCaseInsensitiveHash;
keyFunctions.isEqualFunction = TWTCaseInsensitiveIsEqual;

Creating the value pointer-functions object is easier. Values should use strong memory and behave like objects.

options = NSPointerFunctionsStrongMemory | NSPointerFunctionsObjectPersonality;
NSPointerFunctions *valueFunctions = [[NSPointerFunctions alloc] initWithOptions:options];

Finally, we need to create a map table that uses these key and value pointer-functions:

NSMapTable *mapTable = [[NSMapTable alloc] initWithKeyPointerFunctions:keyFunctions 

And that’s it. We now have a dictionary-like object with case-insensitive, case-preserving keys. Adding this as a category to NSMapTable is left as an exercise for the reader. While you’re at it, implement ‑objectForKeyedSubscript: and ‑setObject:forKeyedSubscript: so that your map table can use dictionary-style subscripting.

There is one important caveat with our solution: when setting objects for existing keys, NSMapTable reuses the existing key. For example,

[mapTable setObject:@"Bar" forKey:@"Foo"];
NSLog(@"%@", [mapTable.keyEnumerator allObjects]);    // Outputs "Foo"

[mapTable setObject:@"Baz" forKey:@"FOO"];
NSLog(@"%@", [mapTable.keyEnumerator allObjects]);    // Also outputs "Foo"

If this is a problem for you, you’ll need to remove the existing object before inserting the new one.

Hopefully we’ve shown how easy it is to create interesting variations on dictionary-like objects using NSMapTable. Map tables are powerful, flexible objects, and becoming comfortable with them can save you a lot of time that would otherwise be spent subclassing NSDictionary.

Tweet about this on Twitter