Implementing a HashTable in Objective-C

Question

I am trying to implement a hash table in Objective-C. I did some testing and the implementation seems to work. I am using an NSMutableArray to store linked lists of entries. It also resizes when it gets almost full. I am using an NSString for a key and any object as a value. I store NSNull objects in an NSMutableArray to be able initialize it to a certain size.

The hash function I copied from the Java HashTable implementation:

#import "YZHashTable.h"
#import "Entry.h"


@interface YZHashTable()

@property (nonatomic,strong) NSMutableArray *tableArray;
@property (nonatomic) NSInteger elementCount;
@end



@implementation YZHashTable

const int HASHTABLECAPACITY=10;
const double HASHTABLELOADFACTOR = 0.75;

-(instancetype)init
{
    self  = [super init];
    if(self){
        [self resizeTableArray];
        _elementCount = 0;
    }


    return self;
}

-(void)resizeTableArray
{
    for(int i = 0; i < HASHTABLECAPACITY; i++){
        [self.tableArray addObject:[NSNull null]];
    }
}


-(NSMutableArray *)tableArray
{
    if(!_tableArray){
        _tableArray = [[NSMutableArray alloc]initWithCapacity:HASHTABLECAPACITY];
    }
    return _tableArray;
}

-(void)setElementCount:(NSInteger)elementCount
{
    if(elementCount < 0) return;
    _elementCount = elementCount;
}


-(void)addObjectForKey:(NSString *)key andValue:(id) value
{
    if(self.elementCount > [self.tableArray count] * HASHTABLELOADFACTOR){
        [self resizeTableArray];
    }
    NSUInteger keyArrayIndex = [self indexForHash:[key hash]] % [self.tableArray count];
    if([[self.tableArray objectAtIndex:keyArrayIndex] isKindOfClass:[NSNull class]]){
        [self.tableArray setObject:[[Entry alloc]initWithKey:key andValue:value] atIndexedSubscript:keyArrayIndex];
    }else{
        Entry *root = [self.tableArray objectAtIndex:keyArrayIndex];
        while(root.next && ![root.key isEqualToString:key]){
            root = root.next;
        }
        if([root.key isEqualToString:key]){
            root.value = value;
        }else{
            root.next = [[Entry alloc]initWithKey:key andValue:value];
        }
    }
    self.elementCount++;
}

-(id)getObjectForKey:(NSString  *)key
{
    id value = nil;

    NSUInteger keyArrayIndex = [self indexForHash:[key hash]] % [self.tableArray count];
    Entry *root = [self.tableArray objectAtIndex:keyArrayIndex];
    if(![root isKindOfClass:[NSNull class]]){
        while(![root.key isEqualToString:key] || root.next != nil){
            root = root.next;
        }
        if([root.key isEqualToString:key]) value = root.value;
    }

    return value;
}


-(id)removeObjectForKey:(NSString  *)key
{
    id value = nil;

    NSUInteger keyArrayIndex = [self indexForHash:[key hash]] % [self.tableArray count];
    Entry *root = [self.tableArray objectAtIndex:keyArrayIndex];
    if(![root isKindOfClass:[NSNull class]]){
        if([root.key isEqualToString:key]){
            if(!root.next){
                [self.tableArray setObject:[NSNull null] atIndexedSubscript:keyArrayIndex];
            }else{
                root = root.next;
            }
            self.elementCount--;
        }else{
            while(root.next && ![root.next.key isEqualToString:key]){
                root = root.next;
            }
            if([root.next.key isEqualToString:key]){
                root.next = root.next.next;
                self.elementCount--;
            }
        }


    }
    return value;
}


-(NSUInteger)count
{
    return self.elementCount;
}

-(NSUInteger)indexForHash:(NSUInteger)hash
{
    hash ^= (hash>>20)^(hash>>12);
    return hash ^ (hash >> 7) ^ (hash >> 4);
}

@end

Answer 1

Use NSHashTable from iOS 6+ SDK. The hash table is modeled after NSSet with the following differences:

• It can hold weak references to its members.
• Its members may be copied on input or may use pointer identity for equality and hashing.
• It can contain arbitrary pointers (its members are not constrained to being objects).

Example usage:

 NSHashTable *hashTable = [NSHashTable 
 hashTableWithOptions:NSPointerFunctionsCopyIn];
 [hashTable addObject:@"foo"];
 [hashTable addObject:@"bar"];
 [hashTable addObject:@100];
 [hashTable removeObject:@"bar"];
 NSLog(@"Members: %@", [hashTable allObjects]);