pg中的数据结构一：可扩展哈希表一

 二叉树搜索具有对数时间的表现有个假设：输入数据具有相当的随机性。现在我们看哈希表，这种数据结构，其在插入、删除、查询操作上也具有常数评价时间的表现，而且这种表现以统计为基础，不依赖数据的随机性。

 

我们先看看pg 里的哈希函数，再看pg 里 动态哈希表“dynmaic hashtable ” （ 我认为用 “可扩展哈希表” 更能体现“dynmaic hashtable ”的功能，更贴近中国人用词习惯，以后就用“可扩展哈希表”吧。 ）结构、哈希表上的操作（增删查改）以及可扩展。

 

说哈希函数前先澄清一下 碰撞，碰撞根据使用的场合不同有两种情况，一是哈希函数在把普通值打散/ 计算出哈希值时可能产生的碰撞，这个需要由哈希函数本身解决，王小云教授研究的碰撞就是这个碰撞；另一个是哈希表中根据哈希键值安排哈希键所在位置时的碰撞，解决这种碰撞的方法有一次探测（linear probing ）、二次探测（quadratic probing ）、开链（separate chainning ）等多种解决方法，pg 以开链解决这个碰撞问题。

Hash 函数：

pg 在hash.h 中有下列hash 函数

extern Datum hashchar(PG_FUNCTION_ARGS);

extern Datum hashint2(PG_FUNCTION_ARGS);

extern Datum hashint4(PG_FUNCTION_ARGS);

extern Datum hashint8(PG_FUNCTION_ARGS);

extern Datum hashoid(PG_FUNCTION_ARGS);

extern Datum hashenum(PG_FUNCTION_ARGS);

extern Datum hashfloat4(PG_FUNCTION_ARGS);

extern Datum hashfloat8(PG_FUNCTION_ARGS);

extern Datum hashoidvector(PG_FUNCTION_ARGS);

extern Datum hashint2vector(PG_FUNCTION_ARGS);

extern Datum hashname(PG_FUNCTION_ARGS);

extern Datum hashtext(PG_FUNCTION_ARGS);

extern Datum hashvarlena(PG_FUNCTION_ARGS);

extern Datum hash_any(register const unsigned char *k, register int keylen);

extern Datum hash_uint32(uint32 k);

   

下面这些哈希函数做将原值做一些位与或转换后，将结果作为参数调用hash_uint32 继续哈希运算

hashchar() 、hashint2() 、hashint4() 、hashint8() 、hashoid() 、hashenum()

下面这些哈希函数做将原值做一些位与或转换或类型转换后，将结果作为参数调用hash_any 继续哈希运算

hashfloat4 () 、hashfloat8 () 、hashoidvector () 、hashint2vector () 、hashname () 、hashtext () 、hashvarlena ()

 

这么多的哈希函数最终落到了 hash_uint32 和 hash_any 这两个哈希函数上，加上两个做散列的宏mix(a,b,c) 和final(a,b,c) 完成了哈希运算。 hash_uint32(uint32 k) 像 hash_any(&k, sizeof(uint32)) 一样有着同样的结果，但hash_uint32 更快，并且不强制调用者把k 存储在内存中。

关于哈希函数研究，可以推荐两个人的书/ 文章看看，一个是中科院的裴定一教授，可以看他的书和文章。有优于PKI 的CPK 标识认证专利的南湘浩教授需要哈希函数的时候就是向裴定一教授要的。南湘浩和曲延文教授以及孙玉院士（都是大牛）合作成立了QNS 工作室，我第一次路过工作室时，第一反映是这是个皮包公司，因为在租金不菲的中关村软件园里有偌大面积，但又没有几个工作人员, 后来登门拜访受教才了解内情。另一个是Bob Jenkins ，可以到他的网站 http://burtleburtle.net/bob/hash/index.html 看。或者看他们的论文。

 

可扩展哈希表可以无限增长。可扩展哈希表有一个顶层的“目录”，他的每一个入口指向ssize 个哈希桶的段的头部，最大哈希桶数是dsize * ssize ，dsize 是可以增大的。当然，哈希表里的记录数可以更大，但是我们不想要一个哈希桶里有很多记录或性能降是低。在共享内存中分配的哈希表时，因为他的地址是固定的，“目录”不能增大。目录的大小应该用hash_select_dirsize 选择。非共享哈希表的目录初始化大小可以是默认的。

 

可扩展哈希表和几个数据结构有关，一个是 HCTL ，这个是创建可扩展哈希表时的信息表，一个是 HTAB ，这个就是哈希表结构，一个是 HASHHDR ，这个是哈希表头结构， 包含了哈希表的所有可变信息 ，还有 HashSegment 、 HashBucket 、 HashElement 等结构，一个 HashSegment 是 HashBucket 数组的头，一个 HashBucket 是 HashElement 链表。结构定义见下面。这些结构和起来组成了可扩展哈希表。 根据pg 默认参数创建的可扩展哈希表 结构图在下面。

typedef struct HASHCTL

{

    long         num_partitions; /* # partitions (must be power of 2) */

    long         ssize;          /* segment size */

    long         dsize;          /* (initial) directory size */

    long         max_dsize;      /* limit to dsize if dir size is limited */

    long         ffactor;        /* fill factor */

    Size        keysize;        /* hash key length in bytes */

    Size        entrysize;      /* total user element size in bytes */

    HashValueFunc hash;         /* hash function */

    HashCompareFunc match;      /* key comparison function */

    HashCopyFunc keycopy;       /* key copying function */

    HashAllocFunc alloc;        /* memory allocator */

    MemoryContext hcxt;         /* memory context to use for allocations */

    HASHHDR    *hctl;           /* location of header in shared mem */

} HASHCTL;

 

struct HTAB

{

    HASHHDR    *hctl;           /* => shared control information */

    HASHSEGMENT *dir;           /* directory of segment starts */

    HashValueFunc hash;         /* hash function */

    HashCompareFunc match;      /* key comparison function */

    HashCopyFunc keycopy;       /* key copying function */

    HashAllocFunc alloc;        /* memory allocator */

    MemoryContext hcxt;         /* memory context if default allocator used */

    char        *tabname;        /* table name (for error messages) */

    bool         isshared;       /* true if table is in shared memory */

 

    /* We keep local copies of these fixed values to reduce contention */

    Size        keysize;        /* hash key length in bytes */

       long               ssize;                    /* segment size --- must be power of 2 */

       int                  sshift;                   /* segment shift = log2(ssize) */

};

struct HASHHDR

{

    /* In a partitioned table, take this lock to touch nentries or freeList */

    slock_t     mutex;          /* unused if not partitioned table */

 

    /* These fields change during entry addition/deletion */

    long         nentries;       /* number of entries in hash table */

    HASHELEMENT *freeList;      /* linked list of free elements */

 

    /* These fields can change, but not in a partitioned table */

    /* Also, dsize can't change in a shared table, even if unpartitioned */

    long         dsize;          /* directory size */

    long         nsegs;          /* number of allocated segments (<= dsize) */

    uint32      max_bucket;     /* ID of maximum bucket in use */

    uint32      high_mask;      /* mask to modulo into entire table */

    uint32      low_mask;       /* mask to modulo into lower half of table */

 

    /* These fields are fixed at hashtable creation */

    Size        keysize;        /* hash key length in bytes */

    Size        entrysize;      /* total user element size in bytes */

    long         num_partitions; /* # partitions (must be power of 2), or 0 */

    long         ffactor;        /* target fill factor */

    long         max_dsize;      /* 'dsize' limit if directory is fixed size */

    long         ssize;          /* segment size --- must be power of 2 */

    int          sshift;         /* segment shift = log2(ssize) */

    int          nelem_alloc;    /* number of entries to allocate at once */

 

#ifdef HASH_STATISTICS

 

    /*

      * Count statistics here.  NB: stats code doesn't bother with mutex, so

      * counts could be corrupted a bit in a partitioned table.

      */

    long        accesses;

    long        collisions;

#endif

};

 

typedef HASHELEMENT *HASHBUCKET;

typedef HASHBUCKET *HASHSEGMENT;

 

根据pg 默认值创建的可扩展哈希表结构图如下：

 

 

哈希表结构图

 

创建过程涉及函数及功能：

根据 info 信息和给定名字及 HashElement 元素个数进行计算创建可扩展哈希表

HTAB * hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)

分配相应数目(dsize) 的HashSegment 数组

static bool init_htab(HTAB *hashp, long nelem)

计算给定数的以2 为底加1 取正对数值

Int my_log2(long num)

给哈希表的HashSegment 分配相应个数(ssize) 的HashBucket

static HASHSEGMENT seg_alloc(HTAB *hashp)

根据entry 大小计算要分的HashElement 的个数

static int choose_nelem_alloc(Size entrysize)

分配HashElement+Entry 并加入到HASHHDR 的freelist 链表

static bool element_alloc(HTAB *hashp, int nelem)

哈希表的销毁：

主要是调用MemoryContextDelete(hashp->hcxt) （参见《pg 内存管理机制三》）销毁哈希表

Void hash_destroy(HTAB *hashp)

 

创建流程图如下：

 

创建可扩展哈希表流程图

上图中红色框主要是根据条件设置 HTAB 结构类型变量的各成员，右边黄色框中主要是计算 HashSegment 、 HashBucket 以及 HashElement 成员的数目并为它们分配内存。

就到这儿吧。