fbpx
วิกิพีเดีย

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

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

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

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

ขั้นตอนวิธีของราบิน-คาร์ปใช้ฟังก์ชันการแฮชที่ง่ายมากซึ่งประกอบไปด้วยการบวกและ การคูณเท่านั้น พิจารณาข้อมูลนำเข้าที่มีข้อมูล   ตัวและขณะนี้มีกรอบขนาด   อยู่ในช่วง   จะได้ว่า   เมื่อ   เป็นค่าคงที่ และ   เป็นข้อมูลที่อยู่ในกรอบดังกล่าว

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

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

  • ขยายกรอบไปทางด้านขวา การหาค่าแฮชก็คือการคำนวณหา   ซึ่งสามารถอาศัยความสัมพันธ์ว่า  
  • ลดขนาดกรอบทางด้านซ้าย การหาค่าแฮชก็คือการคำนวณหา   ซึ่งสามารถอาศัยความสัมพันธ์ว่า  
  • ขยายกรอบไปทางด้านซ้าย
  • ลดขนาดกรอบทางด้านขวา

การแฮชแบบม, วน, บทความน, ไม, การอ, างอ, งจากแหล, งท, มาใดกร, ณาช, วยปร, บปร, งบทความน, โดยเพ, มการอ, างอ, งแหล, งท, มาท, าเช, อถ, เน, อความท, ไม, แหล, งท, มาอาจถ, กค, ดค, านหร, อลบออก, เร, ยนร, าจะนำสารแม, แบบน, ออกได, อย, างไรและเม, อไร, งกฤษ, rolling, hash, . bthkhwamniimmikarxangxingcakaehlngthimaidkrunachwyprbprungbthkhwamni odyephimkarxangxingaehlngthimathinaechuxthux enuxkhwamthiimmiaehlngthimaxacthukkhdkhanhruxlbxxk eriynruwacanasaraemaebbnixxkidxyangiraelaemuxir karaehchaebbmwn xngkvs Rolling hash epnfngkchnaehchthiichaehchkhxmulphayinkrxbthikhxy eluxniperuxy odyemuxmikareluxnkrxbkhun casamarthkhanwnkhaaehchihmidodynakhakhxngkaraehchkhrngkxnmakhanwnxyangrwderwkaraehchaebbmwnmibthbathsakhyinkhntxnwithikhxngrabin kharp duephimdanlang aelakhntxnwithiechkhsmchux Adler 32 sungichinopraekrmxarsingkhkaraehchaebbmwninkhntxnwithikhxngrabin kharp aekikhkhntxnwithikhxngrabin kharpichfngkchnkaraehchthingaymaksungprakxbipdwykarbwkaela karkhunethann phicarnakhxmulnaekhathimikhxmul n displaystyle n twaelakhnanimikrxbkhnad k displaystyle k xyuinchwng p p k 1 displaystyle p p k 1 caidwa 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 displaystyle 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 emux a displaystyle a epnkhakhngthi aela c p c p k 1 displaystyle c p c p k 1 epnkhxmulthixyuinkrxbdngklawephuxthicaimihkha H displaystyle H ihymakekinip cungihkardaeninkarthukkhntxnxyuphayitmxduol m displaystyle m kareluxkkha a displaystyle a aela m displaystyle m thiimehmaasmxacthaihfngkchnaehchmioxkasekidkhwamphidphladechingbwksung sungkareluxkthidithisudkhuxkha a displaystyle a aela m displaystyle m khwrcaepncanwnechphaasmphththkn txngkarxangxing duraylaexiydephimetimthi linear congruential generatorsmmutiwakhnanikrxbxyuinchwng p q displaystyle p q casamarthdaeninkardngniid khyaykrxbipthangdankhwa karhakhaaehchkkhuxkarkhanwnha H p q 1 displaystyle H p q 1 sungsamarthxasykhwamsmphnthwa H p q 1 H p q a c q 1 mod m displaystyle H p q 1 H p q a c q 1 bmod m ldkhnadkrxbthangdansay karhakhaaehchkkhuxkarkhanwnha H p 1 q displaystyle H p 1 q sungsamarthxasykhwamsmphnthwa H p 1 q H p q c p a q p mod m displaystyle H p 1 q H p q c p a q p bmod m khyaykrxbipthangdansay ldkhnadkrxbthangdankhwa bthkhwamniyngepnokhrng khunsamarthchwywikiphiediyidodyephimkhxmul ekhathungcak https th wikipedia org w index php title karaehchaebbmwn amp oldid 4702429, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,

บทความ

, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม