ჰეშ-ცხრილები: set და map

„ეს უკვე მინახავს?“ და „რამდენჯერ?“ რეალურ კოდში ყველაზე ხშირი კითხვებია. ჰეშ-ცხრილი ორივეს საშუალოდ O(1)-ში პასუხობს, ამიტომაც აქვს ის ყველა ენას ჩაშენებული.

დამწყები⏱ 14 წთ

←ეყრდნობა

1მასივები და დინამიური მასივებიჰეშ-ცხრილი არის კალათების მასივი, რომელსაც გასაღების ჰეშით ვინდექსავთ.0სირთულე და ზრდის ტემპისაშუალოდ O(1) და უარეს შემთხვევაში O(n): სწორედ ამ განსხვავებას გვასწავლის Big-O.

გზას უხსნის→

1პრეფიქსული ჯამები, ორი მაჩვენებელი, მოცურავი ფანჯარამოცემული ჯამის მქონე ქვემასივების დასათვლელად უკვე ნანახ პრეფიქსულ ჯამებს ჰეშ-ცხრილში ვინახავთ.5დაბალანსებული ხეები და set / mapstd::set და std::map არის unordered_set-ისა და unordered_map-ის დალაგებული ვერსიები.5ტრაი და ავტოშევსებატრაის წვეროს შვილებს ხშირად map-ში ვინახავთ, სადაც ასო შვილზე მიუთითებს.11მოძრავი ჰეში და რაბინ-კარპიმოძრავი ჰეში ჰეშ-ფუნქციაა, რომელიც ფანჯრის გაცურებისას O(1)-ში ახლდება.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01სიმრავლეები და ასახვები

ორი ყოველდღიური ინსტრუმენტი ჰეშ-ცხრილზეა აგებული:

სიმრავლე (set) უნიკალურ გასაღებებს ინახავს და პასუხობს კითხვას „x მასშია?“. C++ unordered_set, Python set, Java HashSet.
ასახვა (map, ლექსიკონი) ინახავს წყვილებს გასაღები → მნიშვნელობა: სიტყვა → რაოდენობა, მომხმარებლის id → პროფილი. C++ unordered_map, Python dict, Java HashMap.

იდეა: ჰეშ-ფუნქცია h(k) ნებისმიერ გასაღებს, რიცხვს თუ სტრიქონს, კალათების მასივის ინდექსად აქცევს. ჩასასმელად გამოთვალე h(k) და გასაღები იქ ჩადე. საძებნელად ისევ გამოთვალე h(k) და მხოლოდ იმ ერთ კალათაში ჩაიხედე. არც სკანირება, არც სორტირება: გასაღები თავად გეუბნება, სად ცხოვრობს.

02კოლიზიები და ჯაჭვები

შესაძლო გასაღებები კალათებზე ბევრად მეტია, ამიტომ ორი გასაღები ზოგჯერ ერთ კალათაში მოხვდება. ეს კოლიზიაა, და ის ჩვეულებრივი მოვლენაა და არა შეცდომა.

უმარტივესი გამოსავალია ჯაჭვები (chaining): ყოველი კალათა პატარა სიას ინახავს. h(k) = k mod 7-ით გასაღებები 15, 8 და 22 სამივე 1-ს იძლევა, ამიტომ კალათა 1-ში სამელემენტიანი ჯაჭვია. ძებნა კალათას ჰეშით პოულობს და მერე გასაღებებს მხოლოდ ამ ჯაჭვის გასწვრივ ადარებს.

მეორე კლასიკური მიდგომაა ღია მისამართება (open addressing): თუ კალათა დაკავებულია, შეამოწმე შემდეგი (და შემდეგი), სანამ თავისუფალს არ იპოვი. ორივე შემთხვევაში ოპერაციის სამუშაო დაახლოებით ერთი ჯაჭვის სიგრძეა, ამიტომ გვინდა, რომ ჯაჭვები მოკლე დარჩეს.

03დატვირთვის ფაქტორი და რეჰეშირება

დატვირთვის ფაქტორი α = (გასაღებების რაოდენობა) / (კალათების რაოდენობა) ჯაჭვის საშუალო სიგრძეა. კარგი ჰეშ-ფუნქციით, რომელიც გასაღებებს თანაბრად ანაწილებს, ყოველი ოპერაცია დაახლოებით O(1 + α) ღირს.

ამიტომ ცხრილი α-ს შემოსაზღვრულს ინარჩუნებს. როცა ის ზღვარს გადასცდება (unordered_map-ისთვის დაახლოებით 1, Python-ის dict-ისთვის 2/3), ხდება რეჰეშირება: გამოიყოფა დაახლოებით ორჯერ მეტი კალათა და ყველა გასაღები თავიდან ჩაისმება, რადგან h(k) კალათების რაოდენობაზეა დამოკიდებული.

ერთი რეჰეშირება O(n)-ია, მაგრამ ის მხოლოდ ცხრილის გაორმაგების შემდეგ ხდება, ზუსტად ისე, როგორც მზარდ ვექტორში. შედეგი: ჩასმა, ძებნა და წაშლა მოსალოდნელი O(1)-ია, ყველა ოპერაციაზე ამორტიზებით.

04როდის გამოვიყენოთ და სად არის ხაფანგები

ჰეშ-სიმრავლე ან ასახვა გამოიყენე, როცა გჭირდება კუთვნილება, დათვლა ან დაჯგუფება: დუბლიკატების აღმოჩენა, სიტყვების სიხშირის დათვლა, მოცემული ჯამის მქონე წყვილის პოვნა (შეინახე, რაც უკვე ნახე), ანაგრამების დაჯგუფება დალაგებული გასაღებით.

იცოდე საზღვრები:

უარესი შემთხვევა O(n)-ია: თუ ბევრი გასაღები კოლიზირდება, ჯაჭვი ჩვეულებრივ სიად იქცევა. ოლიმპიადების საიტებზე სპეციალური ტესტები unordered_map-ს ამას განზრახ უკეთებს; რანდომიზებული ჰეში იცავს ამისგან.
რიგი არ არსებობს: გავლის რიგი ნებისმიერია. თუ დალაგებული გასაღებები, მინ/მაქს ან „შემდეგი დიდი გასაღები“ გჭირდება, გამოიყენე დალაგებული map/set (დაბალანსებული ხე, O(log n)).
გასაღები ჰეშირებადი უნდა იყოს და არ უნდა შეიცვალოს შენახვის დროს. სიმრავლეში მყოფი გასაღების შეცვლა მას კარგავს.

ფასი ერთი შეხედვით

ჩასმა / ძებნა / წაშლა (მოსალოდნელი)O(1)

უარესი (ყველა კოლიზიაში)O(n)

რეჰეშირებაO(n), rare

სანაცვლოდ დალაგებული map / setO(log n)

დაიმახსოვრე

ჰეშ-ფუნქცია ყოველ გასაღებს პირდაპირ კალათაში აგზავნის, ამიტომ ძებნას სკანირება არ სჭირდება.
კოლიზიები ჩვეულებრივია; ჯაჭვები მათ სწორად ამუშავებს, შემოსაზღვრული დატვირთვის ფაქტორი კი მოკლედ ინარჩუნებს.
ჰეშ-ცხრილი მოსალოდნელ O(1)-ს იძლევა, მაგრამ რიგს არა; როცა რიგი მნიშვნელოვანია, ხეზე დაფუძნებული map გამოიყენე.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: უყურე, როგორ იზრდება ჯაჭვი კალათა 1-ში, მერე შეადარე ძებნა, რომელიც ჯაჭვს გაივლის, და ძებნა, რომელიც ცარიელ კალათას ხვდება. სცადე 2 კალათა გრძელი ჯაჭვებისთვის.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

ჰეშ-ცხრილი: h(k) = k mod 7

[0]∅

[1]∅

[2]∅

[3]∅

[4]∅

[5]∅

[6]∅

ჰეშ-ცხრილი გასაღებებს 7 კალათაზე ასახავს h(k) = k mod 7-ით. იდეალურად ყოველი ძებნა მხოლოდ ერთ კალათას ეხება.

ფსევდოკოდი

 1 table of B buckets; h(k) = k mod B 2 insert k: append to bucket h(k) (chaining on collision) 3 find k: hash to bucket h(k), then scan its chain 4   compare each key until found or chain ends 5 // expected O(1) while the load factor stays bounded

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

7 კალათითა და h(k) = k mod 7-ით, რომელ კალათაში მოხვდება გასაღები 30?

№2

უნდა შეამოწმო, n რიცხვიდან რომელიმე ორის ჯამი უდრის თუ არა მიზანს. რომელია ტიპურად ყველაზე სწრაფი მიდგომა?

№3

ბევრჯერ გჭირდება x-ზე მეტი უმცირესი გასაღები. რომელი სტრუქტურა ჯდება?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

CSESDistinct Numbers დამწყები↗LeetCodeTwo Sum დამწყები↗LeetCodeValid Anagram დამწყები↗LeetCodeGroup Anagrams საშუალო↗LeetCodeLongest Consecutive Sequence საშუალო↗