<p>I'm working on <a href="https://github.com/thomasmueller/minperf" rel="nofollow noreferrer">an algorithm and Java implementation that needs less than 1.6 bits per key</a>.</p>
<p>Previously, I have implemented <a href="https://github.com/h2database/h2database/blob/master/h2/src/tools/org/h2/dev/hash/MinimalPerfectHash.java" rel="nofollow noreferrer">a minimal perfect hash function tool in Java</a> that needs less than 2.0 bits per key.</p>
<p>Other algorithms are implemented in <a href="http://cmph.sourceforge.net/" rel="nofollow noreferrer">CMPH</a>. For example CHD needs about 2.06 bits per key by default. It can be configured to use less space, but generation is then slower.</p>
<p><em>Update</em>: There is now <a href="https://arxiv.org/abs/1910.06416" rel="nofollow noreferrer">a paper</a> about my invention called &quot;RecSplit: Minimal Perfect Hashing via Recursive Splitting&quot;</p>
Minimal perfect hash function
<p>I have many integers in range [0; 2^63-1]. There is only 10^8 integers, however. There is <em>no duplicates</em>. Full list is known at compile-time but it is <em>just unique random numbers</em>. These numbers <em>never changes</em>.<br>
To store one integer <em>explicitly</em>, 8 bytes required, and there is associated 1-byte values, so explicit storing requires about 860 MB.<br>
So I want to find minimal perfect hash function to map each of 10^8 integers from [0;2^63-1] to [0;10^8-1]. I should find this function only once, data never changes, and function can be complicated. But it should be minimal, perfect, and calculating should be fast. How I can do this better? Maybe it is possible to find and use some subsequences if they happens?<br>
Thanks.</p>