สมัครเรียนโทร. 085-350-7540 , 084-88-00-255 , ntprintf@gmail.com

ฟรี TUTORIAL JAVA

ฟรีtutorial JAVA 01 install Eclipse ฟรีtutorial JAVA 02 intro to programming Eclipse ฟรีtutorial JAVA 03 condiotion ฟรีtutorial JAVA 04.loop ฟรีtutorial JAVA 05.array ฟรีtutorial JAVA 05 2 array cont ฟรีtutorial JAVA 06 01 function ฟรีtutorial JAVA 06 02 function cont ฟรีtutorial JAVA 07 object ฟรีtutorial JAVA 08 string ฟรีtutorial JAVA 09 constructor ฟรีtutorial JAVA 10 01 oop ฟรีtutorial JAVA 10 02 oop2 ฟรีtutorial JAVA 11 exception ฟรีtutorial JAVA 12 reading file ฟรีtutorial JAVA 13 thread ฟรีtutorial JAVA 14 generic ฟรีtutorial JAVA 15 01 GUI ฟรีtutorial JAVA 15 02 GUI2 ฟรีtutorial JAVA 15 03.GUI3 ฟรีtutorial JAVA 16 using WindowBuilder ฟรีtutorial JAVA 17 event ฟรีtutorial JAVA 18 database management system ฟรีtutorial JAVA 19 ER diagram ฟรีtutorial JAVA 20 Relational ฟรีtutorial JAVA 21 Xampp ฟรีtutorial JAVA 22 JDBC ฟรีtutorial JAVA 23 MVC ฟรีtutorial JAVA 24 SQL ฟรีtutorial JAVA
ขอย้ำอีกครั้งว่าเนื้อหาที่เห็นอยู่นี้ไม่ใช่เนื้อหาตามปกติที่เราสอนในห้องเรียนเป็นแค่ tutorial ไว้อ่านประกอบเฉยๆ แทบไม่เกี่ยวกันเลย และไม่เกี่ยวกับการบ้านที่ทำครับ ในห้องเรียนเนื้อหาจะเยอะกว่านี้ค่อนข้างมากครับ
ขอบคุณน้องตี้ อย่างสูงสำหรับ Tutorial ดีๆ

ฟรี TUTORIAL DATA STRUCTURE

DATA STRUCTURE

ฟรีtutorial : DATA STRUCTURE : 01 1การเรียงลำดับ(Sorting) ฟรีtutorial : DATA STRUCTURE : 01 2 การเรียงลำดับ2 ฟรีtutorial : DATA STRUCTURE : 02 อาร์เรย์ลิสต์ (Array List) ฟรีtutorial : DATA STRUCTURE : 03 ลิงค์ลิสต์ (Linked List) ฟรีtutorial : DATA STRUCTURE : 04 สแต๊ค ฟรีtutorial : DATA STRUCTURE : 05 1 คิวและไพออริตี้คิว ฟรีtutorial : DATA STRUCTURE : 05 2 คิวและไพออริตี้คิว ฟรีtutorial : DATA STRUCTURE : 06 1 ไบนารีทรี ฟรีtutorial : DATA STRUCTURE : 06 2 ไบนารีเสิร์ชทรี ฟรีtutorial : DATA STRUCTURE : 06 3 ไบนารีเสิร์ชทรี ฟรีtutorial : DATA STRUCTURE : 08 แฮช ฟรีtutorial : DATA STRUCTURE : 09 กราฟ ฟรีtutorial : DATA STRUCTURE :
ขอย้ำอีกครั้งว่าเนื้อหาที่เห็นอยู่นี้ไม่ใช่เนื้อหาตามปกติที่เราสอนในห้องเรียนเป็นแค่ tutorial ไว้อ่านประกอบเฉยๆ แทบไม่เกี่ยวกันเลย และไม่เกี่ยวกับการบ้านที่ทำครับ ในห้องเรียนเนื้อหาจะเยอะกว่านี้ค่อนข้างมากครับ
ขอบคุณน้องตี้ อย่างสูงสำหรับ Tutorial ดีๆ

แฮช(Hash)

 แฮชเป็นโครงสร้างข้อมูลอีกแบบหนึ่งที่มีประสิทธิภาพมากๆในเรื่องเพิ่ม ลบ ค้นหา (ค่อนข้างจำกัดแต่ว่ามีประสิทธิภาพมากๆ) โดยเวลาคงที่เพียงO(1) เท่านั้น โดยการทำงานของแฮชจะแตกต่างจากโครงสร้างข้อมูลแบบอื่นๆคือ โครงสร้างข้อมูลแบบอื่นๆจะเก็บข้อมูลเป็นระเบียบเรียบร้อยด้วยตำแหน่งที่กำหนดเอาไว้ เช่นฮีปก็สามารถหาโหนดพ่อลูกกันได้เพราะตำแหน่งเรียงจากซ้ายไปขวาอย่างตายตัว แต่แฮชใช้วิธีการเอาข้อมูลมาผ่านกระบวนการหนึ่งๆจนได้ตำแหน่งข้อมูลออกมาก็จะเอาไปเก็บไว้ในตำแหน่งนั้น

ตารางแฮช(Hash table) คีย์(Key) ดัชนี(Index)

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

 

รูป 8-1

            เช่น อยากเก็บข้อมูลค้นไข้ในโรงพยาบาล ถ้ากลัวว่าเก็บชื่อแล้วข้อมูลจะซ้ำกันเสียเวลาหา ก็เก็บเป็นเลขประจำตัวประชาชนซึ่งไม่ซ้ำกันแน่ๆ เอาไปผ่านแฮชฟังก์ชันออกได้เลขหนึ่งก็เอาเลขนั้นไปเก็บในตารางแฮช

 

รูป8-2

            จากรูปให้รหัสสมาชิกเป็น key Hash เอาไปผ่าน Function ได้เลขหนึ่งออกมาเป็น address เอาคีย์ไปใส่ในตารางแฮชตาม address ที่ได้ พอเอาคีย์ไปทำการค้นหาก็จะได้ชื่อของสมาชิกนั้นๆออกมา เป็นต้น

ปัญหาการชนกัน

            เนื่องจากการเก็บข้อมูลด้วยแฮชต้องผ่านแฮชฟังก์ชั่นเพื่อหาดัชนี แต่บางครั้งก็อาจเกิดเหตุการณ์ที่แม้จะมีช่องว่างมากมายแต่คีย์ที่ผ่านแฮชฟังก์ชันกลับได้ดัชนีเดียวกัน แต่ช่องหมายเลขเดียวกันไม่สามารถเก็บข้อมูลสองตัวพร้อมกัน หรือก็คือเกิดข้อมูลชนกัน มีวิธีแก้แยกได้เป็น 2 วิธีดังนี้

Separate Chain Hashing

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

 

รูป 8-3

            จะเห็นได้ว่าตารางแฮชหน้าตาเปลี่ยนไปจากที่ช่องที่ 0 จะเก็บได้แค่ข้อมูลเดียว ก็สามารถเก็บได้หลายตัวเพราะมีช่องย่อยๆที่เกิดจาก list เข้ามาช่วยเป็นส่วนต่อ

 

Open Addressing

            อีกวิธีการหนึ่งคือ Open Addressing แปลตรงตัวว่า เปิดที่อยู่(ใหม่) หรือก็คือการหาช่องใหม่ให้นั่นเอง ถ้าข้อมูลที่เข้าเกิดการชนกันขึ้นมาก็ต้องให้หาช่องใหม่ไปลงแทนการสร้างลิสต์ช่องเดิม ซึ่งการคำนวณหาช่องใหม่มี 3 วิธี

-          Double Hashing

เป็นการเปลี่ยนช่องโดยการเอาฟังก์ชันแฮชอีกอันมาช่วยหาช่องใหม่ ทำให้การกระจายตัวของข้อมูลในตารางแฮชสม่ำเสมอ

-          Linear Probe

 เป็นการเปลี่ยนช่องแบบคงที่ ทำให้ข้อมูลอยู่ใกล้ๆกัน

-          Quadratic Probe

-          เป็นการคำนวณหาช่องใหม่ โดยส่วนใหญ่จะใช้ฟังก์ชันยกกำลังสอง ข้อมูลก็จะอยู่ใกล้ๆกันถ้าเกิดการชนอีก

ตัวอย่างการสร้างแฮชแบบ Separate Chain Hashing

 

รูป 8-4

บรรทัดที่ 9 : สร้างคลาส Hash

บรรทัดที่ 11 : สร้างตัวแปร size สำหรับเป็นขนาด

บรรทัดที่ 12 : สร้างตัวแปร capacity สำหรับใช้ใน hashFunction

บรรทัดที่ 13 : สร้าง data  เป็นข้อมูลแบบ LinkedList

บรรทัดที่ 15 : สร้างคอนสตรัคเตอร์ของ Hash

บรรทัดที่ 17 : กำหนดให้ size เริ่มต้นจาก 0

บรรทัดที่ 18 : กำหนดให้ capacity เป็น 13 เป็นเลขเฉพาะจะดีเพื่อลดโอกาสชน

บรรทัดที่ 19:

 

รูป 8-5

บรรทัดที่ 22 : สร้าง hashFunction สำหรับเอาคีย์มาหาดัชนี

บรรทัดที่ 24: ให้ตัวแปร t เรียกเมท็อด hashCode ซึ่งเป็นเมท็อดสำหรับคืนค่าตำแหน่ง เอามาmod ด้วย capacity

บรรทัดที่ 27 : สร้างเมท็อด add

บรรทัดที่ 29 : เอาข้อมูลที่เข้ามาไปผ่าน hashFunction

บรรทัดที่ 30-32 : ถ้าตำแหน่งที่ได้ไม่มีให้สร้างโหนดใน LinkedList เข้ามาเก็บ

บรรทัดที่ 34: ถ้ามีตำแหน่งนั้นอยู่ลปแวก็เพิ่มข้อมูลลงไปเลยด้วยเมท็อด addFirst ที่มีอยู่แล้วใน LinkedList

 

รูป 8-6

บรรทัดที่ 38 : สร้างเมท็อด isContainสำหรับตรวจว่ามีข้อมูลซ้ำกันหรือไม่

บรรทัดที่ 40:เอาข้อมูลที่เข้ามาไปผ่าน hashFunction

บรรทัดที่ 41-43: ถ้าไม่มีข้อมูลตำแหน่งนั้น คืนว่า null

บรรทัดที่ 45: มีข้อมูลคืนค่า true

 

 



แผนผังการเรียนเขียนโปรแกรม

>