hash table (hash map) ინახავს key → value წყვილებს და გვთავაზობს საშუალო O(1) insert, lookup და delete. ის მუშაობს თითოეული გასაღების გატარებით hash ფუნქციის მეშვეობით, რომელიც მას ასახავს ძირითადი მასივის ინდექსზე ("bucket"-ზე).
key "cat" --hash()--> 3 buckets:
key "dog" --hash()--> 0 [0] -> ("dog", 5)
[1]
[2]
[3] -> ("cat", 9)
phone = {}
phone['alice'] = 555_1234 # insert -> hash 'alice' to a bucket
num = phone['alice'] # lookup -> hash again, jump to bucket
del phone['alice'] # delete
'bob' in phone # membership -> O(1) average
| ოპერაცია | საშუალო | ყველაზე খराब |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |
ყველაზე খराब შემთხვევა O(n) ხდება მაშინ, როდესაც მრავალი გასაღები ერთსა და იმავე bucket-ში შედის კოლიზიაში.
Hash table-ები ალბათ ყველაზე გამოყენებული სტრუქტურა პრაქტიკაში — ლექსიკონებისა, ნაკრებების, cache-ების, მონაცემთა ბაზის ინდექსებისა და დუპლიკატების გამორიცხვის უკან.
ხაზოვანი სკანის ჩანაცვლება hash ძებნით ერთ-ერთი ყველაზე გავრცელებული გზაა O(n²) ალგორითმის O(n)-ში გარდაქმნისთვის.