吾业以农耕、先人品、后技术、再分享、闻道有先后、术业有专攻

问题背景：

研究的目的主要就是为了深入学习和理解PHP7内核中哈希表实现原理，因为HashTable是PHP内核最重要的一个数据结构，万能的PHP数组以及函数、类等等的内部实现全都离不开HashTable数据结构；此外对于想熟练编写PHP扩展的码友，学习并理解哈希表也是非常重要的。

获取源码：

https://github.com/blogdaren/PHP7HashTable

头部源码：

/*
 * =====================================================================================
 *
 *      Filename:   PHP7HashTable.h
 *
 *      Description:  哈希表头文件
 *
 *  ------------------------------
 * / HashTable Data Layout Start /
 * ------------------------------
 *
 *                 +=============================+
 *                 | HT_IDX(ht, hN)              |
 *                 | ...                         |
 *                 | HT_IDX(ht, h2)              |
 *                 | HT_IDX(ht, h1)              |
 *                 +-----------------------------+
 * ht->arData ---> | Bucket[0]                   |
 *                 | Bucket[1]                   |
 *                 | ...                         |
 *                 | Bucket[ht->tableSize - 1]   |
 *                 +=============================+
 *
 *  -----------------------------
 * / HashTable Data Layout End  /
 * -----------------------------
 *
 *        Version:  1.0
 *        Created:  2021年03月4日 16时50分55秒
 *       Revision:  none
 *       Compiler:  gcc
 *         Author:  blogdaren
 *   Organization:  http://www.phpcreeper.com
 *
 * =====================================================================================
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int                 int32_t;
typedef unsigned int        uint32_t;
typedef unsigned char       boolean; 
typedef unsigned long       ulong;
typedef unsigned short      ushort;
typedef char *              String;
typedef struct HashTable    HashTable;
typedef struct Bucket       Bucket;
typedef struct BucketValue  BucketValue;

#define IS_UNDEF    (1<<0)
#define IS_STRING   (1<<1)
#define IS_LONG     (1<<2)
#define IS_DOUBLE   (1<<3)
#define IS_ARRAY    (1<<4)

#define USER_API
#define SUCCESS                 1
#define FAILURE                 0
#define HT_MIN_SIZE             8
#define HT_INVALID_IDX          ((uint32_t)-1)   

#define HT_HASH_SIZE(mask)  \
        (((size_t)(uint32_t)-(int32_t)(mask)) * sizeof(uint32_t))
#define HT_DATA_SIZE(size)  \
        ((size_t)(size) * sizeof(Bucket))
#define HT_SIZE_TOTAL(mask, size)   \
        (HT_HASH_SIZE((mask)) + HT_DATA_SIZE((size)))
#define HT_SIZE(ht) \
        HT_SIZE_TOTAL((ht)->tableMask, (ht)->tableSize)
#define HT_GET_HASH_START_ADDRESS(ht)  \
        ((uint32_t*)((char *)ht->arData - HT_HASH_SIZE(ht->tableMask)))
#define HT_OFFSET(ht, h)    \
        (h | ht->tableMask)
#define HT_IDX(ht, h)   \
        (*((uint32_t*)ht->arData + HT_OFFSET(ht, h)))
#define CHECK_WHETHER_NEED_TO_DO_RESIZE(ht) do{ \
            if((ht)->positionNumberUsed >= (ht)->tableSize){    \
                resizeHashTable(ht);    \
            }   \
        }while(0)   \ 

struct HashTable
{
    size_t tableSize;
    size_t tableMask;
    size_t positionNumberUsed;
    size_t validElementNumber;
    Bucket *arData;
};

struct Bucket
{
    ulong       h;
    String      key;
    BucketValue *val;
    size_t      next;
};

struct BucketValue
{
    ushort  type;
    ushort  flag;
    union {
        long        lval;
        double      dval;
        char        *str;
        HashTable   *arr;
    } v;
};

//核心实现代码详见：https://github.com/blogdaren/PHP7HashTable