本文共 2783 字，大约阅读时间需要 9 分钟。

Objective-C 实现哈希表（Hash Table）的链地址法

哈希表是一种高效的数据存储结构，能够快速进行插入、查找和删除操作。以下是 Objective-C 中使用链地址法实现哈希表的完整代码示例，包括插入、查找和删除操作。

HashNode 类定义了哈希表的节点结构

#import 
   
    @interface HashNode : NSObject@property (nonatomic, strong) NSString *key;@property (nonatomic, strong) id value;@property (nonatomic, strong) HashNode *next;@end
   

哈希表的实现类定义

@interface HashTable : NSObject@property (nonatomic, strong) HashNode *head;@property (nonatomic, strong) HashNode *last;@property (nonatomic, strong) id (*hashFunction)(id key);@end

哈希表的实现类实现

@implementation HashTable- (id)init {    self.head = [HashNode new];    self.last = self.head;    return self;}- (void)insertWithKey:(id)key value:(id)value {    HashNode *newNode = [HashNode new];    newNode.key = key;    newNode.value = value;    newNode.next = nil;        int hash = [_hashFunction hash(key)];    HashNode *current = self.head;        // 链地址法解决哈希冲突    while (current != nil && current.key != nil && current.key != key) {        current = current.next;    }        if (current == nil) {        newNode.next = self.last.next;        self.last.next = newNode;        self.last = newNode;    } else {        if (current.key == key) {            newNode.next = current.next;            current.next = newNode;        } else {            newNode.next = current.next;            current.next = newNode;            // 优化：如果当前节点的 key 值不为空且等于新节点的 key 值，则将其链接到新节点后面            if (!current.value && current.key) {                current.next = newNode;            }        }    }}- (id)searchForKey:(id)key {    int hash = [_hashFunction hash(key)];    HashNode *current = self.head;        // 链地址法解决哈希冲突    while (current != nil && current.key != nil && current.key != key) {        current = current.next;    }        if (current != nil && current.key == key) {        return current.value;    }    return nil;}- (void)deleteKey:(id)key {    HashNode *current = self.head;    HashNode *prev = nil;        // 链地址法删除节点    while (current != nil && current.key != nil && current.key != key) {        prev = current;        current = current.next;    }        if (current != nil && current.key == key) {        if (prev != nil) {            prev.next = current.next;            self.last = prev.next ? prev.next : prev;        } else {            self.head = current.next;            self.last = self.head ? self.head : nil;        }        current = nil;    }}- (void)show {    HashNode *current = self.head;    while (current != nil) {        NSLog(@"Key: %@ Value: %@", current.key, current.value);        current = current.next;    }}

链地址法哈希表的优势

哈希表的使用场景

• 数据量较大的数据存储
• 频繁的数据插入、删除和查找操作
• 需要快速访问数据的场景

通过以上代码，可以实现一个功能完善的哈希表，支持插入、查找和删除操作。链地址法通过将哈希冲突转化为链表来解决，虽然在最坏情况下时间复杂度较高，但在大多数实际应用中表现优秀。

转载地址：http://ftnfk.baihongyu.com/