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

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

原理

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

优点

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

缺点

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

设计初衷

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

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

结构

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.hArrayIntMap.c。Key作为integer我使用了intptr_t,这样就可以存放指针类型,从而可以映射指针对象。

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


「ArrayStrMap(Key, Value)」

相关文章
相关标签/搜索