IT A-Z

สารบาญตามตัวอักษร

hashing

ที่มา whatis.com

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

ตัวอย่างอย่างง่ายของการใช้ hashing ในฐานข้อมูล กลุ่มของประชาชนสามารถได้รับการจัดในฐานข้อมูลเหมือนกับ
- Abernathy, Sara
- Epperdingle, Roscoe
- Moore, Wilfred
- Smith, David
(และข้อมูลอื่นๆ)

แต่ละชื่อจะเป็นคีย์ในฐานข้อมูลสำหรับข้อมูลบุคคล กลไกการค้นฐานข้อมูลจะเริ่มต้นมองตัวอักษรต่อตัวอักษรทุกชื่อสำหรับการหาค่าตรงกัน จนกระทั่งพบค่าตรงกัน (หรือกฎให้รายการอื่นออกไป) แต่ถ้าแต่ละเป็นการ hashing อาจจะมีสร้างคีย์ตัวเลข 4 ตำแหน่งสำหรับแต่ละชื่อ (ขึ้นกับจำนวนชื่อในฐานข้อมูล) ตัวอย่าง
- 7864 Abernathy, Sara
- 9802 Epperdingle, Roscoe
- 1990 Moore, Wilfred
- 8822 Smith, David
(และข้อมูลอื่นๆ)

การค้นหาแต่ละชื่อจะประกอบด้วยการคำนวณค่า hash ก่อน (ใช้ฟังก์ชัน hash เดียวกับการเก็บรายการ) จากนั้นเปรียบเทียบค่าตรงกันด้วยค่านั้น โดยทั่วไป การค้นหาด้วยตัวเลข 4 ตำแหน่ง แต่ละค่ามีเพียง 10 ความเป็นไปได้จะเร็วกว่าความยาวค่าที่คาดการณ์ไม่ได้จากแต่ละตัวอักษรมี 26 ความเป็นไปได้

อัลกอริทึม hashing ได้รับการเรียกว่า hash function (บางทีคำนี้มาจากความคิดว่าผลลัพธ์ค่า hash สามารถเป็นการคิดถึงเวอร์ชัน “ผสม” ของค่านำเสนอ) นอกจากการดึงค่าเร็วกว่าแล้ว hashing ได้รับการใช้ เข้ารหัสและถอดรหัสการลายมือชื่อดิจิตอล (ใช้รับรองข่าวสารของผู้ส่งและผู้รับ) ลายมือชื่อดิจิตอลได้รับการส่งผ่านด้วยฟังก์ชัน hash และค่า hash (รู้จักในชื่อ message-digest หรือการย่อยข่าวสาร) และลายมือชื่อได้รับการส่งในการส่งผ่านแยกจากกัน ด้วยการใช้ฟังก์ชัน hash เหมือนกับผู้ส่ง ผู้รับแปลงการย่อยข่าวสารจากลายมือชื่อและเปรียบเทียบกับการย่อยข่าวสารนั้นที่ได้รับ และควรเหมือนกัน

ฟังก์ชัน hash ได้รับการใช้ทำดัชนีค่าเริ่มแรกหรือคีย์ จากนั้นใช้ในแต่ละครั้งกับข้อมูลสัมพันธ์กับค่าหรือคีย์ที่ได้รับการดึงออกมา ดังนั้น hashing เป็นปฏิบัติการทางเดียวเสมอ ไม่จำต้องใช้ “วิศวกรรมผันกลับ” (reverse engineer) กับฟังก์ชัน hash โดยการวิเคราะห์ค่า hash ตามความจริง แนวคิดฟังก์ชัน hash ไม่สามารถแปลงโดยการวิเคราะห์เช่นนี้ ฟังก์ชัน hash ที่ดี จะไม่สร้างค่าค่า hash เดียวกันจากค่านำเข้า 2 ค่า ถ้าเกิดขึ้น สิ่งนี้เรียกว่า collision (การปะทะ) ฟังก์ชัน hash ที่ให้ความเสี่ยงต่ำของ collision ได้รับการพิจารณายอมรับ

นี่เป็นตัวอย่างฟังก์ชัน hash อย่างง่ายที่ได้รับการใช้งาน
- division-remainder method ขนาดจำนวนของรายการในตารางได้รับการประมาณ จำนวนั้นได้รับการใช้เป็นตัวหารกับแตละค่าดั้งเดิมหรือคีย์ที่แยกผลลัพธ์กับเศษของการหาร เศษนี้เป็นค่า hash (เพราะวิธีการนี้น่าเชื่อถือในการสร้างจำนวนของ collision กลไกการค้นหาต้องสามารถรับรู้ collision และเสนอกลไกทางเลือก)
- folding วิธีนี้แบ่งค่าดั้งเดิม (ตำแหน่งในกรณีนี้) เป็นหลายส่วน เพิ่มส่วนเข้าด้วยกัน แล้วใช้ 4 ตำแหน่งสุดท้าย (หรือจำนวนสุ่มอื่นของตำแหน่งที่ทำงานได้) เป็นค่า hash หรือคีย์
- radix transformation เมื่อค่าหรือคีย์เป็นตัวเลข เลขฐาน (หรือ radix) สามารถได้รับการเปลี่ยนผลลัพธ์ในอนุกรมตัวเลขต่างกัน (ตัวอย่าง คีย์เลขฐานสิบ สามารถแปลงเป็นคีย์เลขฐานสิบหก) ลำดับตัวเลขสูงสามารถทิ้งให้เหมาะค่า hash ของความยาวสม่ำเสมอ (uniform)
- digit rearrangement นี่เป็นการนำส่วนของค่าดั้งเดิมหรือคีย์ เช่น ตัวเลขในตำแหน่ง 3 ถึง 6 แปลงกลับตำแหน่ง จากนั้นใช้อนุกรมของตัวเลขเป็นค่า hash หรือคีย์

ฟังก์ชัน hash ทำงานได้ดีสำหรับัดเก็บฐานข้อมูลและดึงค่าอาจจะไม่ทำงานสำหรับวัตถุประสงค์ cryptographic หรือ การตรวจสอบความผิดพลาด มีหลายฟังก์ชัน hash ที่รู้จักกันดีใน cryptographic รวมถึง ฟังก์ชัน hash ย่อยข่าวสาร (message-digest) MD2, MD4 และ MD5 สำหรับการ hash ลายมือชื่อดิจิตอล เป็นค่าสั้นกว่าที่เรียกว่า การย่อยข่าวสาร และ Secure Hash Algorithm (SHA) อัลกอริทึมมาตรฐานที่ทำการย่อยข่าวสารขนาดใหญ่ (60 บิต) และคล้ายกับ MD4

ศัพท์เกี่ยวข้อง

update: 22 เมษายน 2548