digoal
2020-10-10
PostgreSQL , perfect hash function generation
Improve set of candidate multipliers for perfect hash function generation
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 #----------------------------------------------------------------------
您的愿望将传达给PG kernel hacker、数据库厂商等, 帮助提高数据库产品质量和功能, 说不定下一个PG版本就有您提出的功能点. 针对非常好的提议，奖励限量版PG文化衫、纪念品、贴纸、PG热门书籍等，奖品丰富，快来许愿。开不开森.
