search

FastFilter / fastfilter_java

Fast Approximate Membership Filters (Java)
Apache License 2.0
238 stars 27 forks source link

False negative in minimal perfect hash function (test directory) #17

Open richardstartin opened 4 years ago

richardstartin commented 4 years ago

Steps to reproduce:

Hash.setSeed(5400005265475528641L);
long[] keys = new long[] {1773227589100607582L, 1401008621823229258L, 901259869510331588L, 1197333276475942193L, 1651119322544330030L, 986112488938952069L,
                        1675726966169519337L, 1888976485651830901L, 1912475806632315628L, 74149177065144196L, 942187212974983392L, 4215890488646823727L, 3694125823111201993L, 3793738020275325587L,
                        2995933316126352930L, 4017238031310632606L, 3798301062142417109L, 4113831042388378630L, 2707645218409175553L, 3919094501360474098L, 4252303149040498185L, 4199952774063362014L,
                        3327107703856825600L, 3964961892107416731L, 3966935050689896802L, 5921581983460164542L, 5314808407468600915L, 4696106051339789101L, 6634550099558541650L, 6382215924765560390L,
                        5154426188333895839L, 6466726512887879802L, 4836037707257613543L, 5608288809216362089L, 6793579614382201757L, 6709676086154795823L, 5972763369063718749L, 4765003610184494484L,
                        5635899990946803784L, 5349364953307177057L, 6264947502670452080L, 6912802837350428240L, 5429101923532929753L, 5668285853203792528L, 6563481559119688471L, 6317103420640399795L,
                        8937635149702679081L, 8062485652179232600L, 8942552659025336850L, 8508924203915110088L, 8938353353354172574L, 7907183519152868142L, 8654059200278009367L, 9151769575477085925L,
                        8494748655862745947L, 8180511740959930009L, 8244780136171765059L, 9165671267726030534L, 8022333815153416350L, -7348602598025993307L, -7137527130402610919L, -8864995500791741494L,
                        -7906426467332813681L, -7343692788430814188L, -9007903685362026026L, -9178084101442809748L, -7526812997805935236L, -7640655228186765204L, -6001026700792546473L, -6870431948453764034L,
                        -5271447769651360857L, -5591560689279781023L, -5868299437269234751L, -6226415928272647338L, -5431159857161381398L, -6370987534222793305L, -3043487285958836631L, -4301361355076290527L,
                        -3682760495848399784L, -3038236626480548566L, -3895662199162059335L, -3192071612777396897L, -2729235696166508115L, -3087500698602513665L, -4156274151845244416L, -3309406490623888358L,
                        -2528282539021436624L, -1633985981412420612L, -360913997783076114L, -111396594598251164L, -1339842643116805785L, -1403112313973786426L, -856792793066744400L, -392622225906607155L, 
                        -863763710126232180L, -400874713595065720L, -373641626604004087L, -1951676159570020905L, -1774490078013273270L, -468961924964997308L, -1210600430103212706L, -384877607682781339L, -1945436007627906978L};
int bitsPerKey = 8;
var filter = MPHF.construct(keys, bitsPerKey);
assertTrue(filter.mayContain(1773227589100607582L)); // false
thomasmueller commented 4 years ago

The MPHF seems to be buggy. I moved it to the test directory.