स्पैस हैश टेबल के पीछे मुख्य कार्यान्वयन विचार क्या है?

Question

Google स्पैरशैश ओपन-सोर्स लाइब्रेरी में दो कार्यान्वयन क्यों हैं: एक घना हैशटेबल और एक स्पैस?

Answer 1

घना हैशटेबल आपकी सामान्य पाठ्यपुस्तक हैशटेबल कार्यान्वयन है।

स्पैस हैशटेबल केवल उन तत्वों को स्टोर करता है जो वास्तव में सेट किए गए हैं, कई सरणीओं पर विभाजित हैं। विरल तालिकाओं के कार्यान्वयन में comments से उद्धृत करने के लिए:

// To store the sparse array, we store a bitmap B, where B[i] = 1 iff 
// bucket i is non-empty. Then to look up bucket i we really look up 
// array[# of 1s before i in B]. This is constant time for fixed M. 

ताकि प्रत्येक तत्व एक ओवरहेड पड़ता है:

// The idea is that a table with (logically) t buckets is divided 
// into t/M *groups* of M buckets each. (M is a constant set in 
// GROUP_SIZE for efficiency.) Each group is stored sparsely. 
// Thus, inserting into the table causes some array to grow, which is 
// slow but still constant time. Lookup involves doing a 
// logical-position-to-sparse-position lookup, which is also slow but 
// constant time. The larger M is, the slower these operations are 
// but the less overhead (slightly). 

जानने के लिए कौन सरणियों के तत्वों सेट कर रहे हैं, एक विरल तालिका एक बिटमैप शामिल केवल 1 बिट (सीमा में) का।

Answer 2

स्पैरशैश मूल्यों के लिए मैपिंग कुंजियों का एक मेमोरी-कुशल तरीका है (प्रति बिट 1-2 बिट्स)। ब्लूम फ़िल्टर आपको प्रति बिट भी कम बिट्स दे सकते हैं, लेकिन वे बाहर/शायद-अंदर के अलावा अन्य चाबियों को मान नहीं देते हैं, जो थोड़ी सी जानकारी से थोड़ा कम है।