数据结构-散列表（HashTable）

本质

哈希表的底层数据结构是数组，数组中每一个元素存放的是键值对。

structure of hashtable

核心原理

f(key) = index

将key传入，通过某个算法f，计算出索引，如果索引冲突，再通过某个办法对索引进行+1或-1再算一遍，直到算到不冲突为止。

负载因子 = 总键值对数 / 哈希表总长度

负载因子用来衡量用来衡量哈希表的空满程度，一般，当负载因子为0.75～1的值就会进行自动扩容。

存取过程（以iOS方法缓存列表底层实现为例）

example：Class内部结构中有个方法缓存列表，当objc_msgSend进行到搜索方法缓存列表的步骤时，为使查找更高效，缓存列表的底层就是通过哈希表实现对调用过的方法的缓存。
1.存
（1）根据key计算出索引值
（2）如果该索引中没有元素，就存入键值对
（3）如果该索引中有元素，索引冲突，就对索引进行+1或-1进行存储
（4）如果当前已存在的所有索引都有元素，就进行哈希表的扩容
（5）设置新空间是旧空间的2倍
（6）重新分配内存
（7）重新设置掩码_mask = newCapacity-1
（8）会将旧内存释放掉，清空缓存

• objc_cache.mm源码解析

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
    cacheUpdateLock.assertLocked();
    // Never cache before +initialize is done
    if (!cls->isInitialized()) return;
    // Make sure the entry wasn't added to the cache by some other thread 
    // before we grabbed the cacheUpdateLock.
    if (cache_getImp(cls, sel)) return;
    cache_t *cache = getCache(cls);
    cache_key_t key = getKey(sel);
    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = cache->occupied() + 1;
    mask_t capacity = cache->capacity();
    if (cache->isConstantEmptyCache()) {
        // Cache is read-only. Replace it.
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
    }
    else if (newOccupied <= capacity / 4 * 3) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        // Cache is too full. Expand it.
        cache->expand();
    }
    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot because the 
    // minimum size is 4 and we resized at 3/4 full.
    bucket_t *bucket = cache->find(key, receiver);
    if (bucket->key() == 0) cache->incrementOccupied();
    //设置bucket中的key和imp
    bucket->set(key, imp);
}
//扩容
void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    //新的空间是旧的空间的2倍
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;
    if ((uint32_t)(mask_t)newCapacity != newCapacity) {
        // mask overflow - can't grow further
        // fixme this wastes one bit of mask
        newCapacity = oldCapacity;
    }
    //重新分配内存
    reallocate(oldCapacity, newCapacity);
}

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    bool freeOld = canBeFreed();
    bucket_t *oldBuckets = buckets();
    bucket_t *newBuckets = allocateBuckets(newCapacity);
    // Cache's old contents are not propagated. 
    // This is thought to save cache memory at the cost of extra cache fills.
    // fixme re-measure this
    assert(newCapacity > 0);
    assert((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
    //会重新设置最新的_mask = newCapacity - 1;
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        //会将旧的释放掉，清空缓存
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

2.取
（1）通过key得到索引
（2）do-while循环，如果散列表元素的key恰好等于按位与掩码（&_mask）取出的索引，就直接返回
（3）如果不是，就将索引-1继续查找

• objc_cache.mm源码解析

bucket_t * cache_t::find(cache_key_t k, id receiver)
{
    assert(k != 0);
    //返回buckets散列表
    bucket_t *b = buckets();
    mask_t m = mask();
    //得到索引
    mask_t begin = cache_hash(k, m);
    mask_t i = begin;
    do {
        //如果buket_t的索引的恰好等于通过&_mask取出的索引，就直接返回
        if (b[i].key() == 0  ||  b[i].key() == k) {
            return &b[i];
        }
    } while ((i = cache_next(i, m)) != begin);
    //如果不是，直接i-1，如果减到0还不行，就直接是_mask（相当于再从最后一位继续减）
    
    // hack
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)k, cls);
}

static inline mask_t cache_hash(cache_key_t key, mask_t mask) 
{
    //按位与mask得到索引
    return (mask_t)(key & mask);
}

#if __arm__  ||  __x86_64__  ||  __i386__
// objc_msgSend has few registers available.
// Cache scan increments and wraps at special end-marking bucket.
#define CACHE_END_MARKER 1
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
#elif __arm64__
// objc_msgSend has lots of registers available.
// Cache scan decrements. No end marker needed.
#define CACHE_END_MARKER 0
static inline mask_t cache_next(mask_t i, mask_t mask) {
    //arm64架构，索引-1
    return i ? i-1 : mask;
}

总结

Objective-C中的实现，优缺点并存，但相对于实际情况而言，还是优点大于缺点。因为对于方法缓存列表，一般不会有大量的数据，扩容或许是少数情况。此时，你可能会有疑问，当数据量少的时候，岂不是牺牲了内存？然而，哈希表就是采用了空间换时间，牺牲内存空间，换取存取效率的方法。所以，整体符合需求即可。
优点：
整体而言，提升了存取效率，时间复杂度为O(1)，无需遍历。
缺点：
当哈希表比较大时，如果扩容会导致瞬间效率降低。

不同编程语言，哈希表的实现也各有特点，但是本质和原理不变。

例如：
对于大量的数据或者数据库中的存取，Java和Redis也有自己的优化方法。
1.Java中，当哈希函数不合理导致链表过长时，会使用红黑树来保证插入和查找的效率。
2.Redis 使用增量式扩容方法优化了这个缺点，同时还有拉链法的实现(放在链表头部头插，因为新插入的调用概率会高)。