ਇੱਕ hash table (hash map) key → value ਜੋੜਿਆਂ ਨੂੰ ਸਟੋਰ ਕਰਦਾ ਹੈ ਅਤੇ ਔਸਤਨ O(1) insert, lookup, ਅਤੇ delete ਦੀ ਪੇਸ਼ਕਸ਼ ਕਰਦਾ ਹੈ। ਇਹ ਹਰ key ਨੂੰ ਇੱਕ hash function ਦੁਆਰਾ ਚਲਾ ਕੇ ਕੰਮ ਕਰਦਾ ਹੈ ਜੋ ਇਸਨੂੰ ਅੰਤਰਲਿਆ array (ਇੱਕ "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) ਉਦੋਂ ਹੁੰਦਾ ਹੈ ਜਦੋਂ ਬਹੁਤ ਸਾਰੀ keys ਉਸੇ bucket ਵਿੱਚ ਟਕਰਾ ਜਾਂਦੀ ਹਨ।
Hash tables ਸ਼ਾਇਦ ਅਮਲ ਵਿੱਚ ਸਭ ਤੋਂ ਵੱਧ ਵਰਤੇ ਜਾਣ ਵਾਲੀ ਢਾਂਚਾ ਹਨ — ਡਿਕਸ਼ਨਰੀਜ਼, sets, caches, ਡੇਟਾਬੇਸ ਇੰਡੈਕਸ, ਅਤੇ deduplication ਦੇ ਪਿੱਛੇ।
ਇੱਕ ਲੀਨੀਅਰ ਸਕੈਨ ਨੂੰ hash lookup ਨਾਲ ਬਦਲਣਾ O(n²) ਐਲਗੋਰਿਦਮ ਨੂੰ O(n) ਵਿੱਚ ਬਦਲਣ ਦੇ ਸਭ ਤੋਂ ਆਮ ਤਰੀਆਂ ਵਿੱਚੋਂ ਇੱਕ ਹੈ।
ਵਿਸਤ੍ਰਿਤ ਜਵਾਬਾਂ ਨਾਲ IT ਇੰਟਰਵਿਊ ਸਵਾਲਾਂ ਦੀ ਇੱਕ ਲਾਇਬ੍ਰੇਰੀ — ਜੂਨੀਅਰ ਤੋਂ ਸੀਨੀਅਰ ਤੱਕ।
ਦਾਨ ਕਰੋ