Hashing är grundläggande för många algoritmer och datastrukturer som används i stor utsträckning i praktiken. För teoretisk analys av hashing har det funnits två huvudstrategier. För det första kan man anta att hashfunktionen verkligen är slumpmässig, genom att kartlägga varje dataobjekt självständigt och enhetligt till intervallet. Denna idealiserade modell är orealistisk eftersom en verkligt slumpmässig hashfunktion kräver ett exponentiellt antal bitar att beskriva. Alternativt kan man ge rigorösa gränser för prestanda när explicita familjer av hash funktioner används, såsom 2-universal eller O(1)-vis oberoende familjer. För sådana familjer är prestandagarantierna ofta märkbart svagare än för idealisk hasch. I praktiken är det dock allmänt observerat att enkla hash funktioner, inklusive 2-universal hash funktioner, utför som förutsägs av den idealiserade analysen för verkligt slumpmässiga hash funktioner. I den här artikeln försöker vi förklara detta fenomen. Vi visar att de universella hashfunktionernas starka prestanda i praktiken kan uppstå naturligt genom en kombination av hashfunktionens och datans slumpmässighet. Speciellt, efter den stora kroppen av litteratur på slumpmässiga källor och slumpmässiga extraktion, vi modellerar data som kommer från en "blockkälla", där varje ny dataobjekt har några "entropi" med tanke på de tidigare. Så länge (Renyi) entropin per dataobjekt är tillräckligt stor, visar det sig att prestandan när man väljer en hashfunktion från en 2-universell familj är i stort sett densamma som för en verkligt slumpmässig hashfunktion. Vi beskriver resultat för flera urvalsapplikationer, inklusive linjär undersökning, balanserade tilldelningar och Bloom-filter.
Detta är i motsats till det positiva resultatet av Mitzenmacher och Vadhan Ref, som visade att parvis oberoende hash funktioner är tillräckliga, förutsatt att nycklarna provtas från en block källa med tillräcklig Renyi entropy.
Why simple hash functions work: exploiting the entropy in a data stream
{'venue': "SODA '08", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}