ឧបករណ៍បង្ហាញ Hash Table

Hash table ស្វែងរក key មួយក្នុងរយៈពេលប្រហែលមួយជំហានប៉ុណ្ណោះ ដោយការគណនាកន្លែងដែលវាត្រូវរក្សាទុក។ ឧបករណ៍នេះបង្ហាញគ្រប់ជំហានទាំងអស់៖ អនុគមន៍ hash ត្រូវបានគណនាជាមួយ key របស់អ្នក (key mod m សម្រាប់លេខ និង polynomial hash សម្រាប់ពាក្យ), key ត្រូវបញ្ជូនទៅ bucket នោះ ហើយនៅពេល keys ពីរធ្លាក់លើ bucket តែមួយ អ្នកនឹងឃើញពីរបៀបដោះស្រាយ collision។

ប្ដូររវាង separate chaining (ដែល bucket នីមួយៗផ្ទុក linked list នៃ keys) និង linear probing (ដែល key ប៉ះទង្គិចត្រូវផ្លាស់ទីទៅប្រអប់ទំនេរបន្ទាប់)។ សាកល្បងលុប key ក្នុង linear probing ដើម្បីមើលមូលហេតុដែលវាបន្សល់ទុកសញ្ញាសម្គាល់ “deleted” (ហៅថា tombstone) ជំនួសឱ្យប្រអប់ទទេ។ Load factor បង្ហាញពីកម្រិតពេញនៃតារាង។

របៀបប្រើឧបករណ៍ ឧបករណ៍បង្ហាញ Hash Table

1. ជ្រើសរើស Separate chaining ឬ Linear probing និងទំហំតារាង m។
2. វាយបញ្ចូល key (លេខ ឬពាក្យ) រួចចុច Insert, Search ឬ Delete។
3. មើលការគណនា hash នៅខាងលើ រួចតាមដានប្រអប់ដែលបានបន្លិច និងដំណើរការ probe ឬដើរតាម chain។
4. បញ្ចូល key ដែលបង្ក collision (មានការផ្ដល់យោបល់) ហើយប្រៀបធៀបពីរបៀបដែលវិធីទាំងពីរដោះស្រាយវា។

ហេតុអ្វីប្រើ ឧបករណ៍បង្ហាញ Hash Table របស់ ToolOrca

• ការបង្ហាញការគណនា hash function សម្រាប់គ្រប់ key
• ម៉ូដ Separate chaining និង Linear probing
• ចលនាបង្ហាញការដោះស្រាយ collision មួយជំហានម្តងៗ
• សញ្ញា Tombstone សម្រាប់ការលុបក្នុង open addressing
• បង្ហាញ Load factor និងចំនួនលើកធ្វើ probe
• គាំទ្រ key ជាលេខ និងជា string
• កូដជាភាសា C++, Java, Python និង JavaScript

របៀបដែល hash table ដំណើរការ

Hash table គឺជា array ដែលមាន m buckets បូករួមជាមួយ hash function ដែលបំលែង key ឱ្យទៅជាលេខ bucket។ សម្រាប់ចំនួនគត់ រូបមន្តសាមញ្ញគឺ h(k) = k mod m ហើយសម្រាប់ string គឺ h = (h × 31 + character code) mod m លើគ្រប់តួអក្សរ។ ការជ្រើសរើសទំហំតារាងជាចំនួនបឋម (prime number) ជួយបែងចែក keys ឱ្យរាយស្មើដៃល្អ។ ដើម្បីស្វែងរក key យើងគ្រាន់តែ hash វា រួចមើលតែក្នុង bucket នោះប៉ុណ្ណោះ ដែលធ្វើឱ្យការស្វែងរកជាមធ្យមចំណាយពេលត្រឹមតែ O(1)។

Keys ពីរផ្សេងគ្នាអាចផ្ដល់តម្លៃ hash ធ្លាក់លើ bucket តែមួយ ដែលហៅថា collision (ការប៉ះទង្គិច)។ ជាមួយ bucket ចំនួន m ការប៉ះទង្គិចគឺមិនអាចចៀសផុតបានឡើយនៅពេលអ្នករក្សាទុក keys ច្រើន (តាមទ្រឹស្ដី birthday paradox) ដូច្នេះ hash table ទាំងអស់សុទ្ធតែត្រូវការយុទ្ធសាស្ត្រដោះស្រាយ collision។

Separate Chaining ប្រៀបធៀបនឹង Linear Probing

Separate chaining រក្សាទុក linked list តូចមួយក្នុង bucket នីមួយៗ។ Keys ដែលប៉ះទង្គិចគ្នានឹងត្រូវបន្ថែមទៅចុង list ហើយការស្វែងរកត្រូវដើរតែក្នុង list នោះប៉ុណ្ណោះ។ វាដំណើរការបានល្អទោះបីតារាងផ្ទុក keys ច្រើនជាងចំនួន bucket ក៏ដោយ ហើយការលុបក៏មានលក្ខណៈសាមញ្ញ។ HashMap របស់ Java និង unordered_map របស់ C++ ប្រើប្រាស់ chaining។

Linear probing (ទម្រង់មួយនៃ open addressing) រក្សាទុក key មួយក្នុងមួយប្រអប់។ ប្រសិនបើប្រអប់គោលដៅមានគេយកហើយ វានឹងសាកល្បងប្រអប់បន្ទាប់គឺ (i + 1) mod m រហូតដល់រកឃើញប្រអប់ទំនេរ។ ការស្វែងរកក៏ដើរតាមផ្លូវនេះដូចគ្នា ហើយឈប់នៅពេលជួបប្រអប់ទទេ។ ការលុបត្រូវតែបន្សល់ទុក tombstone បើពុំនោះទេការស្វែងរកលើកក្រោយអាចនឹងឈប់លឿនពេក។ វាដំណើរការលឿនជាមួយ cache របស់ម៉ាស៊ីន ប៉ុន្តែប្រឈមនឹងបញ្ហាកកស្ទះ (clustering) នៅពេលតារាងចាប់ផ្តើមពេញ ហេតុនេះគេត្រូវពង្រីកទំហំតារាងមុនពេលវាពេញ។ dict របស់ Python ប្រើប្រាស់ open addressing។

Load factor និងការប្តូរទំហំ (Resizing)

Load factor គឺស្មើ n / m ដែលជាចំនួន keys ចែកនឹងចំនួន buckets។ នៅពេលដែលវាកើនឡើង chains នឹងកាន់តែវែង ហើយការ probe នឹងកាន់តែយឺត។ Hash table ជាក់ស្ដែងនឹងពង្រីកទំហំ (ជាទូទៅកើនឡើងទ្វេដង និង rehash គ្រប់ key ឡើងវិញ) នៅពេល load factor កើនលើសប្រហែល 0.75 សម្រាប់ chaining ឬ 0.5 ទៅ 0.7 សម្រាប់ probing ដើម្បីរក្សាប្រតិបត្តិការឱ្យនៅត្រឹម O(1) ជាមធ្យម។

គ្រប់ visualizer នៅលើគេហទំព័រនេះដំណើរការផ្ទាល់ក្នុង browser របស់អ្នកជាមួយប៊ូតុងបញ្ជាដូចគ្នា៖ ចាក់ (Play), ផ្អាក (Pause), ទៅមុខមួយជំហាន, ថយក្រោយមួយជំហាន និងរបារលៃល្បឿន។ អ្នកក៏អាចអូសរបារកំណត់ទីតាំងដើម្បីលោតទៅជំហានណាមួយ ឬចុចលើផ្ទាំងគំនូរហើយប្រើប្រាស់ Space bar និងគ្រាប់ចុចព្រួញបានផងដែរ។