de algorismoKratui++
Hash III : การซ้อนทับ (II)
  • เพื่อความเร็วในการค้นหาที่มากขึ้น เราใช้ Linked-list เข้ามาช่วย
    โดยถ้าเกิดการ Collision ก็จะทำการต่อท้ายข้อมูลชุดก่อนไปเรื่อย ๆ

    ง่ายไหม? ง่าย
    เห็นภาพไหม? ไม่ เอ้า ไปดูกัน

    จากที่ยาย Sandra Dee ดันไปทับที่ตา John Smith แล้ว เราก็ให้เธอไปต่อตูดตาจอห์นเสียเลย ทีนี้เวลาจะค้นหาก็แค่ค้นลิสต์ในตำแหน่งที่ต้องการไปทีละตัว ๆ แบบนี้แล้วก็จะค้นหาได้เร็วกว่าการเลื่อนตำแหน่งไปเรื่อย ๆ ธรรมดา เอ้า ไปดูโค้ดกัน

    ในที่นี้ใช้ std::vector ของ C++ แทน เพราะขี้เกียจเขีียนลิงก์ลิสต์
    แต่เอาจริง ๆ นะ ถ้าใช้ C++ เขียนก็ใช้ std::unordered_map เถอะ 555

    1. #define MAX 100000
    2.  
    3. typedef struct {
    4. long long val;
    5. int key;
    6. } DATA;
    7.  
    8. std::vector<DATA> storage[MAX];
    9.  
    10. int hash(long long key) {
    11. static const int magic = 19;
    12. return (key+magic)%MAX;
    13. }
    14.  
    15. int add_val(long long key, int val) {
    16. DATA temp;
    17. int idx = hash(key);
    18. temp.key = key; temp.val = val;
    19. storage[idx].push_back(temp);
    20. return idx;
    21. }
    22.  
    23. int get_val(long long key) {
    24. int idx = hash(key);
    25. for (DATA e : storage[idx]) {
    26. if (e.key == key)
    27. return e.val;
    28. }
    29. return 0;
    30. }
    จริง ๆ โค้ดนี้มันก็มีข้อเสียอยู่ คือมันเขียนทับของเก่าไม่ได้  เพราะฟังก์ชัน add_val จะต่อท้าย vector ไม่ใช่เขียนทับ แต่มันก็ "ดีพอ" สำหรับสถานการณ์นี้ที่จะไม่เขียนซ้ำ (หรือหากเขียนเป็นลิงก์ลิสจริง ๆ จะทำให้มันเขียนทับได้ก็ได้)

    อันที่จริงจะจบเรื่อง hashing ไว้ตรงนี้ก็ได้  สำหรับการ hash ที่คีย์เป็นอย่างอื่นนั้นก็จงใช้ความคิดสร้างสรรค์แปลงมันเป็นตัวเลขให้ได้ เช่น string เราอาจจะเอาขนาดมาบวกกับค่า ASCII ของอักษรตัวแรก ลบกับ ASCII ของตัวที่สองคูณกับ ASCII ของตัวสุดท้ายลบ ASCII ตัวกลาง แล้วเอาไปหารเอาเศษด้วยขนาด container ของเราอีกที  อย่างที่บอก ขึ้นกับจินตนาการและไสยศาสตร์

Views

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

Log in