Objective-C中的字典NSDictionary底层其实是一个哈希表
在CFDictionary的结构体的时候看到了key和values这两个二级指针，
可以基本断定为数组结构，由于是两个数组分别存储，
因此，key哈希出来的数组下标地址，同样这个地址对应到values数组的下标，就是匹配到的值。
因此keys和values这两个数组的长度一致才能保证匹配到数据。
内部结构还有个_capacity表示当前通列表的扩充阀域 ，当count数量达到这个长度就扩容
可以看到，NSDictionary设置的key和value，key值会根据特定的hash函数算出建立的空桶数组，
keys和values同样多，然后存储数据的时候，根据hash函数算出来的值，
找到对应的index下标，如果下标已有数据，开放定址法后移动插入，
如果空桶数组到达数据阀值，这个时候就会把空桶数组扩容，然后重新哈希插入。
这样把一些不连续的key-value值插入到了能建立起关系的hash表中，当我们查找的时候，key根据哈希值算出来，
然后根据索引，直接index访问hash表keys和hash表values，这样查询速度就可以和连续线性存储的数据一样接近O(1)了，只是占用空间有点大，性能就很强悍。如果删除的时候，也会根据_maker标记逻辑上的删除，除非NSDictionary（NSDictionary本体的hash值就是count）内存被移除。
我们也会根据dictionary之所以采用这种设计，其一出于查询性能的考虑；其二dictionary在使用过程中总是会很快的被释放，不会长期占用内存。
网友评论