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

心已赠人 2022-06-11 23:53 290阅读 0赞

## 为什么要这么设计 ？ ##

原因有二：   
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
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
       16
       17
       18
       19
       20
       21
       22
       23
       24
       25
       26
       27
       28

. 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
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
       16
       17
       18
       19
       20
       21
       22
       23
       24
       25
       26
       27
       28
       29
       30
       31
       32
       33
       34
       35
       36
       37
       38
       39
       40
       41
       42
       43
       44
       45
       46
       47
       48
       49
       50
       51
       52
       53
       54
       55
       56
       57
       58
       59
       60
       61
       62
       63
       64
       65
       66
       67
       68
       69
       70
       71
       72
       73
       74
       75
       76
       77
       78
       79
       80
       81
       82
       83
       84
       85
       86
       87
       88
       89
       90
       91
       92
       93
       94
       95
       96
       97
       98
       99
       100
       101
       102
       103
       104
       105
       106
       107
       108
       109
       110
       111
       112
       113
       114
       115
       116
       117
       118
       119
       120
       121
       122
       123
       124
       125
       126
       127

--------------------

## 自定义的字典类 ##

#import <Foundation/Foundation.h>
    
    @interface MYDictionary : NSObject
    
    + (instancetype)dictionary;
    
    - (void)setValue:(id)value forkey:(NSString *)key;
    
    - (id)valueForKey:(NSString *)key;
    
    @end
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11

. 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
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
       16
       17
       18
       19
       20
       21
       22
       23
       24
       25
       26
       27
       28
       29
       30
       31
       32
       33
       34
       35
       36
       37
       38
       39
       40
       41
       42
       43
       44
       45
       46
       47
       48
       49
       50
       51
       52
       53
       54
       55
       56
       57
       58
       59
       60
       61
       62
       63
       64
       65
       66
       67
       68
       69
       70
       71
       72
       73
       74
       75
       76
       77
       78
       79
       80
       81
       82
       83
       84
       85
       86
       87
       88
       89
       90
       91
       92
       93
       94
       95
       96
       97
       98
       99
       100
       101
       102
       103
       104
       105
       106
       107

## 最终实验结果： ##

- (void)viewDidLoad {
        [super viewDidLoad];
    
        MYDictionary *dict = [MYDictionary dictionary];
        [dict setValue:@"哈哈" forkey:@"孟"];
        [dict setValue:@"你好" forkey:@"孟"];
        [dict setValue:@123456 forkey:@"数字"];
        NSLog(@"%@",[dict valueForKey:@"孟"]);
        NSLog(@"%@",[dict valueForKey:@"数字"]);
    }
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10

--------------------

成功自定义了一个字典.

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220612/facded741bf14e5e82e7725e07f75aab.png