இரண்டு வெவ்வேறு விசைகள் ஒரே வாளிக்கு hash செய்யலாம் — மோதல். Hash அட்டவணைகள் மோதல்களைத் தீர்ப்பதன் மூலமும் வாளிகள் அடர்ந்துவிடும் முன் மறுவளையை செய்வதன் மூலமும் சராசரியாக O(1) ஆக இருக்கின்றன, சுமை காரணிஆல் கட்டுப்படுத்தப்படுகிறது.
Separate chaining: each bucket holds a list
[3] -> ("cat",9) -> ("rat",2) # both hashed to 3
Open addressing: probe to the next free slot
hash=3 taken -> try 4 -> try 5 ... (linear probing)
load factor α = number_of_entries / number_of_buckets
α rises -> more collisions -> slower lookups
When α exceeds a threshold (e.g. 0.75):
-> allocate a bigger array (usually 2x)
-> REHASH every existing key into new buckets
# Conceptual resize
def _resize(self):
old = self.buckets
self.buckets = [None] * (len(old) * 2)
for entry in all_entries(old):
self._insert(entry.key, entry.value) # rehash into new array
| செயல்பாடு | சராசரி | மோசமான நிலை |
|---|---|---|
| தேடல் / செருகல் / நீக்கல் | O(1) | O(n) |
| ஒற்றை மறுவளையை | — | O(n) |
| செருகல் (amortized, மறுவளையை கொண்டு) | O(1) | — |
மறுவளையை O(n) ஆனாலும் அரிதாக நடக்கிறது, எனவே இது செருகலுக்கு O(1) என amortizes ஆகிறது.
இந்த உள்ளெ விளக்கங்கள் hash வரைபடங்கள் ஏன் சராசரியாக வேகமாக இருக்கின்றன ஆனால் O(n) என்பதற்கு குதிக்க முடியும் என்பதை விளக்குகிறது — செயல்திறனுக்கு உணர்வுள்ள கோடு மற்றும் எதிரியான-input (hash-flooding) பாதுகாப்பு இன்றியமையாதது.
சுமை காரணியைப் புரிந்துகொள்ளுதல் நினைவகம்/வேகம் tuning knobs விளக்கம் அளிக்கிறது உண்மையான libraries கடத்தப்படுகிறது.