ตารางแฮชอธิบาย

โครงสร้างข้อมูลที่ฉันชอบอย่างหนึ่งคือตารางแฮชเพราะมันเรียบง่ายและมีประสิทธิภาพ

คุณอาจเคยใช้มาก่อนเนื่องจากเป็นวิธีจัดเก็บคู่คีย์-ค่าอย่างมีประสิทธิภาพ

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

ที่เก็บข้อมูลและฟังก์ชันแฮช

แนวคิดพื้นฐานของตารางแฮชคือการทำให้เราทำงานได้อย่างมีประสิทธิภาพ (ใน O(1) ) ดึงข้อมูลที่จัดทำดัชนีโดยคีย์

เพื่อทบทวนอย่างรวดเร็ว นี่คือลักษณะการใช้งานตารางแฮชใน Ruby:

prices ={ apple:0.50, ice_cream:3, steak:10}

ในการใช้ตารางแฮช เราต้องการสององค์ประกอบ:

• ที่สำหรับจัดเก็บรายการตาราง
• วิธีกำหนดคู่คีย์/ค่าให้กับตำแหน่งเฉพาะ (ดัชนี) ภายในที่เก็บข้อมูลนี้

กล่าวอีกนัยหนึ่ง เราต้องการอาร์เรย์ &ฟังก์ชันแฮช

การใช้ฟังก์ชันแฮชอย่างง่าย

ฟังก์ชันแฮช เป็นองค์ประกอบสำคัญของตารางแฮช

ฟังก์ชันนี้แปลงคีย์ให้เป็นดัชนีที่สามารถใช้เพื่อค้นหาหรืออัปเดตค่าที่เกี่ยวข้องได้

นี่คือความแตกต่างอย่างมากระหว่างอาร์เรย์ธรรมดาและตารางแฮช

ในอาร์เรย์ คุณสามารถเข้าถึงค่าได้ผ่านดัชนีเท่านั้น และดัชนีต้องเป็นตัวเลขเท่านั้น ในตารางแฮช คุณเข้าถึงค่าผ่านคีย์และคีย์สามารถเป็นอะไรก็ได้ (สตริง สัญลักษณ์ จำนวนเต็ม…) ตราบใดที่คุณสามารถเขียนฟังก์ชันแฮชได้

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

นี่คือตัวอย่าง :

BUCKETS =32def แฮช (อินพุต) input.to_s.chars.inject(0) { |sum, ch| sum + ch.ord } % BUCKETส่ง

ในวิธีนี้เราใช้ to_s เพื่อให้แน่ใจว่าเรากำลังทำงานกับสตริง

วิธีนี้จะช่วยเราหลีกเลี่ยงข้อผิดพลาด 'วิธีการที่ไม่ได้กำหนด' แล้วผสม chars (เพื่อแปลงสตริงเป็น Array ของตัวอักษร) &inject สำหรับการบวกค่า

ภายในบล็อกฉันใช้ ord วิธีการแปลงอักขระเป็นค่าลำดับของพวกมัน

สุดท้าย ฉันใช้ตัวดำเนินการโมดูโล % เพื่อให้แน่ใจว่าค่าผลลัพธ์จะพอดีกับอาร์เรย์ เราเรียกแต่ละรายการในอาร์เรย์นี้ว่า 'ถัง'

การกระจายถัง

ตามหลักการแล้วเราต้องการให้ถังทั้งหมดของเราถูกเติมอย่างเท่าเทียมกัน ซึ่งจะทำให้เรามีประสิทธิภาพที่ดีที่สุดเมื่อเราต้องการดึงค่า

มาดูกันว่าจะเกิดอะไรขึ้นเมื่อเราทดสอบฟังก์ชันแฮชโดยใช้โค้ดนี้:

# สร้างอาร์เรย์ขนาด BUCKETS โดยตั้งค่าองค์ประกอบทั้งหมดเป็น 0table =Array.new(BUCKETS) { 0 }letters =Array('a'..'z')10_000.times do # สร้างอินพุตสตริงแบบสุ่ม =Array.new(5) { letters.sample }.join # Count hash distribution table[hash(input)] +=1end

สิ่งนี้ให้ผลลัพธ์ดังต่อไปนี้:

ดูเหมือนว่าคีย์ของเราจะกระจายอย่างเท่าเทียมกัน…

…แต่จะเกิดอะไรขึ้นหากเราเพิ่มจำนวนที่เก็บข้อมูล

ในตัวอย่างนี้ ฉันใช้ขนาดที่ฝากข้อมูล 128 (เมื่อก่อนคือ 32):

[22, 24, 33, 36, 41, 58, 61, 66, 97, 77, 88, 110, 89, 82, 123, 121, 119, 111, 147, 178, 136, 176, 144, 180, 190, 193, 185, 192, 223, 209, 208, 196, 215, 251, 233, 226, 231, 236, 219, 218, 227, 221, 206, 220, 208, 213, 201, 191, 182, 165, 188, 141, 160, 135, 130, 117, 139, 106, 121, 85, 70, 93, 74, 61, 57, 54, 40, 46, 32, 36, 30, 21, 25, 17, 14, 16, 16, 14, 8, 11, 5, 5, 1, 1, 2, 1, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 4, 3, 6, 0, 2, 9, 13, 11, 12, 14, 12, 23, 12, 22]

มันดูไม่เหมือนการกระจายตัวที่ดีอีกต่อไป!

เกิดอะไรขึ้น?

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

ฟังก์ชันแฮชที่ดีขึ้น

เราต้องการวิธีที่ดีกว่าในการแปลงสตริงของเราให้เป็นดัชนี มาดูการใช้งานที่เป็นไปได้กัน

BUCKETS =256def hash(input) input.to_s.each_char.inject(0) ทำ |sum, ch| (ผลรวม <<8) ^ (ch.ord) ^ (ผลรวม>> 4) สิ้นสุด % BUCKETSend

สิ่งที่เกิดขึ้นที่นี่เปลี่ยนไปเล็กน้อย (ด้วย >> &<< ผู้ประกอบการ) ค่าต่างๆ จะรวมกันโดยใช้ “ตัวดำเนินการ OR พิเศษ” (^ )

3:[:abc, 100] -> [:ccc, 200]4:nil5:[:yx, 50]