赞
踩
二叉树搜索具有对数时间的表现有个假设:输入数据具有相当的随机性。现在我们看哈希表,这种数据结构,其在插入、删除、查询操作上也具有常数评价时间的表现,而且这种表现以统计为基础,不依赖数据的随机性。
我们先看看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继续哈希运算
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。