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

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

การแฮชแบบม้วนมีบทบาทสำคัญในขั้นตอนวิธีของราบิน-คาร์ป (ดูเพิ่มด้านล่าง) และขั้นตอนวิธีเช็คซัมชื่อ 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})modm$
• ลดขนาดกรอบทางด้านซ้าย การหาค่าแฮชก็คือการคำนวณหา $H(p+1,q)$ ซึ่งสามารถอาศัยความสัมพันธ์ว่า $H(p+1,q)=(H(p,q)-c_p{a}^{q-p})modm$
• ขยายกรอบไปทางด้านซ้าย
• ลดขนาดกรอบทางด้านขวา