Data Structure Quiz #11 Hash

ข้อใดจริงเกี่ยวกับโครงสร้างข้อมูล Hash

• เป็นโครงสร้างข้อมูลแบบไม่เชิงเส้น

• ตำแหน่งในการเก็บข้อมูลสัมพันธ์กับลำดับการเข้าของข้อมูล

• Hash function จะระบุตำแหน่งที่เก็บข้อมูล

• ใช้เวลาในการค้นหาข้อมูลอย่างน้อย O(log n)

ข้อใดแปลงตัวอักษรเป็นตัวเลขด้วยหลัก ascii ถูกต้อง

• A -> 97

• A -> 0x65

• E -> 65

• e -> 0x65

Operator/Function ที่นิยมใช้ใน hash function คืออะไร

• Modulo

• Integer Division

• Ceiling

• Floor

เราเรียกเหตุการณ์ที่ hash function ส่งข้อมูลไปยังตำแหน่งที่มีข้อมูลอยู่แล้วว่าอะไร

• Collision

• Crashing

• Chain Hashing

• Probing

กำหนดโครงสร้างข้อมูล Hash ที่มี Hash table ขนาด 10 ช่องและมี Hash function คือ H(x, i) = (x+ 2i)mod 10

ถ้ามีการใส่ข้อมูลที่มีค่าคีย์ = 24 เป็นข้อมูลแรก

ข้อมูลนี้จะถูกเก็บในช่อง index เท่าใด

กำหนดโครงสร้างข้อมูล Hash ที่มี Hash table ขนาด 10 ช่องและมี Hash function คือ H(x, i) = (x+ 2i)mod 10 ดังรูป

ถ้ามีการใส่ข้อมูลที่มีค่าคีย์ = 24 เป็นลำดับถัดไป

ข้อมูลนี้จะถูกเก็บในช่อง index เท่าใด

กำหนดให้ Hash table หนึ่งมี Hash function H(x)=(3x+2)mod12  และมีการแก้การชนแบบ Chain hashing ข้อใดจริง เมื่อมีการใส่ข้อมูลลงไปใน Hash table นี้

• เมื่อเกิดการชน ข้อมูลจะเลื่อนไปเก็บในอีกสองช่องถัดไป

• จะเกิด list ของข้อมูลที่ชนกันที่ index หมายเลข 2, 5, 8 และ 11

• จะเกิด list ของข้อมูลที่ชนกันที่ index หมายเลข 2, 6, และ 10

• จะเกิด list ของข้อมูลกระจายกันไม่มีรูปแบบชัดเจน

เมื่อกำหนดให้ Hash function คือ H(x)=(x+2i)mod 7 เมื่อ i แทนจำนวนการชน การใส่ข้อมูล "TUM" โดยมีการ weighting ลงใน hash table นี้ จะถูกเก็บในข้อมูลอินเด็กซ์หมายเลขอะไร