Hashing by Open Addressing Open Addressing เป็นเทคนิคแก้ไข Collision อีกวิธีหนึ่ง ต่างจาก Chaining ที่ไม่ได้แทรกข้อมูลในโครงสร้างอื่น แต่วางข้อมูลใน Hash Table เอง ขนาด Hash Table ต้องใหญ่กว่าจำนวน Keys 3 วิธียอดนิยม Linear Probing Quadratic Probing Double Hashing หลักการทำงาน ใช้ Hash Function

เทคนิค Linear Probing ใน Open Addressing ใช้ Ordinary Hash Function h(x) แล้วเพิ่มส่วน Linear ทำให้เป็นสมการเชิงเส้น h(x) = x mod m h(x,i) = (h(x) + i) mod m i = 0,1,...,m-1 เริ่ม i=0 เพิ่มจนว่าง ตอน i=0 แล้ว h(x,i)=h(x) ตัวอย่าง ขนาดตาราง 20 (m=20) ข้อมูล: {96, 48, 63, 29, 87, 77, 48, 65, 69, 9

เทคนิค Quadratic Probing ใน Open Addressing ใช้ Ordinary Hash Function h(x) แล้วเพิ่มส่วน Square ทำให้เป็นสมการกำลังสอง h(x) = x mod m h(x,i) = (h(x) + i²) mod m สามารถใช้สมการกำลังสองอื่นๆ ด้วยค่าคงที่ i = 0,1,...,m-1 เริ่ม i=0 เพิ่มจนว่าง ตอน i=0 แล้ว h(x,i)=h(x) ตัวอย่าง ขนาดตาราง 20 (m=20) ข

เทคนิค Double Hashing ใน Open Addressing ใช้ Ordinary Hash Function h(x): U → {0,1,...,m-1} เมื่อชนกัน ใช้ Hash Function อีกตัวเพื่อหาที่ว่าง $$h_{1}(x) = x \bmod m$$ $$h_{2}(x) = x \bmod m$$ $$h(x,i) = (h_{1}(x) + i \cdot h_{2}(x)) \bmod m$$ i = 0, 1, ..., m-1 เริ่มจาก i=0 เพิ่มทีละ 1 จนกว่าจะว่

Brents Method สำหรับ Open Addressed Hashing เป็น Heuristic พยายามลดเวลาเฉลี่ยสำหรับ Successful Search ใน Hash Table หลักการทำงาน เดิมทีใช้กับ Double Hashing แต่ใช้กับ Linear/Quadratic Probing ได้ อายุ (Age) ขององค์ประกอบ x ใน Open Addressing Hash Table คือค่า i น้อยที่สุด ที่ x วางอยู่ที่ A[xᵢ] B

ปัญหาของ BST ทั่วไป Binary Search Tree (BST) มีค่าน้อยกว่าอยู่ซ้าย ค่ามากกว่าอยู่ขวา ความซับซ้อนเฉลี่ยในการค้นหา O(log n) ขึ้นอยู่กับความสูงของต้นไม้ แต่ต้นไม้อาจกลายเป็น Skewed (เอียง) ต้นไม้แบบนี้เหมือน Linked List การค้นหาใช้เวลา O(n) ไม่มีประสิทธิภาพ การแก้ไข: Height-Balanced Tree สร้างต้นไม้

เทคนิค Asymmetric Hashing แยกตารางแฮชเป็น d บล็อก แต่ละบล็อกยาว n/d ค่า Probe xᵢ (0 ≤ i ≤ d) สุ่มจากช่วง {i·n/d, ..., (i+1)·n/(d-1)} เหมือน Multiple Choice Hashing: ตรวจสอบความยาวลิสต์ A[x₀], A[x₁], ..., A[x_{d-1}] แล้วแทรก x เข้าไปในลิสต์ที่สั้นที่สุด ถ้าเท่ากัน แทรกในลิสต์ที่มีดัชนีน้อยที่สุด Ex

LCFS Hashing คืออะไร LCFS (Last Come First Served) เป็นกลยุทธ์ Open Addressing ที่เปลี่ยนวิธีการแก้ไข Collision ใน Open Addressing แบบปกติเป็น FCFS (First Come First Served) คือถ้าชนกัน ตัวที่มี Priority สูงกว่า (มาก่อน) จะอยู่ในตาราง ตัวหลังต้องไปหาที่ว่าง หลักการ LCFS ทำงานตรงข้ามกับ FCFS: เมื่อ

การค้นหาในกราฟ กราฟเป็นโครงสร้างข้อมูลแบบ Non-linear เก็บข้อมูลในโหนด เชื่อมต่อด้วยเส้นขอบ (Edges) ต้องการค้นหาข้อมูลในกราฟมี 2 วิธีหลัก: Breadth First Search (BFS) BFS เป็นอัลกอริทึมการเดินทาง (Traversal) ไปเยี่ยมโหนดทั้งหมดของกราฟ เลือกโหนดหนึ่ง แล้วเยี่ยมโหนดติดกัน (Adjacent) ทีละตัว จบโหนดติดก

ประเภทของเส้นขอบใน DFS บน Digraph DFS สร้างต้นไม้ที่เรียกว่า DFS Tree มีเส้นขอบ 4 ประเภท: Tree Edge (T): เส้นขอบที่อยู่ใน DFS Tree Forward Edge (F): ขนานกับชุด Tree Edges (DFS number น้อยไปมาก, Completion number มากไปน้อย) Backward Edge (B): จาก DFS number มากไปน้อย และ Completion number น้อยไปมาก

Trail ในกราฟ Trail คือเส้นทางที่เป็นลำดับของเส้นขอบ (v1,v2), (v2,v3), ..., (vk-1,vk) ที่โหนดทั้งหมดอาจไม่แตกต่างกัน (อาจซ้ำ) แต่เส้นขอบทั้งหมดต้องแตกต่างกัน (ไม่ซ้ำ) ตัวอย่าง Trail: {(B,A), (A,C), (C,D), (D,A), (A,F)} นี่เป็น Trail แต่ไม่ใช่ Simple Path เพราะโหนด A ถูกเยี่ยมชม 2 ครั้ง ถ้าโหนดแรกแล

Binomial Tree Binomial Heap เป็นคอลเลกชันของ Binomial Trees ต้นไม้ไบนอมีอัล Bk นิยามแบบ Recursive: B0 ประกอบด้วยโหนดเดียว Bk ประกอบด้วย Bk-1 สองต้น ที่เชื่อมต่อกัน รากของหนึ่งเป็น Left-most child ของรากอีกต้น ตัวอย่าง Binomial Heaps คุณสมบัติของ Binomial Trees Bk มีโหนด 2ᵏ ตัว ความสูงของต้นไ

ลักษณะของ Fibonacci Heaps คล้ายกับ Binomial Heaps, Fibonacci Heaps เป็นคอลเลกชันของต้นไม้ (Trees) พัฒนามาจาก Binomial Heaps แต่ต่างกันตรงที่ ต้นไม้ใน Binomial Heaps เป็น Ordered Trees ในขณะที่ Fibonacci Heaps เป็น Rooted แต่ Unordered โครงสร้างโหนด ตัวชี้ p[x] ชี้ไปยังพาเรนต์ ตัวชี้ child[x] ชี้ไ

ต้นไม้เริ่มต้น อัลกอริทึมการแทรก (Insertion Algorithm) insert(heap, n, item) − 1, set i := i / 2 in each iteration, do if item ≤ heap[i/2], then break heap[i] = heap[i/2] done end if heap[i] := item End ตัวอย่าง สมมติต้องการแทรก 30 เข้า Heap:

ต้นไม้เริ่มต้น อัลกอริทึมการลบ (Deletion Algorithm) delete(heap, n) − Begin if heap is empty, then exit else item := heap[1] last := heap[n] n := n − 1 for i := 1, j := 2, j ≤ n, set i := j and j := j * 2, do if j < n, then if he

นิยาม ค่ากุญแจ x มาจาก Universe U โดยที่ U = {0, 1, ..., u-2, u-1} ฟังก์ชันแฮชคือ h โดเมนคือ U เรนจ์อยู่ในเซต {0, 1, ..., m-1} โดยที่ m ≤ u Perfect Hash Function ฟังก์ชันแฮช h ถูกเรียกว่า Perfect Hash Function สำหรับเซต S ⊆ U ถ้าสำหรับทุก x ∈ S ค่า h(x) เป็นเอกลักษณ์ (Unique) Perfect Hash Function

ฟังก์ชันแฮชแบบหาร ใช้ฟังก์ชันแฮช: h(x) = x mod m การจัดเก็บด้วย Chaining ดูแลรักษาอาร์เรย์ A[0, ..., m-1] โดยแต่ละองค์ประกอบเป็นตัวชี้ไปยังหัวของ Linked List ลิสต์ Li ที่ชี้โดย A[i] จะเก็บองค์ประกอบ x ทั้งหมดที่ h(x) = i เทคนิคนี้เรียกว่า Hashing by Chaining การดำเนินการ Insert: คำนวณ i = h(x) แ

ฟังก์ชันแฮชแบบคูณ ใช้ฟังก์ชันแฮชดังนี้: h(x) = ⌊m × (x × A)⌋ mod m โดยที่ A เป็นค่าคงที่จริง (Real-valued constant) ข้อดีของวิธีนี้คือ ค่า m ไม่ได้สำคัญมาก สามารถเลือก m เป็นกำลังของ 2 ได้ แม้ค่า A ใดก็ตามจะให้ฟังก์ชันแฮชได้ แต่มีค่า A บางค่าที่ดีกว่าค่าอื่น ค่า A ที่แนะนำโดย Knuth ตาม Knuth ควรใช

แนวคิดการเพิ่มขนาดอาร์เรย์แบบไดนามิก เมื่อสร้างอาร์เรย์ด้วยการจัดสรรหน่วยความจำแบบไดนามิก (Dynamic Memory Allocation) สามารถเพิ่มขนาดอาร์เรย์เป็นสองเท่าได้โดยทำตามขั้นตอนบางขั้นตอน ตัวอย่าง อาร์เรย์เริ่มต้นขนาด 5: 01234 Element 1Element 2Element 3Element 4Element 5 หลังเพิ่มขนาดเป็นสองเท่า (ข

ปัญหาของอาร์เรย์ทั่วไป ตามนิยาม อาร์เรย์เป็นโครงสร้างข้อมูลแบบเหมogeneous (Homogeneous) คือต้องเก็บข้อมูลชนิดเดียวกันเท่านั้น แต่ถ้าต้องการเก็บข้อมูลหลายชนิดในอาร์เรย์เดียว จะต้องใช้เทคนิคพิเศษ วิธีที่ 1: ใช้ Union ในภาษา C ในภาษา C สามารถใช้ Union เพื่อรวมชนิดข้อมูลต่างๆ ให้กลายเป็นชนิดเดียวกันได