Quelle est l'indépendance requise pour un chaînage séparé?

Si balles sont placées dans cases de manière uniforme et aléatoire, la poubelle la plus lourde contient balles avec une forte probabilité. Dans "The Power of Simple Tabulation Hashing" , Pătraşcu et Thorup mentionnent que "les limites de Chernoff-Hoeffding pour les applications avec une indépendance limitée" ( miroir ) montrent que cette limite sur la population du bac le plus chargé est également valable si les balles sont distribuées par un Fonction de hachage indépendante de .$n$$n$$O(\lg n/\lg \lg n)$$\Omega(\lg n/\lg \lg n)$

Dans «Balls and Bins: Smaller Hash Families and Faster Evaluation» , Celis et al. notez qu'il n'est pas connu s'il existe une famille de fonctions de hachage où

1. Les fonctions de hachage peuvent être représentées avec bits d'espace$O(\lg n)$
2. Les fonctions de hachage peuvent être évaluées en le temps$O(1)$
3. La charge maximale est avec une probabilité élevée.$O(\lg n / \lg \lg n)$

S'il y a une constante telle que toute famille indépendante de k suffit pour # 3, alors la construction polynomiale des familles indépendantes de k rencontrerait # 1 et # 2.$k$$k$$k$

Quelle limite avons - nous pour le bac le plus lourd avec un hachage indépendant de ?$k$

$O(n^{2/k})$

$O(\lg ^c n)$

Apparemment non. "Quicksort, le plus grand seau et le hachage Min-Wise avec une indépendance limitée", par Mathias Bæk Tejs Knudsen et Morten Stöckel montre "une famille de fonctions indépendantes de qui impliquent la taille [le plus lourd chargé] Ω ( $k$$\Omega(n^{1/k})$