Perfect hash functions give unique “names” to arbitrary keys requiring only a few bits per key. This is an essential building block in applications like static hash tables, databases, or bioinformatics. This paper introduces the PHast approach that combines the fastest available queries, very fast construction, and good space consumption (below 2 bits per key). PHast improves bucket-placement which first hashes each key \(k\) to a bucket, and then looks for the bucket seed \(s\) such that a placement function maps pairs \((s,\, k)\) in a collision-free way. PHast can use smallrange hash functions with linear mapping, fixed-width encoding of seeds, and parallel construction. This is achieved using small overlapping slices of allowed values and bumping to handle unsuccessful seed assignment. A variant we called PHast+ uses additive placement, which enables bit-parallel seed searching, speeding up the construction by an order of magnitude.

Partition search is a form of game search, proposed by Matthew L. Ginsberg in 1996, who wrote that the method “incorporates dependency analysis, allowing substantial reductions in the portion of the tree that needs to be expanded.” In this paper, some improvements of the partition search algorithm are proposed. The effectiveness of the most important extension we contribute, which we call local partition search, has been verified experimentally. The results obtained (which we present in the paper) show that using this extension, leads, in the case of bridge, to a significant reduction (almost by half) of the search tree size and calculation time. Another extension we proposed allows for more effective usage of the transposition table (using it to narrow the search window or by cutting more than one entry). Additionally, we contribute a formal proof of the correctness of all presented partition search variants. We draw conclusions from it about a possible generalization of partition search by making the definition of a partition system less restrictive. We also provide a formal definition of a partition system for the double dummy bridge.