暂无图片
暂无图片
暂无图片
暂无图片
暂无图片

PostgreSQL 14 preview - hash 函数生成代码增强 - src/tools/PerfectHash.pm

digoal 2020-10-10
231

作者

digoal

日期

2020-10-10

标签

PostgreSQL , perfect hash function generation


背景

Improve set of candidate multipliers for perfect hash function generation

https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/tools/PerfectHash.pm;h=d6841589a39b9afc4852cba588087005ca1af847;hb=d6841589a39b9afc4852cba588087005ca1af847

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=2a7316458164369436e252e5e60a5957b17103c3

```
Improve set of candidate multipliers for perfect hash function generation
author Michael Paquier michael@paquier.xyz
Thu, 8 Oct 2020 12:16:43 +0800 (13:16 +0900)
committer Michael Paquier michael@paquier.xyz
Thu, 8 Oct 2020 12:16:43 +0800 (13:16 +0900)
commit 2a7316458164369436e252e5e60a5957b17103c3
tree fa8d6146827c6e1777a0a44861080780e3c7e162 tree | snapshot
parent 98681675002d852d926a49d7bc4d4b4856b2fc4a commit | diff

Improve set of candidate multipliers for perfect hash function generation

The previous set of multipliers was not adapted for large sets of short
keys, and this new set of multipliers allows to generate perfect hash
functions for larger sets without having an impact for existing callers
of those functions, as experimentation has showed. A future commit will
make use of that to improve the performance of unicode normalization.

All multipliers compile to shift-and-add instructions on most platforms.
This has been tested as far back as gcc 4.1 and clang 3.8.

Author: John Naylor
Reviewed-by: Mark Dilger, Michael Paquier
Discussion: https://postgr.es/m/CACPNZCt4fbJ0_bGrN5QPt34N4whv=mszM0LMVQdoa2rC9UMRXA@mail.gmail.com
```

1 #---------------------------------------------------------------------- 2 # 3 # PerfectHash.pm 4 # Perl module that constructs minimal perfect hash functions 5 # 6 # This code constructs a minimal perfect hash function for the given 7 # set of keys, using an algorithm described in 8 # "An optimal algorithm for generating minimal perfect hash functions" 9 # by Czech, Havas and Majewski in Information Processing Letters, 10 # 43(5):256-264, October 1992. 11 # This implementation is loosely based on NetBSD's "nbperf", 12 # which was written by Joerg Sonnenberger. 13 # 14 # The resulting hash function is perfect in the sense that if the presented 15 # key is one of the original set, it will return the key's index in the set 16 # (in range 0..N-1). However, the caller must still verify the match, 17 # as false positives are possible. Also, the hash function may return 18 # values that are out of range (negative or >= N), due to summing unrelated 19 # hashtable entries. This indicates that the presented key is definitely 20 # not in the set. 21 # 22 # 23 # Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group 24 # Portions Copyright (c) 1994, Regents of the University of California 25 # 26 # src/tools/PerfectHash.pm 27 # 28 #----------------------------------------------------------------------

PostgreSQL 许愿链接

您的愿望将传达给PG kernel hacker、数据库厂商等, 帮助提高数据库产品质量和功能, 说不定下一个PG版本就有您提出的功能点. 针对非常好的提议,奖励限量版PG文化衫、纪念品、贴纸、PG热门书籍等,奖品丰富,快来许愿。开不开森.

9.9元购买3个月阿里云RDS PostgreSQL实例

PostgreSQL 解决方案集合

德哥 / digoal's github - 公益是一辈子的事.

digoal's wechat

文章转载自digoal,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。

评论