Praktik Universal dalam Praktek

$H$ $h: U \rightarrow \{0,\ldots,M-1\}$

\forall x, y \in U, x \neq y \Rightarrow \underset{h \in H}{Pr} [h (x) = h (y)] \leq \frac{1}{M.}

$\forall x,y \in U, x \neq y \Rightarrow \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{M}$

Konsep hashing universal sekarang menjadi bagian standar dari kursus struktur data sarjana. Alangkah baiknya untuk dapat memotivasi siswa tentang pentingnya hashing universal dalam aplikasi industri. Jadi pertanyaan saya adalah:

Apakah konstruksi keluarga universal fungsi hash penting dalam praktik? Jika jawabannya ya, maukah Anda membagikan beberapa aplikasi industri menarik yang pernah Anda lihat?

data-structures education hash-tables applied-theory Dai
sumber

Saya berharap bahwa semua implementasi struktur hash generik yang ingin mencapai (diamortisasi / diharapkan / nyata) biaya waktu konstan untuk memasukkan, mencari dan menghapus (yang merupakan satu-satunya alasan mengapa kita repot-repot hash di tempat pertama) memerlukan cara yang dapat diandalkan untuk membangun fungsi hashing "baik". Universal hashing adalah upaya (berhasil) untuk memformalkan apa fungsi hashing "baik", dan juga memberi kita alat untuk menghasilkan fungsi seperti itu secara efisien untuk kunci arbitrer. Karena saya tidak memiliki pengalaman industri, ini semua dari sudut pandang teoretis, tapi saya sangat berharap mereka menjadi jalan masuk yang terbaik.

G. Bach

@ G.Bach Terima kasih atas komentar Anda. Tapi saya ingin mendengar pendapat dari sudut pandang industri.

Dai

@Dai Ini mungkin bukan tempat yang tepat untuk mendapatkan pernyataan dari industri.

Raphael

Praktik Universal dalam Praktek

Jawaban: