Hash Map និង Set

មាតិកា

1. បញ្ហាស្វែងរក
2. គំនិតធំ៖ ប្តូរ Key ទៅជាទីតាំង
3. Hash Function
4. Collision និង Chaining
5. Load Factor និងការ Resize
6. តើប្រតិបត្តិការនីមួយៗចំណាយប៉ុន្មាន
7. Map, Set និង Plain Object ក្នុង JavaScript
8. លំនាំ៖ ការរាប់ Frequency
9. លំនាំ៖ Two Sum និង "តើខ្ញុំបានឃើញវារួចហើយឬនៅ?"
10. បញ្ហាសម្ភាសន៍បន្ថែមទៀត
11. រូបមន្ត៖ module hashmap
12. សាកល្បងដោយខ្លួនឯង

1. បញ្ហាស្វែងរក

នេះគឺជាសំណួរដែលអ្នកឆ្លើយជាប្រចាំ៖ "ដោយមាន key នេះ សូមរកអ្វីដែលទៅជាមួយវា។" User ID និង record របស់អ្នកប្រើ។ កូដផលិតផល និងតម្លៃរបស់វា។ ពាក្យមួយ និងចំនួនដងដែលវាលេចឡើង។ URL មួយ និង response ដែលបាន cache។

ជាមួយ array ការស្វែងរកតាម key មានន័យថាស្កេនពីដើមរហូតដល់ជួបវា៖ O(n)។ ជាមួយ array ដែលបានតម្រៀប អ្នកអាច binary search បានក្នុង O(log n)។ ល្អជាង ប៉ុន្តែអ្នកត្រូវរក្សា array ឲ្យនៅតម្រៀប។ អ្វីដែលយើងចង់បានគឺ structure មួយដែលតម្លៃនៃការស្វែងរក key មួយមិនកើនឡើងតាមចំនួនធាតុទាល់តែសោះ។

structure នោះគឺ hash table ហើយវាប្រហែលជា data structure មានប្រយោជន៍បំផុតក្នុងការសរសេរកម្មវិធីប្រចាំថ្ងៃ។ ក្នុង JavaScript វាស្ថិតនៅពីក្រោយ Map, Set និង object ដែលប្រើជា dictionary។ ក្នុង Python វាគឺ dict និង set ក្នុង Java វាគឺ HashMap ក្នុង Go វាគឺ map។ រៀនម្តង អ្នកនឹងយល់ទាំងអស់។

ក្នុងជំពូកនេះ អ្នកនឹងរៀនពីរបៀបដែលវាដំណើរការ បន្ទាប់មកបង្កើតមួយដោយខ្លួនឯង រួចប្រើវាដើម្បីដោះស្រាយបញ្ហាដែលមើលទៅពិបាក រហូតទាល់តែអ្នកឃើញល្បិច។

2. គំនិតធំ៖ ប្តូរ Key ទៅជាទីតាំង

សូមនឹកឃើញពី Array និង String ថាការអាន arr[i] គឺភ្លាមៗ ព្រោះទីតាំងត្រូវបានគណនាដោយនព្វន្ត។ Hash table ខ្ចីល្បិចនោះ។ វារក្សា array ធម្មតាមួយ (ហៅថា bucket) ហើយប្រើ function ដើម្បីប្តូរ key ណាមួយទៅជា index៖

key "cat"  --hash-->  193488125  --mod 8-->  5   -> go to bucket 5

ការរក្សាទុកគឺ "គណនា index ហើយដាក់តម្លៃក្នុង bucket នោះ"។ ការស្វែងរកគឺ "គណនា index ដូចគ្នា ហើយមើលក្នុង bucket នោះ"។ អ្នកមិនដែលស្កេនទេ។ ការងារតែមួយគត់គឺគណនា index ដែលអាស្រ័យលើប្រវែងនៃ key មិនមែនលើចំនួនធាតុដែលបានរក្សាទុកទេ។

គំនិតតូចពីរធ្វើឲ្យវាដំណើរការ៖

1. Hash function ដែលប្តូរ key (ឧទាហរណ៍ string) ទៅជាចំនួនគត់មិនអវិជ្ជមានធំមួយ។ key ដូចគ្នាត្រូវតែផ្តល់ចំនួនគត់ដូចគ្នាជានិច្ច។
2. Operator modulo ដើម្បីបង្រួមលេខធំនោះទៅជា bucket index ត្រឹមត្រូវ៖ hash % bucketCount។ (បើអ្នកចង់រំលឹកពី % សូមមើល នព្វន្ត Modular។)

3. Hash Function

Hash function ល្អមានលក្ខណៈបីយ៉ាង៖

• Deterministic: key ដូចគ្នាផ្តល់លេខដូចគ្នាជានិច្ច។
• លឿន: វាត្រូវតែថោក ព្រោះវាដំណើរការរាល់ប្រតិបត្តិការ។
• ចែកចាយបានល្អ: key ផ្សេងគ្នាគួរធ្លាក់ទៅកន្លែងផ្សេងគ្នា។ key ដែលស្រដៀងគ្នា ("user1", "user2") ក៏គួរតែខ្ចាត់ខ្ចាយដែរ។

នេះគឺជា string hash បុរាណសាមញ្ញមួយ ហៅថា djb2។ វាចាប់ផ្តើមពីលេខវេទមន្តមួយ ហើយសម្រាប់តួអក្សរនីមួយៗ វាគុណនឹង 33 រួចបូកលេខកូដតួអក្សរ៖

function hashString(key: string): number {
  let hash = 5381;
  for (let i = 0; i < key.length; i++) {
    hash = (hash * 33 + key.charCodeAt(i)) >>> 0;
  }
  return hash;
}

console.log(hashString("a"));   // 177670
console.log(hashString("ab"));  // 5863208
console.log(hashString("cat")); // 193488125
console.log(hashString("tac")); // 193506621

ពិនិត្យលេខទីមួយដោយដៃ៖ 5381 * 33 + 97 (លេខកូដតួអក្សរនៃ a) គឺ 177573 + 97 = 177670។ >>> 0 នៅចុងជំហាននីមួយៗរក្សាលេខជាចំនួនគត់ 32-bit មិនអវិជ្ជមាន ដូច្នេះវាមិនដែលធំឥតកំណត់ ឬក្លាយជាអវិជ្ជមានឡើយ។ (បើ >>> ថ្មីសម្រាប់អ្នក សូមមើល Bitwise Operation និង Flag។)

សូមកត់សម្គាល់ថា "cat" និង "tac" មានអក្សរដូចគ្នា ប៉ុន្តែ hash ខុសគ្នា។ Hash អាស្រ័យលើ លំដាប់ ដែលជាអ្វីដែលយើងចង់បានយ៉ាងពិតប្រាកដ។

ការគណនា hash ដើរកាត់ key ម្តង ដូច្នេះវាចំណាយ O(k) ដែល k ជាប្រវែងនៃ key។ សម្រាប់ key ខ្លី យើងចាត់ទុកថាវាថេរ ដែលជាមូលហេតុដែលយើងនិយាយថាការស្វែងរកគឺ O(1)។ Engine ពិតប្រើ hash function ខ្លាំងជាង និងលឿនជាង djb2 ប៉ុន្តែការងារគឺដូចគ្នា។

ចំណុចជាក់ស្តែងពីរ៖

• Hashing ត្រូវការ key ដែលមិនអាចប្តូរបាន (immutable)។ បើ key អាចផ្លាស់ប្តូរបន្ទាប់ពីអ្នករក្សាទុកវា hash របស់វានឹងប្តូរ ហើយអ្នកនឹងរកវាមិនឃើញម្តងទៀតទេ។ នោះជាមូលហេតុដែល key របស់ Map ជាទូទៅជា string ឬលេខ ហើយហេតុអ្វីការប្រើ object ដែលអាចប្តូរបានជា key ត្រូវការប្រុងប្រយ័ត្ន។
• កុំប្រើ hash សម្រាប់ពាក្យសម្ងាត់ ឬសុវត្ថិភាព ត្រឹមតែដោយសារវាត្រូវបានហៅថា hash។ Table hash ធ្វើឲ្យប្រសើរសម្រាប់ល្បឿន។ Password hashing (bcrypt, argon2) ត្រូវបានរចនាឡើងឲ្យ យឺត ហើយជាប្រធានបទផ្សេង។

4. Collision និង Chaining

បញ្ហា pigeonhole៖ មាន key ដែលអាចមានគ្មានកំណត់ ប៉ុន្តែមាន bucket តែបន្តិចបន្តួច។ ពេលខ្លះ key ពីរផ្សេងគ្នានឹងធ្លាក់ក្នុង bucket ដូចគ្នា។ នេះហៅថា collision ហើយ hash table ទាំងអស់មានផែនការសម្រាប់វា។

តោះមើលមួយ។ ជាមួយ 8 bucket hash របស់យើងដាក់ key ទាំងបួននេះនៅទីនេះ៖

key     hash % 8
"cat"      5
"dog"      7
"bird"     6
"fish"     7      <- collides with "dog"

ផែនការទូទៅបំផុតគឺ chaining៖ bucket នីមួយៗរក្សាបញ្ជីតូចមួយនៃ entry ទាំងអស់ដែលធ្លាក់មកទីនោះ។

bucket 0:  (empty)
bucket 1:  (empty)
bucket 2:  (empty)
bucket 3:  (empty)
bucket 4:  (empty)
bucket 5:  [ cat ]
bucket 6:  [ bird ]
bucket 7:  [ dog ] -> [ fish ]

ដើម្បី ស្វែងរក "fish"៖ hash វា ទៅ bucket 7 ហើយដើរតាម chain ខ្លីដោយប្រៀបធៀប key រហូតដល់មួយស្មើនឹង "fish"។ ដើម្បី បញ្ចូល hash វា ដើរតាម chain ដើម្បីពិនិត្យថាមាន key នោះរួចហើយឬនៅ ហើយបន្ថែមទៅ chain បើវាមិនទាន់មាន។ ដើម្បី លុប រកវាក្នុង chain ហើយដកវាចេញ។

ដរាបណា chain នៅខ្លី (មួយ ឬពីរ entry) ទាំងអស់នេះគឺមានប្រសិទ្ធភាពជាពេលវេលាថេរ។ វិធីរក្សាវាឲ្យខ្លីគឺមាន bucket គ្រប់គ្រាន់ ដែលជាផ្នែកបន្ទាប់។

(គ្រួសារយុទ្ធសាស្ត្រមួយទៀតគឺ open addressing៖ បើ bucket ត្រូវបានយករួច សាកល្បងមួយបន្ទាប់ ហើយមួយបន្ទាប់ទៀត។ Engine ពិតជាច្រើនប្រើវា។ Chaining ងាយយល់ជាង ដូច្នេះយើងបង្កើតវា។)

5. Load Factor និងការ Resize

បើអ្នកដាក់ entry មួយលានក្នុង 8 bucket chain នីមួយៗមានប្រហែល 125,000 entry ហើយ table ធ្លាក់ចុះទៅជាបញ្ជីយឺត។ លេខសំខាន់គឺ load factor៖ entries / buckets។ Load factor ជិត ឬតិចជាង 1 មានន័យថា chain មានជាមធ្យមប្រហែលមួយ entry។

ដូច្នេះ table ឃ្លាំមើល load factor របស់ខ្លួន។ នៅពេលវាហួសដែនកំណត់ (យើងប្រើ 0.75) table resize៖ វាបង្កើត bucket array ថ្មីធំជាងពីរដង ហើយ rehash entry ទាំងអស់ចូលទៅក្នុងវា។ (Rehash ចាំបាច់ ព្រោះ hash % bucketCount ប្តូរនៅពេលចំនួន bucket ប្តូរ។)

Resize គឺ O(n) ប៉ុន្តែវាកើតឡើងកម្រ ហើយ resize នីមួយៗបង្កើនសមត្ថភាពទ្វេដង។ ហេតុផល amortized ដូចគ្នានឹង push របស់ array ត្រូវបានអនុវត្ត៖ ថ្លៃជាមធ្យមលើការបញ្ចូលជាច្រើនគឺនៅតែ O(1)។

មើលវាកើតឡើង។ ជាមួយទំហំចាប់ផ្តើម 8 bucket និងដែនកំណត់ 0.75 ការបញ្ចូល 100 key បង្កឲ្យមាន resize នៅ 7, 13, 25, 49 និង 97 entry ហើយ table បញ្ចប់ជាមួយ 256 bucket និង chain វែងបំផុតគឺ 2។ យើងនឹងឃើញរឿងនេះក្នុងកូដបន្តិចទៀត។

6. តើប្រតិបត្តិការនីមួយៗចំណាយប៉ុន្មាន

ករណីអាក្រក់បំផុតកើតឡើងនៅពេល key ច្រើន collide។ Hash function ល្អ និងការ resize ធ្វើឲ្យរឿងនោះមិនទំនងទាល់តែសោះ ដូច្នេះមនុស្សគ្រាន់តែនិយាយថា hash table គឺ O(1)។ សូមចាំអ្វីដែលអក្សរតូចៗមានន័យ៖ ជាមធ្យម ជាមួយ hash function សមរម្យ។

អ្វីដែល hash table មិន ផ្តល់ឲ្យអ្នក៖

• គ្មានការតម្រៀប។ អ្នកមិនអាចសួររក "key តូចបំផុត" ដោយមិនស្កេនទេ។ (បើអ្នកត្រូវការរឿងនោះ tree ក្នុងជំពូកទី 9 ឬ array ដែលបានតម្រៀបគឺប្រសើរជាង។)
• គ្មាន range query។ "key ទាំងអស់រវាង a និង f" ត្រូវការការស្កេន។
• Memory overhead។ Bucket ចំណាយទំហំច្រើនជាង array ដែលតម្រង់ជិតគ្នា។

7. Map, Set និង Plain Object ក្នុង JavaScript

JavaScript ផ្តល់ឧបករណ៍ស្រដៀង hash-table បីយ៉ាង។ ការដឹងថាត្រូវជ្រើសមួយណាជួយជៀសវាង bug ជាច្រើន។

Map

Map រក្សាទុកគូ key-value។ Key អាចជា ប្រភេទណាក៏បាន ហើយ entry ត្រឡប់មកតាម លំដាប់នៃការបញ្ចូល។

const prices = new Map<string, number>();
prices.set("apple", 1.2);
prices.set("banana", 0.5);

console.log(prices.get("apple"));    // 1.2
console.log(prices.get("grape"));    // undefined
console.log(prices.has("banana"));   // true
console.log(prices.size);            // 2
prices.delete("banana");
console.log([...prices.keys()]);     // [ 'apple' ]

Key រក្សាប្រភេទរបស់វា៖ លេខ 1 និង string "1" គឺជា key ផ្សេងគ្នា។

const m = new Map<number | string, string>();
m.set(1, "num");
m.set("1", "str");
console.log(m.size);   // 2
console.log(m.get(1)); // num

Map ក៏គ្រប់គ្រង NaN ជា key ដែរ (វាចាត់ទុក NaN ស្មើនឹងខ្លួនវាផ្ទាល់) ហើយ object ជា key តាម identity មិនមែនតាមមាតិកាទេ៖

console.log(new Map([[NaN, "nan"]]).get(NaN));        // nan
console.log(new Map([[{ a: 1 }, 1]]).get({ a: 1 })); // undefined (a different object)

Set

Set រក្សាទុក តម្លៃតែមួយគត់ ដោយគ្មានស្ទួន ដោយប្រើគំនិត hash ដូចគ្នា ប៉ុន្តែគ្មានតម្លៃភ្ជាប់៖

const tags = new Set(["js", "ts", "js", "node", "ts"]);
console.log(tags.size);      // 3
console.log(tags.has("ts")); // true
console.log([...tags]);      // [ 'js', 'ts', 'node' ]

កូដមួយបន្ទាត់ដែលប្រើញឹកញាប់ជួយលុបស្ទួនចេញពី array៖ [...new Set(array)]។ វាគឺ O(n)។

Plain object

Object ក៏ដំណើរការជា dictionary បានដែរ ហើយវាល្អសម្រាប់រូបរាងតូច និងថេរ ដូចជា { name: "Dara", age: 30 }។ ក្នុងនាមជា dictionary ទូទៅ វាមានអន្ទាក់ខ្លះ៖

• Key ក្លាយជា string។ obj[1] និង obj["1"] គឺជា slot តែមួយ។
• ឈ្មោះដែលទទួលមរតកលេចចូលមក។ {}["constructor"] មិនមែន undefined ទេ៖ វាគឺជា function Object ដែលមានស្រាប់។ "word counter" ដែលស្វែងរកពាក្យ "constructor" អាចច្រលំដោយសាររឿងនេះ។
• លំដាប់ចម្លែក។ Key ដែលស្រដៀងចំនួនគត់មកមុនតាមលំដាប់កើន បន្ទាប់មក key ផ្សេងទៀតតាមលំដាប់នៃការបញ្ចូល។
• គ្មាន property size ហើយ API សម្រាប់លំដាប់ key និងការ iterate ពិបាកប្រើជាង។

const o: Record<string, string> = {};
o[1] = "num";
o["1"] = "str";
console.log(Object.keys(o).length); // 1
console.log(o[1]);                  // str (it overwrote)

const dict: Record<string, number> = {};
console.log(typeof dict["constructor"]); // function (not undefined!)

console.log(Object.keys({ b: 1, 2: 1, 1: 1, a: 1 })); // [ '1', '2', 'b', 'a' ]

ច្បាប់ទូទៅ៖ សម្រាប់ lookup table ណាមួយ ប្រើ Map។ សម្រាប់ "record ដែលមាន field ស្គាល់" ប្រើ object។ សម្រាប់បណ្តុំតម្លៃតែមួយគត់ ប្រើ Set។

ការពិតមួយទៀតអំពី Map៖ លំដាប់នៃការបញ្ចូលរបស់វាមានស្ថេរភាព ហើយការលុប និងបន្ថែម key ម្តងទៀតផ្លាស់ទីវាទៅចុង។ នោះធ្វើឲ្យ Map មានប្រយោជន៍សម្រាប់ cache សាមញ្ញ (ឧទាហរណ៍ល្បិច "least recently used"៖ លុប key ហើយ set វាម្តងទៀត ដើម្បីសម្គាល់ថាវាត្រូវបានប្រើថ្មីៗនេះ)។

8. លំនាំ៖ ការរាប់ Frequency

លំនាំ hash map ទូទៅបំផុតតែមួយ៖ រាប់ថាតើអ្វីៗនីមួយៗលេចឡើងប៉ុន្មានដង។

function countFrequencies(items: string[]): Map<string, number> {
  const counts = new Map<string, number>();
  for (const item of items) counts.set(item, (counts.get(item) ?? 0) + 1);
  return counts;
}

const words = "the cat and the hat and the bat".split(" ");
const counts = countFrequencies(words);
console.log(counts);
// Map(5) { 'the' => 3, 'cat' => 1, 'and' => 2, 'hat' => 1, 'bat' => 1 }

?? 0 ផ្តល់ចំនួនចាប់ផ្តើមសូន្យ នៅពេលដំបូងដែលយើងឃើញធាតុមួយ។ វាគឺជាការ pass O(n) តែមួយ។ ការរកពាក្យដែលលេចឡើងញឹកញាប់បំផុតគឺ pass មួយទៀតលើ entry របស់ map។

កន្លែងដែលអ្នកជួបវានៅកន្លែងធ្វើការ៖ word cloud និងការធ្វើ index ស្វែងរក analytics "ទំព័រកំពូល" ការរាប់សន្លឹកឆ្នោត ការរកឃើញ request ដដែលៗ (rate limiting) និងការពិនិត្យថាតើឯកសារពីរមានបណ្តុំបន្ទាត់ដូចគ្នាឬអត់។

តួអក្សរតែមួយគត់ដំបូង

រក index នៃតួអក្សរដំបូងដែលលេចឡើងតែម្តង។ រាប់អ្វីៗទាំងអស់ បន្ទាប់មកស្កេនម្តងទៀតតាមលំដាប់ដើម៖

function firstUniqueChar(text: string): number {
  const counts = countFrequencies([...text]);
  for (let i = 0; i < text.length; i++) {
    if (counts.get(text[i]) === 1) return i;
  }
  return -1;
}

console.log(firstUniqueChar("leetcode")); // 0  ("l")
console.log(firstUniqueChar("aabb"));     // -1

តើ string ពីរជា anagram ឬអត់?

ពាក្យពីរជា anagram ប្រសិនបើវាប្រើអក្សរដូចគ្នាក្នុងចំនួនដងដូចគ្នា ("listen" និង "silent")។ រាប់ពាក្យទីមួយ ហើយដកជាមួយពាក្យទីពីរ៖

function isAnagram(a: string, b: string): boolean {
  if (a.length !== b.length) return false;
  const counts = countFrequencies([...a]);
  for (const ch of b) {
    const c = counts.get(ch);
    if (!c) return false; // missing, or already used up
    counts.set(ch, c - 1);
  }
  return true;
}

console.log(isAnagram("listen", "silent")); // true
console.log(isAnagram("rat", "car"));       // false

វាដំណើរការក្នុង O(n)។ វិធីជំនួសគឺតម្រៀប string ទាំងពីរហើយប្រៀបធៀប ដែលចំណាយ O(n log n)។ កំណែរាប់លឿនជាង ទោះបីជាកំណែតម្រៀបខ្លីជាងក្នុងការសរសេរក៏ដោយ។

9. លំនាំ៖ Two Sum និង "តើខ្ញុំបានឃើញវារួចហើយឬនៅ?"

នេះគឺជាសំណួរសម្ភាសន៍ដ៏ល្បីបំផុត។ ដោយមាន array នៃលេខ និងគោលដៅមួយ ត្រឡប់ index នៃលេខពីរដែលបូកបានស្មើគោលដៅ។ មានចម្លើយតែមួយប៉ុណ្ណោះ។ សម្រាប់ [2, 7, 11, 15] និងគោលដៅ 9 ចម្លើយគឺ [0, 1]។

Brute force: សាកល្បងគ្រប់គូ។ loop ពីរជាន់គ្នា O(n^2)។ ល្អសម្រាប់ 100 លេខ ប៉ុន្តែឈឺចាប់សម្រាប់ 100,000។

ការយល់ដឹង: សម្រាប់លេខ x នីមួយៗ ដៃគូដែលយើងត្រូវការគឺ target - x។ ជំនួសឲ្យការស្វែងរក array ដើម្បីរកដៃគូ (ការស្កេន O(n)) សូមសួរ hash map ថា "តើខ្ញុំបានឃើញដៃគូរួចហើយឬនៅ?" ចម្លើយនោះគឺ O(1)។ ចងចាំលេខនីមួយៗ និង index របស់វាតាមដែលអ្នកទៅ៖

function twoSum(nums: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    const j = seen.get(target - nums[i]);
    if (j !== undefined) return [j, i];
    seen.set(nums[i], i);
  }
  return null;
}

console.log(twoSum([2, 7, 11, 15], 9)); // [ 0, 1 ]
console.log(twoSum([3, 2, 4], 6));      // [ 1, 2 ]
console.log(twoSum([3, 3], 6));         // [ 0, 1 ]

តាមដាន [2, 7, 11, 15] ជាមួយគោលដៅ 9។ នៅ 2 (index 0) យើងត្រូវការ 7; map ទទេ ដូច្នេះរក្សាទុក 2 -> 0។ នៅ 7 (index 1) យើងត្រូវការ 2; map មានវានៅ index 0 ដូច្នេះត្រឡប់ [0, 1]។

កត់សម្គាល់លំដាប់ក្នុង loop៖ ស្វែងរកមុន រក្សាទុកក្រោយ។ រឿងនោះការពារមិនឲ្យផ្គូរធាតុមួយជាមួយខ្លួនវាផ្ទាល់ ហើយវាគ្រប់គ្រងករណី [3, 3] បានត្រឹមត្រូវ៖ 3 ទីពីររកឃើញទីមួយ។

ថ្លៃចំណាយគឺ O(n) ពេលវេលា និង O(n) space បន្ថែម។ នេះគឺជាការដោះដូរធម្មតាពីជំពូកទី 1៖ យើងចំណាយ memory ដើម្បីលុប loop ខាងក្នុង។ ប្រៀបធៀបវាជាមួយកំណែ two-pointer ដែលបានតម្រៀបពីជំពូកមុន ដែលជា O(n) ពេលវេលា និង O(1) space ប៉ុន្តែត្រូវការ input ដែលបានតម្រៀប ហើយត្រឡប់ទីតាំងតាមលំដាប់ ដែលបានតម្រៀប។ មួយណាល្អជាងអាស្រ័យលើអ្វីដែលអ្នកទទួលបាន។

រូបរាង "ចងចាំអ្វីដែលខ្ញុំបានឃើញ សួរថាតើដៃគូដែលត្រូវការមាននៅក្នុងនោះឬអត់" ដោះស្រាយបញ្ហាមួយគ្រួសារទាំងមូល៖ ស្ទួន គូដែលមានភាពខុសគ្នាកំណត់ subarray ដែលមានផលបូកកំណត់ និងការផ្គូរផ្គង transaction។

10. បញ្ហាសម្ភាសន៍បន្ថែមទៀត

ដាក់ anagram ជាក្រុម

ដាក់បញ្ជីពាក្យជាក្រុម ដើម្បីឲ្យ anagram នៅជាមួយគ្នា។ សម្រាប់ ["eat", "tea", "tan", "ate", "nat", "bat"] ក្រុមគឺ [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]។

ការយល់ដឹង៖ anagram ទាំងអស់ក្លាយជា string ដូចគ្នានៅពេលអ្នកតម្រៀបអក្សររបស់វា ដូច្នេះអក្សរដែលបានតម្រៀបធ្វើជា key ដ៏ល្អឥតខ្ចោះសម្រាប់ក្រុម៖

function groupAnagrams(words: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const w of words) {
    const key = [...w].sort().join("");
    const group = groups.get(key);
    if (group) group.push(w);
    else groups.set(key, [w]);
  }
  return [...groups.values()];
}

console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
// [ [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] ]

ថ្លៃចំណាយគឺ O(n * k log k) សម្រាប់ n ពាក្យដែលមានប្រវែង k (ការតម្រៀបអក្សរនៃពាក្យនីមួយៗ)។ "ដាក់ជាក្រុមតាម key ដែលបានគណនា" គឺជាការប្រើប្រាស់ Map ទូទៅបំផុតមួយក្នុងកម្មវិធីពិត ទោះជាការដាក់ order ជាក្រុមតាមអតិថិជន ឬ log line តាម request ID ក៏ដោយ។

Sequence ជាប់គ្នាវែងបំផុត

ដោយមានលេខដែលមិនទាន់តម្រៀប រកប្រវែងនៃការរត់វែងបំផុតនៃចំនួនគត់ជាប់គ្នា ដូចជា 100, 4, 200, 1, 3, 2 ដែលមាន 1, 2, 3, 4 (ប្រវែង 4)។ ការតម្រៀបនឹងជា O(n log n)។ Set ធ្វើបានក្នុង O(n)៖

function longestConsecutive(nums: number[]): number {
  const set = new Set(nums);
  let best = 0;
  for (const n of set) {
    if (set.has(n - 1)) continue; // not the start of a run
    let len = 1;
    while (set.has(n + len)) len++;
    best = Math.max(best, len);
  }
  return best;
}

console.log(longestConsecutive([100, 4, 200, 1, 3, 2])); // 4

មានតែលេខដែល ចាប់ផ្តើម ការរត់ (គ្មាន n - 1 ក្នុង set) ទេ ដែលចាប់ផ្តើមរាប់។ ការការពារនោះមានន័យថាលេខនីមួយៗត្រូវបានប៉ះយ៉ាងច្រើនពីរដង ដូច្នេះការងារសរុបគឺ O(n) ទោះបីជាមាន while នៅក្នុង for ក៏ដោយ។ នេះជាឧទាហរណ៍មួយនៃមូលហេតុដែលអ្នកត្រូវវែកញែកអំពីរបៀបដែល loop ខាងក្នុងមានអាកប្បកិរិយាជារួម មិនមែនគ្រាន់តែរាប់ loop ជាន់គ្នាទេ។

11. រូបមន្ត៖ module hashmap

ឥឡូវបង្កើតរបស់ខ្លួនអ្នកផ្ទាល់។ បង្កើត src/hash-map.ts៖

// src/hash-map.ts

export function hashString(key: string): number {
  let hash = 5381;
  for (let i = 0; i < key.length; i++) {
    hash = (hash * 33 + key.charCodeAt(i)) >>> 0;
  }
  return hash;
}

type Entry<V> = { key: string; value: V };

// Hash map ពី string key ទៅតម្លៃ ដោយប្រើ chaining។
export class HashMap<V> {
  private buckets: Entry<V>[][];
  private count = 0;

  constructor(private capacity = 8) {
    this.buckets = Array.from({ length: capacity }, () => []);
  }

  get size(): number {
    return this.count;
  }

  get bucketCount(): number {
    return this.capacity;
  }

  private indexFor(key: string): number {
    return hashString(key) % this.capacity;
  }

  set(key: string, value: V): void {
    const bucket = this.buckets[this.indexFor(key)];
    for (const entry of bucket) {
      if (entry.key === key) {
        entry.value = value; // update an existing key
        return;
      }
    }
    bucket.push({ key, value });
    this.count++;
    if (this.count / this.capacity > 0.75) this.resize(this.capacity * 2);
  }

  get(key: string): V | undefined {
    const bucket = this.buckets[this.indexFor(key)];
    for (const entry of bucket) {
      if (entry.key === key) return entry.value;
    }
    return undefined;
  }

  has(key: string): boolean {
    return this.buckets[this.indexFor(key)].some((e) => e.key === key);
  }

  delete(key: string): boolean {
    const bucket = this.buckets[this.indexFor(key)];
    const i = bucket.findIndex((e) => e.key === key);
    if (i === -1) return false;
    bucket.splice(i, 1);
    this.count--;
    return true;
  }

  *entries(): IterableIterator<[string, V]> {
    for (const bucket of this.buckets) {
      for (const entry of bucket) yield [entry.key, entry.value];
    }
  }

  keys(): string[] {
    return [...this.entries()].map(([k]) => k);
  }

  // ប្រវែងនៃ chain វែងបំផុត៖ រង្វាស់នៃរបៀបដែល key ត្រូវបានចែកចាយល្អ។
  longestChain(): number {
    return this.buckets.reduce((max, b) => Math.max(max, b.length), 0);
  }

  private resize(newCapacity: number): void {
    const old = this.buckets;
    this.capacity = newCapacity;
    this.buckets = Array.from({ length: newCapacity }, () => []);
    for (const bucket of old) {
      for (const entry of bucket) {
        this.buckets[this.indexFor(entry.key)].push(entry);
      }
    }
  }
}

អានវាយឺតៗ។ set, get, has និង delete ទាំងអស់ចាប់ផ្តើមជាមួយ indexFor(key) ដើម្បីជ្រើស bucket មួយ ហើយបន្ទាប់មកប៉ះតែ bucket នោះប៉ុណ្ណោះ។ Method resize បង្កើត bucket array ថ្មី ហើយបញ្ចូល entry ទាំងអស់ឡើងវិញ ព្រោះ index នៃ key នីមួយៗអាស្រ័យលើ capacity។ Method *entries គឺជា generator (* និង yield) ដែលជាវិធីងាយស្រួលក្នុងការបញ្ជូនធាតុត្រឡប់មកម្តងមួយៗ។

បន្តជាមួយឯកសារនេះដោយបន្ថែម helper function ពីជំពូកនេះនៅខាងក្រោមឯកសារដដែល។ វាប្រើ Map និង Set ដែលមានស្រាប់៖

export function countFrequencies(items: string[]): Map<string, number> {
  const counts = new Map<string, number>();
  for (const item of items) counts.set(item, (counts.get(item) ?? 0) + 1);
  return counts;
}

export function firstUniqueChar(text: string): number {
  const counts = countFrequencies([...text]);
  for (let i = 0; i < text.length; i++) {
    if (counts.get(text[i]) === 1) return i;
  }
  return -1;
}

export function isAnagram(a: string, b: string): boolean {
  if (a.length !== b.length) return false;
  const counts = countFrequencies([...a]);
  for (const ch of b) {
    const c = counts.get(ch);
    if (!c) return false;
    counts.set(ch, c - 1);
  }
  return true;
}

export function groupAnagrams(words: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const w of words) {
    const key = [...w].sort().join("");
    const group = groups.get(key);
    if (group) group.push(w);
    else groups.set(key, [w]);
  }
  return [...groups.values()];
}

export function twoSum(
  nums: number[],
  target: number
): [number, number] | null {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const j = seen.get(target - nums[i]);
    if (j !== undefined) return [j, i];
    seen.set(nums[i], i);
  }
  return null;
}

export function longestConsecutive(nums: number[]): number {
  const set = new Set(nums);
  let best = 0;
  for (const n of set) {
    if (set.has(n - 1)) continue;
    let len = 1;
    while (set.has(n + len)) len++;
    best = Math.max(best, len);
  }
  return best;
}

ឥឡូវ test នៅក្នុង src/hash-map.test.ts៖

// src/hash-map.test.ts
import { test } from "node:test";
import assert from "node:assert/strict";
import {
  HashMap,
  twoSum,
  isAnagram,
  groupAnagrams,
  firstUniqueChar,
  longestConsecutive,
  countFrequencies,
} from "./hash-map.ts";

test("HashMap set, get, update, delete", () => {
  const m = new HashMap<number>();
  m.set("a", 1);
  m.set("b", 2);
  m.set("a", 10);
  assert.equal(m.get("a"), 10);
  assert.equal(m.size, 2);
  assert.equal(m.delete("b"), true);
  assert.equal(m.delete("b"), false);
  assert.equal(m.has("b"), false);
  assert.equal(m.get("missing"), undefined);
});

test("HashMap survives resizing", () => {
  const m = new HashMap<number>(2);
  for (let i = 0; i < 500; i++) m.set(`key${i}`, i);
  assert.equal(m.size, 500);
  assert.ok(m.bucketCount > 2);
  for (let i = 0; i < 500; i++) assert.equal(m.get(`key${i}`), i);
});

test("twoSum", () => {
  assert.deepEqual(twoSum([2, 7, 11, 15], 9), [0, 1]);
  assert.deepEqual(twoSum([3, 3], 6), [0, 1]);
  assert.equal(twoSum([1, 2], 99), null);
});

test("anagrams, counting, and runs", () => {
  assert.equal(isAnagram("listen", "silent"), true);
  assert.equal(isAnagram("rat", "car"), false);
  assert.deepEqual(
    groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]),
    [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
  );
  assert.equal(firstUniqueChar("leetcode"), 0);
  assert.equal(countFrequencies(["a", "a"]).get("a"), 2);
  assert.equal(longestConsecutive([100, 4, 200, 1, 3, 2]), 4);
});

រត់ npm test។ ជាមួយជំពូកមុនៗ ឥឡូវនេះអ្នកគួរតែឃើញ test 10 ជាប់ និង # fail 0។

បន្ថែម demo ខ្លីក្នុងឯកសារថ្មី demo3.ts ដើម្បីមើល collision និងការ resize៖

import { HashMap } from "./src/hash-map.ts";

const small = new HashMap<string>();
small.set("cat", "c");
small.set("dog", "d");
small.set("bird", "b");
small.set("fish", "f");
console.log(small.size, small.bucketCount, small.longestChain());
// 4 8 2   (dog and fish share a bucket, so the longest chain is 2)
console.log(small.keys());
// [ 'cat', 'bird', 'dog', 'fish' ]   (bucket order, not insertion order)

const big = new HashMap<number>();
for (let i = 0; i < 100; i++) big.set("user" + i, i);
console.log(big.size, big.bucketCount, big.longestChain());
// 100 256 2
console.log(big.get("user42"), big.get("nobody")); // 42 undefined

សូមកត់សម្គាល់ថា keys() មិនត្រឡប់មកតាមលំដាប់នៃការបញ្ចូលទេ៖ table របស់យើងដើរកាត់ bucket តាមលំដាប់ index ដូច្នេះ cat (bucket 5), bird (6), dog និង fish (7) លេចឡើងតាមលំដាប់នោះ។ Map ដែលមានស្រាប់ទៅឆ្ងាយជាងនេះ ដោយចងចាំលំដាប់នៃការបញ្ចូល។ របស់យើងសាមញ្ញជាងដោយចេតនា។

12. សាកល្បងដោយខ្លួនឯង

1. ទាយ bucket។ ជាមួយ 8 bucket និង hashString តើ "cat" ទៅ bucket មួយណា? (ប្រើតម្លៃពីផ្នែកទី 3។) បន្ទាប់មកពិនិត្យជាមួយ hashString("cat") % 8 ក្នុងឯកសារ scratch។
2. រាប់ពាក្យ។ សរសេរ topWord(text) ដែលត្រឡប់ពាក្យដែលលេចឡើងញឹកញាប់បំផុតក្នុងប្រយោគ (អក្សរតូច)។ ប្រើ countFrequencies ហើយគ្រប់គ្រង string ទទេដោយត្រឡប់ undefined។
3. មានស្ទួន។ សរសេរ containsDuplicate(nums) ដោយប្រើ Set។ បន្ទាប់មកសរសេរ containsNearbyDuplicate(nums, k)៖ true ប្រសិនបើតម្លៃស្មើគ្នាពីរនៅឆ្ងាយគ្នាយ៉ាងច្រើន k ទីតាំង។ ព័ត៌មានជំនួយ៖ ចងចាំ index ចុងក្រោយនៃតម្លៃនីមួយៗ។
4. ចំនុចប្រសព្វនៃ array ពីរ។ ត្រឡប់តម្លៃដែលលេចឡើងក្នុង array ទាំងពីរ ដោយគ្មានស្ទួន។ បង្កើត Set ពី array មួយ បន្ទាប់មកស្កេនមួយទៀត។ ប្រាប់ថ្លៃចំណាយ ហើយប្រៀបធៀបវាជាមួយ loop ពីរជាន់គ្នា។
5. បែបសម្ភាសន៍៖ valid anagram ជាមួយ Unicode។ isAnagram ខាងលើចាត់ទុក string ជាលំដាប់នៃ UTF-16 code point តាមរយៈ spread។ តើមានអ្វីកើតឡើងជាមួយ "é" ដែលវាយជាតួអក្សរតែមួយ ធៀបនឹង "e" បូកសញ្ញាសំឡេងផ្សំ?ពន្យល់ពីភាពខុសគ្នា និងរបៀបដែល String.prototype.normalize("NFC") ជួយ។
6. បែបសម្ភាសន៍៖ subarray sum ស្មើ k។ រាប់ subarray ជាប់គ្នាដែលមានផលបូកស្មើ k។ រក្សា prefix sum កំពុងរត់ និង Map នៃចំនួនដងដែល prefix sum មុនៗនីមួយៗបានលេចឡើង។ សម្រាប់ prefix ថ្មី p នីមួយៗ បូក map.get(p - k) ?? 0 ទៅក្នុងចម្លើយ។ ពិនិត្យលើ [1, 2, 3] ជាមួយ k = 3 (ចម្លើយ 2) និងលើ [1, 1, 1] ជាមួយ k = 2 (ចម្លើយ 2)។
7. ពង្រីក HashMap។ បន្ថែម method clear() និងបន្ថែម getOrDefault(key, fallback)។ បន្ទាប់មកផ្លាស់ប្តូរ resize ដើម្បីឲ្យវាបង្រួម table ផងដែរ នៅពេល load factor ធ្លាក់ក្រោម 0.2។ សរសេរ test ដែលបន្ថែម 1,000 key លុបវាទាំងអស់ ហើយពិនិត្យថា bucketCount ថយចុះវិញ។

Hash map ឆ្លើយសំណួរ "អ្វីទៅជាមួយ key នេះ?" ក្នុងជំហានតែមួយ ប៉ុន្តែវាមិនដឹងអ្វីអំពីលំដាប់ទេ។ structure បន្ទាប់ទាក់ទងនឹងលំដាប់ និងការបញ្ចូលថោក៖ linked list។ ក្នុង Linked List អ្នកនឹងបង្កើតមួយពីសូន្យ មើលកន្លែងដែលវាឈ្នះ array និងរៀនល្បិច pointer (ការបញ្ច្រាស ការរកឃើញ cycle ការបញ្ចូលគ្នា) ដែលអ្នកសម្ភាសន៍ចូលចិត្ត។