de algorismoKratui++
Hash I : ลายเซ็นของข้อมูล
  • Hash function คือฟังก์ชันอะไรก็ตามที่เปลี่ยนข้อมูลบ้าบอที่เราจัดการเก็บมันไม่ได้ ให้กลายเป็นข้อมูลน่ารักอีกอันหนึ่งซึ่งเราจัดการเก็บได้ (Data mapping)

    ปัญหา คุณได้ข้อมูลมาชุดหนึ่ง ข้อมูลนี้มีสองส่วนประกอบ ส่วนแรกเป็นค่าที่ไว้ใช้อ้างอิง เป็นเลขจำนวนเต็ม มีค่า k (0 <= k <= 5e11)  และอีกส่วนคือข้อมูลที่ต้องการเก็บ เป็นจำนวนเต็ม v (1 <= v <= 300) โดยจะมีจำนวนข้อมูล n ข้อมูล (1 <= n <= 1e5)

    ในความคิดแรกเราอาจจะอยากใช้อาเรย์ในการเก็บค่าคีย์อ้างอิง (k) เอาไว้ โดยข้อมูล vi ก็เก็บในอาเรย์ใน index ที่ ki ถ้าเป็นแบบนี้แล้วก็จะเข้าถึงข้อมูลได้ใน O(1)

    1. int storage[500000000000];

    2. void add_val(long long key, int val) {
    3. storage[key] = val;
    4. }

    5. int get_val(long long key) {
    6. return storage[key]; // if not found return 0
    7. }

    ปุจฉา : วิธีนี้ทำได้จริงเหรอ?

    ลองประกาศอาเรย์ขนาด 5e11 ตัวดูนะ แล้วจะรู้ว่ามันเป็นไปไม่ได้ ! ขนาดมันใหญ่เกินไป เราจึงมีวิธีแก้ปัญหาที่สอง ก็ประกาศตัวแปรเท่าที่ใช้นั่นแหละ แล้วเก็บทั้งคีย์และค่า เวลาหาก็ไล่หาไปจนเจอคีย์ที่ตรงกับที่เราต้องการ

    1. typedef struct {
    2. long long key;
    3. int val;
    4. } DATA;

    5. DATA storage[10000];
    6. int last = 0;

    7. void add_val(long long key, int val) {
    8. storage[last].key = key;
    9. storage[last].val = val;
    10. last++;
    11. }

    12. int get_val(long long key) {
    13. for (int i=0; i<last; i++) {
    14. if (storage[i].key == key)
    15. return storage[i].val;
    16. }
    17. return 0; // not found
    18. }

    ด้วยวิธีนี้การหาข้อมูลจะใช้เวลา O(n) ซึ่งก็เป็นตัวเลขที่ยอมรับได้ในกรณีที่ n มีค่าไม่เยอะเท่าไหร่ และเรียกใช้แค่ครั้งเดียว

    สมมุติ 1<= n <= 1e6 และมีการเรียกใช้สัก 1 <= q <= 1e6 ครั้งล่ะ

    O(qn) -> 1e12 ไม่ใช่ตัวเลขที่น่ารักเลยสำหรับการเขียนโปรแกรมเชิงแข่งขัน และการเขียนโปรแกรมจัดการฐานข้อมูลในโลกจริงเช่นกัน ลองนึกภาพ Facebook ใช้เวลา O(qn) ในทุกการค้นหาของผู้ใช้สิ ด้วยปริมาณข้อมูลขนาดนั้นคงต้องรอสักครึ่งวันแน่ ๆ ในการแอบส่องเฟสผู้ฯสักคน  'w')b

    รูปที่ ๑ ภาพแสดงการ hash string เป็น int

    นี่จึงเป็นจุดที่เราต้องใช้ไสยศาสตร์เข้ามาช่วย มันเรียกว่า Hash function ซึ่งจะเขียนอย่างไรนั้นก็แล้วแต่ประเภทของข้อมูลและวิธีการใช้ และถึงจะเป็นข้อมูลเดียวกัน การใช้งานเดียวกัน การ hash ก็ทำได้หลากหลายวิธีมาก เรียกได้ว่าขึ้นกับความคิดสร้างสรรค์ของคนเขียนเลยก็ว่าได้ 

    นี่เป็นตัวอย่างการ hash ที่หน้าโง่มาก ๆ (แต่ก็ใช้งานได้ในระดับหนึ่ง)

    1. #define MAX 10000 //n<=10000
    2. int hash(long long key) {
    3. static const int magic 19;
    4. return (key+magic)%MAX;
    5. }

    ปุจฉา : ฟังก์ชั่นนี้ทำอะไร

    ฟังก์ชัน hash แบบขี้เกียจสุด ๆ นี้นำเลขคีย์มาบวกด้วยเลขไสยศาสตร์อะไรสักอย่าง และนำไปหารเอาเศษด้วยจำนวนข้อมูลที่สามารถเก็บได้ (n)  มาดูตัวอย่างกันดีกว่า

    hash(0) = 19,
    hash(219302) = 9321,
    hash(2093139432333) = 2352

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

    ฉะนั้นแล้วเราย่อมเก็บข้อมูลไว้ในอาเรย์ขนาด 10000 ตัวได้ไม่ว่าเลขคีย์จะเยอะแค่ไหนก็ตาม และการคำนวนนี้ใช้เวลา O(1) และการหาก็คือการเอาคีย์ไปใส่ใน hash เพื่อให้ได้เลขตำแหน่งที่เก็บออกมา นั่นก็ O(1) เหมือนกัน !

    1. #defind MAX 100000
    2. int hash(long long key) {
    3. static const int magic 19;
    4. return (key+magic)%MAX;
    5. }
    6. int storage[MAX];

    7. void add_val(long long key, int val) {
    8. storage[hash(key)] = val;
    9. }

    10. int get_val(long long key) {
    11. return storage[hash(key)]; // if not found return 0
    12. }

    ปุจฉา : วิธีนี้ทำได้จริงเหรอ?

    ลองกลับไปดูรูปที่ ๑ แล้วสังเกตุอะไรแปลก ๆ ไหม?  ใช่แล้ว Michael กับ Toby เมื่อใส่ลงไปในฟังก์ชัน hash แล้วให้เลข 2 เหมือนกัน  แล้วลองกลับมาดูฟังก์ชันของ hash ของเรากัน

    hash(0) = 19
    hash(10000) = 19
    hash(20000) = 19

    สิ่งนี้เรียกว่า Hash collision นั่นคือการซ้อนทัับกันของ hash ในการแข่งขันเขียนโปรแกรมแล้วเราไม่มีทางรู้ได้เลยว่าค่าที่ได้มาจะซ้อนทับกันหรือไม่ เช่นเดียวกับในโลกจริง แม้ว่าในโลกจริงจะตรวจสอบชุดข้อมูลได้ หากแต่กับโปรแกรมใหญ่ ๆ แล้ว มันก็ทำได้ยาก

    การทับกันของ hash นี้ หากเป็นไปตามโค้ดข้างบนแล้ว จะทำให้ข้อมูลตัวเก่าถูกแทนที่ด้วยตัวใหม่ ส่งผลให้เกิดคำตอบที่ผิดได้ เราอาจแก้ลองปัญหาได้โดยการเปลี่ยนเลข magic ซึ่งอาจจะช่วยได้ หรือช่วยไม่ได้ แล้วแต่เวรกรรม (ไสยศาสตร์ยังไงล่ะ)

    แล้วเราจะมีวิธีแก้มันอย่างไร ติดตามต่อใน Hash II : การซ้อนทับ

Views

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

Log in