การแฮชแบบม้วน
บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
การแฮชแบบม้วน (อังกฤษ: Rolling hash) เป็นฟังก์ชันแฮชที่ใช้แฮชข้อมูลภายในกรอบที่ค่อย ๆ เลื่อนไปเรื่อย ๆ โดยเมื่อมีการเลื่อนกรอบขึ้น จะสามารถคำนวณค่าแฮชใหม่ได้โดยนำค่าของการแฮชครั้งก่อนมาคำนวณอย่างรวดเร็ว
การแฮชแบบม้วนมีบทบาทสำคัญในขั้นตอนวิธีของราบิน-คาร์ป (ดูเพิ่มด้านล่าง) และขั้นตอนวิธีเช็คซัมชื่อ Adler-32 ซึ่งใช้ในโปรแกรมอาร์ซิงค์
การแฮชแบบม้วนในขั้นตอนวิธีของราบิน-คาร์ป[แก้]
ขั้นตอนวิธีของราบิน-คาร์ปใช้ฟังก์ชันการแฮชที่ง่ายมากซึ่งประกอบไปด้วยการบวกและ การคูณเท่านั้น พิจารณาข้อมูลนำเข้าที่มีข้อมูล ตัวและขณะนี้มีกรอบขนาด อยู่ในช่วง จะได้ว่า เมื่อ เป็นค่าคงที่ และ เป็นข้อมูลที่อยู่ในกรอบดังกล่าว
เพื่อที่จะไม่ให้ค่า ใหญ่มากเกินไป จึงให้การดำเนินการทุกขั้นตอนอยู่ภายใต้มอดุโล การเลือกค่า และ ที่ไม่เหมาะสมอาจทำให้ฟังก์ชันแฮชมีโอกาสเกิดความผิดพลาดเชิงบวกสูง ซึ่งการเลือกที่ดีที่สุดคือค่า และ ควรจะเป็นจำนวนเฉพาะสัมพัทธ์กัน[ต้องการอ้างอิง] ดูรายละเอียดเพิ่มเติมที่ linear congruential generator
สมมุติว่าขณะนี้กรอบอยู่ในช่วง จะสามารถดำเนินการดังนี้ได้
- ขยายกรอบไปทางด้านขวา การหาค่าแฮชก็คือการคำนวณหา ซึ่งสามารถอาศัยความสัมพันธ์ว่า
- ลดขนาดกรอบทางด้านซ้าย การหาค่าแฮชก็คือการคำนวณหา ซึ่งสามารถอาศัยความสัมพันธ์ว่า
- ขยายกรอบไปทางด้านซ้าย
- ลดขนาดกรอบทางด้านขวา