Menggunakan kembali fungsi hash 5-independen untuk penyelidikan linear

Dalam tabel hash yang menyelesaikan tabrakan dengan linear probing, untuk memastikan kinerja yang diharapkan, perlu dan cukup bahwa fungsi hash berasal dari keluarga 5-independen. (Kecukupan: "Pemeriksaan linear dengan kemandirian yang konstan", Pagh et al. , Keharusan: "Pada k-Kemandirian yang Diperlukan oleh Pemeriksaan Linier dan Kemandirian Minwise", Pătraşcu dan Thorup )$O(1)$

Ini adalah pemahaman saya bahwa keluarga 5-independen yang paling cepat diketahui menggunakan tabulasi. Memilih fungsi dari keluarga seperti itu mungkin mahal, jadi saya ingin meminimalkan berapa kali saya melakukannya sambil tetap mencegah serangan kompleksitas algoritmik seperti yang dijelaskan dalam "Denial of Service via Algorithmic Complexity Attacks" karya Crosby dan Wallach . Saya kurang khawatir tentang serangan waktu (yaitu musuh dengan stopwatch). Apa konsekuensi menggunakan kembali fungsi yang sama:

1. Saat menumbuhkan tabel hash yang terlalu penuh?
2. Ketika menyusut tabel hash yang tidak cukup penuh?
3. Saat membangun kembali tabel hash yang memiliki terlalu banyak bit "dihapus" yang ditetapkan?
4. Dalam tabel hash yang berbeda yang mungkin berisi beberapa kunci yang sama?$k$
5. Dalam tabel hash yang berbeda yang tidak mengandung kunci yang sama?$k$

$1/2$

• https://issues.cloudera.org/browse/IMPALA-2653
• https://github.com/rust-lang/rust/issues/36481