「游戏引擎Mojoc」(9)C使用二分查找实现泛型字典映射

字典映射是最基础，最重要的数据结构，通常会利用哈希表来实现。Mojoc提供了另外一种形式的实现，通过数组和二分查找策略，来完成字典数据的映射。源代码在这里：ArrayStrMap.h。

原理

字典映射的核心在于，如何把一个字符串，通过某个策略映射到一个唯一的标识上。利用hash算法生成hash code，然后映射到数组index上就是一种方法。Mojoc ArrayStrMap的思路很简单直接，就是把字符串排序，然后利用二分查找，来搜索查找。

优点

• 实现简单，没有hash算法的选择，冲突处理，容量调优，索引映射，再散列等等。
• 内存紧凑，遍历速度快，缓存命中率高。
• 元素保持有序。
• 可以像数组一样添加删除元素。

缺点

• 添加删除元素速度慢，受元素个数影响较大。
• 查找元素速度，随着元素个数增加而增加。

设计初衷

用C完整实现一个高效的hash map是很有难度的。并且hash算法的选择各有利弊，hash冲突后形成链表的策略给我感觉很不简洁。如果选用现有开源的实现，就会有代码风格统一问题，移植问题，尤其是C语言对于宏的使用，增加了代码的复杂性和阅读难度。

所以退而求其次，使用 数组排序 + 二分查找 的方式来实现一个简单的版本。如果在元素数量很少，一般200以内，查找效率几乎可以忽略不计。在尽量不去删除元素又可以避开一部分开销。结果ArrayStrMap在使用过程中得到了出乎意料的结果，稳定好用简单。

结构

typedef struct
{
    char*  key;
    int    keyLength;

    /**
     * value 数据会按照valueTypeSize拷贝到valuePtr指向的内存空间
     */
    void*  valuePtr;
}
ArrayStrMapElement;


typedef struct
{
    /**
     * 元素的类型大小，也就是泛型T
     */
    int                            valueTypeSize;

    /**
     * 存放所有的 ArrayStrMapElement 
     */
    ArrayList(ArrayStrMapElement*) elementList[1];
}
ArrayStrMap;

• ArrayStrMapElement 是字典的数据，包含了字典的key值和value值。
• ArrayStrMap 包含一组ArrayStrMapElement指针，通过key排序存放。
• valueTypeSize 就是泛型的机制，代表了value的数据长度。
• valuePtr 指向了实际value的内存地址，value的数据类型由valueTypeSize决定。

#define ArrayStrMap(keyName, valueType) ArrayStrMap

• 一种泛型可读性的标识。比如ArrayStrMap(filePath, SkeletonData*) 就代表了key是文件路径，value是骨骼数据。

接口设计

// 映射元素k-v
void* (*TryPut)(ArrayStrMap* arrayStrMap, char* key, void* valuePtr);

// 查找元素
void* (*Get)(ArrayStrMap* arrayStrMap, char* key, void* defaultValuePtr);

// 尝试查替换元素
void* (*TrySet)(ArrayStrMap* arrayStrMap, char* key, void* valuePtr);

// 尝试删除元素
bool (*TryRemove)(ArrayStrMap* arrayStrMap, char* key);

核心的API就这个，但在设计上有一些小细节，比如：
* Try前缀代表了操作可能失败，也就是key查找失败。
* Get 提供了找不到key时候，返回一个默认值。
* TrySet是替换value的意思。

当然，这些API都可以提供一组，宏定义的快捷方式。

// 尝试添加映射
#define AArrayStrMap_TryPut(arrayStrMap, key, value) \
    AArrayStrMap->TryPut(arrayStrMap, key, &(value))


// 查找元素
#define AArrayStrMap_Get(arrayStrMap, key, valueType) \
    (*(valueType*) AArrayStrMap->Get(arrayStrMap, key, NULL_PTR))


// 查找元素并返回指针
#define AArrayStrMap_GetPtr(arrayStrMap, key, valueType) \
    ((valueType*) AArrayStrMap->Get(arrayStrMap, key, NULL))


// 尝试替换value
#define AArrayStrMap_TrySet(arrayStrMap, key, value) \
    AArrayStrMap->TrySet(arrayStrMap, key, &(value));

核心算法

核心算法自然就是二分查找了，查找，插入都是在二分查找基础上构建的。

/**
 * Search index of key, if negative not found then return "-insertIndex - 1"
 * so insert index is "-BinarySearch() - 1"
 */
static inline int BinarySearch(ArrayList* elementList, char* key, int keyLength)
{
    int high  = elementList->size;
    int low   = -1;
    int guess = -1;

    while (high - low > 1)
    {
        // not consider int overflow
        guess                       = (high + low) >> 1;
        ArrayStrMapElement* element = AArrayList_Get(elementList, guess, ArrayStrMapElement*);

        if (element->keyLength < keyLength)
        {
            low  = guess;
        }
        else if (element->keyLength > keyLength)
        {
            high = guess;
        }
        else if (element->keyLength == keyLength)
        {
            int cmp = memcmp(element->key, key, keyLength);

            if (cmp < 0)
            {
                low  = guess;
            }
            else if (cmp > 0)
            {
                high = guess;
            }
            else if (cmp == 0)
            {
                // cmp 0 means find the key
                return guess;
            }
        }
     }

    // if guess == high the guess is bigger than key in ArrayStrMap and insert value at guess

    if (guess == low)
    {
        // the guess is smaller than key in ArrayStrMap and insert value behind
        // or if ArrayStrMap empty then guess is -1, also do this make guess at 0
        guess++;
    }

    // when ArrayStrMap empty guess is 0, so we -1 make sure return negative value
    return -guess - 1;
}

这是一个典型的二分查找算法，有一些细节考虑：
* 一个重要的优化，排序首先按照，key的长度，并且keyLength会被缓存。
* 其次，key长度相同，在根据字母的字典顺序，也就是使用memcmp来判断。
* 找到了返回索引，否则返回可以插入索引减一的位置，就是-guess - 1，这样找不到插入位置就可以是，”-BinarySearch() - 1`。这是为了优化，先查找存在性，如果没有就插入的情况，可以直接在正确的index插入，而不需要再查找一次。

泛型

泛型的意义就是，ArrayStrMap可以存放任意类型的元素。这个机制就在于valueTypeSize，初始化的时候设定了valueTypeSize，后面一切元素的操作都会建立在valueTypeSize的基础上进行数据的操作。从而实现了不同元素类型共享一套API。

最后

虽然这是一个简单版本的字典映射实现，但在真正构建的时候，仍然有很多的优化和细节问题需要处理。尤其还有很多的API的设计都是在工程实践的过程中迭代出来的，具体就请看源代码了，ArrayStrMap.c。

另外，这是一个key为字符串的实现版本，同样的会有一个integer版本的实现，机制是完全相同的，只是key的数据类型不同，具体代码在这里 ArrayIntMap.h 和 ArrayIntMap.c。Key作为integer我使用了intptr_t，这样就可以存放指针类型，从而可以映射指针对象。

Mojoc的泛型ArrayStrMap的实现，只使用了C语言的标准库，可以拿出来独立使用。更多的使用示例请看scottcgi/Mojoc的源代码，全局搜索ArrayStrMap。

---

「ArrayStrMap(Key, Value)」