2
\$\begingroup\$

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
\$\endgroup\$
-1
\$\begingroup\$

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]);
\$\endgroup\$
  • \$\begingroup\$ This isn't a code review. It's a suggestion to use something else. Can you comment at all on the code that was written? \$\endgroup\$ – user1118321 Feb 24 '18 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.