การแฮชแบบม้วน

จากวิกิพีเดีย สารานุกรมเสรี

การแฮชแบบม้วน (อังกฤษ: Rolling hash) เป็นฟังก์ชันแฮชที่ใช้แฮชข้อมูลภายในกรอบที่ค่อย ๆ เลื่อนไปเรื่อย ๆ โดยเมื่อมีการเลื่อนกรอบขึ้น จะสามารถคำนวณค่าแฮชใหม่ได้โดยนำค่าของการแฮชครั้งก่อนมาคำนวณอย่างรวดเร็ว

การแฮชแบบม้วนมีบทบาทสำคัญในขั้นตอนวิธีของราบิน-คาร์ป (ดูเพิ่มด้านล่าง) และขั้นตอนวิธีเช็คซัมชื่อ Adler-32 ซึ่งใช้ในโปรแกรมอาร์ซิงค์

การแฮชแบบม้วนในขั้นตอนวิธีของราบิน-คาร์ป[แก้]

ขั้นตอนวิธีของราบิน-คาร์ปใช้ฟังก์ชันการแฮชที่ง่ายมากซึ่งประกอบไปด้วยการบวกและ การคูณเท่านั้น พิจารณาข้อมูลนำเข้าที่มีข้อมูล n ตัวและขณะนี้มีกรอบขนาด k อยู่ในช่วง [p,p+k-1] จะได้ว่า H(p,p+k-1) = c_p a^{k-1} + c_{p+1} a^{k-2} + c_{p+2} a^{k-3} + ... + c_{p+k-1} a^{0} เมื่อ a เป็นค่าคงที่ และ c_p, ..., c_{p+k-1} เป็นข้อมูลที่อยู่ในกรอบดังกล่าว

เพื่อที่จะไม่ให้ค่า H ใหญ่มากเกินไป จึงให้การดำเนินการทุกขั้นตอนอยู่ภายใต้มอดุโล m การเลือกค่า a และ m ที่ไม่เหมาะสมอาจทำให้ฟังก์ชันแฮชมีโอกาสเกิดความผิดพลาดเชิงบวกสูง ซึ่งการเลือกที่ดีที่สุดคือค่า a และ m ควรจะเป็นจำนวนเฉพาะสัมพัทธ์กัน[ต้องการอ้างอิง] ดูรายละเอียดเพิ่มเติมที่ linear congruential generator

สมมุติว่าขณะนี้กรอบอยู่ในช่วง [p,q] จะสามารถดำเนินการดังนี้ได้

  • ขยายกรอบไปทางด้านขวา การหาค่าแฮชก็คือการคำนวณหา H(p,q+1) ซึ่งสามารถอาศัยความสัมพันธ์ว่า H(p,q+1) = (H(p,q) a + c_{q+1})  \bmod m
  • ลดขนาดกรอบทางด้านซ้าย การหาค่าแฮชก็คือการคำนวณหา H(p+1,q) ซึ่งสามารถอาศัยความสัมพันธ์ว่า H(p+1,q) = (H(p,q) - c_p a^{q-p}) \bmod m
  • ขยายกรอบไปทางด้านซ้าย
  • ลดขนาดกรอบทางด้านขวา