งานวิจัยของนักศึกษาปริญญาตรีที่พลิกข้อจำกัดการค้นหาในตารางแฮช

 (quantamagazine.org)
5 คะแนน โดย GN⁺ 2025-02-11 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Andrew Krapivin ขณะเป็นนักศึกษาปริญญาตรีที่ Rutgers ได้แรงบันดาลใจจากบทความวิจัย Tiny Pointers แล้วคิดค้นตารางแฮชแบบใหม่ พร้อมแสดงให้เห็นว่าสามารถก้าวข้ามประสิทธิภาพการค้นหาและการแทรกที่เคยถือกันว่าเป็นข้อจำกัดเดิมได้
  • Krapivin, Martín Farach-Colton และ William Kuszmaul โต้แย้ง ข้อสันนิษฐานอายุ 40 ปีของ Yao สำหรับหมวดหมู่ตารางแฮชบางประเภท ในบทความวิจัยเมื่อเดือนมกราคม 2025
  • ข้อสันนิษฐานเดิมมองว่า สำหรับค่า x ซึ่งแทนระดับที่ตารางเกือบเต็ม เวลาค้นหาและแทรกในกรณีเลวร้ายที่สุดไม่อาจดีกว่า x ได้ แต่โครงสร้างใหม่ทำเวลาได้เป็นสัดส่วนกับ (log x)²
  • ทีมวิจัยยังแสดงให้เห็นว่า ในหมวดหมู่ตารางแฮชยอดนิยมที่ Yao ศึกษา (log x)² เป็นขอบเขตเหมาะที่สุดที่ลดลงไปกว่านี้ไม่ได้ และในตารางแฮชแบบไม่โลภ เวลาเฉลี่ยในการค้นหาสามารถเป็นค่าคงที่ที่ไม่ขึ้นกับ x ได้
  • แม้จะยังไม่นำไปสู่การใช้งานทันที แต่ผลงานนี้วางรากฐานทางทฤษฎีที่เปิดโอกาสให้ปรับปรุงเชิงปฏิบัติได้ ด้วยการจัดระเบียบความเข้าใจใหม่เกี่ยวกับขีดจำกัดประสิทธิภาพของ ตารางแฮช ซึ่งเป็นโครงสร้างข้อมูลเก่าแก่

ตารางแฮชแบบใหม่ที่เริ่มจาก Tiny Pointers

  • Andrew Krapivin ได้อ่านบทความวิจัย Tiny Pointers ตอนเป็นนักศึกษาปริญญาตรีที่ Rutgers University ในฤดูใบไม้ร่วงปี 2021 และเมื่อกลับมาอ่านอย่างละเอียดในอีก 2 ปีต่อมา เขาก็นึกวิธีสร้างพอยน์เตอร์ที่เล็กลงได้
  • เนื่องจากต้องจัดระเบียบข้อมูลที่พอยน์เตอร์ชี้ไปให้ดีขึ้น ตารางแฮช ซึ่งเป็นวิธีจัดเก็บข้อมูลทั่วไปจึงกลายเป็นหัวข้อวิจัย
  • ระหว่างการทดลอง Krapivin สร้างตารางแฮชแบบใหม่ที่ไม่พึ่งพาการตรวจสอบแบบสม่ำเสมอ (uniform probing) และพบว่าเวลารวมถึงจำนวนขั้นตอนในการหาองค์ประกอบหนึ่ง ๆ น้อยกว่าที่คาด
  • Martín Farach-Colton แรก ๆ ยังสงสัยการออกแบบนี้ แต่ William Kuszmaul มองว่าโครงสร้างของ Krapivin ไม่ได้เป็นแค่ตารางแฮชที่น่าสนใจเท่านั้น หากยังเป็นผลลัพธ์ที่โค่น ข้อสันนิษฐานอายุ 40 ปี ด้วย

ปัญหาขีดจำกัดประสิทธิภาพของตารางแฮช

  • ตารางแฮชเป็นโครงสร้างข้อมูลสำหรับจัดเก็บและเข้าถึงข้อมูล โดยพื้นฐานรองรับการทำงาน 3 อย่าง
    • ค้นหา (query) องค์ประกอบ
    • ลบองค์ประกอบ
    • แทรกองค์ประกอบลงในสล็อตว่าง
  • ตารางแฮชแรก ๆ ย้อนกลับไปถึงช่วงต้นทศวรรษ 1950 และนับแต่นั้นก็เป็นโครงสร้างข้อมูลเก่าแก่ที่ถูกศึกษาและใช้งานต่อเนื่องในวิทยาการคอมพิวเตอร์
  • ขีดจำกัดความเร็วของการค้นหาหรือการแทรกมักเชื่อมโยงกับเวลาที่ใช้ในการหา ตำแหน่งว่าง ในตารางแฮช
  • ระดับที่ตารางแฮชเต็มสามารถแสดงเป็นสัดส่วนรวมได้ แต่เมื่อศึกษาตารางที่เกือบเต็ม นักวิจัยใช้ค่า x
    • ถ้า x เท่ากับ 100 ตารางจะเต็ม 99%
    • ถ้า x เท่ากับ 1,000 ตารางจะเต็ม 99.9%
  • ในตารางแฮชทั่วไปบางประเภท เป็นที่รู้กันว่าเวลาแทรกคาดหวังในกรณีเลวร้ายที่สุด เช่น การใส่องค์ประกอบลงในตำแหน่งว่างสุดท้ายที่เหลืออยู่ จะ เป็นสัดส่วนกับ x

ข้อสันนิษฐานของ Yao ปี 1985 และการโต้แย้ง

  • Andrew Yao เสนอในบทความวิจัยปี 1985 ว่า สำหรับตารางแฮชที่มีคุณสมบัติบางอย่าง วิธีที่ดีที่สุดในการหาองค์ประกอบแต่ละตัวหรือช่องว่าง คือ การตรวจสอบแบบสม่ำเสมอ ซึ่งไล่ดูตำแหน่งที่เป็นไปได้แบบสุ่ม
  • ในกรณีเลวร้ายที่สุด คือสถานการณ์ที่ต้องหาตำแหน่งว่างสุดท้ายที่เหลืออยู่ ข้อสันนิษฐานว่า ไม่อาจดีกว่า x ได้ ถูกยอมรับกันเป็นส่วนใหญ่ว่าจริงอยู่ตลอด 40 ปี
  • Krapivin เดินหน้าสำรวจเรื่องที่เกี่ยวข้องกับ Tiny Pointers โดยไม่รู้ข้อสันนิษฐานของ Yao และสร้างตารางแฮชแบบใหม่ที่ไม่พึ่งพาการตรวจสอบแบบสม่ำเสมอ
  • บทความวิจัยเดือนมกราคม 2025 ของ Krapivin, Farach-Colton และ Kuszmaul แสดงให้เห็นว่า ในตารางแฮชแบบใหม่นี้ เวลาค้นหาและแทรกในกรณีเลวร้ายที่สุดเป็นสัดส่วนกับ (log x)²
  • ผลลัพธ์นี้ขัดแย้งโดยตรงกับข้อสันนิษฐานของ Yao และทีมวิจัยยังพิสูจน์ด้วยว่า ในหมวดหมู่ตารางแฮชยอดนิยมที่ Yao ศึกษา (log x)² เป็นขอบเขตเหมาะที่สุดที่ลดลงไปกว่านี้ไม่ได้

ผลลัพธ์ที่น่าประหลาดใจยิ่งกว่าเกี่ยวกับเวลาเฉลี่ยในการค้นหา

  • ในปี 1985 Yao ไม่ได้ศึกษําแค่เวลาค้นหาในกรณีเลวร้ายที่สุด แต่ยังศึกษํา เวลาเฉลี่ย ของการค้นหาที่เป็นไปได้ทั้งหมดด้วย
  • เขาพิสูจน์ว่า ในตารางแฮชที่มีคุณสมบัติบางอย่าง โดยเฉพาะตารางแฮชแบบ โลภ (greedy) ที่ต้องใส่องค์ประกอบใหม่ลงในตำแหน่งแรกที่เป็นไปได้ เวลาเฉลี่ยไม่อาจดีกว่า log x ได้
  • Farach-Colton, Krapivin และ Kuszmaul พยายามตรวจสอบว่าข้อจำกัดเดียวกันนี้ใช้กับตารางแฮชแบบไม่โลภด้วยหรือไม่ และแสดงผ่านตัวอย่างโต้แย้งว่าไม่ใช่
  • ตารางแฮชแบบไม่โลภที่เป็นตัวอย่างโต้แย้งนี้มีเวลาเฉลี่ยในการค้นหา ดีกว่า log x มาก และในความเป็นจริงไม่ขึ้นกับ x เลย
  • การที่สามารถทำ เวลาเฉลี่ยในการค้นหาเป็นค่าคงที่ ได้ โดยไม่ขึ้นกับว่าตารางแฮชเต็มแค่ไหน เป็นผลลัพธ์ที่แม้แต่ทีมวิจัยเองก็ไม่คาดคิด

การปรับปรุงเชิงทฤษฎีสำหรับโครงสร้างข้อมูลเก่าแก่

  • Alex Conway ประเมินว่า ตารางแฮชเป็นหนึ่งในโครงสร้างข้อมูลที่เก่าแก่ที่สุด และยังคงเป็นหนึ่งในวิธีจัดเก็บข้อมูลที่มีประสิทธิภาพที่สุด
  • Guy Blelloch มองว่าผลลัพธ์นี้งดงามตรงที่หยิบปัญหาคลาสสิกมาศึกษาและแก้ไขได้
  • Sepehr Assadi ประเมินว่า ทีมวิจัยไม่เพียงโต้แย้งข้อสันนิษฐานของ Yao เท่านั้น แต่ยังพบ คำตอบที่ดีที่สุด ต่อคำถามของเขาด้วย
  • Conway มองว่า แม้ผลลัพธ์นี้จะยังไม่นำไปสู่การประยุกต์ใช้งานทันที แต่การทำความเข้าใจโครงสร้างข้อมูลประเภทนี้ให้ดีขึ้นเป็นเรื่องสำคัญ
  • ผลลัพธ์ครั้งนี้ซึ่งจัดระเบียบขีดจำกัดทางทฤษฎีของตารางแฮชใหม่ จะเป็นรากฐานที่อาจนำไปสู่การปรับปรุงประสิทธิภาพจริงในอนาคต

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-02-11
ความคิดเห็นบน Hacker News

  • มองว่า Krapivin สามารถสร้างความก้าวหน้าครั้งนี้ได้เพราะไม่รู้จัก ข้อคาดการณ์ของ Yao และผู้พัฒนา Balatro ก็สร้างผลงานที่ได้รับรางวัลได้เพราะไม่ค่อยรู้จักเกม deck builder เดิม ๆ
    ทำให้คิดว่าวิธีเข้าหาปัญหาที่ดีที่สุดอาจเป็นการไม่รู้หรือเมินความพยายามคล้าย ๆ กันส่วนใหญ่ในอดีต
    โลกตอนนี้เชื่อมโยงกันมากเกินไป จนความสดใหม่ที่ไม่ตกอยู่ใน กรอบความคิด ของคนรุ่นก่อนพบเห็นได้น้อยลง และแม้อินเทอร์เน็ตจะยอดเยี่ยม แต่ก็น่าเสียดายที่มันทำให้ความคิดเป็นเนื้อเดียวกัน

    • มองว่าการเมินความพยายามก่อนหน้าเป็นเรื่องดีเฉพาะเมื่อมี วิธีแก้ใหม่ ที่ไปคนละทิศทางกับของเดิมโดยสิ้นเชิงอยู่จริงเท่านั้น
      โดยมากแล้ว ถ้าเมินกรณีความสำเร็จในอดีต ก็เท่ากับกลับไปหว่านเมล็ดบนผืนดินที่เคยพิสูจน์แล้วว่าแห้งแล้งอีกครั้ง
    • จากประสบการณ์ของผม แนวทางที่ดีที่สุดคือ ลองแก้ปัญหาเองก่อนโดยยังไม่อ่านงานวิจัยก่อนหน้า จากนั้นค่อยอ่านงานวิจัยเหล่านั้น แล้วปรับปรุงแนวทางของตัวเองให้สอดคล้องกับมัน
      ถ้าอ่านงานวิจัยก่อนหน้าเร็วเกินไป ก็จะติดอยู่ในกรอบความคิดเดิม ๆ แต่ถ้าไม่อ่านเลย ก็จะพลาดสิ่งสำคัญที่ตัวเองคิดไม่ถึง
      แม้แนวทางของตัวเองจะด้อยกว่าระดับล้ำหน้าสุดในปัจจุบัน แต่การเปรียบเทียบจะทำให้ได้อินไซต์สำคัญว่าทำไม แนวทางระดับล้ำหน้าสุด จึงดีกว่า
    • ผู้พัฒนา Balatro รู้จัก deck builder และได้รับแรงบันดาลใจโดยตรงจาก Luck be a Landlord แต่บอกว่าไม่รู้ว่าแนวนี้ใหญ่แค่ไหน
      ตามคำพูดโดยตรงของผู้พัฒนา อิทธิพลที่ใหญ่ที่สุดต่อ Balatro คือ Luck be a Landlord และหลังจากดูวิดีโอการเล่นของ Northernlion ไปไม่กี่คลิป เขาก็ชอบแนวคิด roguelike แบบเน้นทำคะแนนในธีมที่ไม่ใช่แฟนตาซี จึงเปลี่ยนเกมการ์ดที่กำลังทำอยู่ให้เป็น roguelike
      ตั้งแต่นั้นมา เขาตั้งใจเว้นระยะจากแนวเกมนี้ และอยากสำรวจพื้นที่การออกแบบแบบไร้เดียงสาโดยลองผิดลองถูกด้วยตัวเอง
      แม้จะได้ยินคนเปรียบเทียบกับ Slay the Spire อยู่บ่อย ๆ แต่ตอนออกแบบ Balatro เขายังไม่เคยเล่นหรือดูวิดีโอของเกมนั้น และเพิ่งมารู้จักในภายหลังมาก ๆ
      https://www.reddit.com/r/Games/comments/1bdtmlg/comment/kup7...
    • “ผู้คนกำลังเอาใจช่วยเธออยู่นะ” เธอกล่าวพร้อมรอยยิ้ม
      “แต่ผมไม่มีทางทำได้เลยถ้าไม่ได้รับความช่วยเหลือจากทุกคน” [Milo] แย้ง
      “ก็อาจจะใช่” Reason กล่าวอย่างเคร่งขรึม “แต่เธอมีความกล้าที่จะลอง และสิ่งที่เธอทำได้มักขึ้นอยู่กับสิ่งที่เธอตั้งใจจะทำ”
      King Azaz กล่าวว่า “เพราะอย่างนั้น เรื่องสำคัญมากอย่างหนึ่งในการผจญภัยของเธอ เราจึงบอกไม่ได้จนกว่าเธอจะกลับมา”
      “ผมจำได้” Milo กล่าวอย่างกระตือรือร้น “ตอนนี้บอกผมเถอะครับ”
      “มันเป็นไปไม่ได้” ราชากล่าว พลางมองไปที่ Mathemagician
      “เป็นไปไม่ได้โดยสิ้นเชิง” Mathemagician กล่าว พลางมองไปที่ราชา
      “ถ้าอย่างนั้น….” เจ้าแมลงกล่าวขึ้นอย่างกะทันหันด้วยอาการมึนงง
      “ใช่แล้ว ถูกต้อง” ทั้งสองกล่าวพร้อมกัน “แต่ถ้าเราบอกเธอตอนนั้น เธออาจไม่ออกเดินทางก็ได้… และอย่างที่เธอได้รู้แล้ว มีหลายสิ่งหลายอย่างที่เป็นไปได้จริง ๆ ตราบใดที่เธอไม่รู้ว่ามันเป็นไปไม่ได้”
      — The Phantom Tollbooth (1961)
    • อาจารย์ที่ผมเคยเรียนตอนมหาวิทยาลัยคนหนึ่งมีผลงานตีพิมพ์ชิ้นแรกมาจากคำตอบการบ้านที่ส่งไป โดยบังเอิญไปแก้ ปัญหาที่ยังไม่มีใครแก้ได้ เกี่ยวกับขอบเขตของปัญหาหนึ่งได้
      ผมมีเหตุหลายอย่างจนสอบตกวิชานั้นและต้องเรียนใหม่ จึงสังเกตเห็นนิสัยอย่างหนึ่ง
      ในทุกเทอม ช่วงครึ่งหลังของรายวิชา เขาจะใส่โจทย์หนึ่งข้อในชุดโจทย์ราว 30 ข้อในรูปแบบที่จริง ๆ แล้วเป็นปัญหาที่ยังไม่มีใครแก้ได้ แล้วก่อนกำหนดส่งหนึ่งหรือสองวันก็ส่งฉบับแก้ไขมาโดยบอกว่า “อ้อ ผมพลาดไป”
      จากที่มันเกิดขึ้นแค่ครั้งเดียวเป๊ะ ๆ ทุกครั้ง ผมว่าไม่น่าจะเป็นเรื่องบังเอิญ

  • monort [0] ส่งลิงก์วิดีโอ [1] มาให้ ซึ่งช่วยได้มาก
    นี่เป็นสรุปเร็ว ๆ หลังจากดูวิดีโอหนึ่งรอบ ชื่อของมันคือ Funnel Hashing
    แนวคิดคือแบ่งอาร์เรย์ออกเป็นอาร์เรย์ย่อยที่เล็กลงแบบเอ็กซ์โปเนนเชียล ก้อนแรกคือ n/m ก้อนที่สองคือ n/(m^2) ลดลงไปเรื่อย ๆ จนเหลือองค์ประกอบเดียว ถ้าเรียกว่า A0, A1 ฯลฯ ก็จะได้ |A0| = n/m, |A1| = n/(m^2) และมีทั้งหมด k ขั้น
    ลองแทรกใน A0 จำนวน c ครั้ง ถ้าล้มเหลวก็ลองใน A1 จำนวน c ครั้ง ถ้ายังล้มเหลวอีก ก็ไล่ลงไปตาม “funnel” จนกว่าจะเจอสล็อตว่าง
    เรียก \delta ว่าอัตราส่วนของสล็อตว่าง แต่ผมไม่แน่ใจว่าค่านี้เป็นพารามิเตอร์ที่กำหนดตอนสร้างแฮชเทเบิล หรือเป็นค่าที่อัปเดตแบบไดนามิก ถ้าตั้ง c = log(1/d), k = log(1/d) ความซับซ้อนเวลาในกรณีเลวร้ายสุดจะเป็น O(log^2(1/d))
    ผมเข้าใจว่าวิธีนี้เลี่ยง ผลลัพธ์ของ Yao ได้เพราะมันไม่ใช่แบบ greedy ผลลัพธ์ของ Yao ใช้ได้กับนโยบายการแทรกและค้นหาแบบ greedy ส่วนวิธีข้างต้นไหลลงไปเป็นลูกโซ่ตาม funnel จึงเป็นแบบ non-greedy
    รายละเอียดปลีกย่อยคงมีส่วนที่ยุ่งยากอยู่มาก แต่เท่าที่ผมเข้าใจไอเดียก็ประมาณนี้ ถ้าผมจับประเด็นผิดไปหมด ช่วยบอกด้วยก็ดี
    ทำให้นึกถึงไอเดีย “Distinct Elements in Streams” ของ Chakraborty, Vinodchandran, Meel [2] มาก
    [0] https://news.ycombinator.com/item?id=43007860
    [1] https://www.youtube.com/watch?v=ArQNyOU1hyE
    [2] https://arxiv.org/pdf/2301.10191

    • จริง ๆ แล้วเสนออัลกอริทึมสองตัวคือ Funnel Hashing และ Elastic Hashing
      Funnel Hashing เป็นแบบ “greedy” และหักล้างข้อคาดเดาของ Yao เกี่ยวกับกลไกแฮชแบบ greedy
      Elastic Hashing เป็นแบบ “non-greedy” และให้เวลาแบบ amortized ที่ดีกว่าอัลกอริทึมแบบ greedy
    • คำอธิบายที่ว่าเลี่ยงข้อคาดเดาของ Yao ได้เพราะเป็น non-greedy ขัดกับบทความ
      ไม่รู้ว่าบทความผิด หรือเป็นการเข้าใจเปเปอร์ผิด แต่สงสัยว่าผู้เขียนบทความชี้จุดที่ตนเองไม่รู้หรือเปล่า
    • ส่วนที่ดูวิดีโอแล้วไม่เข้าใจคือ ถ้าเกิด ชนกันไปจนถึงปลาย funnel ซึ่งนาน ๆ ครั้งจะเกิด จะเกิดอะไรขึ้น
      ดูเหมือนเกี่ยวกับ “ขั้นตอนสุดท้ายพิเศษเพื่อจับคีย์ไม่กี่ตัว” แถว ๆ นาที 14:41 ของวิดีโอ แต่ถ้าส่วนนั้นต้องมีขนาดคงที่ มันก็อาจเต็มได้ แล้วกรณีนั้นควรทำอย่างไร?
    • เป็นไอเดียที่ค่อนข้างเรียบร้อยและอาจมีประโยชน์ในสภาพแวดล้อมที่มีข้อจำกัดด้านหน่วยความจำ
      [โปรโมตแบบหน้าด้าน ๆ]: ถ้าสนใจแฮชเทเบิล Dandelion Hashtable [0] ก็น่าดูเหมือนกัน
      เราใช้มันในฐานข้อมูลรุ่นถัดไปของเรา และนำเสนอที่ HPDC'24 ปัจจุบันเป็นแฮชเทเบิลแบบ in-memory ที่เร็วที่สุดตามการใช้งานจริง
      มันปรับปรุง closed addressing ด้วยการทำ chaining แบบจำกัด cacheline ทำให้เซิร์ฟเวอร์ทั่วไปประมวลผลคำขอ in-memory ได้มากกว่า 1 พันล้านรายการต่อวินาที
      [0] https://dandelion-datastore.com/#dlht
    • Funnel hashing เป็นแบบ greedy

  • การนำเสนอของผู้คิดค้น: https://www.youtube.com/watch?v=ArQNyOU1hyE

    • ในรูปแบบที่ไม่เคร่งครัด น่าจะเป็นสิ่งที่หลายคนเคยนึกถึงแล้ว แต่ไม่ได้คิดว่าพิเศษอะไร
      มันดูเหมือนหนึ่งใน ทริกจัดการทรัพยากร ที่ทำกันเมื่อถูกข้อจำกัดบีบและทรัพยากรไม่พอ
      การแบ่งตามลำดับความสำคัญเป็นแนวทางที่พบได้ทั่วไปในการจัดสรรทรัพยากร และนี่ก็เป็นรูปแบบหนึ่งของมัน
      น่าสงสัยว่ามี “ทริกในสนามเพลาะ” แบบอื่น ๆ ที่คนทำงานหน้างานทำกันอยู่กี่อย่าง ที่แม้แต่ผู้คิดค้นเองก็ไม่รู้ว่าเป็นเรื่องยิ่งใหญ่ แต่กลับไปพลิกสิ่งที่เป็นที่ยอมรับกันกว้างขวางได้ เช่น “ตอนมีของต้องส่งเยอะ ๆ ผมหาวิธีฉลาด ๆ ในการวาดเส้นทางที่มักเร็วที่สุดได้...” อะไรทำนองนั้น
      แน่นอนว่าการมองเห็นคุณค่าของมัน ทำให้เป็นทางการ ลงมือทำ และตีพิมพ์เป็นเปเปอร์นั้นต้องใช้ความพยายามมาก ไม่ได้ตั้งใจจะลดทอนเครดิตส่วนนั้น
    • ยิ่งเชื่อมากขึ้นเรื่อย ๆ ว่าเปเปอร์จะเข้าใจง่ายขึ้นมากเมื่อมีวิดีโอการนำเสนอจากผู้สร้างประกอบ
      อยากให้เปเปอร์มี วิดีโอพรีเซนต์ แนบมาด้วยเลย
    • วิดีโอดีกว่าบทความมาก
      อย่างไรก็ตาม แนวทางนี้ก็จัดสรรหน่วยความจำเพิ่มผ่านอาร์เรย์เสริมอยู่ดี เลยรู้สึกแปลกนิดหน่อยว่ามันดีกว่าการแค่ จัดสรรเกิน เพื่อลดโอกาสคีย์ชนกันและทำให้กรณีเลวร้ายสุดแย่น้อยลงอย่างไร

  • ลองอ่านผ่าน ๆ เปเปอร์ [1] แล้ว ความต่างหลักดูเหมือนอยู่ที่อัลกอริทึมการแทรกของแฮชเทเบิลไม่ได้เติมสล็อตว่างแรกที่เจอแบบ greedy แต่ค้นต่อไปไกลกว่านั้น
    เมื่อรวมกับลำดับการ probe ที่ชาญฉลาด จึงพิสูจน์ได้ว่าสามารถหาสล็อตว่างได้อย่างมีประสิทธิภาพ แม้ในสถานการณ์ที่ตารางเต็มมาก
    กล่าวคือ การแทรกตอนที่แฮชเทเบิลยังไม่ค่อยเต็มจะช้าลง แต่หลีกเลี่ยงสถานการณ์เลวร้ายสุดที่ต้องค้นโดยไม่รู้ว่าสล็อตว่างไม่กี่ช่องสุดท้ายอยู่ที่ไหน
    [1]: https://arxiv.org/pdf/2501.02305
    เป็นผลลัพธ์เชิงทฤษฎีที่น่าสนใจ แต่ในทางปฏิบัติ ผมคาดว่า “เคล็ดลับ” ปัจจุบันที่จัดสรรตารางให้ใหญ่กว่าที่จำเป็นน่าจะเป็นทางออกที่ดีกว่า
    ตัวอย่างเช่น hashbrown ของ Rust ตั้งใจเว้นตารางไว้ 1/8 หรือ 12.5% ให้เป็นช่องว่าง ซึ่งใช้หน่วยความจำเพิ่มขึ้นเล็กน้อย แต่ทำให้การแทรกและการค้นหาเร็วมากด้วยความน่าจะเป็นสูง

    • ผมอาจอ่านอัลกอริทึมผิดก็ได้ แต่จากเปเปอร์ การปรับปรุงหลักดูเหมือนเป็น กลยุทธ์แบบไม่สม่ำเสมอ ที่แบ่งอาร์เรย์เป็น bucket และโฟกัส bucket ต่างกันตามระดับความเต็มของตาราง
      วิธีนี้เพิ่มจำนวนตำแหน่ง probe โดยเฉลี่ย แม้ตอนที่ตารางยังไม่ค่อยเต็ม
      แต่ภายในกลยุทธ์นี้ก็ยังวางรายการลงในสล็อตว่างแรกที่เห็นอยู่ดี
      “การข้ามสล็อต” เกี่ยวข้องกับการกระโดดไปข้างหน้าในลำดับแฮช
    • อาจทำไฮบริดได้ไหม คือใช้ การเติมแบบ greedy ไปช่วงหนึ่ง แล้วเมื่อ table เริ่มเต็มจึงสลับเป็นการเติมที่ละเอียดขึ้นด้วย heuristic?

  • มีใครมี implementation ง่าย ๆ ของ ‘Tiny pointers’ ไหม? หัวผมชอบดู โค้ดหรือ pseudocode ก่อนดู proof

  • เจ๋งดี ผมสงสัยมาตลอดว่าจะมีวิธี containerize ตารางแบบนี้ได้ไหม
    ตารางทั่วไปเหมือนเรือบรรทุกสินค้าเทกองที่ยัดทุกอย่างลงไป ถ้าจัดระเบียบได้ดีกว่าเหมือนเรือคอนเทนเนอร์ ก็น่าจะบรรทุกอะไรได้มากขึ้นอย่างมีประสิทธิภาพกว่า และขนลงได้เร็วขึ้นมากด้วย

    • ทำง่ายมาก
      แปลงแถวของตารางให้เป็นสตริงหรืออะไรอย่าง JSON แล้วใช้ base16 กับตัวแปรนั้น ก็จะได้สตริง base16 ของข้อมูลนั้น
      สร้างตารางแฮชแล้วตั้งค่าคีย์สำหรับสตริง base16 นั้น ก็จะได้คอนเทนเนอร์ที่บรรจุข้อมูล
      จากนั้นก็แค่ถอดรหัสสตริงฐานสิบหก ก็จะได้ข้อมูล base32

  • คุณสมบัติทางทฤษฎีของตารางแฮชน่าประทับใจมาตลอดจนเกือบเหมือนเวทมนตร์ และผลลัพธ์ครั้งนี้ก็ขยายมันออกไปอีก
    สิ่งที่เคยรู้สึกแปลกคือ ทำไมตารางแฮชถึงดีกว่า tree ซึ่งโดยสัญชาตญาณดูเหมือนเป็นวิธีที่มีประสิทธิภาพที่สุดในการเก็บข้อมูลได้มากขนาดนั้น
    สิ่งที่ผมตระหนักคือ ทฤษฎีตารางแฮชจัดการกับเซตของออบเจ็กต์ขนาดคงที่ เราสร้างฟังก์ชันแฮชสำหรับเซตคงที่นี้ แล้วใช้มันเหมือนดัชนีเวกเตอร์เพื่อเก็บในเวกเตอร์ที่จัดสรรไว้ล่วงหน้า จึงได้สูตรที่ทำให้การแทรก ลบ และค้นหาใกล้เคียง O(1) ในขณะที่โครงสร้าง tree หลายแบบไม่ได้สมมติขนาดเฉพาะไว้
    ปัญหาคือต้องกำหนดขนาดไว้ล่วงหน้า และเมื่อเวกเตอร์เกือบเต็ม กระบวนการอย่างการแทรกอาจช้าลงได้
    เท่าที่อ่านบทความคร่าว ๆ ผลลัพธ์ครั้งนี้ดูเหมือนจะแก้ส่วนที่ช้าลงนั้น และทำให้การแทรกยังเร็วได้แม้ในตารางที่เกือบเต็ม
    น่าสนใจและฉลาดดี แต่คงไม่ใช่ความก้าวหน้าเชิงปฏิบัติที่ใหญ่โตนัก ในงานจริงผมคิดว่าแทนที่จะคิดหาวิธีเติมตารางอย่างชาญฉลาด แค่เพิ่มขนาดที่ตั้งสมมติไว้ก็พอ
    เขียนไว้เพื่อเช็กว่าผมเข้าใจถูกไหม ถ้าผิดก็แก้ได้เลย

    • การพิสูจน์การทำงานแบบเวลาคงที่รวมเวลาที่ใช้ในการปรับขนาดตารางไว้ด้วย
      ในการแทรกที่มีการปรับขนาด จะใช้เวลามากกว่ามากในเชิงเส้นตามขนาดตาราง แต่เวลานั้นถูก amortize ไปกับการแทรกทั้งหมดที่ทำมาก่อนแล้ว
      ถ้าขยายให้ใหญ่พอทุกครั้งที่ตารางเริ่มเต็มเกินไป ความถี่ก็จะค่อย ๆ ลดลง ดังนั้นโดยเฉลี่ยแล้วยังเป็นเวลาคงที่อยู่
    • tree มีการเรียงลำดับ จึงเหมาะกับการไล่ดูหรือค้นหาสับเซตและช่วง ส่วน hashmap เหมาะกว่าสำหรับการ เจาะไปหา คีย์เฉพาะ เช่น การค้นหาแบบคีย์-ค่า
    • เรื่องนี้น่าจะจริงเฉพาะในโลก imperative ที่ใช้การเปลี่ยนแปลงสถานะเท่านั้น
      ในโลก functional tree ยังน่าจะเหมาะกว่าอยู่มาก
    • อย่างที่พูดคร่าว ๆ ดูเหมือนเป็นไอเดียที่แบ่งตารางเชิงแนวคิดเป็นโครงสร้าง 2 มิติ เติม “แถว” หนึ่งให้เต็มประมาณ 75% แล้วค่อยย้ายไปแถวถัดไป
      ผมไม่มีเวลาอ่านเปเปอร์ให้เข้าใจทั้งหมด แต่เขาอ้างว่าวิธีนี้ทำให้การแทรกเร็วอย่างสม่ำเสมอ ผมเข้าใจถึง 75% ของความจุรวม แต่ไม่รู้ว่าพอทุกแถวถึง 75% แล้วจะมีโหมดอื่นหรือไม่
      เขายังอ้างว่าการค้นหาก็เร็ว แต่ผมอ่านไม่พอว่าการค้นหาทำงานอย่างไรหรือทำไมจึงเร็ว
      มีหลายสถานการณ์ที่ดีมากถ้าตารางแฮชที่เกือบเต็มยังทำงานได้ ระหว่างที่โปรแกรมรันอยู่เราไม่ได้ปรับขนาดได้เสมอไป และในบางสภาพแวดล้อมหน่วยความจำสำคัญมาก
      ถึงอย่างนั้นก็อยากดู implementation แล้วลองเล่นเอง ผมยังไม่มั่นใจว่าในกรณีทั่วไปมัน “คุ้มค่า” หรือไม่
      ประสิทธิภาพแคชก็น่าจะไม่ดีด้วย ตารางแฮชส่วนใหญ่ก็เป็นแบบนั้น ยกเว้นกรณีที่อ่านด้วย linear probing ในตารางที่ค่อนข้างเต็ม ซึ่งสามารถดึงจากหน่วยความจำแบบต่อเนื่องมาตรวจได้
      ยังไม่ชัดเจนว่าคุ้มค่าในแง่ประสิทธิภาพหรือไม่ แต่เป็นไอเดียใหม่ที่น่าสนใจ และอยากเข้าใจให้ครบ

  • ผมไม่เข้าใจส่วนที่บอกว่า “ในตารางแฮชใหม่นี้ เวลาที่ต้องใช้สำหรับ query และการแทรกในกรณีแย่สุดแปรผันตาม (log x)2 และเร็วกว่า x มาก” แต่ก็ยังบอกว่า “ผลลัพธ์ของทีมอาจไม่นำไปสู่การใช้งานทันที”
    ทำไมถึงไม่นำไปสู่การใช้งานทันทีล่ะ? หมายความว่าเป็นสถานการณ์ที่สามารถปรับ implementation ของแฮชให้ดีขึ้นได้จากการวิเคราะห์ use case จริง มากกว่าวิธีเชิงคณิตศาสตร์ล้วน ๆ หรือเปล่า?

    • ผมไม่ได้อ่านเปเปอร์ แต่บางครั้ง asymptotic improvement ก็ไม่กลายเป็นการปรับปรุงในโลกจริง เพราะมีค่าคงที่ตัวคูณขนาดใหญ่ที่การวิเคราะห์ O() ไม่แสดงไว้
      บางทีต้องมีชุดข้อมูลใหญ่แบบไม่สมจริงถึงจะเห็นความเร็วที่เพิ่มขึ้น
    • ผมไม่ได้ตามสถานะล่าสุดดีนัก แต่เคย implement ตารางแฮชอยู่หลายครั้ง และปกติก็ขยายเมื่อเต็ม 75%
      แบบนั้น x จะไม่เกิน 4 ดังนั้นการปรับปรุง O(x) เป็น O((log x)^2) จึงไม่มีความหมายเมื่อ x เล็กขนาดนั้น
      ในแอปพลิเคชันเฉพาะบางอย่างที่มีข้อจำกัดด้านหน่วยความจำอาจตั้ง x ให้ใหญ่ขึ้น แต่โดยส่วนตัวผมไม่เคยเจอกรณีแบบนั้น
    • ในงานจริงคงแทบไม่มีใครใช้ uniform probing hash table
      ทุกครั้งที่ต้องการ load factor สูงมาก เช่น เกิน 90% cuckoo hashing ก็เพียงพอแล้ว และที่ 70~80% หรือต่ำกว่า linear probing ก็เร็วมากและดีพอ
    • ในการใช้งานจริง เราจองพื้นที่ให้ตารางแฮชเพิ่มอีกเล็กน้อยเพื่อเลี่ยง operation กรณีแย่สุด
      ผลลัพธ์ใหม่นี้ยังมีต้นทุนที่ทำให้การแทรกใน “กรณีดี” ช้าลงด้วย
    • การวิเคราะห์ complexity กับการเขียนโปรแกรมระบบจริงแยกทางกันมาพักหนึ่งแล้ว
      ในเปเปอร์นี้ผมไม่เห็นอะไรที่จะส่งผลต่อการปฏิบัติงานจริง

  • ผลลัพธ์นี้ดูสำคัญเฉพาะเมื่อ ตารางแฮชเกือบเต็มเท่านั้น
    ถ้าอย่างนั้นแค่กำหนดขนาดตารางให้ใหญ่ขึ้น 10% หรือถ้าปรับขนาดได้ก็ resize ให้เร็วขึ้นไม่ได้หรือ?

    • ใช่ ตารางแฮชในโลกจริงส่วนใหญ่ก็ทำแบบนั้น
      ถ้าความเป็นไปได้ของ hash collision สูงเกินไป มันก็ปรับขนาดเอง
    • ในโลกจริง อัตราการเติมมาตรฐานของ linear probing คือ 75% และตอนนั้น locality ก็ดีที่สุดด้วย
      ถ้าตารางเต็มเกินไป ก็แค่จัดสรรหน่วยความจำเพิ่มเป็นสองเท่าหรือเพิ่มตามสัดส่วนคงที่ แล้วคัดลอกรายการเดิมไป
      ตาราง probing แบบไม่เชิงเส้นส่วนใหญ่ เช่น cuckoo hashing เสียเปรียบเพราะความจริงที่ว่า RAM ไม่ได้ “สุ่ม” เลย

  • มีใครรู้จัก GitHub repository ที่มี implementation นี้ไหม?