巨核信息共享中心

关于散列表的研究以及NSDictionary底层探索

—

由

ghost0329
于

关于散列表的研究以及NSDictionary底层探索

有道笔记链接：https://note.youdao.com/s/FsSLFw9k

众所周知，在iOS开发当中便利一个数组，去不断匹配value是一种很低效的方式，但是如果直接通过NSarry的index（索引）去取值，则会快很多，但是字典是无序的，也就是没有一个对外暴露的索引，我们该如何通过字典的key去快速定位Value呢？

在了解这些之前，我们就必须要了解散列表，即哈希表（Hash table）。

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

所以我们知道哈希表底层其实是一个数组，那么只要我们通过一定的算法将key值转化为数组中index和value的对应关系就可以极大的提升字典差值的效率了。

话不多说，开搞！

已知Key对象的值为0b0000 0001(计算机储存的所有对象都为二进制数据)，当我们设定这个key的时候，我们会通过一个hash函数去生成一个特定索引。这个函数可能是用“&”与运算符，也可能用“%”取余，不同平台的算法各不相同，但都是相通的。

比如我们定义一个mask，值为：0b0000 1111（取余即为15）；我们用key1 & mask，如下：

//通过“&”运算符，我们得到一个明确的索引，即1。
  0b0000 0001
& 0b0000 1111
--------------
  0b0000 0001

哈希表对应分布如下：

索引value
0NULL
1buket(key1,value2)
2NULL
3NULL
4NULL
5NULL

如果我们继续往字典储存新值，如key2为：0b0000 0010

//通过“&”运算符，我们得到一个明确的索引，即2。
  0b0000 0010
& 0b0000 1111
--------------
  0b0000 0010

哈希表对应分布如下：

索引（地址）value
0NULL
1buket(key1,value2)
2buket(key2,value2)
3NULL
4NULL
5NULL

以此类推，我们将会得到一个Array，所以了解了这些后，我们很容易就明白，当我们传入一个key时，字典并不是通过key去循环便利去找出我们想要的value，而是通过一个函数去生成value的一个索引，从而更精准的定位我们想要的value，如传入：（0b0000 0001），我们就得到了索引为1，再通过索引1，直接拿到Value。

那么新问题产生了！

在上面我们定义了一个mask为0b0000 1111的值，根据“&”运算的逻辑，值都为1才为1，只要其中有一个为0，则为0。所以我们得到的索引最大值都不会超过mask，即15。即数组内储存的元素最多不能超过15条。

  1. 那么一旦超过呢？没错，字典底层为我们编写了“扩容”的操作。（源码如下）
  2. 如果生成的索引index已经被占用了呢？这时候iOS底层源码编写了向前/向后查找，直到查找到存在空位时，储存（但是实际开发中，冲突很麻烦，甚至会影响散列表的查找速度，所以应该采用最大限度减少冲突的散列函数）。

下面时iOS中字典扩容的源码，有兴趣的可以看一下。 iOS CFDictionary源码

//字典结构体
struct __CFDictionary {
    CFRuntimeBase _base;
    CFIndex _count;		/* number of values */
    CFIndex _capacity;		/* maximum number of values */
    CFIndex _bucketsNum;	/* number of slots */
    uintptr_t _marker;
    void *_context;		/* private */
    CFIndex _deletes;
    CFOptionFlags _xflags;      /* bits for GC */
    //保留的所有的key
    const void **_keys;		/* can be NULL if not allocated yet */
    //保存了所有value
    const void **_values;	/* can be NULL if not allocated yet */
};

static void __CFDictionaryGrow(CFMutableDictionaryRef dict, CFIndex numNewValues) {
    //获得原有的keys和values
    const void **oldkeys = dict->_keys;
    const void **oldvalues = dict->_values;
    //原来插槽数
    CFIndex idx, oldnbuckets = dict->_bucketsNum;
    //原来字典中的values
    CFIndex oldCount = dict->_count;
    CFAllocatorRef allocator = __CFGetAllocator(dict), keysAllocator, valuesAllocator;
    void *keysBase, *valuesBase;
    dict->_capacity = __CFDictionaryRoundUpCapacity(oldCount + numNewValues);
    dict->_bucketsNum = __CFDictionaryNumBucketsForCapacity(dict->_capacity);
    dict->_deletes = 0;
    if (_CFDictionaryIsSplit(dict)) {   // iff GC, use split memory sometimes unscanned memory
    unsigned weakOrStrong = (dict->_xflags & __kCFDictionaryWeakKeys) ? AUTO_MEMORY_UNSCANNED : AUTO_MEMORY_SCANNED;
    void *mem = _CFAllocatorAllocateGC(allocator, dict->_bucketsNum * sizeof(const void *), weakOrStrong);
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_keys, mem);
        keysAllocator = (dict->_xflags & __kCFDictionaryWeakKeys) ? kCFAllocatorNull : allocator;  // GC: avoids write-barrier in weak case.
        keysBase = mem;
    
        weakOrStrong = (dict->_xflags & __kCFDictionaryWeakValues) ? AUTO_MEMORY_UNSCANNED : AUTO_MEMORY_SCANNED;
    mem = _CFAllocatorAllocateGC(allocator, dict->_bucketsNum * sizeof(const void *), weakOrStrong);
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_values, mem);
        valuesAllocator = (dict->_xflags & __kCFDictionaryWeakValues) ? kCFAllocatorNull : allocator; // GC: avoids write-barrier in weak case.
        valuesBase = mem;
    } else {
        //扩容成原先大小的两倍
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_keys, _CFAllocatorAllocateGC(allocator, 2 * dict->_bucketsNum * sizeof(const void *), AUTO_MEMORY_SCANNED));
        dict->_values = (const void **)(dict->_keys + dict->_bucketsNum);
        keysAllocator = valuesAllocator = allocator;
        keysBase = valuesBase = dict->_keys;
    }
    if (NULL == dict->_keys || NULL == dict->_values) HALT;
    if (__CFOASafe) __CFSetLastAllocationEventName(dict->_keys, "CFDictionary (store)");
    // 重新计算keys数据的hash值，存放到新的数组中
    for (idx = dict->_bucketsNum; idx--;) {
        dict->_keys[idx] = (const void *)dict->_marker;
        dict->_values[idx] = 0;
    }
    if (NULL == oldkeys) return;
    for (idx = 0; idx < oldnbuckets; idx++) {
        if (dict->_marker != (uintptr_t)oldkeys[idx] && ~dict->_marker != (uintptr_t)oldkeys[idx]) {
            CFIndex match, nomatch;
            __CFDictionaryFindBuckets2(dict, oldkeys[idx], &match, &nomatch);
            CFAssert3(kCFNotFound == match, __kCFLogAssertion, "%s(): two values (%p, %p) now hash to the same slot; mutable value changed while in table or hash value is not immutable", __PRETTY_FUNCTION__, oldkeys[idx], dict->_keys[match]);
            if (kCFNotFound != nomatch) {
                CF_WRITE_BARRIER_BASE_ASSIGN(keysAllocator, keysBase, dict->_keys[nomatch], oldkeys[idx]);
                CF_WRITE_BARRIER_BASE_ASSIGN(valuesAllocator, valuesBase, dict->_values[nomatch], oldvalues[idx]);
            }
        }
    }
    CFAssert1(dict->_count == oldCount, __kCFLogAssertion, "%s(): dict count differs after rehashing; error", __PRETTY_FUNCTION__);
    _CFAllocatorDeallocateGC(allocator, oldkeys);
    if (_CFDictionaryIsSplit(dict)) _CFAllocatorDeallocateGC(allocator, oldvalues);
}

但是扩容有一个很明显的缺点，就是会让字典的容量越来越大，甚至产生很多空间的浪费。所以哈希表是一种用空间换效率的技术。（会空闲一部分内存）

总结一下，所以散列表的核心是散列函数，大致可以用如下函数表示，不管是用“%”取余，还是用与运算符“&”，我们所定义的mask都决定了散列表的容量大小，所以应尽可能优化散列函数，避免mask的频繁变动和散列表数据的冲突，保证散列表查询的效率。以上就是我对于散列表的理解和研究，如果错漏，还请大家踊跃提出，共同交流。

f(key) == index

下面补充几个网上推荐的hash表函数：

相关参考文档补充 iOS字典底层原理：https://www.jianshu.com/p/0d7cd6341f65 iOS 用OC简单还原hash值生成

—–zhaohanjun