Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ตารางแฮช (อังกฤษ: Hash table, Hash map) เป็นโครงสร้างข้อมูลในรูปแบบตาราง ซึ่งอาจใช้แถวลำดับในการทำ ใช้ในการเก็บข้อมูลจำนวนมาก เพื่อสะดวกต่อการเก็บและค้นหา โดยการผ่านฟังก์ชันแฮช
| ตารางแฮช | |
|---|---|
 การใช้งานตารางแฮชผ่านฟังก์ชันแฮช | |
| ความสำคัญของลำดับ | ไม่มีความสำคัญ |
| การซ้ำกันของสมาชิก | ไม่อนุญาตให้ซ้ำได้ |
| เวลาที่ใช้ค้นหาตามดัชนี | - |
| เวลาที่ใช้ค้นหาตามค่า | O (1) |
| เวลาที่ใช้ในการเข้าถึง | O (1) |
| การทำให้ว่าง | - |
| เวลาที่ใช้ทำให้ว่าง | - |
| โครงสร้างต้นแบบ | ตาราง |
ลักษณะของตารางแฮช
ตารางแฮชมักใช้แถวลำดับหรือขนาดใหญ่เพื่อใช้ในการจัดการเก็บข้อมูลจำนวนมาก โดยมีลักษณะการเก็บแบบดัชนีได้ (Indexing) วิธีการเก็บนั้นจะนำข้อมูลที่จะนำมาเก็บผ่านฟังก์ชันฟังก์ชันหนึ่ง(เราจะเรียกข้อมูลที่ผ่านฟังก์ชันนั้นว่า key) ซึ่งเรียกว่าฟังก์ชันแฮชจะได้เลขซึ่งจำเพาะกับข้อมูลนั้น กล่าวคือ ข้อมูลแต่ละตัวเมื่อผ่านฟังก์ชันแฮชแล้ว จะได้เลขที่แตกต่างกัน แล้วจึงนำข้อมูลไปเก็บไว้ในตาราง แถวลำดับ หรือ Map ที่กำหนดไว้
ตามรูปเป็นการเก็บหมายเลขโทรศัพท์ โดยใช้ชื่อผู้ใช้โทรศัพท์เป็น key ก็สามารถทำได้โดยการสร้างฟังก์ชันแฮชของชื่อผู้ใช้โทรศัพท์ เราก็จะได้ว่าหมายเลขโทรศัพท์นี้ควรเก็บในช่องใด เมื่อจะค้นหาหมายเลขโทรศัพท์ของผู้ใช้โทรศัพท์คนใด ก็นำชื่อผู้ใช้โทรศัพท์ผ่านฟังก์ชันแฮช ก็จะรู้ว่าหมายเลขโทรศัพท์ของเขาผู้นั้นอยู่ในช่องใดได้ทันที ฟังก์ชันแฮชก็เปรียบเทียบได้กับ สารบัญหรือดรรชนีของหนังสือนั่นเอง
จุดเด่นของตารางแฮช
ตารางแฮชเน้นการค้นหาและเพิ่มลดสมาชิกอย่างรวดเร็ว จนเป็นเวลาคงที่ O(1) แต่ข้อมูลเหล่านั้นจะต้องไม่มีลำดับและไม่ซ้ำกันเท่านั้น
บริการที่มักจะมี
- คืนข้อมูลที่คู่กับ key ที่กำหนด
- เพิ่มข้อมูลลงในตารางแฮชให้สอดคล้องกับ key ที่กำหนด
- ลดข้อมูลที่คู่ key ที่กำหนดในตารางแฮช
ความเร็วที่ใช้ในการทำงาน
การทำงานของตารางแฮชเน้นการเข้าถึงข้อมูลอย่างรวดเร็วเป็นเวลาคงที่ O(1) ในกรณีเฉลี่ย (ใช้กับข้อมูลสุ่ม และมีการออกแบบโครงสร้างข้อมูลอย่างถูกต้อง)
| การทำงาน | เวลา |
|---|---|
| การหาตามคีย์ (ฟังก์ชันแฮช) | O(1) |
| การเข้าถึงสมาชิก | โดยเฉลี่ย O(1) |
การแก้ปัญหาการชนกัน
การชนกัน (collision) เกิดจากการที่สมาชิกมากกว่าสองตัวเกิดมีผลของฟังก์ชันแฮชตรงกัน ทำให้เกิดการเก็บที่เดียวกัน หรือเมื่อคำนวณผลจากฟังก์ชันแฮชแล้วอาจมีค่ามากกว่าขนาดของ ตารางแฮชทำให้ต้องวนกลับมาใส่แล้วเจอตัวที่เดิมเคยมีอยู่แล้ว วิธีการแก้ปํญหาที่นิยมมีสองวิธีคือ วิธี SperateChaining และ OpenAddressing
วิธี Separate Chaining
Separate Chaining คือการใช้รายการหรือแถวลำดับขยายขนาดได้แทนการเก็บ สมาชิกโดยตรง ตารางแฮชแต่ละช่องก็จะกลายเก็บข้อมูลในลักษณะเป็นรายการ เมื่อตัวใดที่ต้องเก็บในตารางแฮชตำแหน่งเดียวกัน ก็จะถูกเก็บไว้ในรายการนี้ต่อไปเรื่อยๆ (คล้ายๆพจนานุกรม เมื่อเปิดสารบัญแล้วเจอว่าตัวอักษรตัวแรกของคำที่เราจะหาอยู่ในหน้าใด ก็เปิดหน้านั้นแล้วต้องมานั่งไล่หาต่อในรายการของคำที่มีตัวอักษรตัวแรกเหมือนกับคำที่เราจะหาต่อไป)
วิธี Open Addressing
เมื่อการการชนเกิดขึ้นวิธีการของ Open Addressing คือการหาช่องในตารางแฮชใหม่โดยกระโดดไปจากที่เดิมเป็นฟังก์ชันหนึ่ง จนกว่าจะหาช่องว่างเจอจึงจะใส่ค่าลงไป ฟังก์ชันที่มักจะใช้กระโดดมีสามแบบคือ การตรวจเชิงเส้น (Linear Probing), การตรวจกำลังสอง (Quadatic Probing) และการแฮชสองชั้น (Double Hashing)
การตรวจเชิงเส้น
การตรวจเชิงเส้นจะทำให้กระโดดไปจากจุดเดิมเป็นระยะคงที่ การกระโดดเช่นนี้จะทำให้เกิดข้อมูลอยู่ ติดๆกันเป็นกลุ่มขนาดใหญ่แต่มีจำนวนกลุ่มน้อยๆ ทำให้ผลที่เข้ามาถ้ามีการชนกันบริเวณนี้ จะต้องเสียเวลากระโดดไปเพื่อพ้นจากช่วงนี้ และทำให้กลุ่มนี้ใหญ่ขึ้นไปเรื่อยๆอีก เราเรียกการเกาะกลุ่มเป็นจำนวนกลุ่มน้อยๆแต่กลุ่มขนาดใหญ่ๆ เนื่องจากการตรวจเชิงเส้นว่า การเกาะกลุ่มปฐมภูมิ (Primary Clustering)
การตรวจกำลังสอง
การตรวจกำลังสองมักคำนวณว่าจะทำให้กระโดดไปจากจุดเดิมเป็นระยะหนึ่ง ซึ่งเป็นฟังก์ชัน (มักเป็นฟังก์ชันยกกำลังสอง) การกระโดดเช่นนี้จะทำให้เกิดข้อมูลอยู่ ติดๆกันเป็นกลุ่มขนาดเล็กแต่มีจำนวนกลุ่มหลายกลุ่ม เพราะการกระโดดจะเป็นการกระโดดข้ามไปไม่ติดกัน แต่ถึงอย่างไรก็ตามถ้าแฮชชนกัน ก็จะไปเจอกลุ่มเล็กๆกลุ่มเดิมอยู่ดี และจะไม่เจอช่องว่างบางช่องว่างได้ เราเรียกการเกาะกลุ่มขนาดเล็กๆเป็นจำนวนมาก เนื่องจากการตรวจกำลังสองว่า การเกาะกลุ่มทุติยภูมิ (Secondary Clustering)
การแฮชสองชั้น
การแฮชสองชั้นจะใช้ฟังก์ชันการกระโดดเป็นฟังก์ชันแฮชอีกฟังก์ชันหนึ่ง (มักเอาฟังก์ชันแฮชฟังก์ชันเดิมมาช่วยคิด) จึงทำให้การกระโดดกระจายค่อนข้างสม่ำเสมอและไม่เกาะกลุ่มกัน
ความหนาแน่นของข้อมูล และการ Rehash
ถึงแม้ว่าการอนุญาตให้ชนกันทำให้เราสามารถใช้ตารางขนาดเล็กได้ แต่การให้เกิดการชนกันจนรายการยาวเกินไปหรือหนาแน่นเกินไป จะทำให้การเข้าถึงข้อมูลต้องเสียเวลาค้นหาในรายการมากกว่า จึงทำให้ผิดจุดประสงค์ความเป็นตารางแฮชที่ต้องการเข้าถึงข้อมูลอย่างรวดเร็วได้
เราจึงนิยามค่าสัดส่วนบรรจุ(load factor: 
)ให้มีค่าเท่ากับจำนวนข้อมูล(N)หารด้วยขนาดของตาราง(tablesize)
ซึ่งในวิธี SeparateChaining จะสามารถประมาณได้ว่าเป็นความยาวเฉลี่ยของรายการในแต่ละช่อง สำหรับวิธี OpenAddressing นั้นต้องมีค่าสัดส่วนบรรจุน้อยกว่าหนึ่งอยู่เสมอ ในทางปฏิบัติสำหรับ OpenAddressing เรามักให้ค่าสัดส่วนบรรจุให้น้อยกว่า 0.5 เพื่อกันการชนกันมาก []
เมื่อมีข้อมูลมากขึ้นแต่จำนวนตารางเท่าเดิม ค่าสัดส่วนบรรจุก็จะมากขึ้นเรื่อยๆ วิธีการแก้คือจะสร้างตารางแฮชที่ใหญ่กว่าเดิมและย้ายข้อมูลทั้งหมดไปแฮชใหม่ๆ เรามักเรียกขั้นตอนนี้ว่า รีแฮช (rehash)
ดูเพิ่ม
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
tarangaehch xngkvs Hash table Hash map epnokhrngsrangkhxmulinrupaebbtarang sungxacichaethwladbinkartha ichinkarekbkhxmulcanwnmak ephuxsadwktxkarekbaelakhnha odykarphanfngkchnaehchtarangaehchkarichngantarangaehchphanfngkchnaehchkhwamsakhykhxngladbimmikhwamsakhykarsaknkhxngsmachikimxnuyatihsaidewlathiichkhnhatamdchni ewlathiichkhnhatamkhaO 1 ewlathiichinkarekhathungO 1 karthaihwang ewlathiichthaihwang okhrngsrangtnaebbtaranglksnakhxngtarangaehchtarangaehchmkichaethwladbhruxkhnadihyephuxichinkarcdkarekbkhxmulcanwnmak odymilksnakarekbaebbdchniid Indexing withikarekbnncanakhxmulthicanamaekbphanfngkchnfngkchnhnung eracaeriykkhxmulthiphanfngkchnnnwa key sungeriykwafngkchnaehchcaidelkhsungcaephaakbkhxmulnn klawkhux khxmulaetlatwemuxphanfngkchnaehchaelw caidelkhthiaetktangkn aelwcungnakhxmulipekbiwintarang aethwladb hrux Map thikahndiw tamrupepnkarekbhmayelkhothrsphth odyichchuxphuichothrsphthepn key ksamarththaidodykarsrangfngkchnaehchkhxngchuxphuichothrsphth erakcaidwahmayelkhothrsphthnikhwrekbinchxngid emuxcakhnhahmayelkhothrsphthkhxngphuichothrsphthkhnid knachuxphuichothrsphthphanfngkchnaehch kcaruwahmayelkhothrsphthkhxngekhaphunnxyuinchxngididthnthi fngkchnaehchkepriybethiybidkb sarbyhruxdrrchnikhxnghnngsuxnnexngcudednkhxngtarangaehchtarangaehchennkarkhnhaaelaephimldsmachikxyangrwderw cnepnewlakhngthi O 1 aetkhxmulehlanncatxngimmiladbaelaimsaknethannbrikarthimkcamikhunkhxmulthikhukb key thikahnd ephimkhxmullngintarangaehchihsxdkhlxngkb key thikahnd ldkhxmulthikhu key thikahndintarangaehchkhwamerwthiichinkarthangankarthangankhxngtarangaehchennkarekhathungkhxmulxyangrwderwepnewlakhngthi O 1 inkrniechliy ichkbkhxmulsum aelamikarxxkaebbokhrngsrangkhxmulxyangthuktxng karthangan ewlakarhatamkhiy fngkchnaehch O 1 karekhathungsmachik odyechliy O 1 karaekpyhakarchnknkarchnkn collision ekidcakkarthismachikmakkwasxngtwekidmiphlkhxngfngkchnaehchtrngkn thaihekidkarekbthiediywkn hruxemuxkhanwnphlcakfngkchnaehchaelwxacmikhamakkwakhnadkhxng tarangaehchthaihtxngwnklbmaisaelwecxtwthiedimekhymixyuaelw withikaraekpyhathiniymmisxngwithikhux withi SperateChaining aela OpenAddressing withi Separate Chaining karaekpyhakarchnkndwy SeparateChaining Separate Chaining khuxkarichraykarhruxaethwladbkhyaykhnadidaethnkarekb smachikodytrng tarangaehchaetlachxngkcaklayekbkhxmulinlksnaepnraykar emuxtwidthitxngekbintarangaehchtaaehnngediywkn kcathukekbiwinraykarnitxiperuxy khlayphcnanukrm emuxepidsarbyaelwecxwatwxksrtwaerkkhxngkhathieracahaxyuinhnaid kepidhnannaelwtxngmanngilhatxinraykarkhxngkhathimitwxksrtwaerkehmuxnkbkhathieracahatxip withi Open Addressing karaekpyhakarchnkndwy OpenAddressing emuxkarkarchnekidkhunwithikarkhxng Open Addressing khuxkarhachxngintarangaehchihmodykraoddipcakthiedimepnfngkchnhnung cnkwacahachxngwangecxcungcaiskhalngip fngkchnthimkcaichkraoddmisamaebbkhux kartrwcechingesn Linear Probing kartrwckalngsxng Quadatic Probing aelakaraehchsxngchn Double Hashing kartrwcechingesn kartrwcechingesncathaihkraoddipcakcudedimepnrayakhngthi karkraoddechnnicathaihekidkhxmulxyu tidknepnklumkhnadihyaetmicanwnklumnxy thaihphlthiekhamathamikarchnknbriewnni catxngesiyewlakraoddipephuxphncakchwngni aelathaihklumniihykhuniperuxyxik eraeriykkarekaaklumepncanwnklumnxyaetklumkhnadihy enuxngcakkartrwcechingesnwa karekaaklumpthmphumi Primary Clustering kartrwckalngsxng kartrwckalngsxngmkkhanwnwacathaihkraoddipcakcudedimepnrayahnung sungepnfngkchn mkepnfngkchnykkalngsxng karkraoddechnnicathaihekidkhxmulxyu tidknepnklumkhnadelkaetmicanwnklumhlayklum ephraakarkraoddcaepnkarkraoddkhamipimtidkn aetthungxyangirktamthaaehchchnkn kcaipecxklumelkklumedimxyudi aelacaimecxchxngwangbangchxngwangid eraeriykkarekaaklumkhnadelkepncanwnmak enuxngcakkartrwckalngsxngwa karekaaklumthutiyphumi Secondary Clustering karaehchsxngchn karaehchsxngchncaichfngkchnkarkraoddepnfngkchnaehchxikfngkchnhnung mkexafngkchnaehchfngkchnedimmachwykhid cungthaihkarkraoddkracaykhxnkhangsmaesmxaelaimekaaklumkn khwamhnaaennkhxngkhxmul aelakar Rehash thungaemwakarxnuyatihchnknthaiherasamarthichtarangkhnadelkid aetkarihekidkarchnkncnraykaryawekiniphruxhnaaennekinip cathaihkarekhathungkhxmultxngesiyewlakhnhainraykarmakkwa cungthaihphidcudprasngkhkhwamepntarangaehchthitxngkarekhathungkhxmulxyangrwderwid eracungniyamkhasdswnbrrcu load factor l displaystyle lambda ihmikhaethakbcanwnkhxmul N hardwykhnadkhxngtarang tablesize l Ntablesize displaystyle lambda frac N tablesize sunginwithi SeparateChaining casamarthpramanidwaepnkhwamyawechliykhxngraykarinaetlachxng sahrbwithi OpenAddressing nntxngmikhasdswnbrrcunxykwahnungxyuesmx inthangptibtisahrb OpenAddressing eramkihkhasdswnbrrcuihnxykwa 0 5 ephuxknkarchnknmak txngkarxangxing emuxmikhxmulmakkhunaetcanwntarangethaedim khasdswnbrrcukcamakkhuneruxy withikaraekkhuxcasrangtarangaehchthiihykwaedimaelayaykhxmulthnghmdipaehchihm eramkeriykkhntxnniwa riaehch rehash duephimfngkchnaehch okhrngsrangkhxmul