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

?

我们先看看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