iOS - OC字典底层实现模拟(数组+链表)

为什么要这么设计 ？

原因有二：  1. 每个对象创建时，都默认生成一个hashCode ,也就是一个经过哈希算法生成的一串数字 。当利用key去取字典中的value时，若是使用遍历或者二分查找等方法，效率都相对较低 ，于是出现了根据每个key生成的hashCode将该键值对放到hashCode对应的数组中的指定位置，这样当用key去取值时，便不必遍历去获取，即可以根据hashCode直接取出。  2. hashCode数字过大，或许会经过取余生成一个较小的数字，假如是对999取余，那么得到的结果始终处于0-999之间。但是，这样做的弊端在于取余所得到的值，可能是相同的，这样可能导致完全不相干的键值对被新的键值对（取余后值key相等）所覆盖。于是出现了数组中套链表实现的数组。这样，key值取余得到值相等的键值对，都将保存在同一个链表数组中，当查找key对应的值时，首先获取到该链表数组，然后遍历该数组，取正确的key所对应的值即可。

具体代码如下：

---

链表实现的数组

#import <Foundation/Foundation.h> @interface MYLinkedArray : NSObject @property (assign , nonatomic) NSUInteger size; //数组长度 - (void)addObject:(NSObject *)obj; //添加元素 - (void)remove:(NSObject *)obj; //移除指定元素 - (void)removeAtIndex:(NSInteger)index; //移除指定索引元素 - (NSObject *)objectAtIndex:(NSInteger)index; //获取指定位置的值 + (instancetype)array; //数组初始化 @end @interface Node : NSObject @property (strong , nonatomic) Node *previous; //上个节点 @property (strong , nonatomic) Node *next; //下个节点 @property (strong , nonatomic) id content; //当前节点内容 @end 12345678910111213141516171819202122232425262728

. m文件

#import "MYLinkedArray.h" @interface MYLinkedArray () @property (nonatomic, strong) Node *first; //首个节点 @property (nonatomic, strong) Node *last; //最后节点 @end @implementation MYLinkedArray //添加元素 - (void)addObject:(NSObject *)obj { if (!obj) return; _size ++ ; Node *node = [[Node alloc]init]; //首个节点为空 if (!_first) { _first = node; _last = node; node.previous = nil; node.next = nil; node.content = obj; return; } //数组中有值 node.previous = _last; node.next = nil; node.content = obj; _last = node; _last.next = node; } //移除元素 - (void)remove:(NSObject *)obj { if (!obj||!_size) return; Node *tmpNode = _first; for (NSInteger index = 0; index < _size; index ++) { if ([tmpNode.content isEqual:obj]) { [self removeNode:tmpNode]; //移除节点 break; } } } //根据索引移除元素 - (void)removeAtIndex:(NSInteger)index { if (index<0||index>=_size) return; Node *tmpNode = _first; for (NSInteger i = 0; i < _size; i ++) { if (i == index) { [self removeNode:tmpNode]; //移除节点 break; } tmpNode = tmpNode.next; } } //获取指定索引元素 - (NSObject *)objectAtIndex:(NSInteger)index { if (index<0||index>=_size) return nil; Node *tmpNode = _first; for (NSInteger i = 0; i < _size; i ++) { if (i == index) { return tmpNode.content; } tmpNode = tmpNode.next; } return nil; } //私有 - (void)removeNode:(Node *)node { //连接上下节点 Node *preNode = node.previous; Node *nextNode = node.next; preNode.next = nextNode; nextNode.previous = preNode; node.content = nil; //清空被移除节点内容 _size -- ;//长度更新 } //构造方法 + (instancetype)array { return [[self alloc]init]; } @end @implementation Node @end 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127

---

自定义的字典类

#import <Foundation/Foundation.h> @interface MYDictionary : NSObject + (instancetype)dictionary; - (void)setValue:(id)value forkey:(NSString *)key; - (id)valueForKey:(NSString *)key; @end 1234567891011

. m文件

#import "MYDictionary.h" #import "MYLinkedArray.h" @interface KeyValueCache : NSObject @property (nonatomic, strong) NSString *key; @property (nonatomic, strong) id value; @end @implementation KeyValueCache + (instancetype)key:(NSString *)key value:(id)value { KeyValueCache *model = [[self alloc]init]; model.key = key; model.value = value; return model; } @end @interface MYDictionary () @end @implementation MYDictionary { MYLinkedArray *_keyValues[999]; } //构造方法 + (instancetype)dictionary { return [[self alloc]init]; } //赋值 - (void)setValue:(id)value forkey:(NSString *)key { //获取hashCode NSUInteger hash = key.hash; //默认一个对象占用8个字节 NSUInteger realCode = hash%(sizeof(_keyValues)/8); MYLinkedArray *linkArr = _keyValues[realCode]; if (linkArr) { //如果存在链表数组 for (NSInteger index = 0; index < linkArr.size; index ++) { KeyValueCache *keyValue = (KeyValueCache *)[linkArr objectAtIndex:index]; if ([keyValue.key isEqualToString:key]) { //如果存在相同的Key ，更新value keyValue.value = value; //重新赋值value return; } } //创建新的键值对存储 KeyValueCache *newKeyValue = [KeyValueCache key:key value:value]; [linkArr addObject:newKeyValue]; }else{ //不存在链表数组 //创建新的链表数组 MYLinkedArray *newLinkArray = [MYLinkedArray array]; KeyValueCache *newKeyValue = [KeyValueCache key:key value:value]; [newLinkArray addObject:newKeyValue]; _keyValues[realCode] = newLinkArray; } } //根据键取值 - (id)valueForKey:(NSString *)key { if (!key.length) return nil; //获取hashCode NSUInteger hash = key.hash; NSUInteger realCode = hash%(sizeof(_keyValues)/8); MYLinkedArray *linkArr = _keyValues[realCode]; if (linkArr) { //遍历链表，取出value for (NSInteger index = 0; index < linkArr.size; index ++) { KeyValueCache *keyvalue = (KeyValueCache *)[linkArr objectAtIndex:index]; if ([keyvalue.key isEqualToString:key]) { return keyvalue.value; } } } return nil; } @end 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107

最终实验结果：

- (void)viewDidLoad { [super viewDidLoad]; MYDictionary *dict = [MYDictionary dictionary]; [dict setValue:@"哈哈" forkey:@"孟"]; [dict setValue:@"你好" forkey:@"孟"]; [dict setValue:@123456 forkey:@"数字"]; NSLog(@"%@",[dict valueForKey:@"孟"]); NSLog(@"%@",[dict valueForKey:@"数字"]); } 12345678910

---

成功自定义了一个字典.