11 November 2016

hash 概述

<img class="img-responsive" src="http://sunznx.github.io/images/php/hash_1.png"/>

按照我的理解,哈希的表示大概就是上面那样来实现,下面给出的是一个 php 的实现,因为在 php 中,没有 列表 (list) 这个数据结构
但是可以用 数组 (array) 来实现,上图可以用下面的 php 代码来表示

class obj {
    public $key;
    public $value;
};

$list0 = [$obj0, $obj1, $obj2, $obj3, $obj4];
$list1 = [];
$list2 = [];
$list3 = [$obj5, $obj6, $obj7];
$list4 = [];
$list5 = [];
$list6 = [$obj8, $obj9];
$list7 = [];

$hash = array(
    0 => $list0,
    1 => $list1,
    2 => $list2,
    3 => $list3,
    4 => $list4,
    5 => $list5,
    6 => $list6,
    7 => $list7
);

用 c 实现的 hash

在 php 中,我们可以用下面的代码来指定一个 key 对应的值为 val

$hashTable['key'] = 'val';

在 c 语言中,数组里面的键值不能是字符串,只能是数字。因此我们需要一个 hashFunc 把 key 这个字符串转成数字。
但是,由于可能存在 不同的字符串 最终会转换成相同的数字,比如 abcd (0123)dcba (3210) ,如果按照字符串的大小来转换

// php
$hashTable['abcd'] = 'val1';
$hashTable['dcba'] = 'val2';

// c
hashTable[6] = 'val1';
hashTable[6] = 'val2';

这个就是 hashTable 冲突 (val2 会将 val1 的值覆盖掉),解决 hashTable 冲突的思路就是让 hashTable[6] 变成一个列表,也就是说可以有多个值

hashTable[6].list.push('abcd', 'val1')
hashTable[6].list.push('dcba', 'val2')    // 现在 hashTable[6] = [{'abcd' => 'val1'}, {'dcba' => 'val2'}]

这时候我们要想得到 'abcd' 这个键值对应的值,就要这样做

foreach (hashTable[6].list as k => v) {
   if (k == 'abcd') {
        return v;
   }

   return 'not found';
}

下面是 c++ 实现的过程

  1. 首先需要一个 obj,主要是为了来实现下面的数据结构

    {'abcd' => 'val1'}
    
    clacss ourObj {
    public:
        const char *key;
        int keylen;
        int value;
    
        ourObj(const char *key, int keylen, int value) {
            this->key    = key;
            this->keylen = keylen;
            this->value  = value;
        }
    };
    
  2. 再来就是需要一个 列表,这个列表要套在一个 HashTable 里面

    class ourHash {
    public:
        list<ourObj> objList;
    };
    
    ourHash hashTable[8];
    
// add
hashTable[6].list.push('abcd', 'val1')
hashTable[6].list.push('dcba', 'val2')    // 现在 hashTable[6].list = [{'abcd' => 'val1'}, {'dcba' => 'val2'}]

// get
foreach (hashTable[6].list as k => v) {
   if (k == 'abcd') {
        return v;
   }

   return 'not found';
}
// 往 hash 表里面添加一个 key, value 结构
void add(const char *key, int keylen, int value) {
    int index         = hashFunc(key, keylen);     // 将字符串转换成数字,按照上面的例子,index = 6
    list<ourObj> *obj = &hashTable[index].objList; // hashTable[6].list

    obj->push_back(ourObj(key, keylen, value));    // hashTable[6].list.push({'key', 'value'})
}

// 从 hash 查找 key 对应 value 值
int get(const char *key, int keylen) {
    int index        = hashFunc(key, keylen);      // 将字符串转换成数字,按照上面的例子,index = 6
    list<ourObj> obj = hashTable[index].objList;   // hashTable[6].list

    /* 遍历链表 */
    list<ourObj>::iterator iter;
    for (iter = obj.begin(); iter != obj.end(); iter++) {
        if (strncmp(iter->key, key, keylen) == 0) {/* find the key */
            return iter->value;                    /* return the value */
        }
    }

    return -1;
}

完整的测试

#include <iostream>
#include <cstring>
#include <list>

using namespace std;

class ourObj {
public:
    const char *key;
    int keylen;
    int value;

    ourObj(const char *key, int keylen, int value) {
        this->key    = key;
        this->keylen = keylen;
        this->value  = value;
    }
};

class ourHash {
public:
    list<ourObj> objList;
};
ourHash hashTable[8];

int hashSize = 8;

int hashFunc(const char *key, int keylen) {
    int total = 0;

    for (int i = 0; i < keylen; i++) {
        int num = key[i] - 'a';
        total += num;
    }

    total = total % hashSize;

    return total;
}

void add(const char *key, int keylen, int value) {
    int index = hashFunc(key, keylen);

    list<ourObj> *obj = &hashTable[index].objList;

    obj->push_back(ourObj(key, keylen, value));
}

int get(const char *key, int keylen) {
    int index = hashFunc(key, keylen);

    list<ourObj> obj = hashTable[index].objList;

    /* 遍历链表 */
    list<ourObj>::iterator iter;
    for (iter = obj.begin(); iter != obj.end(); iter++) {
        if (strncmp(iter->key, key, keylen) == 0) { /* find the key */
            return iter->value;
        }
    }

    return -1;
}

int main(void) {
    add("keya", strlen("keya"), 1);
    add("keyb", strlen("keyb"), 11);

    cout << get("keya", strlen("keya")) << endl; /* 1  */
    cout << get("keyb", strlen("keyb")) << endl; /* 11 */

    return 0;
}

php 内核中的实现

看下面的链接吧,不想再写了 :(
http://www.php-internals.com/book/?p=chapt03/03-01-02-hashtable-in-php

typedef struct bucket {
    ulong h;                       /* 对 char *key 进行 hash 后的值,或者是用户指定的数字索引值 */
    uint nKeyLength;               /* hash 关键字的长度,如果数组索引为数字,此值为 0 */
    void *pData;                   /* 指向 value,一般是用户数据的副本,如果是指针数据,则指向 pDataPtr */
    void *pDataPtr;                /* 如果是指针数据,此值会指向真正的 value,同时上面 pData 会指向此值 */
    struct bucket *pListNext;      /* 整个 hash 表的下一元素 */
    struct bucket *pListLast;      /* 整个哈希表该元素的上一个元素 */
    struct bucket *pNext;          /* 存放在同一个 hash Bucket 内的下一个元素 */
    struct bucket *pLast;          /* 同一个哈希 bucket 的上一个元素 */
    char arKey[1];                 /* 保存当前值所对于的 key 字符串,这个字段只能定义在最后,实现变长结构体 */
} Bucket;

typedef struct _hashtable {
    uint nTableSize;               /* hash Bucket 的大小,最小为 8,以 2x 增长 */
    uint nTableMask;               /* nTableSize-1, 索引取值的优化 */
    uint nNumOfElements;           /* hash Bucket 中当前存在的元素个数,count()函数会直接返回此值 */
    ulong nNextFreeElement;        /* 下一个数字索引的位置 $arr[] = xxx; */
    Bucket *pInternalPointer;      /* Used for element traversal */
    Bucket *pListHead;             /* 存储数组头元素指针 */
    Bucket *pListTail;             /* 存储数组尾元素指针 */
    Bucket **arBuckets;            /* 存储 hash 数组 */
    dtor_func_t pDestructor;       /* 在删除元素时执行的回调函数,用于资源的释放 */
    zend_bool persistent;          /* malloc/emalloc */
    unsigned char nApplyCount;     /* 标记当前 hash Bucket 被递归访问的次数(防止多次递归) */
    zend_bool bApplyProtection;    /* 标记当前 hash 桶允许不允许多次访问,不允许时,最多只能递归 3 次 */

#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;