आप balanced binary search tree की जगह hash map कब चुनेंगे?

hash map तब चुनिए जब आपको सिर्फ key से lookup, insert और delete चाहिए और average constant time चाहिए। balanced tree तब चुनिए जब आपको क्रम चाहिए: range scans, सबसे नजदीकी key, या sorted क्रम में घूमना, वह भी logarithmic time में। tree आपको worst case व्यवहार का भरोसा भी देता है, जबकि hash map खराब hashing से बहुत बिगड़ सकता है या गलत वक्त पर resize में अटक सकता है।

मेरा डिफॉल्ट hash map ही है, क्योंकि ज्यादातर वक्त मैं id से point lookup कर रहा होता हूं और constant average time को हराना मुश्किल है। लेकिन जैसे ही जरूरत में ordering आती है, मैं बदल देता हूं। दो timestamps के बीच के सारे events दो, या इसके बाद वाली key बताओ, यह सब range query है, और hash map बिना सब कुछ स्कैन किए यह कर ही नहीं सकता। वहां tree चाहिए, या व्यवहार में binary search वाला कोई sorted स्ट्रक्चर। मैं tail के बारे में भी सोचता हूं। hash lookups औसतन constant होती हैं, लेकिन खराब hash function या rehash से spike आ सकता है, और latency budget के अंदर मुझे इसकी परवाह होती है। एक leaderboard फीचर में हमने user से score की dictionary से शुरुआत की थी और फिर हर read पर पूरी चीज sort करनी पड़ती थी। जैसे ही हम Redis के sorted set पर गए, reads logarithmic हो गईं और peak पर endpoint गिरना बंद हो गया। वही डेटा, अलग access pattern, अलग स्ट्रक्चर।