हैश टेबल खोज की सीमाओं को उलट देने वाला अंडरग्रेजुएट रिसर्च

 (quantamagazine.org)
5 पॉइंट द्वारा GN⁺ 2025-02-11 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Rutgers में अंडरग्रेजुएट रहे Andrew Krapivin ने Tiny Pointers पेपर से प्रेरित होकर एक नई hash table बनाई, और दिखाया कि खोज व insertion performance को अब तक मानी जा रही सीमाओं से आगे ले जाया जा सकता है
  • Krapivin, Martín Farach-Colton और William Kuszmaul ने जनवरी 2025 के पेपर में hash tables की एक खास श्रेणी को लेकर Yao के 40 साल पुराने अनुमान को गलत साबित किया
  • पुराने अनुमान के अनुसार, table के लगभग भर जाने की मात्रा बताने वाले x के लिए सबसे खराब स्थिति में search और insertion time x से बेहतर नहीं हो सकता था, लेकिन नई संरचना (log x)² के अनुपात में time हासिल करती है
  • शोधकर्ताओं ने यह भी दिखाया कि Yao द्वारा देखी गई लोकप्रिय hash table श्रेणी में (log x)² ही वह optimal bound है जिसे और कम नहीं किया जा सकता, और non-greedy hash tables में average search time x से स्वतंत्र constant तक हो सकता है
  • भले ही इसका तुरंत कोई application न निकले, यह पुराने data structure hash table की performance सीमाओं को नए सिरे से परिभाषित कर practical सुधारों की संभावना खोलने वाला theoretical आधार बनता है

Tiny Pointers से शुरू हुई नई hash table

  • Andrew Krapivin ने 2021 की शरद ऋतु में Rutgers University में अंडरग्रेजुएट रहते हुए Tiny Pointers पेपर देखा, और दो साल बाद इसे विस्तार से पढ़ते समय उन्हें और छोटे pointers बनाने का तरीका सूझा
  • चूंकि pointers जिस data की ओर इशारा करेंगे उसे बेहतर ढंग से organize करना जरूरी था, इसलिए सामान्य data storage method hash table research का विषय बनी
  • प्रयोगों के दौरान Krapivin ने uniform probing पर निर्भर न रहने वाली नई hash table बनाई, और पाया कि किसी खास element को खोजने में लगने वाला time और steps की संख्या अपेक्षा से कम है
  • Martín Farach-Colton ने शुरुआत में इस design पर शक किया, लेकिन William Kuszmaul ने माना कि Krapivin की संरचना सिर्फ एक दिलचस्प hash table नहीं, बल्कि 40 साल पुराने अनुमान को गिराने वाला परिणाम है

Hash table की performance सीमा की समस्या

  • Hash table data को store और access करने वाला data structure है, और मूल रूप से तीन operations support करता है
    • element को search (query) करना
    • element को delete करना
    • खाली slot में element insert करना
  • पहली hash table 1950 के शुरुआती दशक तक जाती है, और तब से computer science में लगातार research और इस्तेमाल में रही यह एक पुराना data structure है
  • search या insertion की speed limit आम तौर पर hash table में खाली जगह खोजने में लगने वाले time से जुड़ी होती है
  • hash table कितनी भरी हुई है, इसे कुल अनुपात से व्यक्त किया जा सकता है, लेकिन लगभग भरी हुई table पर काम करते समय researchers value x का इस्तेमाल करते हैं
    • अगर x 100 है, तो table 99% भरी है
    • अगर x 1,000 है, तो table 99.9% भरी है
  • कुछ सामान्य hash tables में, जैसे आखिरी बची खाली जगह में element डालना, worst-case expected insertion time x के अनुपात में माना जाता था

Yao का 1985 का अनुमान और उसका खंडन

  • Andrew Yao ने 1985 के पेपर में माना कि कुछ गुणों वाली hash tables में किसी individual element या खाली जगह को खोजने का सबसे अच्छा तरीका संभावित positions को random तरीके से scan करने वाली uniform probing है
  • सबसे खराब स्थिति में, यानी आखिरी बची खाली जगह खोजने के मामले में, x से बेहतर नहीं हो सकता—यह अनुमान 40 वर्षों तक ज्यादातर सच माना गया
  • Krapivin ने Yao के अनुमान को जाने बिना Tiny Pointers से जुड़ी पड़ताल आगे बढ़ाई, और uniform probing पर निर्भर न रहने वाली नई hash table बनाई
  • Krapivin, Farach-Colton और Kuszmaul के जनवरी 2025 के पेपर ने दिखाया कि इस नई hash table में worst-case search और insertion time (log x)² के अनुपात में है
  • यह परिणाम Yao के अनुमान से सीधे टकराता है, और researchers ने यह भी prove किया कि Yao द्वारा देखी गई लोकप्रिय hash table category में (log x)² ही optimal bound है जिसे और कम नहीं किया जा सकता

Average search time पर और भी चौंकाने वाला परिणाम

  • Yao ने 1985 में worst-case search time के साथ-साथ सभी संभावित searches पर लगने वाले average time को भी देखा था
  • कुछ गुणों वाली hash tables, खासकर ऐसी greedy hash tables जिनमें नए element को पहली उपलब्ध position में डालना होता है, के लिए उन्होंने prove किया कि average time log x से बेहतर नहीं हो सकता
  • Farach-Colton, Krapivin और Kuszmaul यह जांचना चाहते थे कि क्या यही सीमा non-greedy hash tables पर भी लागू होती है, और एक counterexample के जरिए दिखाया कि ऐसा नहीं है
  • यह counterexample, यानी non-greedy hash table, average search time में log x से कहीं बेहतर है, और असल में x पर बिल्कुल निर्भर नहीं करता
  • hash table कितनी भी भरी हो, constant average search time हासिल किया जा सकता है—यह बात खुद researchers के लिए भी अप्रत्याशित थी

पुराने data structure का theoretical update

  • Alex Conway के अनुसार hash table सबसे पुराने data structures में से एक है, फिर भी data store करने के सबसे efficient तरीकों में से एक बनी हुई है
  • Guy Blelloch ने इस result को इसलिए सुंदर माना क्योंकि यह एक classical problem को address और solve करता है
  • Sepehr Assadi ने आकलन किया कि researchers ने न सिर्फ Yao के अनुमान को गलत साबित किया, बल्कि उनके सवाल का सबसे अच्छा जवाब भी खोज लिया
  • Conway का मानना है कि भले ही यह result तुरंत किसी application में न बदले, ऐसे data structures को बेहतर समझना महत्वपूर्ण है
  • hash table की theoretical limits को नए सिरे से व्यवस्थित करने वाला यह result आगे चलकर real-world performance improvements का आधार बन सकता है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-02-11
Hacker News की रायें

  • मुझे लगता है Krapivin यह breakthrough इसलिए कर पाए क्योंकि उन्हें Yao की conjecture के बारे में पता नहीं था, और Balatro के developer ने भी award-winning गेम इसलिए बनाया क्योंकि उन्हें मौजूदा deck builders के बारे में ज़्यादा पता नहीं था
    समस्या को approach करने का सबसे अच्छा तरीका शायद यह हो सकता है कि पहले की मिलती-जुलती कोशिशों में से ज़्यादातर के बारे में न पता हो, या उन्हें ignore किया जाए
    आज की दुनिया इतनी connected है कि पहले आए लोगों के सोचने के ढांचे में फंसे बिना कोई ताज़गी देखना दुर्लभ हो गया है; internet शानदार है, लेकिन यह सोच को homogeneous बना देता है, यह बात अफसोसजनक है

    • मुझे लगता है पहले की कोशिशों को ignore करना तभी अच्छा होता है, जब मौजूदा तरीकों से बिल्कुल अलग दिशा में कोई नया solution सच में मौजूद हो
      आम तौर पर, अतीत की सफलताओं को ignore करने पर आप उस जमीन पर फिर से बीज बोते हैं जो पहले ही बंजर साबित हो चुकी थी
    • मेरे अनुभव में सबसे अच्छा approach यह है कि पहले prior research पढ़े बिना समस्या को हल करने की कोशिश करें, फिर उसके बाद prior research पढ़ें, और उसके हिसाब से अपना approach बेहतर करें
      अगर बहुत जल्दी prior research पढ़ लेते हैं तो मौजूदा सोच में कैद हो जाते हैं, और अगर बिल्कुल नहीं पढ़ते तो वे अहम चीजें छूट जाती हैं जो खुद आपके दिमाग में नहीं आईं
      भले ही आपका approach मौजूदा state-of-the-art से कमतर हो, तुलना के जरिए यह अहम insight मिल सकती है कि state-of-the-art approach बेहतर क्यों है
    • Balatro के developer को deck builders के बारे में पता था और वे सीधे तौर पर Luck be a Landlord से inspired थे, लेकिन उन्हें नहीं पता था कि यह genre कितना बड़ा है
      developer के direct quote के मुताबिक, Balatro पर सबसे बड़ा असर Luck be a Landlord का था; Northernlion के कुछ gameplay videos देखने के बाद उन्हें non-fantasy theme वाले score-attack roguelike का concept पसंद आया और उन्होंने उस समय बना रहे card game को roguelike में बदल दिया
      उस point से उन्होंने जानबूझकर genre से दूरी बनाए रखी, और खुद गलतियां करते हुए design space को भोलेपन से explore करना चाहा
      Slay the Spire से तुलना बहुत सुनने को मिलती है, लेकिन Balatro design करते समय उन्होंने वह game न खेली थी, न उसके videos देखे थे; उससे वे काफी बाद में ही परिचित हुए
      https://www.reddit.com/r/Games/comments/1bdtmlg/comment/kup7...
    • “लोग तुम्हें cheer कर रहे हैं।” उसने मुस्कुराते हुए कहा
      “लेकिन सबकी मदद के बिना मैं यह कभी नहीं कर पाता।” [Milo] ने जवाब दिया
      “शायद ऐसा हो।” Reason ने गंभीरता से कहा। “लेकिन तुम्हारे पास कोशिश करने की हिम्मत थी, और तुम क्या कर सकते हो यह अक्सर इस पर निर्भर करता है कि तुम क्या करने की ठानते हो।”
      King Azaz ने कहा। “इसलिए तुम्हारे adventure की एक बहुत अहम बात ऐसी थी जो तुम्हारे लौटने से पहले हम बता नहीं सकते थे।”
      “मुझे याद है।” Milo ने उत्सुकता से कहा। “अब बताइए।”
      “वह असंभव था।” राजा ने Mathemagician की ओर देखते हुए कहा
      “पूरी तरह असंभव।” Mathemagician ने राजा की ओर देखते हुए कहा
      “तो फिर….” कीड़े ने अचानक चक्कर-सा खाते हुए कहा
      “हाँ, बिल्कुल।” दोनों ने साथ कहा। “लेकिन अगर हमने तुम्हें तब बता दिया होता, तो शायद तुम जाते ही नहीं… और जैसा तुमने जाना, जब तक तुम्हें यह नहीं पता कि कोई चीज असंभव है, तब तक वाकई बहुत सारी चीजें संभव होती हैं।”
      — The Phantom Tollbooth (1961)
    • कॉलेज में मेरे एक professor थे जिनका पहला published paper homework में submit किए गए solution से निकला था; संयोग से उन्होंने किसी problem की bounds से जुड़ी एक open problem हल कर दी थी
      मेरी कुछ परिस्थितियों के कारण मैं उस class में fail हो गया और उसे दोबारा लेते समय मुझे उनकी एक आदत पता चली
      हर semester के later assignments में से किसी एक में, लगभग 30 problems के problem set में वे एक ऐसा problem दे देते थे जो असल में open problem होता था, और deadline से एक-दो दिन पहले “अरे, गलती हो गई” कहते हुए revised version भेजते थे
      यह देखते हुए कि ऐसा हमेशा ठीक एक बार ही होता था, मुझे नहीं लगता कि यह coincidence रहा होगा

  • monort [0] ने वीडियो [1] का लिंक दिया, जिससे काफी मदद मिली
    वीडियो एक बार देखने के आधार पर यह एक तेज़ सारांश है; इसका नाम Funnel Hashing है
    आइडिया यह है कि array को घातीय रूप से छोटे sub-arrays में बाँटा जाता है। पहला chunk n/m, दूसरा n/(m^2) की तरह घटता जाता है और अंत में single element तक पहुँचता है। इन्हें A0, A1 वगैरह कहें तो |A0| = n/m, |A1| = n/(m^2) होता है और कुल k चरण होते हैं
    A0 में c बार insert करने की कोशिश की जाती है, और fail होने पर A1 में c बार कोशिश की जाती है। वह भी fail हो जाए तो खाली slot मिलने तक “funnel” के साथ नीचे जाते हैं
    \delta को खाली slots का ratio कहा गया है, लेकिन मुझे पक्का नहीं कि यह hash table बनाते समय तय किया गया parameter है या dynamically update होने वाली value। c = log(1/d), k = log(1/d) रखने पर worst-case time complexity O(log^2(1/d)) हो जाती है
    मेरी समझ में यह तरीका greedy नहीं है, इसलिए Yao के परिणाम को bypass करता है। Yao का परिणाम greedy insertion और search policy के लिए लागू होता है, और ऊपर वाला तरीका funnel के नीचे क्रमिक रूप से उतरता है, इसलिए non-greedy है
    Details में कई कठिन हिस्से होंगे, लेकिन मेरी समझ में आइडिया इतना ही है। अगर मैंने पूरी तरह गलत समझा है तो बताएं
    Chakraborty, Vinodchandran, Meel के “Distinct Elements in Streams” आइडिया [2] की बहुत याद आती है
    [0] https://news.ycombinator.com/item?id=43007860
    [1] https://www.youtube.com/watch?v=ArQNyOU1hyE
    [2] https://arxiv.org/pdf/2301.10191

    • असल में वे दो algorithms, Funnel Hashing और Elastic Hashing, propose करते हैं
      Funnel Hashing “greedy” है, और greedy hash mechanism पर Yao के conjecture को तोड़ता है
      Elastic Hashing “non-greedy” है और greedy algorithms से बेहतर amortized time देता है
    • यह समझाना कि Yao के conjecture को non-greedy होने की वजह से bypass किया गया है, article से contradict करता है
      Article गलत है या paper की समझ गलत है, पता नहीं; लेकिन उत्सुकता है कि क्या article लेखक ने कोई ऐसी बात पकड़ी है जो बाकी लोगों को नहीं पता
    • वीडियो देखते हुए जो बात समझ नहीं आई, वह यह है कि बहुत rare case में funnel के अंत तक collision हो जाए तो क्या होता है
      लगता है यह वीडियो में लगभग 14:41 पर “कुछ keys को पकड़ने के लिए special last stage” से जुड़ा है, लेकिन अगर उसका भी fixed size होना ज़रूरी है तो वह भर सकता है। उस case में क्या करना चाहिए?
    • Memory-constrained environments में उपयोगी हो सकने वाला काफी साफ-सुथरा आइडिया है
      [बेशर्म promotion]: अगर hash tables में interest है तो Dandelion Hashtable [0] भी देखने लायक है
      हम इसे अपने next-generation database में इस्तेमाल कर रहे हैं, यह HPDC'24 में present हुआ था, और मौजूदा real-world use के हिसाब से सबसे तेज़ in-memory hash table है
      यह limited cacheline chaining से closed addressing को बेहतर बनाकर सामान्य servers पर प्रति सेकंड 1 billion से अधिक in-memory requests process करता है
      [0] https://dandelion-datastore.com/#dlht
    • Funnel hashing greedy है

  • Inventor की presentation: https://www.youtube.com/watch?v=ArQNyOU1hyE

    • Non-rigorous रूप में, शायद बहुत से लोगों ने पहले ही इसके बारे में सोचा होगा लेकिन इसे खास नहीं माना होगा
      यह constraints और resource की कमी में अपनाई जाने वाली resource-management trick में से एक जैसी दिखती है
      Priority के आधार पर बाँटना resource allocation में आम approach है, और यह उसी का एक variation है
      सोचता हूँ कि मैदान में लोगों ने जो दूसरी “trenches वाली tricks” अपनाई हैं, उनमें से कितनी ऐसी होंगी जिन्हें inventor खुद भी बड़ी बात नहीं मानता था, लेकिन वे व्यापक रूप से accepted चीज़ों को पलट सकती हैं। जैसे, “जब बहुत कुछ deliver करना हो तो मैंने आम तौर पर सबसे तेज़ route बनाने का एक clever तरीका खोजा...”
      बेशक उसे पहचानना, formalize करना, उस पर काम करना और paper के रूप में publish करना बड़ी मेहनत है। मैं उस credit को कम नहीं कर रहा
    • मुझे बार-बार यकीन होता जा रहा है कि papers को creator की presentation video के साथ समझना कहीं आसान होता है
      अच्छा हो कि paper में बस video presentation शामिल हो
    • Video article से बहुत बेहतर है
      हालांकि यह approach भी auxiliary arrays के जरिए memory और allocate करती है; थोड़ा अजीब लगता है कि यह सिर्फ over-allocation करके key collision की संभावना घटाने और worst case को भी कम खराब बनाने से कैसे बेहतर है

  • Paper [1] को सरसरी तौर पर देखने पर मुख्य फर्क यह लगता है कि hash table insertion algorithm पहली मिली खाली slot को greedily नहीं भरता, बल्कि उससे भी आगे search करता है
    इसे clever probing order के साथ combine करके वे साबित करते हैं कि table बहुत भरी होने पर भी खाली slot efficiently मिल जाता है
    यानी hash table कम भरी होने पर insertion धीमा हो जाता है, लेकिन आखिरी बची कुछ खाली slots कहाँ हैं यह न जानते हुए search करने वाली worst-case situation से बचता है
    [1]: https://arxiv.org/pdf/2501.02305
    यह दिलचस्प theoretical result है, लेकिन practically मुझे लगता है कि ज़रूरत से बड़ा table allocate करने वाली मौजूदा “trick” बेहतर solution होगी
    उदाहरण के लिए Rust का hashbrown जानबूझकर table का 1/8, यानी 12.5%, खाली छोड़ता है; memory थोड़ी ज्यादा लगती है, लेकिन insertion और lookup को high probability के साथ बहुत तेज़ बना देता है

    • हो सकता है मैंने algorithm गलत पढ़ा हो, लेकिन paper देखकर लगता है कि core improvement array को buckets में बाँटने और table के भरने की degree के हिसाब से अलग-अलग buckets पर focus करने वाली non-uniform strategy है
      यह approach table कम भरी होने पर भी average probe positions की संख्या बढ़ाती है
      फिर भी इस strategy के भीतर item को पहली दिखी खाली slot में ही रखा जाता है
      “Slots skip करना” hash order में आगे की तरफ jump करने से जुड़ा है
    • क्या एक hybrid संभव नहीं होगा, जिसमें कुछ समय तक greedy filling इस्तेमाल करें, और table भरने लगते ही heuristic के तौर पर अधिक sophisticated filling पर switch कर जाएँ?

  • क्या किसी के पास ‘Tiny pointers’ का simple implementation है? मेरा दिमाग proof से पहले code या pseudocode देखना पसंद करता है

  • शानदार। मैं हमेशा सोचता था कि क्या इस तरह टेबल्स को containerize करने का कोई तरीका हो सकता है
    सामान्य टेबल किसी bulk carrier जैसी होती है जिसमें सब कुछ ठूँस दिया गया हो। अगर इसे container ship की तरह बेहतर तरीके से व्यवस्थित किया जा सके, तो लगता है कि कहीं ज़्यादा चीज़ें ज़्यादा कुशलता से लादी जा सकेंगी और ज़्यादा तेज़ी से उतारी भी जा सकेंगी

    • यह आसान है
      टेबल की rows को किसी string या JSON जैसी चीज़ में बदलें, और उस variable पर base16 लागू करें, तो वह उस data की base16 string बन जाएगी
      एक hash table बनाकर उस base16 string के लिए key value सेट कर दें, तो data वाला container बन जाता है
      अब बस hexadecimal string को decode करें, तो base32 data मिल जाएगा

  • hash table के सैद्धांतिक गुण हमेशा जादू जैसे प्रभावशाली लगे हैं, और यह परिणाम उन्हें और आगे बढ़ाता है
    जो बात अजीब लगती थी वह यह थी कि intuitively data store करने का सबसे efficient तरीका लगने वाले tree से hash table इतना बेहतर कैसे हो सकता है
    मुझे यह समझ आया कि hash table theory fixed-size objects के set से deal करती है। इस fixed set के लिए hash function बनाया जाता है, और उसे vector index की तरह इस्तेमाल करके pre-allocated vector में store किया जाता है। इसी से insert, delete और lookup को O(1) के करीब करने का नुस्खा मिलता है। इसके उलट कई tree structures किसी खास size को assume नहीं करते
    समस्या यह है कि size पहले से तय करना पड़ता है, और vector लगभग भर जाए तो insertion जैसी processes धीमी हो सकती हैं
    article को सरसरी तौर पर देखने पर लगता है कि यह result उसी धीमे होने वाले हिस्से को solve करता है, और लगभग भरी हुई table में भी fast insertion संभव बनाता है
    interesting और clever है, लेकिन व्यवहार में शायद कोई बड़ा practical advance नहीं होगा। real-world में, table को clever तरीके से भरने की चिंता करने के बजाय assumed size बढ़ा देना बेहतर लगता है
    मैं यह अपनी समझ verify करने के लिए लिख रहा हूँ, इसलिए अगर गलत हूँ तो सुधार सकते हैं

    • constant-time operations के proof में table resize करने में लगने वाला time भी शामिल होता है
      जिस insertion में resize होता है, उसमें table size के linear proportion में कहीं ज़्यादा time लगता है, लेकिन वह time पहले किए गए सभी insertions पर amortize हो जाता है
      जब भी table बहुत भरने लगे, उसे पर्याप्त बड़ा कर देने से इसकी frequency धीरे-धीरे कम होती जाती है, इसलिए average में फिर भी constant time रहता है
    • trees sorted होते हैं, इसलिए subsets और ranges को scan या search करने के लिए अच्छे होते हैं, और hashmap किसी specific key तक navigate करने, यानी key-value lookup के लिए बेहतर होता है
    • यह शायद सिर्फ उस imperative दुनिया में सही है जहाँ mutation का इस्तेमाल होता है
      functional दुनिया में अभी भी trees ज़्यादा उपयुक्त होने की संभावना है
    • मोटे तौर पर, जैसा कहा गया, यह table को conceptually 2D structure में partition करने और एक “row” को लगभग 75% भरने तक भरकर फिर अगली row पर जाने का idea लगता है
      paper को पूरी तरह समझने का time नहीं मिला, लेकिन दावा है कि इस तरीके से insertions लगातार fast रहते हैं। total capacity के 75% तक तो समझ आता है, लेकिन सभी rows के 75% पर पहुँच जाने के बाद कोई दूसरा mode है या नहीं, पता नहीं
      वे lookup को भी fast बताते हैं, लेकिन lookup कैसे काम करता है या fast क्यों है, यह मैं पर्याप्त नहीं पढ़ पाया
      लगभग भरी हुई hash table फिर भी काम करे, ऐसे सच में कई अच्छे scenarios हैं। program execution के दौरान हमेशा resize करना संभव नहीं होता, और कुछ environments में memory बहुत critical होती है
      फिर भी implementation देखकर खुद हाथ आज़माना चाहूँगा। typical case में यह “worth it” है या नहीं, इसे लेकर पक्का नहीं हूँ
      cache efficiency भी शायद अच्छी न हो। अधिकतर hash tables के साथ ऐसा ही है, लेकिन काफी भरी हुई table में linear probing से पढ़ने वाला case exception है, जहाँ memory से लगातार entries निकालकर check की जा सकती हैं
      performance के लिहाज़ से इसकी value है या नहीं, अभी clear नहीं है, लेकिन यह interesting नया idea है और मैं इसे पूरी तरह समझना चाहूँगा

  • “इस नए hash table में worst-case query और insertion के लिए आवश्यक समय (log x)2 के proportional है, और x से बहुत तेज़ है” कहने के साथ-साथ “team का result immediate applications में न बदल भी सकता है” वाली बात समझ नहीं आई
    यह immediate applications में क्यों नहीं बदलेगा? क्या मतलब यह है कि real use-case analysis के जरिए pure mathematical approach से बेहतर hash implementation tune किया जा सकता है?

    • paper नहीं पढ़ा है, लेकिन कभी-कभी asymptotic improvement O() analysis से बाहर रह जाने वाले बड़े multiplicative constants के कारण वास्तविक दुनिया में improvement नहीं देता
      speedup देखने के लिए dataset को अवास्तविक रूप से बड़ा होना पड़ सकता है
    • मैं latest state के साथ बहुत up-to-date नहीं हूँ, लेकिन hash tables कुछ बार implement किए हैं, और आम तौर पर 75% भरने पर expand किया है
      तब x 4 से बड़ा नहीं होता, इसलिए O(x) को O((log x)^2) में improve करने का कोई मतलब नहीं जब x इतना छोटा हो
      memory-constrained कुछ special applications में x को बड़ा रखा जाएगा, लेकिन व्यक्तिगत तौर पर मुझे ऐसे cases नहीं मिले
    • real-world में uniform probing hash table इस्तेमाल करने वाले लोग शायद बहुत कम होंगे
      जब भी बहुत high load factor, जैसे 90% से ज़्यादा, चाहिए था, cuckoo hashing काफी रहा, और 70–80% या उससे कम पर linear probing बहुत fast और पर्याप्त अच्छा था
    • practice में worst-case operations से बचने के लिए hash table में थोड़ा extra space reserve कर दिया जाता है
      नए result की cost यह भी है कि “good case” insertions धीमे हो जाते हैं
    • complexity analysis और actual systems programming कुछ समय से अलग-अलग दिशाओं में जा रहे थे
      paper में ऐसा कुछ नहीं दिखता जो practice पर असर डाले

  • यह result hash table के लगभग भर जाने पर ही महत्वपूर्ण लगता है
    तो क्या table size को 10% बड़ा रख देना, या resizing possible हो तो थोड़ा पहले resize कर देना काफी नहीं होगा?

    • हाँ। अधिकतर real hash tables ऐसा ही करती हैं
      जब hash collision की संभावना बहुत बढ़ जाती है, तो वे खुद resize कर लेती हैं
    • real world में linear probing का standard fill ratio 75% है, और इसी पर locality भी सबसे अच्छी होती है
      table बहुत भर जाए तो बस memory को दोगुना या किसी fixed multiple से अधिक allocate करके existing items copy कर दिए जाते हैं
      ज़्यादातर non-linear probing tables, जैसे cuckoo hashing, इस fact के कारण नुकसान में रहती हैं कि RAM बिल्कुल भी “random” नहीं है

  • क्या किसी को इस implementation वाला GitHub repository पता है?