Berapa banyak independensi yang diperlukan untuk rantai terpisah?

Jika $n$ bola ditempatkan ke $n$ nampan secara seragam secara acak, nampan dengan beban terberat memiliki bola $O(\lg n/\lg \lg n)$ dengan probabilitas tinggi. Dalam "The Power of Simple Tabulation Hashing" , Pătraşcu dan Thorup menyebutkan bahwa "Chernoff-Hoeffding terikat untuk aplikasi dengan independensi terbatas" ( mirror ) menunjukkan bahwa ini terikat pada populasi bin yang paling berat yang dimuat juga berlaku jika bola didistribusikan oleh sebuah $\Omega(\lg n/\lg \lg n)$ fungsi hash independen.

Dalam "Bola dan Sampah: Keluarga Hash Lebih Kecil dan Evaluasi Lebih Cepat" , Celis et al. perhatikan bahwa tidak diketahui apakah ada keluarga fungsi hash di mana

1. Fungsi hash dapat direpresentasikan dengan bit ruang$O(\lg n)$
2. Fungsi hash dapat dievaluasi dalam waktu$O(1)$
3. Beban maksimal adalah dengan probabilitas tinggi.$O(\lg n / \lg \lg n)$

Jika ada konstanta sedemikian sehingga setiap keluarga k- cukup mencukupi untuk # 3, maka konstruksi polinomial keluarga k- independen akan memenuhi # 1 dan # 2.$k$$k$$k$

$k$

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

$O(\lg ^c n)$

$k$$\Omega(n^{1/k})$