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

我是007

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

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

　　 说哈希函数前先澄清一下 碰撞，碰撞根据使用的场合不同有两种情况，一是哈希函数在把普通值打散/计算出哈希值时可能产生的碰撞，这个需要由哈希函数本身解决，王小云教授研究的碰撞就是这个碰撞；另一个是哈希表中根据哈希键值安排哈希键所在位置时的碰撞，解决这种碰撞的方法有一次探测（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 Datumhashenum(PG_FUNCTION_ARGS);
　　extern Datum hashfloat4(PG_FUNCTION_ARGS);
　　extern Datumhashfloat8(PG_FUNCTION_ARGS);
　　extern Datumhashoidvector(PG_FUNCTION_ARGS);
　　extern Datumhashint2vector(PG_FUNCTION_ARGS);
　　extern Datumhashname(PG_FUNCTION_ARGS);
　　extern Datumhashtext(PG_FUNCTION_ARGS);
　　extern Datumhashvarlena(PG_FUNCTION_ARGS);
　　extern Datumhash_any(register const unsigned char *k, register int keylen);
　　extern Datumhash_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; /* segmentsize */
　　 long dsize; /* (initial)directory size */
　　 long max_dsize; /* limit todsize 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; /* hashfunction */
　　 HashCompareFuncmatch; /*key comparison function */
　　 HashCopyFunckeycopy; /*key copying function */
　　 HashAllocFunc alloc; /* memoryallocator */
　　 MemoryContext hcxt; /* memorycontext 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 */
　　 HashValueFunchash; /*hash function */
　　 HashCompareFuncmatch; /*key comparison function */
　　 HashCopyFunckeycopy; /*key copying function */
　　 HashAllocFuncalloc; /*memory allocator */
　　 MemoryContexthcxt; /*memory context if default allocator used */
　　 char  *tabname; /* table name (for error messages) */
　　 bool isshared; /* true iftable is in shared memory */
　　
　　 /* We keep local copies of these fixed values to reducecontention */
　　 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 nentriesor freeList */
　　 slock_t mutex; /* unused if not partitioned table */
　　
　　 /* These fields change during entry addition/deletion */
　　 long nentries; /* number ofentries 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 ifunpartitioned */
　　 long dsize; /* directorysize */
　　 long nsegs; /* number ofallocated 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 keylength in bytes */
　　 Size entrysize; /* total user element size in bytes*/
　　 long num_partitions;/* # partitions (must be power of 2), or 0 */
　　 long ffactor; /* target fillfactor */
　　 long max_dsize; /* 'dsize' limitif directory is fixed size */
　　 long ssize; /* segmentsize --- must be power of 2 */
　　 int sshift; /* segmentshift = log2(ssize) */
　　 int nelem_alloc; /* number ofentries to allocate at once */
　　
　　#ifdef HASH_STATISTICS
　　
　　 /*
　　 * Count statisticshere. NB: stats code doesn't bother withmutex, so
　　 * counts could becorrupted 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成员的数目并为它们分配内存。
　　 就到这儿吧。