เทคนิคการสำรวจฟังก์ชันแฮชจำนวนเต็มแบบอัตโนมัติ

 (github.com/skeeto)
3 คะแนน โดย GN⁺ 2024-05-06 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Hash Function Prospector เป็นเครื่องมือที่สร้าง ฟังก์ชันแฮชจำนวนเต็ม แบบสุ่มจำนวนมหาศาล แล้วทำ JIT compile เพื่อประเมินพฤติกรรมแบบ avalanche ก่อนจะแสดงฟังก์ชันที่ดีที่สุดในปัจจุบันออกมาเป็นไวยากรณ์ภาษา C
  • การประเมินใช้ avalanche score ซึ่งหมายถึงจำนวนบิตเอาต์พุตที่โดยเฉลี่ยยังคงค่าเดิมเมื่อพลิกบิตอินพุตเพียงบิตเดียว ยิ่งต่ำยิ่งดี และค่าที่อุดมคติคือ 0
  • เป้าหมายการสำรวจคือฟังก์ชันแฮชจำนวนเต็มแบบ 32 บิตและ 64 บิต โดยตัวเครื่องมือรันได้เฉพาะบน x86-64 เพราะพึ่งพา JIT compiler แต่ฟังก์ชันที่ค้นพบสามารถนำไปใช้ในสภาพแวดล้อมอื่นได้
  • ฟังก์ชันสำคัญที่ค้นพบใช้โครงแบบ xorshift-multiply-xorshift โดย lowbias32 แบบ 2 รอบมี bias ต่ำกว่า MurmurHash3 32-bit finalizer อยู่เล็กน้อย และ triple32 แบบ 3 รอบเข้าใกล้ขีดจำกัดเชิงทฤษฎีของ bias
  • การวัด bias แบบ exact สำหรับฟังก์ชัน 32 บิตทำได้ด้วย -E และ -e ส่วนแฮช 16 บิตใช้เครื่องมือแยกชื่อ hp16 และต้องระวังกฎ integer promotion ของภาษา C

บทบาทของ Hash Function Prospector

  • Hash Function Prospector เป็นเครื่องมือสำหรับ ค้นหาฟังก์ชันแฮชจำนวนเต็ม แบบอัตโนมัติ
  • มันสร้างฟังก์ชันแฮชจำนวนเต็มแบบสุ่มขึ้นมาหลายพันล้านแบบ จากนั้นทำ JIT compile แล้วประเมินพฤติกรรมแบบ avalanche
  • ในบรรดาฟังก์ชันที่สร้างขึ้น ฟังก์ชันที่ดีที่สุดในปัจจุบันจะถูกแสดงออกมาเป็น ไวยากรณ์ภาษา C
  • มีลิงก์บทความที่เกี่ยวข้องคือ Prospecting for Hash Functions

เกณฑ์การประเมินและขอบเขตที่รองรับ

  • avalanche score คือจำนวนบิตเอาต์พุตที่โดยเฉลี่ยยังคงค่าเดิมเมื่อพลิกบิตอินพุตหนึ่งบิต
    • ยิ่งคะแนนต่ำยิ่งดี
    • ในอุดมคติ บิตเอาต์พุตทุกบิตควรมีโอกาส 50% ที่จะพลิก ทำให้ score เป็น 0
  • Prospector สามารถสร้างฟังก์ชันแฮชจำนวนเต็มแบบ 32 บิต และ 64 บิต ได้
  • สามารถดูตัวเลือกทั้งหมดได้จากวิธีใช้ -h
  • เนื่องจาก JIT compiler ตัวเครื่องมือเองจึงรองรับเฉพาะ x86-64
    • อย่างไรก็ตาม ฟังก์ชันแฮชที่ค้นพบสามารถนำไปใช้ที่ไหนก็ได้

การดำเนินการแบบผันกลับได้ที่ใช้ในการสำรวจ

  • ตัวสร้างจะประกอบฟังก์ชันขึ้นแบบสุ่มจาก การดำเนินการแบบผันกลับได้ 9 แบบ ที่เลือกไว้
  • รายการการดำเนินการมีดังนี้
    • x = ~x
    • x ^= constant
    • x *= constant | 1
    • x += constant
    • x ^= x >> constant
    • x ^= x << constant
    • x += x << constant
    • x -= x << constant
    • x <<<= constant
    • x = bswap(x)
  • ในทางเทคนิค x = ~x สามารถเขียนแทนด้วย x ^= constant ได้ แต่โอกาสที่ตัวสร้างจะสุ่มเลือกค่าคงที่ XOR นั้นได้โดยบังเอิญมีต่ำ จึงนับเป็นการดำเนินการแยกต่างหาก

ฟังก์ชันแฮช 32 บิตที่ค้นพบ

  • ฟังก์ชันแบบ 2 รอบ

    • หนึ่งในกลุ่มฟังก์ชันที่ค้นพบและใช้งานได้จริงคือโครงแบบ 2-round xorshift-multiply-xorshift
    • TheIronBorn ใช้การปรับให้เหมาะสมเชิงจัดหมู่เพื่อหาพารามิเตอร์ที่ดีที่สุดเท่าที่รู้จักของโครงแบบนี้ และผลลัพธ์คือ [16 21f0aaad 15 d35a2d97 15] = 0.10760229515479501
    • lowbias32 เป็น permutation แบบ 2 รอบสำหรับ 32 บิตที่มี bias ต่ำ และมี bias ต่ำกว่า MurmurHash3 32-bit finalizer อยู่เพียงเล็กน้อย
    • exact bias ของ lowbias32 คือ 0.17353355999581582
    • โครงแบบนี้ถูกค้นพบโดย Prospector และพารามิเตอร์ถูกปรับแต่งด้วย hill climbing และ genetic algorithm
    • มีฟังก์ชันผกผัน lowbias32_r ให้ด้วย
    • prospector32 เป็นฟังก์ชันที่ค้นพบด้วย Prospector เพียงอย่างเดียว
    • exact bias คือ 0.34968228323361017
    • มี bias สูงกว่า lowbias32 ที่กล่าวถึงก่อนหน้า
    • หากต้องการสุ่มค้นหาค่าคงที่การคูณทางเลือก สามารถระบุแพตเทิร์นได้ดังนี้
    • ./prospector -p xorr:15,mul,xorr:12,mul,xorr:15

  • ฟังก์ชันแบบ 3 รอบ

    • หากเพิ่มรอบ multiply-xorshift เข้าไปอีกหนึ่งรอบในโครงแบบเดียวกัน ก็สามารถไปถึงขีดจำกัดเชิงทฤษฎีของ bias ได้เมื่อเลือกพารามิเตอร์อย่างระมัดระวัง
    • triple32 มี exact bias เท่ากับ 0.020888578919738908
    • README อธิบายว่ามันไม่สามารถแยกความแตกต่างจาก PRF ที่สมบูรณ์แบบซึ่งเป็น permutation แบบสุ่มของจำนวนเต็ม 32 บิตทั้งหมดได้
    • มีฟังก์ชันผกผัน triple32_r ให้ด้วย
    • รายการค่าคงที่สำหรับแบบ 3 รอบมีผลลัพธ์ bias ต่ำตั้งแต่ 0.020888578919738908 ไปจนถึงประมาณ 0.022984943828687553
    • triple32inc ซึ่งเพิ่มการดำเนินการ increment ไว้หน้า triple32 จะทำลายปัญหา hash(0) = 0 และยังลด bias ลงอีกเล็กน้อย
    • exact bias คือ 0.020829410544597495
    • ฟังก์ชันผกผัน triple32inc_r จะทำ x-- ในตอนท้าย

การวัด exact bias

  • โหมด -E ใช้ประเมิน bias ของฟังก์ชันแฮชที่กำหนด
  • โดยปกติ Prospector จะใช้ค่าประมาณเพื่อประเมิน bias อย่างรวดเร็ว
    • ค่าประมาณนี้ไม่เป็น deterministic และมี noise ในผลลัพธ์ค่อนข้างมาก
  • หากต้องการวัด exact bias ด้วยการสำรวจครบทุกกรณี ให้ใช้ตัวเลือก -e
  • ฟังก์ชันที่จะตรวจสอบสามารถกำหนดได้สองวิธี
    • กำหนดด้วย -p และแพตเทิร์น
    • กำหนดด้วย -l และ shared library ที่มีฟังก์ชัน hash()
  • วิธีแบบ shared library ทำให้สามารถทดสอบฟังก์ชันแฮชที่ไม่สามารถแทนด้วยรูปแบบฟังก์ชันจำกัดของ Prospector ได้
  • อินพุตตั้งต้นจะถือว่าเป็น ฟังก์ชันแฮช 32 บิต
  • สวิตช์ -8 ใช้ทดสอบฟังก์ชัน 64 บิตด้วยวิธีประมาณค่า
    • ฟังก์ชันแฮช 64 บิตใช้เวลานานเกินไป จึงไม่มีการทดสอบ exhaustive แบบ exact

hp16 สำหรับแฮช 16 บิต

  • แฮช 16 บิตมีข้อจำกัดต่างออกไป จึงมีเครื่องมือแยกชื่อ hp16 ให้ใช้งาน
  • ต่างจาก Prospector สำหรับ 32 บิตและ 64 บิต hp16 พกพาได้เต็มรูปแบบและสามารถรันได้บนแทบทุกระบบ
  • hp16 ยังสามารถสร้างและประเมิน 128KiB s-box ได้ด้วย
  • เนื่องจากแฮช 16 บิตอาจจำเป็นบนเครื่องที่ไม่มีคำสั่งคูณที่รวดเร็ว จึงมีตัวเลือกให้ละเว้นการดำเนินการบางชนิดระหว่างการสำรวจ
    • -m
    • -r

ผลลัพธ์ 16 บิตและข้อควรระวังในการเขียน C

  • ตัวอย่างผลลัพธ์ 16 บิตในปัจจุบันมีดังนี้
    • xorshift-multiply แบบ 2 รอบ hash16_xm2: bias 0.0085905051336723701
    • xorshift-multiply แบบ 3 รอบ hash16_xm3: bias 0.0045976709018820602
    • hash16_s6 แบบไม่มีการคูณ: bias 0.023840118344741465
  • มีการระบุว่า hash16_s6 แบบไม่มีการคูณนี้เทียบเท่ากับรูปแบบ xorshift-multiply บางแบบ
  • แฮช xorshift แบบ 3 รอบที่ดีซึ่งสำรวจแบบสั้นด้วย hp16 -Xn3 เป็นค่าประมาณที่ใกล้เคียงกับ s-box ที่ดีจาก hp16 -S
  • เมื่อต้องเขียนการดำเนินการ 16 บิตด้วยภาษา C ต้องระวัง กฎ integer promotion
    • ตัวอย่างเช่น ใน implementation แบบ 32 บิต ตัวถูกดำเนินการ unsigned 16 บิตอาจถูกยกระดับเป็นจำนวนเต็ม signed 32 บิต
    • ในกรณีนี้อาจเกิดผลลัพธ์ที่ไม่ถูกต้องได้ในบางสถานการณ์
    • โค้ดภาษา C ที่โปรแกรมนี้สร้างออกมาจึงระวังยกระดับการดำเนินการ 16 บิตเป็น unsigned int ในตำแหน่งที่จำเป็น

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

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

 
GN⁺ 2024-05-06
ความคิดเห็นจาก Hacker News

  • แม้จะไม่รู้จักเขาเป็นการส่วนตัว แต่ผมชอบโค้ดของเขา
    โดยเฉพาะไลบรารี JSON https://github.com/skeeto/pdjson, ไลบรารีสำหรับ parse option https://github.com/skeeto/optparse และ https://github.com/skeeto/getopt, ตัวถอดรหัส UTF-8 แบบไม่มี branch https://github.com/skeeto/branchless-utf8, สแตกแบบ lock-free https://github.com/skeeto/lstack และไลบรารี trie https://github.com/skeeto/trie
    อีกอย่างที่ชอบคือรสนิยมด้านไลเซนส์ ที่โปรเจกต์ข้างต้นทั้งหมดเผยแพร่ภายใต้ The Unlicense

    • Skeeto คือระดับตำนานเลย สำหรับผมอยู่ระดับเดียวกับ Fabrice Bellard
      ผมติดตามเขาบน GitHub มาหลายปีแล้ว และเขามักปล่อย เครื่องมือเล็ก ๆ แปลก ๆ สำหรับ niche เฉพาะทาง ที่น่าสนใจออกมาอยู่เรื่อย ๆ ตัวอย่างเช่น Branchless UTF-8 ที่มีชื่อเสียง
    • เขายังเป็นผู้เขียน elfeed https://github.com/skeeto/elfeed ด้วย ซึ่งเป็น “ไคลเอนต์เว็บฟีดสำหรับ Emacs” และผมได้แรงบันดาลใจมากมายจากการใช้งานที่มินิมอลของมัน

  • สวัสดีครับ ผมเป็นคนสร้าง MurmurHash เอง งานนี้น่าสนใจดี และน่าขำที่แนวทางคูณ-ชิฟต์-XOR ยืนระยะมาได้ดีนานขนาดนี้

    • XOR-shift ช่วยชดเชยจุดอ่อนสองอย่างของการคูณ: บิตสูงไม่มีบิตที่อยู่เหนือขึ้นไปให้ส่งอิทธิพลลงมา และบิตต่ำไม่มีบิตที่อยู่ต่ำลงไปให้รับอิทธิพลขึ้นมา
    • ดูเหมือนว่าสิ่งเหล่านี้ก็เหมือน MurmurHash คือถูกตั้งใจให้เป็น แฮชแบบไม่เข้ารหัสลับ
      อย่างไรก็ตาม แนวคิด avalanche + bias ดูเหมือนจะยังขาดอะไรไปพอสมควร ตัวอย่างเช่นฟังก์ชัน triple32 ที่ระบุไว้ท้ายสุดมี bias ที่ถูกต้องคือ 0.020888578919738908 และเมื่อ FabriceNeyret2 นำไป implement บน ShaderToy จะได้ภาพแบบนี้: https://www.shadertoy.com/view/WttXWX หรือ https://i.imgur.com/qU2P5rx.png
      แต่ถ้าลองทำ อนุพันธ์ความชันของ normal map แบบง่าย ๆ จะเห็นเส้น “ผลึก” ที่สะดุดตาค่อนข้างมาก น่าจะมีศัพท์เทคนิคเรียกรูปแบบสันนูนแบบนี้อยู่: https://i.imgur.com/IHWT1GM.png
      เสริมอีกอย่าง ผมคิดว่าแนวคิดทั้งหมดนี้น่าจะมีมาตั้งราว 5 ปีแล้วไม่ใช่หรือ: https://nullprogram.com/blog/2018/07/31/

  • จากประสบการณ์ที่เคยพัฒนาแฮชฟังก์ชันที่ดี ผมคิดถึงไอเดีย การค้นหาแฮชแบบอัตโนมัติ อยู่บ่อย ๆ
    เห็นงานแบบนี้แล้วเจ๋งดี ถ้านำไปเชื่อมกับ SMHasher3 ซึ่งเป็นชุดทดสอบแฮชเก่าของ Frank J. T. Wojcik ในเวอร์ชันที่ปรับปรุงดีขึ้นและเร็วขึ้นมาก เพื่อประเมินผลลัพธ์โดยอัตโนมัติ ก็น่าจะดี อาจใช้แค่บางส่วนของการทดสอบเพื่อความเร็ว และให้ fail อย่างรวดเร็วได้ด้วย
    ถ้าขยายไปเป็นแฮช 64 บิตและ 128 บิตก็น่าจะดี แต่แน่นอนว่าพื้นที่ค้นหาจะใหญ่ขึ้นอีก ในเรื่องที่เกี่ยวกัน ผมเคยเขียนโค้ด NodeJS สำหรับวัด avalanche ในการคูณจำนวนเฉพาะ 64 บิต เพื่อเลือกค่าที่จะใช้กับ Rain ด้วย
    [Rain]: https://github.com/dosyago/rain
    [SMHasher3]: https://gitlab.com/fwojcik/smhasher3

  • ถ้าทำให้สิ่งนี้ generalize ไปยัง operation ที่ใช้ได้ใน ส่วนขยายการจัดการบิตของ RISC-V ก็น่าสนใจดี อาจค้นพบฟังก์ชันที่แข็งแรงสำหรับใช้ในอนาคตเมื่อคำสั่งเหล่านั้นแพร่หลายมากขึ้น
    การคูณแบบไม่มี carry ก็สามารถขยายชุด operation ที่ย้อนกลับได้ และบนฮาร์ดแวร์เดิมบางตัวก็เร็วด้วย CRC ก็เกี่ยวข้องอยู่บ้าง แต่ทำได้บนชุดฮาร์ดแวร์ที่กว้างกว่า และควรเป็น subset ที่เข้มงวดของสิ่งที่ CLMUL หาได้
    การใช้งานแฮชจำนวนมากสนใจแค่บิตล่างสุดหรือบิตบนสุดของค่าแฮช ดังนั้นการประเมิน bias ของช่วงบิตบนสุด/ล่างสุด หรือเศษเหลือจากการหารด้วยตัวเลขหลาย ๆ ค่าก็น่าสนใจเช่นกัน ฟังก์ชันที่ดูเหมือนไม่มี bias เมื่อดูจากเอาต์พุตทั้งหมด อาจดีขึ้นหรือแย่ลงเมื่อใช้ตัวชี้วัดที่ไม่ได้ดูเอาต์พุตทั้งหมด หรือเมื่ออินพุตไม่สม่ำเสมออย่างข้อความ ASCII

  • อธิบายได้ไหมว่าทำไมสิ่งนี้ถึงเจ๋ง และเอาไปใช้ที่ไหนได้บ้าง?

    • ดูเหมือนเป็นเครื่องมือที่สร้างลำดับคำสั่งสำหรับทำฟังก์ชันแฮช แล้วประเมินว่าฟังก์ชันแฮชนั้นดีแค่ไหน
      เป้าหมายของตัวชี้วัดน่าจะอยู่ที่ว่า เมื่อบิตอินพุตหนึ่งบิตเปลี่ยนไป บิตเอาต์พุตให้มากที่สุดเท่าที่เป็นไปได้จะเปลี่ยนไปแบบสุ่มให้มากที่สุดหรือไม่ จากนั้นจะพิมพ์โค้ด C ของฟังก์ชันแฮชที่ดีที่สุดในบรรดาที่สร้างขึ้น
      ดังนั้นจึงมีประโยชน์เมื่อคุณต้องการฟังก์ชันแฮชแต่คิดว่าฟังก์ชันเดิม ๆ ยังดีไม่พอ หรือเมื่อต้องการไอเดียโครงสร้างใหม่ระหว่างศึกษาฟังก์ชันแฮช การสร้างโค้ดเองก็น่าสนใจอยู่แล้ว และการทำแบบสุ่มก็เป็นก้าวแรกไปสู่ genetic programming ที่เจ๋งยิ่งกว่า นอกจากนี้ดูเหมือนว่ามนุษย์จะชอบให้คอมพิวเตอร์เผา CPU cycle เพื่อคำนวณแฮชที่ส่วนใหญ่จะไม่ได้ถูกใช้งานมาตั้งแต่ราว 15 ปีก่อนแล้ว
    • ฟังก์ชันแบบนี้จำเป็นต่อ hash table และยังมีชื่อที่เกี่ยวข้องอย่าง hash map กับ hash set ด้วย
      hash table เป็นโครงสร้างข้อมูลที่ยอดเยี่ยมซึ่งทำให้อัลกอริทึมจำนวนมาก implement ได้อย่างเรียบง่ายและมีประสิทธิภาพ ประสิทธิภาพนี้ขึ้นอยู่กับว่าสามารถสร้างแฮชที่มีขนาดเล็กเมื่อเทียบกับข้อมูล เช่น 32 บิตหรือ 64 บิต และแทบไม่ซ้ำกันได้หรือไม่
      ตัวอย่างเช่น หากแฮชชื่อผู้ใช้โดยใช้แค่รหัส ASCII ของตัวอักษรตัวแรกของชื่อ ผู้ใช้จำนวนมากก็จะถูกแมปไปเป็นตัวเลขเดียวกัน ทำให้ทำงานได้ไม่ดี สิ่งนี้เรียกว่า collision และถ้ามี collision มาก hash table ก็จะไม่มีประสิทธิภาพอย่างมาก
      วิธีที่ดีกว่าคือนำบิตจากชื่อผู้ใช้ทั้งชื่อมาผสมกันด้วยวิธีใดวิธีหนึ่ง เพื่อให้ throwaway_1237 กับ throwaway_12373 กลายเป็นตัวเลขคนละค่า ฟังก์ชันแฮชทำหน้าที่แมปแบบนี้ และคุณสมบัติ avalanche อธิบายว่ามันหลีกเลี่ยง collision ได้ดีแค่ไหน
      โดยทั่วไปมักมี trade-off ระหว่างความเร็วของฟังก์ชันแฮชจริงกับความสามารถในการหลีกเลี่ยง collision ฟังก์ชันแฮชระดับโลกมักดูค่อนข้างประหลาด เช่น คูณด้วยค่าคงที่แปลก ๆ ทำ XOR และ shift จึงเป็นเรื่องยากมากที่มนุษย์จะดูฟังก์ชันซับซ้อนแบบนี้แล้วคาดเดาประสิทธิภาพได้
      โค้ดนี้ลองฟังก์ชันแฮชหลายแบบแบบสุ่มแล้วให้แข่งกัน หากสำเร็จ ก็เจ๋งเพราะสามารถปรับปรุงประสิทธิภาพจริงของโครงสร้างข้อมูลหลักที่ใช้กันในหลายภาษาและไลบรารีได้
    • เพราะเป็นฟังก์ชันแฮชสำหรับจำนวนเต็ม จึงใช้ได้เมื่อต้องการ แฮชจำนวนเต็มที่เร็ว ใน set หรือ map หากฟังก์ชันแตกต่างกันมากพอ ก็ยังให้แฮชที่เร็วสำหรับ Bloom filter ได้ด้วย

  • เมื่อไม่กี่สัปดาห์ก่อนผม implement 1brc ด้วย Go ไว้ที่ https://github.com/infogulch/1brc-go แล้วพอเห็น repository นี้ก็ได้แรงบันดาลใจว่าจะลองหาฟังก์ชัน perfect hash แบบปรับแต่งเอง เพื่อให้สถานีตรวจวัดแต่ละแห่งลง bucket ของตัวเองโดยไม่มี collision
    แต่พอเห็นกฎที่ว่าห้ามปรับแต่งฟังก์ชันแฮชให้เข้ากับข้อมูลก่อนเริ่มโปรแกรม ก็เลยพับไอเดียไป
    ผมสร้างชุดทดสอบที่ตรวจค่าคงที่สุ่ม ค่าเริ่มต้น ค่าคงที่สำหรับการคูณ และจำนวน shift/rotate แล้วพิมพ์ค่าคงที่ที่ดีที่สุดเท่าที่พบ โดยดูจากจำนวน bucket ที่ชนกันและจำนวน collision คิดว่าที่อัตราการเติมประมาณ 40% ลดลงมาเหลือแค่ bucket เดียวที่มีสองค่าชนกันได้แล้ว น่าสนใจที่ค่าคงที่ที่ทำผลงานดีที่สุดมักมีจำนวนตำแหน่ง shift คล้ายกัน ไม่ขึ้นกับค่าคงที่อื่น ๆ สุดท้ายเลย hardcode ค่าเหล่านั้นไว้

    • สำหรับข้อมูลเพิ่มเติม มีเทคนิคที่ดีกว่าในการหา minimal perfect hash function อยู่ วิธีนี้ถือว่า implement ได้ค่อนข้างง่าย: https://cmph.sourceforge.net/chd.html

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

  • การจำกัดไว้เฉพาะ operation ที่ reversible มีข้อดีทางคณิตศาสตร์ แต่ในขณะเดียวกันก็ตัดหลายอย่างออกไปด้วย
    ตอนที่ทำอะไรคล้าย ๆ กัน ผมนึกถึง perfect hashing ที่รู้ชุดอินพุตล่วงหน้า วิธีทั่วไปคือใช้อาร์เรย์ของค่าคงที่ แต่โดยเฉพาะถ้าอินพุตเป็นจำนวนเต็มขนาดเล็กอยู่แล้ว ก็อยากดูว่าจะบีบให้ compact กว่านี้ได้ไหม แน่นอนว่าสามารถทำแบบ hash -= hash >> gap_index ได้
    ดังนั้นผมจึงลองใช้รายการ primitive operation ราว ๆ 100 รายการ บางรายการซ้ำซ้อนกัน แต่ถ้าคิดแยกกันก็เป็นสิ่งที่มีประโยชน์ จากนั้นก็เริ่มเบื่อ เลยไม่ได้ทำอะไรต่อเป็นโปรเจกต์

    • “ข้อดีทางคณิตศาสตร์ของการจำกัดไว้เฉพาะ operation ที่ reversible” คืออะไร และในบริบทนี้ operation ที่ reversible น่าพึงประสงค์เพราะอะไร?

  • ยังไม่ค่อยแน่ใจว่ามันทำอะไรแน่ ๆ กำลังหาค่าที่ดีที่สุดตลอดกาลอยู่หรือเปล่า? ถ้าไม่ใช่ ก็สงสัยว่าทำไมค่าที่ดีที่สุดถึงเปลี่ยนทุกครั้งที่รัน
    อีกอย่าง ถ้ารู้ว่าค่าจำนวนเต็มจะออกมาเฉพาะในช่วงหนึ่ง เช่น ระหว่าง 10,000 ถึง 200,000 อยากรู้ว่ามีใครรู้กลไกในการค้นหาฟังก์ชันแฮชที่ดีเพื่อนำค่าเหล่านั้นใส่ลงในจำนวน hash bucket ที่เหมาะสมที่สุดหรือไม่

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

  • สงสัยว่าถ้าใช้ค่าคงที่เดียวกันในการคูณสองครั้ง ขนาดโค้ด จะลดลง และอาจทำให้คำนวณเร็วขึ้นเล็กน้อยหรือเปล่า
    อัปเดตคำตอบบน StackOverflow แล้วด้วย: https://stackoverflow.com/questions/664014/what-integer-hash...