การแฮชในโครงสร้างข้อมูล: ฟังก์ชัน เทคนิค [พร้อมตัวอย่าง]

บทนำ

การแฮชเป็น โครงสร้างข้อมูลที่ สำคัญที่ ออกแบบมาเพื่อแก้ปัญหาการค้นหาและจัดเก็บข้อมูลในอาร์เรย์อย่างมีประสิทธิภาพ ตัวอย่างเช่น หากคุณมีรายการตัวเลข 20000 หมายเลข และคุณได้ให้หมายเลขเพื่อค้นหาในรายการนั้น คุณจะสแกนแต่ละหมายเลขในรายการจนกว่าคุณจะพบหมายเลขที่ตรงกัน

ต้องใช้เวลาเป็นจำนวนมากในการค้นหารายการทั้งหมดและค้นหาหมายเลขเฉพาะนั้น ขั้นตอนการสแกนด้วยตนเองนี้ไม่เพียงแต่ใช้เวลานาน แต่ยังไร้ประสิทธิภาพอีกด้วย ด้วยการแฮชในโครงสร้างข้อมูล คุณสามารถจำกัดการค้นหาให้แคบลงและค้นหาตัวเลขได้ภายในไม่กี่วินาที

บล็อกนี้จะช่วยให้คุณเข้าใจวิธีการแฮช ตารางแฮช และการตรวจสอบเชิงเส้นอย่างลึกซึ้งยิ่งขึ้นพร้อมตัวอย่าง

Hashing ในโครงสร้างข้อมูลคืออะไร?

การแฮชใน โครงสร้างข้อมูล เป็นเทคนิคการแมปข้อมูลจำนวนมากลงในตารางขนาดเล็กโดยใช้ฟังก์ชันแฮช เรียกอีกอย่างว่าฟังก์ชันย่อยข้อความ เป็นเทคนิคที่ระบุเฉพาะรายการเฉพาะจากคอลเล็กชันของรายการที่คล้ายคลึงกัน

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

คุณเพียงแค่ต้องค้นหาดัชนีของรายการที่ต้องการ แทนที่จะค้นหาข้อมูล ด้วยการจัดทำดัชนี คุณสามารถสแกนรายการทั้งหมดและเรียกค้นรายการที่คุณต้องการได้อย่างรวดเร็ว การทำดัชนียังช่วยในการแทรกการดำเนินการเมื่อคุณต้องการแทรกข้อมูลในตำแหน่งเฉพาะ ไม่ว่าตารางจะใหญ่หรือเล็กก็ตาม คุณสามารถอัปเดตและเรียกข้อมูลได้ภายในไม่กี่วินาที

การแฮชใน โครงสร้างข้อมูล เป็นกระบวนการสองขั้นตอน

1. ฟังก์ชันแฮชจะแปลงรายการเป็นจำนวนเต็มหรือค่าแฮชขนาดเล็ก จำนวนเต็มนี้ใช้เป็นดัชนีเพื่อเก็บข้อมูลดั้งเดิม
2. มันเก็บข้อมูลในตารางแฮช คุณสามารถใช้คีย์แฮชเพื่อค้นหาข้อมูลได้อย่างรวดเร็ว

ตัวอย่างของการแฮชในโครงสร้างข้อมูล

ต่อไปนี้เป็นตัวอย่างในชีวิตจริงของ การแฮชในโครงสร้างข้อมูล -

• ในโรงเรียน ครูจะกำหนดหมายเลขม้วนที่ไม่ซ้ำกันให้กับนักเรียนแต่ละคน ต่อมาครูใช้หมายเลขม้วนนั้นเพื่อดึงข้อมูลเกี่ยวกับนักเรียนคนนั้น
• ห้องสมุดมีหนังสือมากมายนับไม่ถ้วน บรรณารักษ์กำหนดหมายเลขเฉพาะให้กับหนังสือแต่ละเล่ม ตัวเลขที่ไม่ซ้ำกันนี้ช่วยในการระบุตำแหน่งของหนังสือบนชั้นวางหนังสือ

ชำระเงิน: การเรียงลำดับในโครงสร้างข้อมูล

ฟังก์ชันแฮช

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

แฮช = hashfunc (คีย์)

ดัชนี = แฮช% array_size

ฟังก์ชัน have ต้องเป็นไปตามข้อกำหนดต่อไปนี้:

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

ตารางแฮช

การแฮชในโครงสร้างข้อมูล จะใช้ตารางแฮชเพื่อจัดเก็บคู่คีย์-ค่า ตารางแฮชใช้ฟังก์ชันแฮชเพื่อสร้างดัชนี การแฮชใช้ดัชนีเฉพาะนี้เพื่อดำเนินการแทรก อัปเดต และค้นหา

การแฮชในโครงสร้างข้อมูลทำงานอย่างไร

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

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

ให้เราเข้าใจ การแฮชในโครงสร้างข้อมูล ด้วยตัวอย่าง ลองนึกภาพว่าคุณต้องเก็บบางรายการ (จัดเป็นคู่คีย์-ค่า) ไว้ในตารางแฮชที่มี 30 เซลล์

ค่าต่างๆ ได้แก่ (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

ตารางแฮชจะมีลักษณะดังนี้:

อ่านเพิ่มเติม: ประเภทของโครงสร้างข้อมูลใน Python

เทคนิคการแก้ปัญหาการชนกัน

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

โพรบเชิงเส้น

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

ตัวอย่างการตรวจวัดเชิงเส้น

ลองนึกภาพคุณถูกขอให้จัดเก็บบางรายการไว้ในตารางแฮชขนาด 30 รายการดังกล่าวได้รับการจัดเรียงในรูปแบบคู่คีย์-ค่าแล้ว ค่าที่กำหนด ได้แก่ (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

hash(n) คือดัชนีที่คำนวณโดยใช้ฟังก์ชันแฮช และ T คือขนาดตาราง หากดัชนีสล็อต = ( hash(n) % T) เต็ม เราจะมองหาดัชนีสล็อตถัดไปโดยเพิ่ม 1 ((hash(n) + 1) % T) ถ้า (hash(n) + 1) % T เต็ม เราก็ลอง (hash(n) + 2) % T ถ้า (hash(n) + 2) % T เต็ม เราก็ลอง (hash( n) + 3) % ต.

ตารางแฮชจะมีลักษณะดังนี้:

Double Hashing

เทคนิคการแฮชแบบคู่ใช้ฟังก์ชันแฮชสองฟังก์ชัน ฟังก์ชันแฮชที่สองจะถูกนำมาใช้เมื่อฟังก์ชันแรกทำให้เกิดการชนกัน มันมีดัชนีออฟเซ็ตเพื่อเก็บค่า

สูตรสำหรับเทคนิคการแฮชแบบคู่มีดังนี้:

(firstHash(คีย์) + i * secondHash(คีย์)) % sizeOfTable

โดยที่ i คือค่าออฟเซ็ต ค่าออฟเซ็ตนี้จะเพิ่มขึ้นเรื่อย ๆ จนกว่าจะพบช่องว่าง

ตัวอย่างเช่น คุณมีฟังก์ชันแฮชสองฟังก์ชัน: h1 และ h2 คุณต้องทำตามขั้นตอนต่อไปนี้เพื่อค้นหาช่องว่าง:

1. ตรวจสอบว่า hash1(key) ว่างเปล่าหรือไม่ ถ้าใช่ ให้เก็บค่าในช่องนี้
2. หาก hash1(key) ไม่ว่างเปล่า ให้ค้นหาสล็อตอื่นโดยใช้ hash2(key)
3. ตรวจสอบว่า hash1(key) + hash2(key) ว่างเปล่าหรือไม่ ถ้าใช่ ให้เก็บค่าในช่องนี้
4. ให้เพิ่มตัวนับและทำซ้ำด้วย hash1(key)+2hash2(key), hash1(key)+3hash2(key) และอื่นๆ จนกว่าจะพบช่องว่าง

ตัวอย่าง Double Hashing

ลองนึกภาพว่าคุณต้องเก็บสิ่งของบางอย่างไว้ในตารางแฮชขนาด 20 ค่าที่ระบุคือ: (16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1)

ชั่วโมง1(n)=n%20

ชั่วโมง2(n)=n%13

nh(n, i) = (h1 (n) + ih2(n)) mod 20

บทสรุป

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

คุณสามารถลองใช้ตัวอย่างเพื่อเสริมสร้างความรู้ด้านโครงสร้างข้อมูลของคุณ หากคุณอยากทราบข้อมูลเพิ่มเติมเกี่ยวกับ โครงสร้างข้อมูล ให้ดูที่ upGrad Executive PG Program ใน หลักสูตร Full Stack Development หลักสูตรนี้ออกแบบมาสำหรับมืออาชีพด้านการทำงานและมีการฝึกอบรมและการจัดหางานอย่างเข้มงวดกับบริษัทชั้นนำ