de algorismoKratui++
Hash II : การซ้อนทับ (I)
  • บทความนี้จะพูดถึงวิธีการแก้ปัญหาการซ้อนทับกันของ hash
    ด้วยวิธีการเลื่อนตำแหน่ง

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

    _ _ _ * _ * * _ _ 

    ให้ _ แทนตำแหน่งที่ว่าง และ * แทนตำแหน่งที่มีข้อมูลอยู่แล้ว หากฟังก์ชั่น hash ให้ค่าเป็น 2 (index เริ่มที่ 0) แล้ว ก็จะไม่มีปัญหาอะไร เพราะช่องมันว่างอยู่ก็ใส่ข้อมูลไปเลย ให้ข้อมูลใหม่คือตัว o

    _ _ o * _ * * _ _ 

    ทีนี้พอมีข้อมูลใหม่มา มีค่า hash เป็น 5 ซึ่งดันมีเจ้าที่อยู่แล้ว ก็ต้องเลื่อนตำแหน่งไปอีกเป็นช่องที่ 6 แต่ช่องนี้ก็มีเจ้าที่แล้วจึงเลื่อนไปช่องที่ 7 ซึ่งว่างอยู่ จึงทำการลงข้อมูลได้

    _ _ * * _ * * o _

    ง่ายไหม? ง่าย มาดูโค้ดกัน

    1. #defind MAX 100000
    2. typedef struct {
    3. long long key;
    4. int val;
    5. } DATA

    6. DATA storage[MAX];
    7. int flag[MAX] = {};

    8. int hash(long long key) {
    9. static const int magic 19;
    10. int i = (magic + key)%MAX;
    11. // if used and key does not match
    12. for (; flag[i] && storage[i].key != key; i++);
    13. return i;
    14. }

    15. void add_val(long long key, int val) {
    16. int i = hash(key)
    17. storage[i].val = val;
    18. storage[i].key = key;
    19. flag[i] = 1;
    20. }

    21. int get_val(long long key) {
    22. return storage[hash(key)].val; // if not found return 0
    23. }
    ในที่นี้จะทำการ flag ช่องที่ใช้งานไปแล้วเพื่อที่ hash ฟังก์ชันจะได้รู้ว่าช่องไหนที่ถูกใช้ไปแล้ว (สำหรับการจองใหม่) และตรวจสอบว่าค่าคีย์ของช่องดังกล่าวเท่ากับคีย์ที่หาหรือไม่ (สำหรับการค้นค่า) หากข้อใดข้อหนึ่งเป็นจริงก็จะหยุดหาต่อและให้ค่าตำแหน่งออกมา

    จากข้อมูลตรงนี้ทำให้หากเราซวยมากจริง ๆ คือ hash ได้ตัว index = 0 แต่ช่องว่างตัวสุดท้ายดันอยู่ที่ index = n-1 จะทำให้ใช้เวลา O(n)  ก็ต้องภาวนาต่อสิ่งศักดิศิทธิ์ว่ามันจะไม่เกินขึ้น (ไสยศาสตร์โปรแกรมมิ่ง)

    การเปลี่ยนเลข magic และขนาดของ MAX จะช่วยได้ ยิ่งค่า MAX มากก็จะทำให้มีช่องว่างมาก เกิด Load factor ที่น้อยลง โอกาสของการทับกันก็จะน้อยลงตาม ส่วน magic นะเหรอ ดวงยังไงละ เช่น ถ้า magic = 19 เกิด ช่องว่างที่ห่างกัน n ช่อง แต่หาก magic = 18 จะห่างกันแค่ช่องเดียว

    แล้วมันมีวิธีที่ดีกว่าการเลื่อนไปเรื่อย ๆ ไหม คำตอบคือมี! ติดตามต่อใน
    Hash III : การซ้อนทับ (II)
Views

เข้าสู่ระบบเพื่อแสดงความคิดเห็น

Log in