Di dalam Peran 1985Ilmuwan komputer Andrew YaoBahwa ia akan terus memenangkan penghargaan AM Turing, mengatakan bahwa di antara tabel hash dengan serangkaian properti tertentu, cara terbaik untuk menemukan elemen individu atau tempat kosong adalah dengan melewati kemungkinan poin acak, pendekatan yang dikenal sebagai Survei Seragam. Dia juga menyatakan bahwa, dalam kasus terburuk, di mana Anda mencari tempat terbuka terakhir, Anda tidak akan pernah bisa melakukan yang lebih baik dari tidak dikenal. Selama 40 tahun, sebagian besar ilmuwan komputer berasumsi bahwa dugaan Yao benar.
Krapivin tidak dipertahankan oleh kebijaksanaan konvensional karena alasan sederhana yang tidak dia ketahui. “Saya melakukan ini tanpa mengetahui dugaan Yao,” katanya. Eksplorasi dengan pointer kecil menyebabkan hash jenis meja baru, yang tidak bergantung pada survei yang seragam. Dan untuk tabel hash baru ini, waktu yang diperlukan untuk konsultasi dan penyisipan kasus yang lebih buruk sebanding dengan (log tidak dikenal)2—Far lebih cepat dari tidak dikenal. Hasil ini secara langsung bertentangan dengan dugaan Yao. Farach-Colton dan Kuszmaul membantu Krapivin menunjukkan itu (log tidak dikenal)2 Ini adalah yang optimal dan tidak terkalahkan untuk tabel hash populer yang ditulis Yao.
“Hasil ini indah karena membahas dan memecahkan masalah klasik seperti itu,” katanya Guy Blenloch dari Carnegie Mellon.
“Bukan hanya karena mereka membantah [Yao’s conjecture]Mereka juga menemukan jawaban terbaik untuk pertanyaan mereka, ”katanya Sepehr Assadi dari University of Waterloo. “Kami bisa menghabiskan 40 tahun lagi sebelum kami tahu jawaban yang benar.”
Selain menyangkal dugaan Yao, artikel baru ini juga berisi apa yang banyak dianggap sebagai hasil yang lebih mengejutkan. Ini mengacu pada situasi terkait, meskipun sedikit berbeda, pada tahun 1985, Yao tidak hanya melihat saat -saat terburuk dari konsultasi, tetapi juga dalam waktu rata -rata yang dibutuhkan dalam semua kemungkinan konsultasi. Dia membuktikan bahwa tabel hash dengan sifat -sifat tertentu, termasuk yang dilabeli sebagai “serakah”, yang berarti bahwa elemen baru harus ditempatkan di tempat pertama yang tersedia, mereka tidak akan pernah bisa mencapai waktu rata -rata lebih baik daripada log tidak dikenal.
Farach-Colton, Krapivin dan Kuszmaul ingin melihat apakah batas yang sama juga berlaku untuk hash no Grreedia. Mereka menunjukkan bahwa itu tidak memberikan contoh tandingan, tabel hash non -hijau dengan waktu konsultasi rata -rata yang jauh lebih baik daripada mencapai tidak dikenal. Faktanya, itu tidak tergantung pada tidak dikenal sama sekali. “Anda mendapatkan nomor,” kata Farach-Colton, “sesuatu yang hanya konstan dan tidak bergantung pada seberapa penuh tabel hash.” Fakta bahwa ia dapat mencapai waktu konsultasi rata -rata yang konstan, terlepas dari kepenuhan tabel hash, sama sekali tidak terduga, bahkan untuk penulis sendiri.
Hasil tim mungkin tidak mengarah pada aplikasi langsung apa pun, tetapi tidak terlalu penting, kata Conway. “Penting untuk lebih memahami jenis struktur data ini. Dia tidak tahu kapan hasil seperti ini akan membuka sesuatu yang memungkinkannya untuk melakukan yang lebih baik dalam praktiknya. ”
Cerita asli Cetak ulang dengan izin dari Majalah berapa banyakpublikasi editorial independen dari Yayasan Simons yang misinya adalah untuk meningkatkan pemahaman publik tentang sains yang mencakup perkembangan penelitian dan tren dalam matematika dan ilmu fisik dan kehidupan.
