CoE KKU

ในบทที่ผ่านเราได้กล่าวถึง search tree ADT ซึ่งสนับสนุนการดำเนินงานหลายอย่างกับเซตของสมาชิกได้ ในบทนี้จะกล่าวถึง Hash table ADT ที่สนับสนุนการดำเนินงานงานเพียงบางอย่างที่มีอยู่ใน binary search tree เท่านั้น

การใช้งาน hash tables นั้นปกติเรียกว่า hashing และกล่าวได้ว่า Hashing ก็คือเทคนิคที่ใช้เพื่อการทำงานของ insertions, deletions และ finds ด้วยเวลาเฉลี่ยที่เป็นค่าคงที่ (constant average time) โดยจะไม่สนับสนุนการดำเนินการใด ๆ อย่างมีประสิทธิภาพที่ต้องอาศัยสารสนเทศของการจัดลำดับ เช่น findmin, findMax หรือการพิมพ์ค่าเรียงลำดับตามค่า ในบทนี้จะกล่าวถึง

• วิธีการต่าง ๆ ในการใช้ hash table
• วิเคราะห์เปรียบเทียบวิธีต่าง ๆ ดังกล่าว
• แสดงการประยุกต์ใช้ hashing
• เปรียบเทียบ hash tables กับ binary search trees