ทีมวิจัยระดับปริญญาตรีนำเสนอโครงสร้างข้อมูลแบบใหม่เพื่อปรับปรุงโครงสร้างข้อมูล open-addressing hash table หรือโครงสร้างแฮชที่เก็บข้อมูลในตารางแฮชโดยตรง โดยสามารถสร้างอัลกอริทึมที่เร็วกว่า การคาดคะเนของ Andrew Yao ที่วางข้อจำกัดความเร็วของปัญหาแบบนี้ไว้ตั้งแต่ปี 1985

ทีมงานนี้ประกอบด้วย Martin Farach-Colton จากมหาวิทยาลัยนิวยอร์ค, Andrew Krapivin จากมหาวิทยาลัยเคมบริดจ์, และ William Kuszmaul จากมหาวิทยาลัยคาร์เนกีเมลลอน โดยเสนอกระบวนการแฮชรูปแบบใหม่สองแบบ คือ Elastic Hashing และ Funnel Hashing โดยตัวสำคัญคือ Funnel Hashing ที่ทนทานต่อการค้นหาข้อมูลแม้ในกรณีที่แย่ที่สุดก็ยังอยู่ที่ระดับ O(log² δ⁻¹) เท่านั้น

open-addressing hash table เป็นโครงสร้างข้อมูลที่เก็บข้อมูลไว้ในตารางแฮชโดยตรง โดยเมื่อการแฮชได้ค่าตรงกัน (hash collision) จะต้องหาทางค้นหาช่องว่างเพื่อเก็บข้อมูล (probing) ทำให้ประสิทธิภาพในการค้นหาและใส่ข้อมูลใหญ่กว่า O(1) ในกรณีที่แย่ที่สุดคือตารางเกือบเต็มแล้ว หากใช้กระบวนการค้นหาช่องว่างแบบไล่หาไปเรื่อยๆ กระบวนการค้นหาช่องว่างนี้จะใช้เวลาถึง O(n) ตามขนาดตาราง แต่ Funnel Hashing สามารถลด Big-O ลงได้เหลือระดับ log² เท่านั้น ซึ่งเล็กลงมาก

ที่มา - Quanta Magazine