សួស្តី ហាប! ខ្ញុំសូមបង្ហាញជូនអ្នកនូវការបកប្រែអត្ថបទ
"តើមូលដ្ឋានទិន្នន័យទំនាក់ទំនងដំណើរការយ៉ាងដូចម្តេច".

នៅពេលនិយាយអំពីមូលដ្ឋានទិន្នន័យទំនាក់ទំនង ខ្ញុំមិនអាចជួយអ្វីបានឡើយ ប៉ុន្តែគិតថាមានអ្វីមួយបាត់។ ពួកវាត្រូវបានប្រើនៅគ្រប់ទីកន្លែង។ មានមូលដ្ឋានទិន្នន័យផ្សេងៗគ្នាជាច្រើនដែលមានចាប់ពី SQLite តូច និងមានប្រយោជន៍ដល់ Teradata ដែលមានអនុភាព។ ប៉ុន្តែមានតែអត្ថបទមួយចំនួនប៉ុណ្ណោះដែលពន្យល់ពីរបៀបដែលមូលដ្ឋានទិន្នន័យដំណើរការ។ អ្នកអាចស្វែងរកដោយខ្លួនឯងដោយប្រើ "howdoesarelationaldatabasework" ដើម្បីមើលថាតើមានលទ្ធផលប៉ុន្មាន។ លើសពីនេះទៅទៀត អត្ថបទទាំងនេះគឺខ្លី។ ប្រសិនបើអ្នកកំពុងស្វែងរកបច្ចេកវិទ្យាដែលគួរឱ្យភ្ញាក់ផ្អើលចុងក្រោយបំផុត (BigData, NoSQL ឬ JavaScript) អ្នកនឹងឃើញអត្ថបទស៊ីជម្រៅបន្ថែមទៀតដែលពន្យល់ពីរបៀបដែលពួកវាដំណើរការ។

តើ​មូលដ្ឋាន​ទិន្នន័យ​ទំនាក់ទំនង​ចាស់​ពេក​ហើយ​ធុញ​ពេក​ដែល​ត្រូវ​ពន្យល់​នៅ​ក្រៅ​វគ្គសិក្សា​នៅ​សាកលវិទ្យាល័យ ឯកសារ​ស្រាវជ្រាវ និង​សៀវភៅ​ឬ?

ក្នុងនាមជាអ្នកអភិវឌ្ឍន៍ ខ្ញុំស្អប់ការប្រើអ្វីដែលខ្ញុំមិនយល់។ ហើយប្រសិនបើមូលដ្ឋានទិន្នន័យត្រូវបានប្រើប្រាស់អស់រយៈពេលជាង 40 ឆ្នាំ ត្រូវតែមានហេតុផល។ អស់ជាច្រើនឆ្នាំមកនេះ ខ្ញុំបានចំណាយពេលរាប់រយម៉ោងដើម្បីយល់ច្បាស់នូវប្រអប់ខ្មៅដ៏ចម្លែកទាំងនេះ ដែលខ្ញុំប្រើជារៀងរាល់ថ្ងៃ។ មូលដ្ឋានទិន្នន័យទំនាក់ទំនង គួរឱ្យចាប់អារម្មណ៍ខ្លាំងណាស់ដោយសារតែពួកគេ។ ផ្អែកលើគោលគំនិតមានប្រយោជន៍ និងអាចប្រើឡើងវិញបាន។. ប្រសិនបើអ្នកចាប់អារម្មណ៍ក្នុងការយល់ដឹងអំពីមូលដ្ឋានទិន្នន័យ ប៉ុន្តែមិនដែលមានពេលវេលា ឬទំនោរចង់ស្វែងយល់ពីប្រធានបទដ៏ទូលំទូលាយនេះទេ អ្នកគួរតែរីករាយនឹងអត្ថបទនេះ។

ទោះបីជាចំណងជើងនៃអត្ថបទនេះគឺច្បាស់លាស់ក៏ដោយ គោលបំណងនៃអត្ថបទនេះគឺមិនយល់ពីរបៀបប្រើមូលដ្ឋានទិន្នន័យ. អាស្រ័យហេតុនេះ អ្នកគួរតែដឹងពីរបៀបសរសេរសំណើការតភ្ជាប់សាមញ្ញ និងសំណួរជាមូលដ្ឋាន ឆៅ; បើមិនដូច្នេះទេ អ្នកប្រហែលជាមិនយល់អត្ថបទនេះទេ។ នោះជារឿងតែមួយគត់ដែលអ្នកត្រូវដឹង ខ្ញុំនឹងពន្យល់អ្វីដែលនៅសល់។

ខ្ញុំនឹងចាប់ផ្តើមជាមួយនឹងមូលដ្ឋានគ្រឹះវិទ្យាសាស្ត្រកុំព្យូទ័រមួយចំនួន ដូចជាភាពស្មុគស្មាញពេលវេលានៃក្បួនដោះស្រាយ (BigO)។ ខ្ញុំដឹងថាអ្នកមួយចំនួនស្អប់គំនិតនេះ ប៉ុន្តែបើគ្មានវាទេ អ្នកនឹងមិនអាចយល់ពីភាពស្មុគ្រស្មាញនៅក្នុងមូលដ្ឋានទិន្នន័យបានទេ។ ដោយសារនេះជាប្រធានបទធំ ខ្ញុំនឹងផ្តោតលើ អ្វីដែលខ្ញុំគិតថាសំខាន់: របៀបដែលមូលដ្ឋានទិន្នន័យដំណើរការ SQL មួយ ការសាកសួរ. ខ្ញុំគ្រាន់តែនឹងណែនាំ គោលគំនិតមូលដ្ឋានទិន្នន័យដូច្នេះនៅចុងបញ្ចប់នៃអត្ថបទ អ្នកមានគំនិតអំពីអ្វីដែលកំពុងកើតឡើងនៅក្រោមក្រណាត់។

ដោយសារនេះជាអត្ថបទដ៏វែង និងបច្ចេកទេសដែលពាក់ព័ន្ធនឹងក្បួនដោះស្រាយ និងរចនាសម្ព័ន្ធទិន្នន័យជាច្រើន សូមចំណាយពេលរបស់អ្នកដើម្បីអានវា។ គំនិតខ្លះអាចពិបាកយល់។ អ្នកអាចរំលងពួកវា ហើយនៅតែទទួលបានគំនិតទូទៅ។

ដើម្បីឱ្យកាន់តែមានចំណេះដឹងក្នុងចំណោមអ្នក អត្ថបទនេះចែកចេញជា 3 ផ្នែក៖

• ទិដ្ឋភាពទូទៅនៃសមាសធាតុមូលដ្ឋានទិន្នន័យកម្រិតទាប និងកម្រិតខ្ពស់
• ទិដ្ឋភាពទូទៅនៃដំណើរការបង្កើនប្រសិទ្ធភាពសំណួរ
• ទិដ្ឋភាពទូទៅនៃប្រតិបត្តិការ និងការគ្រប់គ្រងអាងស្តុកទុក

ត្រឡប់ទៅ មូលដ្ឋាន វិញ

ឆ្នាំមុន (នៅក្នុងកាឡាក់ស៊ីឆ្ងាយ ឆ្ងាយ...) អ្នកអភិវឌ្ឍន៍ត្រូវដឹងច្បាស់អំពីចំនួនប្រតិបត្តិការដែលពួកគេកំពុងសរសេរកូដ។ ពួកគេបានដឹងពីក្បួនដោះស្រាយ និងរចនាសម្ព័ន្ធទិន្នន័យរបស់ពួកគេដោយបេះដូង ដោយសារតែពួកគេមិនមានលទ្ធភាពខ្ជះខ្ជាយស៊ីភីយូ និងអង្គចងចាំនៃកុំព្យូទ័រយឺតរបស់ពួកគេ។

នៅក្នុងផ្នែកនេះ ខ្ញុំនឹងរំលឹកអ្នកអំពីគោលគំនិតមួយចំនួននេះ ដោយសារពួកគេមានសារៈសំខាន់ក្នុងការយល់ដឹងអំពីមូលដ្ឋានទិន្នន័យ។ ខ្ញុំ​នឹង​ណែនាំ​គោល​គំនិត​ផង​ដែរ។ សន្ទស្សន៍មូលដ្ឋានទិន្នន័យ.

O(1) ទល់នឹង O(n2)

សព្វថ្ងៃនេះ អ្នកអភិវឌ្ឍន៍ជាច្រើនមិនខ្វល់អំពីភាពស្មុគស្មាញនៃពេលវេលានៃក្បួនដោះស្រាយ... ហើយពួកគេនិយាយត្រូវ!

ប៉ុន្តែនៅពេលដែលអ្នកកំពុងដោះស្រាយជាមួយនឹងទិន្នន័យជាច្រើន (ខ្ញុំមិននិយាយរាប់ពាន់នាក់ទេ) ឬប្រសិនបើអ្នកកំពុងតស៊ូគិតជាមិល្លីវិនាទី វានឹងក្លាយជារឿងសំខាន់ក្នុងការយល់ដឹងអំពីគំនិតនេះ។ ហើយដូចដែលអ្នកអាចស្រមៃបាន មូលដ្ឋានទិន្នន័យត្រូវតែដោះស្រាយជាមួយស្ថានភាពទាំងពីរ! ខ្ញុំនឹងមិនធ្វើឱ្យអ្នកចំណាយពេលលើសពីការចាំបាច់ ដើម្បីសម្រេចបាននូវចំណុចនេះទេ។ វានឹងជួយយើងឱ្យយល់អំពីគំនិតនៃការបង្កើនប្រសិទ្ធភាពផ្អែកលើការចំណាយនៅពេលក្រោយ (ការចំណាយ ដែលមានមូលដ្ឋាននៅ បង្កើនប្រសិទ្ធិភាព។).

គំនិត

ភាពស្មុគស្មាញពេលវេលានៃក្បួនដោះស្រាយ ប្រើដើម្បីមើលថាតើវាត្រូវចំណាយពេលប៉ុន្មានដើម្បីប្រតិបត្តិក្បួនដោះស្រាយសម្រាប់ចំនួនទិន្នន័យដែលបានផ្តល់ឱ្យ. ដើម្បីពិពណ៌នាអំពីភាពស្មុគស្មាញនេះ យើងប្រើសញ្ញាណគណិតវិទ្យា O ធំ។ សញ្ញាណនេះត្រូវបានប្រើជាមួយមុខងារដែលពិពណ៌នាអំពីចំនួនប្រតិបត្តិការដែលក្បួនដោះស្រាយត្រូវការសម្រាប់ចំនួនធាតុបញ្ចូលដែលបានផ្តល់ឱ្យ។

ឧទាហរណ៍ នៅពេលដែលខ្ញុំនិយាយថា "ក្បួនដោះស្រាយនេះមានភាពស្មុគស្មាញ O(some_function())" វាមានន័យថា algorithm ទាមទារប្រតិបត្តិការ some_function(a_certain_amount_of_data) ដើម្បីដំណើរការចំនួនជាក់លាក់នៃទិន្នន័យ។

ដូច្នេះ វាមិនមែនជាចំនួនទិន្នន័យដែលសំខាន់ **បើមិនដូច្នេះទេ ** របៀបដែលចំនួនប្រតិបត្តិការកើនឡើងជាមួយនឹងការបង្កើនបរិមាណទិន្នន័យ. ភាពស្មុគស្មាញនៃពេលវេលាមិនផ្តល់ចំនួនប្រតិបត្តិការជាក់លាក់ទេ ប៉ុន្តែជាវិធីដ៏ល្អក្នុងការប៉ាន់ប្រមាណពេលវេលាប្រតិបត្តិ។

នៅក្នុងក្រាហ្វនេះ អ្នកអាចមើលឃើញចំនួនប្រតិបត្តិការធៀបនឹងចំនួនទិន្នន័យបញ្ចូលសម្រាប់ប្រភេទផ្សេងៗនៃភាពស្មុគស្មាញនៃពេលវេលានៃក្បួនដោះស្រាយ។ ខ្ញុំបានប្រើមាត្រដ្ឋានលោការីត ដើម្បីបង្ហាញពួកគេ។ ម្យ៉ាងវិញទៀត បរិមាណទិន្នន័យកើនឡើងយ៉ាងឆាប់រហ័សពី 1 ទៅ 1 ពាន់លាន។ យើងអាចមើលឃើញថា:

• O(1) ឬភាពស្មុគស្មាញថេរនៅតែថេរ (បើមិនដូច្នេះទេវានឹងមិនត្រូវបានគេហៅថាភាពស្មុគស្មាញថេរទេ) ។
• O(ចូល(n)) នៅតែមានកម្រិតទាប ទោះបីជាមានទិន្នន័យរាប់ពាន់លានក៏ដោយ។.
• ការលំបាកបំផុត - O(n2) ដែលចំនួនប្រតិបត្តិការកើនឡើងយ៉ាងឆាប់រហ័ស.
• ផលវិបាកពីរផ្សេងទៀតកើនឡើងយ៉ាងឆាប់រហ័ស។

ឧទហរណ៍

ជាមួយនឹងចំនួនទិន្នន័យតិចតួច ភាពខុសគ្នារវាង O(1) និង O(n2) គឺមានភាពធ្វេសប្រហែស។ ឧទាហរណ៍ ឧបមាថាអ្នកមានក្បួនដោះស្រាយដែលត្រូវដំណើរការ 2000 ធាតុ។

• ក្បួនដោះស្រាយ O(1) នឹងធ្វើឱ្យអ្នកចំណាយ 1 ប្រតិបត្តិការ
• ក្បួនដោះស្រាយ O(log(n)) នឹងត្រូវចំណាយអស់ 7 ប្រតិបត្តិការ
• ក្បួនដោះស្រាយ O(n) នឹងត្រូវចំណាយអស់ 2 ប្រតិបត្តិការ
• ក្បួនដោះស្រាយ O(n*log(n)) នឹងត្រូវចំណាយអស់ 14 ប្រតិបត្តិការ
• ក្បួនដោះស្រាយ O(n2) នឹងធ្វើឱ្យអ្នកចំណាយប្រតិបត្តិការ 4

ភាពខុសគ្នារវាង O(1) និង O(n2) ហាក់ដូចជាធំ (4 លានប្រតិបត្តិការ) ប៉ុន្តែអ្នកនឹងបាត់បង់អតិបរមា 2 ms, គ្រាន់តែដល់ពេលព្រិចភ្នែករបស់អ្នក។ ជាការពិត ខួរក្បាលទំនើបអាចដំណើរការបាន។ ប្រតិបត្តិការរាប់រយលានក្នុងមួយវិនាទី. នេះជាមូលហេតុដែលការអនុវត្ត និងការបង្កើនប្រសិទ្ធភាពមិនមែនជាបញ្ហានៅក្នុងគម្រោង IT ជាច្រើន។

ដូចដែលខ្ញុំបាននិយាយ វានៅតែមានសារៈសំខាន់ក្នុងការដឹងពីគំនិតនេះនៅពេលធ្វើការជាមួយទិន្នន័យដ៏ធំ។ ប្រសិនបើពេលនេះ algorithm ត្រូវដំណើរការ 1 ធាតុ (ដែលមិនច្រើនសម្រាប់ database):

• ក្បួនដោះស្រាយ O(1) នឹងធ្វើឱ្យអ្នកចំណាយ 1 ប្រតិបត្តិការ
• ក្បួនដោះស្រាយ O(log(n)) នឹងត្រូវចំណាយអស់ 14 ប្រតិបត្តិការ
• ក្បួនដោះស្រាយ O(n) នឹងត្រូវចំណាយអស់ 1 ប្រតិបត្តិការ
• ក្បួនដោះស្រាយ O(n*log(n)) នឹងត្រូវចំណាយអស់ 14 ប្រតិបត្តិការ
• ក្បួនដោះស្រាយ O(n2) នឹងធ្វើឱ្យអ្នកចំណាយប្រតិបត្តិការ 1

ខ្ញុំ​មិន​បាន​ធ្វើ​គណិតវិទ្យា​ទេ ប៉ុន្តែ​ខ្ញុំ​ចង់​និយាយ​ថា​ជាមួយ​នឹង​ក្បួន​ដោះស្រាយ O(n2) អ្នក​មាន​ពេល​ផឹក​កាហ្វេ (សូម្បី​តែ​ពីរ!) ប្រសិនបើអ្នកបន្ថែម 0 ផ្សេងទៀតទៅក្នុងបរិមាណទិន្នន័យ នោះអ្នកនឹងមានពេលសម្រាក។

ចូរ​យើង​ចូល​កាន់តែ​ជ្រៅ

សម្រាប់សេចក្ដីយោង:

• ការរកមើលតារាង hash ដ៏ល្អ រកឃើញធាតុនៅក្នុង O(1)។
• ការស្វែងរកដើមឈើដែលមានតុល្យភាពល្អ ផ្តល់លទ្ធផលជា O(log(n))។
• ការស្វែងរកអារេបង្កើតលទ្ធផលជា O(n)។
• ក្បួនដោះស្រាយតម្រៀបល្អបំផុតមានភាពស្មុគស្មាញ O(n*log(n))។
• ក្បួនដោះស្រាយការតម្រៀបមិនល្អមានភាពស្មុគស្មាញ O(n2)។

ចំណាំ៖ នៅក្នុងផ្នែកខាងក្រោមយើងនឹងឃើញក្បួនដោះស្រាយ និងរចនាសម្ព័ន្ធទិន្នន័យទាំងនេះ។

មានប្រភេទជាច្រើននៃភាពស្មុគស្មាញនៃពេលវេលាក្បួនដោះស្រាយ៖

• សេណារីយ៉ូករណីមធ្យម
• សេណារីយ៉ូករណីល្អបំផុត
• និងសេណារីយ៉ូករណីអាក្រក់បំផុត។

ភាពស្មុគស្មាញនៃពេលវេលាច្រើនតែជាសេណារីយ៉ូដ៏អាក្រក់បំផុត។

ខ្ញុំគ្រាន់តែនិយាយអំពីភាពស្មុគស្មាញនៃពេលវេលានៃក្បួនដោះស្រាយប៉ុណ្ណោះ ប៉ុន្តែភាពស្មុគស្មាញក៏អនុវត្តចំពោះ៖

• ការប្រើប្រាស់អង្គចងចាំនៃក្បួនដោះស្រាយ
• ក្បួនដោះស្រាយការប្រើប្រាស់ថាស I/O

ជាការពិតណាស់មានផលវិបាកអាក្រក់ជាង n2 ឧទាហរណ៍៖

• n4: សាហាវណាស់! ក្បួនដោះស្រាយមួយចំនួនដែលបានរៀបរាប់មានភាពស្មុគស្មាញនេះ។
• 3n: កាន់តែអាក្រក់! ក្បួនដោះស្រាយមួយក្នុងចំណោមក្បួនដោះស្រាយដែលយើងនឹងឃើញនៅពាក់កណ្តាលនៃអត្ថបទនេះមានភាពស្មុគស្មាញនេះ (ហើយវាពិតជាត្រូវបានគេប្រើនៅក្នុងមូលដ្ឋានទិន្នន័យជាច្រើន)។
• factorial n៖ អ្នកនឹងមិនទទួលបានលទ្ធផលរបស់អ្នកទេ ទោះបីមានទិន្នន័យតិចតួចក៏ដោយ។
• nn: ប្រសិនបើអ្នកជួបប្រទះភាពស្មុគស្មាញនេះ អ្នកគួរតែសួរខ្លួនឯងថាតើនេះពិតជាសកម្មភាពរបស់អ្នកមែនទេ...

ចំណាំ៖ ខ្ញុំមិនបានផ្តល់និយមន័យពិតប្រាកដនៃការរចនា O ធំទេ គ្រាន់តែជាគំនិតមួយ។ អ្នកអាចអានអត្ថបទនេះនៅ Wikipedia សម្រាប់និយមន័យពិតប្រាកដ (asymptotic) ។

MergeSort

តើអ្នកធ្វើអ្វីនៅពេលដែលអ្នកត្រូវការតម្រៀបបណ្តុំ? អ្វី? អ្នកហៅមុខងារ sort()... យល់ព្រម ចម្លើយល្អ... ប៉ុន្តែសម្រាប់ database អ្នកត្រូវតែយល់ពីរបៀបដែលមុខងារ sort() នេះដំណើរការ។

មាន​ក្បួន​តម្រៀប​ល្អ​មួយ​ចំនួន ដូច្នេះ​ខ្ញុំ​នឹង​ផ្តោត​លើ​ចំណុច​សំខាន់​បំផុត៖ តម្រៀបបញ្ចូលគ្នា. អ្នកប្រហែលជាមិនយល់ទេថាហេតុអ្វីបានជាការតម្រៀបទិន្នន័យមានប្រយោជន៍នៅពេលនេះ ប៉ុន្តែអ្នកគួរតែបន្ទាប់ពីផ្នែកបង្កើនប្រសិទ្ធភាពសំណួរ។ ជាងនេះទៅទៀត ការយល់ដឹងអំពីប្រភេទការរួមបញ្ចូលគ្នានឹងជួយយើងឱ្យយល់នៅពេលក្រោយ នូវប្រតិបត្តិការចូលរួមមូលដ្ឋានទិន្នន័យទូទៅដែលហៅថា បញ្ចូល ចូលរួម (សមាគមរួមបញ្ចូលគ្នា).

បញ្ចូលគ្នា

ដូច​ជា​ក្បួន​ដោះស្រាយ​ដែល​មាន​ប្រយោជន៍​ជា​ច្រើន ការ​តម្រៀប​បញ្ចូល​គ្នា​គឺ​ពឹង​ផ្អែក​លើ​ល្បិច​មួយ៖ ការ​រួម​បញ្ចូល​អារេ​តម្រៀប 2 ទំហំ N/2 ទៅ​ក្នុង​អារេ​ដែល​បាន​តម្រៀប​ធាតុ N ចំណាយ​តែ​ប្រតិបត្តិការ N ប៉ុណ្ណោះ។ ប្រតិបត្តិការនេះត្រូវបានគេហៅថាការរួមបញ្ចូលគ្នា។

តោះ​មើល​អត្ថន័យ​នេះ​ជាមួយ​ឧទាហរណ៍​ដ៏​សាមញ្ញ៖

តួរលេខនេះបង្ហាញថា ដើម្បីកសាងអារេធាតុ 8 ដែលតម្រៀបចុងក្រោយ អ្នកត្រូវធ្វើម្តងទៀតម្តងលើអារេធាតុ 2 4 ប៉ុណ្ណោះ។ ដោយសារអារេធាតុទាំង 4 ត្រូវបានតម្រៀបរួចហើយ៖

• 1) អ្នកប្រៀបធៀបធាតុបច្ចុប្បន្នទាំងពីរនៅក្នុងអារេពីរ (នៅដើមបច្ចុប្បន្ន = ដំបូង)
• 2) បន្ទាប់មកយកមួយតូចបំផុតដាក់វាចូលទៅក្នុងអារេធាតុ 8
• 3) ហើយផ្លាស់ទីទៅធាតុបន្ទាប់នៅក្នុងអារេដែលអ្នកបានយកធាតុតូចបំផុត។
• ហើយធ្វើម្តងទៀត 1,2,3 រហូតដល់អ្នកឈានដល់ធាតុចុងក្រោយនៃអារេមួយ។
• បន្ទាប់​មក​អ្នក​យក​ធាតុ​ដែល​នៅ​សល់​នៃ​អារេ​ផ្សេង​ទៀត​ទៅ​ដាក់​ក្នុង​អារេ​ធាតុ 8 ។

វាដំណើរការដោយសារតែអារេ 4 ធាតុទាំងពីរត្រូវបានតម្រៀប ហើយដូច្នេះអ្នកមិនចាំបាច់ "ត្រឡប់ទៅ" នៅក្នុងអារេទាំងនោះទេ។

ឥឡូវ​យើង​យល់​ពី​ល្បិច​នេះ​ហើយ នេះ​គឺ​ជា​កូដ​ក្លែង​ក្លាយ​របស់​ខ្ញុំ​សម្រាប់​បញ្ចូល​គ្នា៖

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

ការតម្រៀបបញ្ចូលគ្នាបំបែកបញ្ហាទៅជាបញ្ហាតូច ហើយបន្ទាប់មកស្វែងរកលទ្ធផលនៃបញ្ហាតូចជាង ដើម្បីទទួលបានលទ្ធផលនៃបញ្ហាដើម (ចំណាំ៖ ក្បួនដោះស្រាយប្រភេទនេះត្រូវបានគេហៅថា ការបែងចែក និងសញ្ជ័យ)។ ប្រសិនបើអ្នកមិនយល់ពីក្បួនដោះស្រាយនេះទេ កុំបារម្ភ។ ខ្ញុំ​មិន​យល់​វា​ជា​លើក​ដំបូង​ដែល​ខ្ញុំ​បាន​ឃើញ​វា​។ ប្រសិនបើវាអាចជួយអ្នកបាន ខ្ញុំឃើញក្បួនដោះស្រាយនេះជាក្បួនដោះស្រាយពីរដំណាក់កាល៖

• ដំណាក់កាលបែងចែក ដែលអារេត្រូវបានបែងចែកទៅជាអារេតូចជាង
• ដំណាក់កាលតម្រៀបគឺជាកន្លែងដែលអារេតូចត្រូវបានបញ្ចូលគ្នា (ដោយប្រើការរួបរួម) ដើម្បីបង្កើតអារេធំជាង។

ដំណាក់កាលបែងចែក

នៅ​ក្នុង​ដំណាក់​កាល​បែង​ចែក​អារេ​ត្រូវ​បាន​បែង​ចែក​ជា​អារេឯកតា​ជា​ 3 ជំហាន។ ចំនួនជំហានផ្លូវការគឺ log(N) (ចាប់តាំងពី N=8, log(N)=3)។

តើខ្ញុំដឹងរឿងនេះដោយរបៀបណា?

ខ្ញុំពូកែមែន! នៅក្នុងពាក្យមួយ - គណិតវិទ្យា។ គំនិតគឺថាជំហាននីមួយៗបែងចែកទំហំនៃអារេដើមដោយ 2 ។ ចំនួនជំហានគឺជាចំនួនដងដែលអ្នកអាចបែងចែកអារេដើមជាពីរ។ នេះគឺជានិយមន័យពិតប្រាកដនៃលោការីត (គោល ២)។

ដំណាក់កាលតម្រៀប

នៅក្នុងដំណាក់កាលតម្រៀប អ្នកចាប់ផ្តើមជាមួយអារេឯកតា (ធាតុតែមួយ)។ ក្នុងអំឡុងពេលជំហាននីមួយៗ អ្នកអនុវត្តប្រតិបត្តិការបញ្ចូលគ្នាច្រើន ហើយការចំណាយសរុបគឺ N = 8 ប្រតិបត្តិការ៖

• នៅដំណាក់កាលដំបូង អ្នកមានការរួមបញ្ចូលគ្នាចំនួន 4 ដែលមានតម្លៃ 2 ប្រតិបត្តិការនីមួយៗ
• នៅក្នុងជំហានទីពីរ អ្នកមាន 2 បញ្ចូលគ្នា ដែលចំណាយអស់ 4 ប្រតិបត្តិការនីមួយៗ
• នៅ​ជំហាន​ទី​បី អ្នក​មាន​ការ​បញ្ចូល​គ្នា 1 ដែល​ត្រូវ​ចំណាយ​ប្រតិបត្តិការ 8

ដោយសារមានជំហាន log(N) ការចំណាយសរុប N * log(N) ប្រតិបត្តិការ.

គុណសម្បត្តិនៃការរួមបញ្ចូលគ្នា

ហេតុអ្វី​បាន​ជា​ក្បួន​ដោះស្រាយ​នេះ​មាន​ឥទ្ធិពល​ខ្លាំង​ម្ល៉េះ?

ដោយសារតែ៖

• អ្នកអាចផ្លាស់ប្តូរវាដើម្បីកាត់បន្ថយទំហំអង្គចងចាំ ដូច្នេះអ្នកមិនបង្កើតអារេថ្មី ប៉ុន្តែកែប្រែអារេបញ្ចូលដោយផ្ទាល់។

ចំណាំ៖ ប្រភេទនៃក្បួនដោះស្រាយនេះត្រូវបានគេហៅថា in-កន្លែង (តម្រៀបដោយគ្មានអង្គចងចាំបន្ថែម) ។

• អ្នកអាចផ្លាស់ប្តូរវាដើម្បីប្រើទំហំថាស និងទំហំអង្គចងចាំតូចមួយក្នុងពេលតែមួយ ដោយមិនចាំបាច់មានបន្ទុក I/O លើថាសសំខាន់ៗទេ។ គំនិតនេះគឺដើម្បីផ្ទុកទៅក្នុងអង្គចងចាំតែផ្នែកទាំងនោះដែលបច្ចុប្បន្នកំពុងដំណើរការ។ នេះមានសារៈសំខាន់នៅពេលដែលអ្នកត្រូវការតម្រៀបតារាងពហុជីហ្គាបៃដែលមានអង្គចងចាំតែ 100 មេហ្គាបៃប៉ុណ្ណោះ។

ចំណាំ៖ ប្រភេទនៃក្បួនដោះស្រាយនេះត្រូវបានគេហៅថា តម្រៀបខាងក្រៅ.

• អ្នកអាចផ្លាស់ប្តូរវាដើម្បីដំណើរការលើដំណើរការ/ខ្សែស្រឡាយ/ម៉ាស៊ីនមេច្រើន។

ឧទាហរណ៍ ការតម្រៀបបញ្ចូលគ្នាដែលបានចែកចាយគឺជាសមាសធាតុសំខាន់មួយ។ Hadoop (ដែលជារចនាសម្ព័ន្ធនៅក្នុងទិន្នន័យធំ) ។

• ក្បួនដោះស្រាយនេះអាចប្រែក្លាយជាមាស (ពិតជា!)។

ក្បួនដោះស្រាយការតម្រៀបនេះត្រូវបានប្រើនៅក្នុងមូលដ្ឋានទិន្នន័យភាគច្រើន (ប្រសិនបើមិនទាំងអស់) ប៉ុន្តែវាមិនមែនតែមួយទេ។ បើ​ចង់​ដឹង​បន្ថែម​អាច​អាន​អត្ថបទ​នេះ​បាន។ ការងារស្រាវជ្រាវដែលពិភាក្សាអំពីគុណសម្បត្តិ និងគុណវិបត្តិនៃក្បួនដោះស្រាយការតម្រៀបមូលដ្ឋានទិន្នន័យទូទៅ។

អារេ មែកធាង និងតារាង Hash

ឥឡូវនេះយើងយល់ពីគំនិតនៃភាពស្មុគស្មាញនៃពេលវេលានិងការតម្រៀបខ្ញុំគួរតែប្រាប់អ្នកអំពីរចនាសម្ព័ន្ធទិន្នន័យចំនួន 3 ។ នេះសំខាន់ព្រោះពួកគេ។ គឺជាមូលដ្ឋានទិន្នន័យទំនើប. ខ្ញុំ​នឹង​ណែនាំ​គោល​គំនិត​ផង​ដែរ។ សន្ទស្សន៍មូលដ្ឋានទិន្នន័យ.

អារេ

អារេពីរវិមាត្រគឺជារចនាសម្ព័ន្ធទិន្នន័យសាមញ្ញបំផុត។ តារាងអាចត្រូវបានគេគិតថាជាអារេ។ ឧទាហរណ៍:

អារេ 2 វិមាត្រនេះគឺជាតារាងដែលមានជួរដេក និងជួរឈរ៖

• បន្ទាត់នីមួយៗតំណាងឱ្យអង្គភាពមួយ។
• ជួរ​ឈរ​ផ្ទុក​លក្ខណៈ​សម្បត្តិ​ដែល​ពណ៌នា​អំពី​ធាតុ។
• ជួរនីមួយៗផ្ទុកទិន្នន័យនៃប្រភេទជាក់លាក់មួយ (ចំនួនគត់ ខ្សែអក្សរ កាលបរិច្ឆេទ...)។

វាងាយស្រួលសម្រាប់ការរក្សាទុក និងមើលឃើញទិន្នន័យ ទោះបីជាយ៉ាងណាក៏ដោយ នៅពេលដែលអ្នកត្រូវការស្វែងរកតម្លៃជាក់លាក់ វាមិនសមរម្យទេ។

ឧទាហរណ៍ ប្រសិនបើអ្នកចង់ស្វែងរកបុរសទាំងអស់ដែលធ្វើការនៅចក្រភពអង់គ្លេស អ្នកត្រូវមើលជួរនីមួយៗដើម្បីកំណត់ថាតើជួរនោះជារបស់ចក្រភពអង់គ្លេសឬអត់។ វានឹងធ្វើឱ្យអ្នកចំណាយលើប្រតិបត្តិការ Nដែលជាកន្លែង N - ចំនួនបន្ទាត់ដែលមិនអាក្រក់ ប៉ុន្តែតើអាចមានវិធីលឿនជាងនេះទេ? ឥឡូវនេះវាដល់ពេលហើយសម្រាប់យើងដើម្បីស្គាល់ដើមឈើ។

ចំណាំ៖ មូលដ្ឋានទិន្នន័យទំនើបភាគច្រើនផ្តល់នូវអារេបន្ថែមសម្រាប់ការរក្សាទុកតារាងប្រកបដោយប្រសិទ្ធភាព៖ heap-organizedtables និង index-organizedtables។ ប៉ុន្តែនេះមិនផ្លាស់ប្តូរបញ្ហានៃការស្វែងរកលក្ខខណ្ឌជាក់លាក់មួយយ៉ាងឆាប់រហ័សនៅក្នុងក្រុមនៃជួរឈរនោះទេ។

មែកធាងមូលដ្ឋានទិន្នន័យ និងលិបិក្រម

មែកធាងស្វែងរកប្រព័ន្ធគោលពីរគឺជាមែកធាងគោលពីរដែលមានលក្ខណៈសម្បត្តិពិសេស គន្លឹះនៅថ្នាំងនីមួយៗត្រូវតែជា៖

• ធំជាងគ្រាប់ចុចទាំងអស់ដែលរក្សាទុកក្នុងមែកធាងរងខាងឆ្វេង
• តិចជាងគ្រាប់ចុចទាំងអស់ដែលរក្សាទុកក្នុងមែកធាងរងខាងស្តាំ

សូមមើលអ្វីដែលមានន័យដោយមើលឃើញ

គំនិត

ដើមឈើនេះមានធាតុ N = 15 ។ ឧបមាថាខ្ញុំកំពុងស្វែងរក ២០៨៖

• ខ្ញុំចាប់ផ្តើមពី root ដែលកូនសោគឺ 136។ ចាប់តាំងពី 136<208 ខ្ញុំមើលនៅ subtree ខាងស្តាំនៃ node 136។
• 398> 208 ដូច្នេះខ្ញុំកំពុងមើលមែកធាងខាងឆ្វេងនៃ node 398
• 250> 208 ដូច្នេះខ្ញុំកំពុងមើលមែកធាងខាងឆ្វេងនៃ node 250
• 200<208 ដូច្នេះហើយ ខ្ញុំកំពុងមើលមែកធាងខាងស្តាំនៃ node 200។ ប៉ុន្តែ 200 មិនមាន subtree ត្រឹមត្រូវទេ តម្លៃមិនមានទេ។ (ព្រោះ​បើ​វា​មាន វា​នឹង​ស្ថិត​នៅ​ក្នុង​អនុមែកធាង​ខាង​ស្ដាំ ២០០)។

ឥឡូវនេះឧបមាថាខ្ញុំកំពុងស្វែងរក 40

• ខ្ញុំចាប់ផ្តើមពី root ដែលកូនសោគឺ 136។ ចាប់តាំងពីលេខ 136 > 40 ខ្ញុំមើលនៅផ្នែកខាងឆ្វេងនៃ node 136។
• 80 > 40 ដូច្នេះហើយ ខ្ញុំកំពុងមើលមែកធាងខាងឆ្វេងនៃ node 80
• ៤០=៤០, ថ្នាំងមាន. ខ្ញុំទាញយកលេខសម្គាល់ជួរដេកនៅខាងក្នុងថ្នាំង (មិនមែនក្នុងរូបភាព) ហើយរកមើលក្នុងតារាងសម្រាប់លេខសម្គាល់ជួរដេកដែលបានផ្តល់ឱ្យ។
• ការដឹងពីលេខសម្គាល់ជួរដេកអនុញ្ញាតឱ្យខ្ញុំដឹងច្បាស់ពីកន្លែងដែលទិន្នន័យនៅក្នុងតារាង ដូច្នេះខ្ញុំអាចទាញយកវាបានភ្លាមៗ។

នៅទីបញ្ចប់ ការស្វែងរកទាំងពីរនឹងត្រូវចំណាយលើចំនួនកម្រិតនៅខាងក្នុងដើមឈើ។ ប្រសិនបើអ្នកអានផ្នែកអំពីការតម្រៀបបញ្ចូលគ្នាដោយប្រុងប្រយ័ត្ន អ្នកគួរតែឃើញថាមានកម្រិត log(N)។ វាប្រែចេញ, កំណត់​ហេតុ​តម្លៃ​ស្វែង​រក (N), មិនអាក្រក់​ទេ!

ចូរយើងត្រលប់ទៅបញ្ហារបស់យើង។

ប៉ុន្តែនេះគឺអរូបីណាស់ ដូច្នេះសូមត្រលប់ទៅបញ្ហារបស់យើងវិញ។ ជំនួសឱ្យចំនួនគត់សាមញ្ញ សូមស្រមៃមើលខ្សែអក្សរដែលតំណាងឱ្យប្រទេសរបស់នរណាម្នាក់នៅក្នុងតារាងមុន។ ចូរនិយាយថាអ្នកមានដើមឈើដែលមានវាល "ប្រទេស" (ជួរទី 3) នៃតារាង:

• បើចង់ដឹងថាអ្នកណាធ្វើការនៅចក្រភពអង់គ្លេស
• អ្នកមើលដើមឈើដើម្បីទទួលបានថ្នាំងដែលតំណាងឱ្យចក្រភពអង់គ្លេស
• នៅខាងក្នុង "UKnode" អ្នកនឹងរកឃើញទីតាំងនៃកំណត់ត្រាកម្មករចក្រភពអង់គ្លេស។

ការស្វែងរកនេះនឹងចំណាយប្រតិបត្តិការ log(N) ជំនួសឱ្យប្រតិបត្តិការ N ប្រសិនបើអ្នកប្រើអារេដោយផ្ទាល់។ អ្វីដែលអ្នកទើបតែបង្ហាញគឺ សន្ទស្សន៍មូលដ្ឋានទិន្នន័យ.

អ្នកអាចបង្កើតមែកធាងលិបិក្រមសម្រាប់ក្រុមនៃវាលណាមួយ (ខ្សែអក្សរ លេខ 2 បន្ទាត់ លេខ និងខ្សែអក្សរ កាលបរិច្ឆេទ...) ដរាបណាអ្នកមានមុខងារដើម្បីប្រៀបធៀបគ្រាប់ចុច (ឧទាហរណ៍ក្រុមវាល) ដូច្នេះអ្នកអាចកំណត់ បញ្ជាទិញក្នុងចំណោមសោ (ដែលជាករណីសម្រាប់ប្រភេទមូលដ្ឋានណាមួយនៅក្នុងមូលដ្ឋានទិន្នន័យ)។

B+TreeIndex

ខណៈពេលដែលដើមឈើនេះដំណើរការល្អសម្រាប់ការទទួលបានតម្លៃជាក់លាក់មួយ មានបញ្ហាធំនៅពេលដែលអ្នកត្រូវការ ទទួលបានធាតុជាច្រើនរវាងតម្លៃពីរ. វានឹងត្រូវចំណាយលើ O(N) ពីព្រោះអ្នកនឹងត្រូវមើលថ្នាំងនីមួយៗនៅក្នុងមែកធាង ហើយពិនិត្យមើលថាតើវាស្ថិតនៅចន្លោះតម្លៃទាំងពីរនេះដែរឬទេ (ឧ. ជាមួយនឹងការបញ្ជាឆ្លងកាត់ដើមឈើ)។ ជាងនេះទៅទៀត ប្រតិបត្តិការនេះមិនមែនជាឌីស I/O ដែលងាយស្រួលទេ ព្រោះអ្នកត្រូវអានមែកធាងទាំងមូល។ យើងត្រូវរកវិធីដើម្បីអនុវត្តប្រកបដោយប្រសិទ្ធភាព សំណើរជួរ. ដើម្បីដោះស្រាយបញ្ហានេះ មូលដ្ឋានទិន្នន័យទំនើបប្រើកំណែដែលបានកែប្រែនៃមែកធាងមុនគេហៅថា B+Tree។ នៅក្នុងដើមឈើ B + Tree៖

• មានតែថ្នាំងទាបបំផុត (ស្លឹក) រក្សាទុកព័ត៌មាន (ទីតាំងនៃជួរដេកក្នុងតារាងដែលពាក់ព័ន្ធ)
• ថ្នាំងដែលនៅសល់នៅទីនេះ សម្រាប់​ការ​ធ្វើ​ដំណើរ​ ទៅថ្នាំងត្រឹមត្រូវ។ កំឡុងពេលស្វែងរក.

ដូចដែលអ្នកអាចឃើញមានថ្នាំងច្រើនទៀតនៅទីនេះ (ពីរដង) ។ ជាការពិតណាស់ អ្នកមានថ្នាំងបន្ថែម "ថ្នាំងការសម្រេចចិត្ត" ដែលនឹងជួយអ្នកស្វែងរកថ្នាំងត្រឹមត្រូវ (ដែលរក្សាទុកទីតាំងនៃជួរដេកក្នុងតារាងដែលពាក់ព័ន្ធ)។ ប៉ុន្តែភាពស្មុគស្មាញនៃការស្វែងរកនៅតែ O(log(N)) (មានតែមួយកម្រិតទៀត)។ ភាពខុសគ្នាធំគឺថា ថ្នាំងនៅកម្រិតទាបត្រូវបានភ្ជាប់ជាមួយអ្នកស្នងរបស់ពួកគេ។.

ជាមួយនឹង B+Tree នេះ ប្រសិនបើអ្នកកំពុងស្វែងរកតម្លៃចន្លោះពី 40 និង 100៖

• អ្នកគ្រាន់តែត្រូវការរកមើល 40 (ឬតម្លៃជិតបំផុតបន្ទាប់ពី 40 ប្រសិនបើ 40 មិនមាន) ដូចអ្នកបានធ្វើជាមួយមែកធាងមុនដែរ។
• បន្ទាប់មកប្រមូលអ្នកស្នងមរតកចំនួន 40 នាក់ដោយប្រើតំណភ្ជាប់អ្នកស្នងមរតកផ្ទាល់រហូតដល់អ្នកឈានដល់ 100 ។

ចូរនិយាយថាអ្នករកឃើញអ្នកស្នង M ហើយដើមឈើមានថ្នាំង N ។ ការស្វែងរកថ្នាំងជាក់លាក់មួយមានតម្លៃ log(N) ដូចមែកធាងមុនដែរ។ ប៉ុន្តែនៅពេលដែលអ្នកទទួលបានថ្នាំងនេះ អ្នកនឹងទទួលបានអ្នកស្នងតំណែង M ក្នុងប្រតិបត្តិការ M ដោយយោងទៅលើអ្នកស្នងរបស់ពួកគេ។ ការស្វែងរកនេះចំណាយត្រឹមតែ M+log(N) ប៉ុណ្ណោះ ប្រតិបត្តិការប្រៀបធៀបទៅនឹងប្រតិបត្តិការ N នៅលើមែកធាងមុន។ លើសពីនេះទៅទៀត អ្នកមិនចាំបាច់អានមែកធាងពេញលេញទេ (មានតែថ្នាំង M+log(N)) ដែលមានន័យថាការប្រើប្រាស់ថាសតិច។ ប្រសិនបើ M តូច (ឧទាហរណ៍ 200 ជួរ) និង N ធំ (1 ជួរ) វានឹងមានភាពខុសគ្នាខ្លាំង។

ប៉ុន្តែមានបញ្ហាថ្មីនៅទីនេះ (ម្តងទៀត!) ប្រសិនបើអ្នកបន្ថែម ឬលុបជួរដេកក្នុងមូលដ្ឋានទិន្នន័យ (ហើយដូច្នេះនៅក្នុងសន្ទស្សន៍ B+Tree ដែលពាក់ព័ន្ធ)៖

• អ្នកត្រូវតែរក្សាសណ្តាប់ធ្នាប់រវាងថ្នាំងនៅខាងក្នុង B+Tree បើមិនដូច្នេះទេ អ្នកនឹងមិនអាចស្វែងរកថ្នាំងនៅខាងក្នុងដើមឈើដែលមិនបានតម្រៀបបានទេ។
• អ្នកត្រូវតែរក្សាចំនួនអប្បបរមានៃកម្រិតដែលអាចធ្វើបាននៅក្នុង B+Tree បើមិនដូច្នេះទេភាពស្មុគស្មាញនៃពេលវេលា O(log(N)) ក្លាយជា O(N)។

និយាយម្យ៉ាងទៀត B+Tree ត្រូវតែបញ្ជាដោយខ្លួនឯង និងមានតុល្យភាព។ សំណាងល្អ វាអាចទៅរួចជាមួយនឹងប្រតិបត្តិការលុប និងបញ្ចូលឆ្លាតវៃ។ ប៉ុន្តែនេះមកដោយថ្លៃដើម៖ ការបញ្ចូល និងការលុបក្នុងមែកធាង B+ មានតម្លៃ O(log(N))។ នោះហើយជាមូលហេតុដែលអ្នកមួយចំនួនបានឮ ការប្រើលិបិក្រមច្រើនពេកមិនមែនជាគំនិតល្អទេ។. ពិតជា អ្នកកំពុងពន្យឺតការបញ្ចូល/អាប់ដេត/លុបជួរយ៉ាងលឿនក្នុងតារាងដោយសារតែមូលដ្ឋានទិន្នន័យត្រូវការធ្វើបច្ចុប្បន្នភាពលិបិក្រមតារាងដោយប្រើប្រតិបត្តិការ O(log(N)) ដែលមានតម្លៃថ្លៃសម្រាប់សន្ទស្សន៍នីមួយៗ។ លើសពីនេះ ការបន្ថែមលិបិក្រមមានន័យថា បន្ទុកការងារកាន់តែច្រើន អ្នកគ្រប់គ្រងប្រតិបត្តិការ (នឹងត្រូវបានពិពណ៌នានៅចុងបញ្ចប់នៃអត្ថបទ) ។

សម្រាប់ព័ត៌មានលម្អិត អ្នកអាចមើលអត្ថបទវិគីភីឌានៅលើ B+មែកធាង. ប្រសិនបើអ្នកចង់បានឧទាហរណ៍នៃការអនុវត្ត B+Tree នៅក្នុងមូលដ្ឋានទិន្នន័យ សូមក្រឡេកមើល អត្ថបទនេះ и អត្ថបទនេះ ពីអ្នកអភិវឌ្ឍន៍ MySQL ឈានមុខគេ។ ពួកគេទាំងពីរផ្តោតលើរបៀបដែល InnoDB (ម៉ាស៊ីន MySQL) គ្រប់គ្រងសន្ទស្សន៍។

ចំណាំ៖ អ្នកអានម្នាក់បានប្រាប់ខ្ញុំថា ដោយសារការបង្កើនប្រសិទ្ធភាពកម្រិតទាប មែកធាង B+ គួរតែមានតុល្យភាពទាំងស្រុង។

Hasshable

រចនាសម្ព័ន្ធទិន្នន័យសំខាន់ចុងក្រោយរបស់យើងគឺតារាងសញ្ញា។ វាមានប្រយោជន៍ណាស់នៅពេលអ្នកចង់រកមើលតម្លៃយ៉ាងឆាប់រហ័ស។ ជាងនេះទៅទៀត ការយល់ដឹងអំពីតារាង hash នឹងជួយយើងឱ្យយល់នៅពេលក្រោយនូវប្រតិបត្តិការចូលរួមនៃមូលដ្ឋានទិន្នន័យទូទៅដែលហៅថា hash join ( hash ចូលរួម) រចនាសម្ព័នទិន្នន័យនេះក៏ត្រូវបានប្រើប្រាស់ដោយមូលដ្ឋានទិន្នន័យផងដែរ ដើម្បីរក្សាទុកវត្ថុខាងក្នុងមួយចំនួន (ឧ. តុចាក់សោ ឬ អាងស្តុកទុកយើងនឹងឃើញគោលគំនិតទាំងពីរនេះនៅពេលក្រោយ)។

តារាង hash គឺជារចនាសម្ព័ន្ធទិន្នន័យដែលស្វែងរកធាតុដោយគន្លឹះរបស់វា។ ដើម្បីបង្កើតតារាង hash អ្នកត្រូវកំណត់៖

• សញ្ញាព្រមាន សម្រាប់ធាតុរបស់អ្នក។
• មុខងារ hash សម្រាប់សោ។ សញ្ញាសម្ងាត់ដែលបានគណនាផ្តល់ទីតាំងនៃធាតុ (ហៅថា ផ្នែក ).
• មុខងារសម្រាប់ការប្រៀបធៀបគ្រាប់ចុច. នៅពេលដែលអ្នកបានរកឃើញផ្នែកត្រឹមត្រូវ អ្នកត្រូវតែស្វែងរកធាតុដែលអ្នកកំពុងស្វែងរកនៅក្នុងផ្នែកដោយប្រើការប្រៀបធៀបនេះ។

ឧទាហរណ៍សាមញ្ញ

ចូរ​យើង​យក​ឧទាហរណ៍​ច្បាស់​មួយ៖

តារាង hash នេះមាន 10 ផ្នែក។ ដោយ​សារ​ខ្ញុំ​ខ្ជិល ខ្ញុំ​បាន​គូរ​តែ 5 ផ្នែក​ប៉ុណ្ណោះ ប៉ុន្តែ​ខ្ញុំ​ដឹង​ថា​អ្នក​ឆ្លាត ដូច្នេះ​ខ្ញុំ​នឹង​ឱ្យ​អ្នក​គូរ​រូប 5 ផ្សេង​ទៀត​ដោយ​ខ្លួន​ឯង។ ខ្ញុំបានប្រើមុខងារ hash module 10 នៃ key។ ម្យ៉ាងវិញទៀត ខ្ញុំរក្សាទុកតែខ្ទង់ចុងក្រោយនៃគន្លឹះរបស់ធាតុ ដើម្បីស្វែងរកផ្នែករបស់វា៖

• ប្រសិនបើខ្ទង់ចុងក្រោយគឺ 0 នោះធាតុធ្លាក់ចូលទៅក្នុងផ្នែក 0,
• ប្រសិនបើខ្ទង់ចុងក្រោយគឺ 1 នោះធាតុធ្លាក់ចូលទៅក្នុងផ្នែក 1,
• ប្រសិនបើខ្ទង់ចុងក្រោយគឺ 2 ធាតុធ្លាក់ចូលទៅក្នុងតំបន់ 2,
• ...

អនុគមន៍ប្រៀបធៀបដែលខ្ញុំបានប្រើគឺគ្រាន់តែសមភាពរវាងចំនួនគត់ពីរ។

ចូរនិយាយថាអ្នកចង់ទទួលបានធាតុ 78:

• តារាង hash គណនាកូដ hash សម្រាប់ 78 ដែលជា 8 ។
• តារាង hash មើលទៅផ្នែកទី 8 ហើយធាតុដំបូងដែលវារកឃើញគឺ 78 ។
• នាងប្រគល់ធាតុ 78 មកអ្នកវិញ។
• ការស្វែងរកចំណាយត្រឹមតែ 2 ប្រតិបត្តិការប៉ុណ្ណោះ។ (មួយដើម្បីគណនាតម្លៃ hash និងមួយទៀតដើម្បីរកមើលធាតុនៅក្នុងផ្នែក)។

ឥឡូវឧបមាថាអ្នកចង់ទទួលបានធាតុ ៥៩៖

• តារាង hash គណនាកូដ hash សម្រាប់ 59 ដែលជា 9 ។
• តារាង hash ស្វែងរកក្នុងផ្នែកទី 9 ធាតុដំបូងដែលបានរកឃើញគឺ 99។ ចាប់តាំងពី 99!=59 ធាតុ 99 មិនមែនជាធាតុត្រឹមត្រូវទេ។
• ដោយប្រើតក្កវិជ្ជាដូចគ្នា ធាតុទីពីរ (9), ទីបី (79), ..., ចុងក្រោយ (29) ត្រូវបានយក។
• រកមិនឃើញធាតុ។
• ការស្វែងរកចំណាយប្រតិបត្តិការចំនួន 7.

មុខងារ hash ល្អ។

ដូចដែលអ្នកអាចឃើញអាស្រ័យលើតម្លៃដែលអ្នកកំពុងស្វែងរកតម្លៃមិនដូចគ្នាទេ!

ប្រសិនបើឥឡូវនេះខ្ញុំផ្លាស់ប្តូរមុខងារ hash module 1 នៃ key (នោះគឺយក 000 ខ្ទង់ចុងក្រោយ) ការរកមើលទីពីរចំណាយត្រឹមតែ 000 ប្រតិបត្តិការប៉ុណ្ណោះ ព្រោះមិនមានធាតុនៅក្នុងផ្នែក 6។ បញ្ហាប្រឈមពិតប្រាកដគឺការស្វែងរកមុខងារ hash ដ៏ល្អដែលនឹងបង្កើតធុងដែលមានធាតុមួយចំនួនតូចបំផុត។.

ក្នុងឧទាហរណ៍របស់ខ្ញុំ ការស្វែងរកមុខងារ hash ល្អគឺងាយស្រួល។ ប៉ុន្តែនេះគឺជាឧទាហរណ៍ដ៏សាមញ្ញមួយ ការស្វែងរកមុខងារ hash ដ៏ល្អគឺពិបាកជាងនៅពេលដែលគន្លឹះគឺ៖

• ខ្សែអក្សរ (ឧទាហរណ៍ - នាមត្រកូល)
• 2 បន្ទាត់ (ឧទាហរណ៍ - នាមត្រកូល និងនាមខ្លួន)
• 2 បន្ទាត់ និងកាលបរិច្ឆេទ (ឧទាហរណ៍ - នាមត្រកូល នាមខ្លួន និងថ្ងៃខែឆ្នាំកំណើត)
• ...

ជាមួយនឹងមុខងារ hash ដ៏ល្អ ការរកមើលតារាង hash មានតម្លៃ O(1).

អារេទល់នឹងតារាងសញ្ញា

ហេតុអ្វីមិនប្រើអារេ?

ហ៊ឺ សំណួរល្អណាស់។

• តារាង hash អាចជា ផ្ទុកដោយផ្នែកទៅក្នុងអង្គចងចាំហើយផ្នែកដែលនៅសល់អាចនៅតែមាននៅលើថាស។
• ជាមួយនឹងអារេមួយ អ្នកត្រូវតែប្រើចន្លោះជាប់គ្នានៅក្នុងអង្គចងចាំ។ ប្រសិនបើអ្នកកំពុងផ្ទុកតុធំ វាពិបាកណាស់ក្នុងការស្វែងរកកន្លែងបន្តគ្រប់គ្រាន់.
• សម្រាប់តារាង hash អ្នកអាចជ្រើសរើសគន្លឹះដែលអ្នកចង់បាន (ឧទាហរណ៍ ប្រទេស និងនាមត្រកូលរបស់មនុស្ស)។

សម្រាប់ព័ត៌មានបន្ថែម អ្នកអាចអានអត្ថបទអំពី កោះជ្វាហាស់ម៉ាប់ដែលជាការអនុវត្តប្រកបដោយប្រសិទ្ធភាពនៃតារាង hash; អ្នកមិនចាំបាច់យល់ Java ដើម្បីយល់ពីគោលគំនិតដែលមាននៅក្នុងអត្ថបទនេះទេ។

ប្រភព: www.habr.com