AbstractMotivationMinimal perfect hashing is the problem of mapping a static set ofndistinct keys into the address space{1,…,n}bijectively. It is well-known thatnlog2(e)bits are necessary to specify a minimal perfect hash function (MPHF)f, when no additional knowledge of the input keys is to be used. However, it is often the case in practice that the input keys have intrinsic relationships that we can exploit to lower the bit complexity off. For example, consider a string and the set of all its distinctk-mers as input keys: since two consecutivek-mers share an overlap ofk−1symbols, it seems possible to beat the classiclog2(e)bits/key barrier in this case. Moreover, we would likefto map consecutivek-mers to consecutive addresses, as to also preserve as much as possible their relationship in the codomain. This is a useful feature in practice as it guarantees a certain degree of locality of reference forf, resulting in a better evaluation time when querying consecutivek-mers.ResultsMotivated by these premises, we initiate the study of a new type of locality-preserving MPHF designed fork-mers extracted consecutively from a collection of strings. We design a construction whose space usage decreases for growingkand discuss experiments with a practical implementation of the method: in practice, the functions built with our method can be several times smaller and even faster to query than the most efficient MPHFs in the literature.