OC类和对象之四hash结构

1，简介

hash是一种将关键字data的key值进行散列存储的技术，它可以根据关键字的key值得到关键字的实际存储位置，它查找的效率为O(1)级别，现实中根据冲突的情况可能会是1点多的情况。

2，举例

    例如现在有100个关键字结构体，它们的key的取值范围为1-10000，如果内存够用的话，可以直接分配10000个空间，根据关键字的key值直接放入到对应的空间里面就行。但是一般情况下是不太可能有全部的空间的，例如对于指针类型的数据进行hash，它们的取值范围为全部的4个或者8个字节数据，这种情况就不能直接以关键字的key值作为实际的存储地址了，但是我们可以进行一次hash处理，将大范围的数据经过函数处理成小范围的数据。例如对于4字节指针，它的取值范围为0~2^32-1,
指针本身的取值范围很大，如果预估计key值在100个以内，那么对于指针p，可以采用hash(key) = (int)p %
101，这样上亿的范围的key经过求余就被处理成了0-100的范围。毫无疑问，不同的key可能会有相同的hash值，这就是常说的冲突。下面提供一种常见的解决冲突的方法-链地址吧。它通过相同的hash值的关键字放到一个链表里。对于上述情况首先是一个0-100的数组，数组元素就是一个链表。如果需要查找一个指针p，首先进行(int)p%101得到它的hash值，然后以hash值作为数组索引，找到一个链表；然后在链表中进行从前向后的遍历即可。

3，Object-C库

    苹果object-c源代码的hash结构就是采用这种各大数据结构体教材中都会讲的类似于链地址的方式解决冲突的。不过它的链地址不是一个链表，而是一个数组结构，而且当出现冲突的时候，它通过释放原来的数组结构，并进行分配大一个数组结构来存放新的元素的。它的劣势很明显，如果冲突比较多会频繁的alloc和free，它的优势是不用二级指针的指向来找到元素，为了进一步优化，它对于一个和两个元素采用了oneOrMany的union结构，这样对一个的元素进行hashGet会减少一次二级指针的获取操作，这应该是预估了冲突一般情况下都很少发生才这样做的。整个Hash结构是一个大数组，数组的基地址是buckets。每一个bucket可以看成是一个小数组，它存储着具有相同hash值的冲突列表。

3.1，整体Hash结构

    首先看一下整个hash结构体，我已经在代码中加入了个人注释：

typedef struct {
    const NXHashTablePrototype  *prototype OBJC_HASH_AVAILABILITY; //hash结构所使用的hash，以及比较函数的函数表。
    unsigned              count OBJC_HASH_AVAILABILITY; //hash结构已经有的关键字个数
    unsigned              nbBuckets OBJC_HASH_AVAILABILITY; //此hash表的容量大小，随着count的增多会动态扩容
    void                  *buckets OBJC_HASH_AVAILABILITY;  //hash表的数组基地址
    const void                  *info OBJC_HASH_AVAILABILITY; //未关注
} NXHashTableOBJC_HASH_AVAILABILITY;

count是已有的关键字个数，每次进行插入时候会增1.

nbBuckets是hash表的容量。

buckets是hash表的数组基地址

3.2，Hash数组基地址

    buckets是hash表的数组基地址， 它之所以采用buckets指针，是为了能够进行动态的扩容。当hash->count >hash->nbBuckets时候，它会进行扩容，扩容的新大小是原来的2倍加1.

代码如下:

if (table->count >table->nbBuckets) _NXHashRehash (table);
#   define MORE_CAPACITY(b) (b*2+1)
static void _NXHashRehash (NXHashTable*table)
{
    _NXHashRehashToCapacity (table,MORE_CAPACITY(table->nbBuckets)); //扩容成原来的2倍加1.
}

3.3，Hash结构体的虚函数表

hash函数指针结构体，存储着hash函数，判相同函数，以及释放内存的函数指针。

typedef struct {
    uintptr_t (*hash)(const void *info, const void *data);
    int      (*isEqual)(const void *info, const void *data1, const void *data2);
    void     (*free)(const void *info, void *data);
    int      style; /* reserved for future expansion; currently0 */
} NXHashTablePrototype;

hash表的元素需要满足两种约束：

    1，相同的data值应该具有相同的hash值，即data1 = data2 => hash(data1) = hash(data2)

    2，isEqual函数可以确定两个data是否相同，即isEqual(data1, data2) => data1= data2

3.4，虚函数表的初始化及具体实现

3.4.1，初始化

    这个为hash函数结构体的内容，存放着函数指针以表示不同的具体实现，针对ptr和str采用了不同的函数实现。通过这种方式实现了C++的继承结构。

const NXHashTablePrototypeNXPtrPrototype = {
    NXPtrHash, NXPtrIsEqual, NXNoEffectFree, 0
};
 
const NXHashTablePrototypeNXStrPrototype = {
    NXStrHash, NXStrIsEqual, NXNoEffectFree, 0
};

3.4.2，函数实现

以下为真正的函数实现，针对ptr和str采用不同的函数，类似于C++的继承。方法的实现都比较简单，PtrHash使用的异或，比较使用的是直接判等。

uintptr_t NXPtrHash (const void *info, const void *data) {
    return (((uintptr_t) data)>> 16) ^ ((uintptr_t) data);
};
 
uintptr_t NXStrHash (const void *info, const void *data) {
    register uintptr_t    hash = 0;
    register unsigned char      *s = (unsigned char *) data;
    /* unsigned to avoid a sign-extend */
    /* unroll the loop */
    if (s) for (; ; ) {
        if (*s == '\0') break;
        hash ^= (uintptr_t) *s++;
        if (*s == '\0') break;
        hash ^= (uintptr_t) *s++ << 8;
        if (*s == '\0') break;
        hash ^= (uintptr_t) *s++ << 16;
        if (*s == '\0') break;
        hash ^= (uintptr_t) *s++ << 24;
      }
    return hash;
};
int NXPtrIsEqual (const void *info, const void *data1, const void *data2) {
    return data1 == data2;
};
int NXStrIsEqual (const void *info, const void *data1, const void *data2) {
    if (data1 == data2) return YES;
    if (! data1) return ! strlen ((char *) data2);
    if (! data2) return ! strlen ((char *) data1);
    if (((char *) data1)[0] != ((char *) data2)[0]) return NO;
    return (strcmp ((char *) data1, (char *) data2)) ? NO : YES;
};
 
void NXReallyFree (const void *info, void *data) {
    free (data);
};

3.5，Hash数组的元素

    HashBucket是hash表的元素，它存储着具有相同hash值的所有key。它为了高效率获取只有一个元素的情况，使用了union oneOrMany结构。当只有

一个元素的时候，one就指代这data值，当有多个元素的时候，需要通过访问many数组，方可获取。

    具体代码如下：

/* In order to improveefficiency, buckets contain a pointer to an array or directly the data when thearray size is 1 */
typedef union {
    const void      *one;
    const void      **many;
} oneOrMany;
/* an optimizationconsists of storing directly data when count = 1 */
 
typedef struct    {
    unsigned count;
    oneOrMany elements;
} HashBucket;

3.6，根据key获取数组索引地址

BUCKETOF是一个宏，它返回指定data值经过hash后的数组地址

#   define   BUCKETOF(table,data) (((HashBucket*)table->buckets)+((*table->prototype->hash)(table->info, data) %table->nbBuckets))

主要分三步：

    1，(*table->prototype->hash)(table->info,data)这个表示调用具体hash表的函数表的hash函数。对于ptr型的实际调用是NXPtrHash函数。

    2，((*table->prototype->hash)(table->info,data) % table->nbBuckets) 这个表示将得到的hash值进行求余，以对应于hash桶的索引。

    3，(((HashBucket*)table->buckets)+((*table->prototype->hash)(table->info, data) %table->nbBuckets)) 这个表示将索引加上基地址buckets，即时对应的data散列到的HashBucket数组中

3.7，Hash数组的插入

3.7.1，描述

这是hash插入的函数。

分为三种情况

    1，j==0，此hash没有元素，直接将data放入bucket->elements.one = data

    2，j==1，已经有一个元素，需要重分配一个两个元素的数组，将data插入前面。newt[1] =bucket->elements.one;   *newt = data;

    3，j >1，超过一个元素，同样重分配j+1个元素，然后进行copy，并释放掉原来的内存。

注意：当table->count大于桶的个数的时候，会进行扩容。

3.7.2，扩容

代码：

void *NXHashInsert (NXHashTable*table, const void *data) {
    HashBucket      *bucket= BUCKETOF(table, data);
    unsigned j = bucket->count;
    const void      **pairs;
    const void      **newt;
    void      *z = ZONE_FROM_PTR(table);
 
    if (! j) {
        bucket->count++;bucket->elements.one = data;
        table->count++;
        return NULL;
      };
    if (j == 1) {
       if (ISEQUAL(table, data,bucket->elements.one)) {
            const void      *old = bucket->elements.one;
            bucket->elements.one = data;
            return (void *) old;
          };
        newt = ALLOCPAIRS(z, 2);
        newt[1] = bucket->elements.one;
        *newt = data;
        bucket->count++;bucket->elements.many = newt;
        table->count++;
        if (table->count >table->nbBuckets) _NXHashRehash (table);
        return NULL;
      };
    pairs = bucket->elements.many;
    while (j--) {
        /* we don't cache isEqualbecause lists are short */
       if (ISEQUAL(table, data,*pairs)) {
            const void      *old = *pairs;
            *pairs = data;
            return (void *) old;
          };
        pairs ++;
      };
    /* we enlarge this bucket; and put new datain front */
    newt = ALLOCPAIRS(z, bucket->count+1);
    if (bucket->count) bcopy ((const char*)bucket->elements.many,(char*)(newt+1), bucket->count *PTRSIZE);
    *newt = data;
    free ((void*)bucket->elements.many);
    bucket->count++;bucket->elements.many = newt;
    table->count++;
    if (table->count > table->nbBuckets)_NXHashRehash (table);
    return NULL;  }

3.8，Hash数组扩容

当table->count大于Hash数组的个数的时候，开始进行扩容。扩容将新的容量变成原来的容量加1.但是注意扩容不能简单的内存copy，这主要是因为BUCKETOF最后的求余是使用的table->nbBuckets。也就是说相同的key值在不同的大小的Hash表中具有不同的数组索引，直接内存copy会使原来的Hash失效，因此只能采用再次插入的办法，是一个很费效率的工作，因此初始化的时候分配一个差不多适合大小的数组是一个很大的必要。

if (table->count> table->nbBuckets) _NXHashRehash (table);
#   defineMORE_CAPACITY(b) (b*2+1)
static void _NXHashRehash(NXHashTable *table)
{
   _NXHashRehashToCapacity (table, MORE_CAPACITY(table->nbBuckets)); //扩容成原来的2倍加1.
}

3.9，Hash数组的查找

这是个hash查找的函数，非常简单。

仍然分三种情况

    1，j==0，表明此索引还没有被hash到，直接返回空

    2，j==1，表明只有一个元素，因此使用ISEQUAL与bucket->elements.one进行比较，相同则返回。

3，j>1，表明多于一个元素，需要进行遍历many数组，逐个比较。

判断是否两个key是否相同的宏，需要使用上面提到的虚函数表。

#define ISEQUAL(table, data1, data2) ((data1 == data2) ||(*table->prototype->isEqual)(table->info, data1, data2))

库代码：

void *NXHashGet (NXHashTable*table, const void *data) {
    HashBucket      *bucket= BUCKETOF(table, data);
    unsigned j = bucket->count;
    const void      **pairs;
 
    if (! j) return NULL;
    if (j == 1) {
       return ISEQUAL(table, data,bucket->elements.one)
          ? (void *) bucket->elements.one: NULL;
      };
    pairs = bucket->elements.many;
    while (j--) {
        /* we don't cache isEqualbecause lists are short */
       if (ISEQUAL(table, data,*pairs)) return (void *) *pairs;
        pairs ++;
      };
    return NULL;
}