ฟังก์ชันแฮชและตารางแฮช

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

ฟังก์ชันแฮช

ต่อไปนี้คือฟังก์ชันแฮชบางส่วน -

วิธีการหาร

นี่เป็นวิธีที่ง่ายที่สุดในการสร้างฟังก์ชันแฮช ฟังก์ชันแฮชสามารถอธิบายได้ว่า −

h(k) = k mod n

ในที่นี้ h(k) คือค่าแฮชที่ได้จากการหารค่าคีย์ k ด้วยขนาดของตารางแฮช n โดยใช้เศษที่เหลือ ดีที่สุดคือ n เป็นจำนวนเฉพาะเนื่องจากทำให้แน่ใจว่ามีการกระจายคีย์ที่มีความสม่ำเสมอมากขึ้น

ตัวอย่างของวิธีการหารมีดังนี้ −

k=1276
n=10
h(1276) = 1276 mod 10
= 6

ค่าแฮชที่ได้รับคือ 6

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

วิธีการคูณ

ฟังก์ชันแฮชที่ใช้สำหรับวิธีการคูณคือ −

h(k) = floor( n( kA mod 1 ) )

ในที่นี้ k คือคีย์ และ A สามารถเป็นค่าคงที่ใดๆ ระหว่าง 0 ถึง 1 ทั้ง k และ A ถูกคูณและแยกส่วนของเศษส่วน จากนั้นคูณด้วย n เพื่อให้ได้ค่าแฮช

ตัวอย่างของวิธีการคูณมีดังนี้ −

k=123
n=100
A=0.618033
h(123) = 100 (123 * 0.618033 mod 1)
= 100 (76.018059 mod 1)
= 100 (0.018059)
= 1

ค่าแฮชที่ได้รับคือ 1

ข้อดีของวิธีการคูณคือสามารถใช้ได้กับค่า A ใดๆ แม้ว่าค่าบางค่าจะถือว่าดีกว่าค่าอื่นๆ

วิธีมิดสแควร์

วิธีกำลังสองกลางเป็นฟังก์ชันแฮชที่ดีมาก มันเกี่ยวข้องกับการยกกำลังค่าของคีย์แล้วแยกตัวเลข r ตรงกลางเป็นค่าแฮช ค่าของ r สามารถตัดสินใจได้ตามขนาดของตารางแฮช

ตัวอย่างของวิธี Mid Square มีดังนี้ −

สมมติว่าตารางแฮชมีตำแหน่งหน่วยความจำ 100 ตำแหน่ง ดังนั้น r=2 เพราะต้องใช้ตัวเลขสองหลักในการแมปคีย์กับตำแหน่งหน่วยความจำ

k = 50
k*k = 2500
h(50) = 50

The hash value obtained is 50

ตารางแฮช

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

ตัวอย่างของตารางแฮชมีดังนี้ −

ลำดับคีย์ที่ต้องเก็บไว้ในตารางแฮชคือ −

35 50 11 79 76 85

ฟังก์ชันแฮช h(k) ที่ใช้คือ:

h(k) = k mod 10

การใช้โพรบเชิงเส้น ค่าจะถูกเก็บไว้ในตารางแฮชเป็น -