从排序说起

一种很棒的排序算法，木桶排序（计数排序）。

算法如下，比如[ 1 9 3 7]需要排序。按木桶排序，我们要准备好10个桶，比如我们建立一个数组a[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0,} 0代表没使用。
我们依次扫描 1 9 3 7 ，
遇到1 ，赋值a[1] = 1 // 1代表这个桶使用了
遇到9 ，赋值a[9] = 1
遇到3，赋值a[3] = 1
遇到7 ，赋值a[7] = 1
那么就排好了，我们再建立一个数组b，通过扫一遍a数组，遇到数组元素里面的值是1的，就把a数组的下标放到b数组里。最后的b数组就是这样{1, 3, 7, 9}

我们知道，需要比较的排序，最快的时间复杂度是O(NlogN)。木桶很快，可以做到O(N)。但是也不是完美的，他的空间复杂度取决于最大的那个元素。当然实际使用我们不可能用这么多桶，毕竟内存不是无限的。这时候我们就想，能不能把下标的范围缩小？例如我们只有5个桶，我要把1 9 3 7 都放进这五个桶里。那么我们只要把每个数字对 5 求模，就能实现我们的想法。最大的9，求模后得4。这就是NSDictionary的基本思想。

HashTable

NSDictionary是基于HashTable实现的一种称为 key-value 的数据结构。跟桶排序一样，hash利用一个叫hash的函数把key约束在0 ~ tablesize - 1 范围内。这里我们不打算一开始谈论HashTable的各种优缺点，我们的目的是写一个简单的，具有NSDictionary类似功能的轮子。在实现我们需求过程中去深入了解HashTable的各种特点。我们的字典只支持存储字符串，没有线程安全的考虑，但是实现实现这样的轮子可以让我们对hashtable这种数据结构了然于胸，对于字典我们不在感觉到神秘，实际上，很轻易的也能让我们的字典支持泛型。

准备材料
我们给这个轮子起个名字叫YesDictionary
类似NSDictionary，我们需要做几个决定：
1 容量选择
2 桶数量的选择
3 hash函数的选择
4 填充因子
5 冲突解决办法

容量选择

在决定给我们的YesDictionary安排多少个桶的时候，我们先去 CFDictionary找点启发。
在早期的CF文件中，Dictionary有如下定义

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 */
    const void **_keys;        /* can be NULL if not allocated yet */
    const void **_values;    /* can be NULL if not allocated yet */
};

在新的CF文件中，apple 新加入了叫CFBasicHashXX的相关基础类，因为很多数据结构都使用到hash，例如Set，Dictionary等。
在CFDictionary类的定义中，我们看到了_capacity，_bucketsNum，容量和桶的数量。apple给这两个变量定义了取值范围

static const uint32_t __CFDictionaryCapacities[42] = {
    4, 8, 17, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349,
    15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498,
    3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324,
    228826127, 370248451, 599074578, 969323029, 1568397607, 2537720636U
};

static const uint32_t __CFDictionaryBuckets[42] = {    // primes
    5, 11, 23, 41, 67, 113, 199, 317, 521, 839, 1361, 2207, 3571, 5779, 9349, 15121,
    24473, 39607, 64081, 103681, 167759, 271429, 439199, 710641, 1149857, 1860503, 3010349,
    4870843, 7881193, 12752029, 20633237, 33385273, 54018521, 87403763, 141422317, 228826121,
    370248451, 599074561, 969323023, 1568397599, 2537720629U, 4106118251U
};

上面的意思是，如果字典容量是4，就准备5个桶，如果容量是8，就准备11个桶，很显然桶的数量必须比容量要大。这就叫字典的扩充。仔细看我们还能发现一些规律，就是桶数量都是素数。为了能把key放在正确的桶里，我们需要对key进行hash，或者叫压缩，取特征，怎样都行。《算法导论》建议桶的数量取素数比较保险。取素数的目的，是为了把一系列的key hash后求模，他们的值能均匀分布在0 ~ tablesize - 1 的范围里，减少冲突(不同的key 产生同样的hash值称为冲突，毕竟一个桶不能放两个key)。至于其中的数学论证，有兴趣的可以自行了解。
因此，我们的 YesDictionary 使用桶的数量也取素数。

目前解决只是桶的数量，还有容量，这个跟填充因子有关联，我们一起讨论（呼，离着手编码还有一段距离呢）。填充因子其实就是容量和桶的数量的比值。填充因子低了，桶的利用率就低了，填充因子高了，发生冲突的概率就大大的提升，效率就变低。大部分hashmap 的填充因子选择了0.75 ，至于为什么不是0.6，0.5，这就涉及到hash碰撞中，节点出现的频率在hash桶中遵循泊松分布，也就是说填充因子超过0.75，冲突的几率就大大增加。所以我们的填充因子也选择0.75。

先给出我们山寨版的YesDictionary的结构定义

typedef signed int YesIndex;
typedef enum {
    YES_EMPTY = 0,
    YES_FULL,
    YES_DEL
} YesStatus;


typedef struct _YesDictionary {
    YesIndex count; //字典键值对的个数
    YesIndex capacityLevel; //容量等级，扩充的时候用到
    YesIndex capacity; //字典容量
    YesIndex bucketsNum; //字典桶的个数
    YesStatus *marker;  // fixit 标记每个桶的状态
    CFStringRef *keys; //字典的keys
    CFStringRef *values; //字典values
} YesDictionary, *YesDictionaryRef;

我们用YesStatus表示桶的状态，它具有空桶，桶被填充，桶的数据被删除三种状态。
CFDictionary _marker变量，看上去像个整型，其实它是一个指针，地址是 0xa1b1c1d3，无法得知这个地址指向哪里，但是苹果用这个对桶的状态进行了标记，我们YesDictionary开辟了一个marker数组进行标记。这稍微多占用了一些内存。

下面是我们打算使用的桶

static int _capacity[MAX_LEVEL] = {
    4, 8, 17
};
static int _bukets[MAX_LEVEL] = {
    5, 11, 23
};

MAX_LEVEL 定义为3 ，意味着YesDictionary 只支持两次扩容，也就是我们的桶最多只有23个，后面可以任意添加。目前仅作说明使用。

我们先看怎么创建一个YesDictionary字典

YesDictionaryRef YesDictionaryCreate(void) {
    YesDictionaryRef dic = malloc(sizeof(YesDictionary));
    memset(dic, 0, sizeof(YesDictionary));
    return _YesDictionaryInit(dic);
}

这段代码我们申请了一小块malloc控制的内存，并且用memset把这段内存清零。然后使用_YesDictionaryInit函数初始化YesDictionary。

YesDictionaryRef _YesDictionaryInit(YesDictionaryRef dic) {
    dic->capacityLevel = 0;
    dic->capacity = _capacity[dic->capacityLevel];
    dic->bucketsNum = _bukets[dic->capacityLevel];
    dic->count = 0;
    size_t size = sizeof(CFStringRef);
    YesIndex num = dic->bucketsNum;
    CFStringRef* keys = calloc(num, size);
    CFStringRef* values = calloc(num, size);
    YesStatus* marker = calloc(num, sizeof(YesStatus));
    dic->keys = keys;
    dic->values = values;
    dic->marker = marker;
    return dic;
}

_YesDictionaryInit 给字典进行初始化，分配了keys values marker所需要的内存。这里用了calloc函数，这个函数支持将分配的内存清零。

接着，实现字典的键值对添加

void YesDictionaryAdd(YesDictionaryRef dic, CFStringRef key, CFStringRef value) {
    
    float factor = dic->count * 1.0f / dic->capacity;
    if (factor > FILL_FACTOR) {
        _YesDictionaryGrow(dic);
    }
    
    YesIndex match;
     YesStatus status = _findBucketIndex(dic, key, &match);
    if (match != kCFNotFound) {
        if (YES_FULL == status) {
            CFRelease(dic->keys[match]);
            CFRelease(dic->values[match]);
        } else {
            ++dic->count;
        }
        dic->marker[match] = YES_FULL;
        dic->keys[match] = key;
        dic->values[match] = value;
        CFRetain(key);
        CFRetain(value);
    }
}

在添加前，我们根据填充因子决定字典是否需要扩容。如果需要，就执行扩容方法_YesDictionaryGrow，否则，调用_findBucketIndex函数寻找一个可以使用的桶。添加键值对，我们需要对其进行一次retain，防止释放，同时把桶的状态标记为YES_FULL。

_YesDictionaryGrow 实现了字典的扩容

void _YesDictionaryGrow(YesDictionaryRef dic) {
    if (dic->capacityLevel == MAX_LEVEL - 1) {
        printf("小demo，不能增长了\n");
        return;
    }

    YesStatus* oldMarker = dic->marker;
    CFStringRef* oldKeys = dic->keys;
    CFStringRef* oldValues = dic->values;
    YesIndex oldBucketsNum = _bukets[dic->capacityLevel];
    
    ++ dic->capacityLevel;
    dic->capacity = _capacity[dic->capacityLevel];
    dic->bucketsNum = _bukets[dic->capacityLevel];
    size_t size = sizeof(CFStringRef);
    YesIndex num = dic->bucketsNum;
    CFStringRef* keys = calloc(num, size);
    CFStringRef* values = calloc(num, size);
    YesStatus* marker = calloc(num, sizeof(YesStatus));
    dic->marker = marker;
    dic->keys = keys;
    dic->values = values;
    
    for (YesIndex i = 0; i < oldBucketsNum; ++i) {
        if (oldMarker[i] != YES_FULL) continue;
        YesIndex match;
        _findBuketIndex(dic, oldKeys[i], &match);
        marker[match] = YES_FULL;
        keys[match] = oldKeys[i];
        values[match] = oldValues[i];
    }

    free(oldMarker);
    free(oldKeys);
    free(oldValues);
}

这个函数逻辑很简单，通过递增capacityLevel 为字典选择下一级的桶，然后把就旧桶上的key-value 通过_findBuketIndex 映射到新的桶里。需要注意的是，这里不需要对 key-value retain操作，并且记得释放 旧桶 和旧标记。

_findBuketIndex函数是整个字典的关键，它函数指示了我们的 key-value 要存放到那个桶里

YesStatus _findBuketIndex(YesDictionaryRef dic, const CFStringRef key, YesIndex* found) {
    *found = kCFNotFound;
    YesIndex probe = _hash(key) % dic->bucketsNum;
    YesStatus *marker = dic->marker;
    CFStringRef *keys = dic->keys;
    YesIndex probeStep = 1;
    while (true) {
        YesStatus status = marker[probe];
        switch (status) {
            case YES_EMPTY: {
                *found = probe;
                return YES_EMPTY;
            }
            case YES_FULL: {
                if (kCFCompareEqualTo == CFStringCompare(key, keys[probe], kCFCompareCaseInsensitive)) {
                    *found = probe;
                    return YES_FULL;
                }
                probe += probeStep;
                break;
            }
            case YES_DEL: {
                *found = probe;
                return YES_DEL;
            }
        }
        if (probe >= dic->bucketsNum) {
            probe -= dic->bucketsNum;
        }
    }
}

YesIndex probe = _hash(key) % dic->bucketsNum; 这句代码计算了key 的hash值。其中关键是hash函数的实现，在apple公开的文件中，CFDictionary 的hash函数笔者找不到其实现。请注意的是，CFDictionary有一个hash函数如下

CF_PRIVATE CFHashCode __CFBasicHashHash(CFTypeRef cf) {
    CFBasicHashRef ht = (CFBasicHashRef)cf;
    return CFBasicHashGetCount(ht);
}

这个函数简单的返回字典键值对的数量，它并不是对key的hash，而是字典本身的的hash。因为假如这是对key的hash，那么插入和查找的时候，hash的结果会不一致。
以下是YesDictionary 的hash函数，这个叫time33，大部分hashtable都使用这个函数，他是简单不断的乘以33而得名。time33简单，并且能取得很好的分布效果。同时我们给hash一个初值 MAGIC_INIT，值为5381，据说能获得更好的分布效果。

uint32_t _hash(CFStringRef str) {
    char buffer[BUFSIZE];
    CFStringEncoding encoding = kCFStringEncodingUTF8;
    const char *ptr = CFStringGetCStringPtr(str, encoding);
    if (ptr == NULL) {
        if (CFStringGetCString(str, buffer, BUFSIZE, encoding)) ptr = buffer;
    }
    return time33(ptr);
}

uint32_t time33(const char *str) {
    uint32_t hash = MAGIC_INIT;
    while (*str) {
        hash += (hash << 5 ) + (*(str++));
    }
    return (hash & 0x7FFFFFFF);
}

_findBuketIndex同时处理了key相同的情况， YesDictionary 的key只能唯一，所以我们简单的将上一个key-value覆盖。如果大量的key hash后产生的桶的位置一样，这种冲突现象称为一次堆积，或叫一次聚集。 _findBuketIndex解决冲突使用了开放定址法，简单的将hash值 + 1 ，循环寻找下一个桶，直到找到为止。这种方法比拉链法简单，有效。它不像拉链法需要同时维护链表这种数据结构，同时，简单的地址偏移，实现成本很低。除此之外，还有再散列等，再散列有可能造成二次堆积，或叫二次聚集。。。有关解决冲突的方法，有兴趣的可以自行深入，这里就不再讨论了。

到目前为止，YesDictionary 插入实现了。为了方便观察，我们给YesDictionary实现 show 和 relaese 方法。

void YesDictionaryShow(YesDictionaryRef dic) {
    CFStringRef *keys = dic->keys;
    CFStringRef *values = dic->values;
    YesStatus *marker = dic->marker;
    CFMutableStringRef showString = CFStringCreateMutable(kCFAllocatorDefault, 1024);
    for (YesIndex i = 0, count = dic->bucketsNum; i != count; ++i) {
        if (marker[i] != YES_FULL) continue;
        CFStringAppend(showString, keys[i]);
        CFStringAppendCString(showString, " = ", kCFStringEncodingUTF8);
        CFStringAppend(showString, values[i]);
        CFStringAppendCString(showString, "\n", kCFStringEncodingUTF8);
    }
    CFShow(showString);
    CFRelease(showString);
}

void YesDictionaryRelease(YesDictionaryRef dic) {
    CFStringRef *keys = dic->keys;
    CFStringRef *values = dic->values;
    YesStatus *marker = dic->marker;
    for (YesIndex i = 0, count = dic->bucketsNum; i != count; ++i) {
        if (marker[i] != YES_FULL) continue;
        CFRelease(keys[i]);
        CFRelease(values[i]);
    }
    free(marker);
    free(keys);
    free(values);
    free(dic);
}

YesDictionary 的其他删除和查找方法和插入大同小异，这里就不一一实现了。接下来我们看看它能不能工作。

   YesDictionaryRef dic = YesDictionaryCreate();
    
    char key[50], value[50];
    for (int i = 0; i < 13; ++i) {
        sprintf(key, "%d", i);
        sprintf(value, "value(%d)", i);
        CFStringRef cfkey = CFStringCreateWithCString(kCFAllocatorDefault, key, kCFStringEncodingUTF8);
        CFStringRef cfvalue = CFStringCreateWithCString(kCFAllocatorDefault, value, kCFStringEncodingUTF8);
        YesDictionaryAdd(dic, cfkey, cfvalue);
        CFRelease(cfkey);
        CFRelease(cfvalue);
    }
    
    YesDictionaryShow(dic);
    YesDictionaryRelease(dic);

我们创建一个字典dic，并且循环插入0~12做为key，value 就是 value(i)。要注意的是不要插入超过17个元素，因为YesDictionary只有最多23个桶。
在控制台输出如下

pic.png

因为我们是有序输入，所以key分布效果不会太好。不管怎么样，我们的YesDictionary can work 了。

下一篇文章《iOS重做轮子，写一个NSDictionary（二）》，我们继续重做轮子，用红黑树实现一个NSDictionary。