ஒரு ஹேஷ் அட்டவணை (hash map) key → value쌍களைச் சேமித்து, சராசரியில் O(1) செருகல், தேடல் மற்றும் நீக்குதல் வழங்குகிறது. இது ஒவ்வொரு விசையையும் ஒரு ஹேஷ் செயல்பாடு மூலம் கடந்து செல்வதன் மூலம் செயல்படுகிறது, இது அடிப்படை வரிசையில் (ஒரு "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
| செயல்பாடு | சராசரி | மோசம் |
|---|---|---|
| செருகல் | O(1) | O(n) |
| தேடல் | O(1) | O(n) |
| நீக்குதல் | O(1) | O(n) |
மோசமான நிலை O(n) பல விசைகள் ஒரே bucket இல் மோதிக்கொள்ளும் போது ஏற்படுகிறது.
ஹேஷ் அட்டவணைகள் பல்வேறு நிகழ்ச்சிகளில் அநேகமாக மிகவும் பயன்படுத்தப்படும் கட்டமைப்பு — அகராதிகள், தொகுப்புகள், கேச், தரவுத்தளக் குறியீடுகள் மற்றும் நகல் நீக்குதல்.
நேரியல் ஸ்கேனை ஒரு ஹேஷ் தேடல் மூலம் மாற்றுவது O(n²) வழிமுறையை O(n) ஆக மாற்றுவதற்கான மிகவும் பொதுவான வழிகளில் ஒன்றாகும்.