मेरे पास फू नामक एक वर्ग है जो निजी तौर पर 4-बाइट int से अधिक कुछ नहीं है। अगर मैं इसका मान 8-बाइट size_t के रूप में लौटाता हूं, तो क्या मैं unordered_map<> या कुछ और खराब करने जा रहा हूं? मैं सभी बिट्स को return foo + foo << 32; जैसी किसी चीज़ से भर सकता था। क्या यह बेहतर होगा, या यह और भी बुरा होगा क्योंकि सभी हैश अब 0x1000000001 के गुणक हैं? या कैसे return ~foo + foo << 32; के बारे में जो सभी 64 बिट्स का उपयोग करेगा और एक सामान्य कारक भी नहीं होगा?

namespace std {
  template<> struct hash<MyNamespace::Foo> {
    typedef size_t result_type;
    typedef MyNamespace::Foo argument_tupe;
    size_t operator() (const MyNamespace::Foo& f ) const { return (size_t) f.u32InternalValue; }
  };
}
0
Swiss Frank 14 सितंबर 2020, 17:37

1 उत्तर

सबसे बढ़िया उत्तर

एक वृद्धिशील uint32_t कुंजी को uint64_t में परिवर्तित किया गया है जो अच्छी तरह से काम करती है

unordered_map क्रमशः हैश-टेबल के लिए स्थान आरक्षित करेगा।

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

// 4 Buckets example

******** ******** ******** ******** ******** ******** ******** ******XX

bucket 00 would contains keys like {0, 256, 200000 ...}
bucket 01 would contains keys like {1, 513, 4008001 ...}
bucket 10 would contains keys like {2, 130, 10002 ...}
bucket 11 would contains keys like {3, 259, 1027, 20003, ...}

यदि आप एक बकेट में अतिरिक्त मान सहेजने का प्रयास करते हैं, और यह लोड फैक्टर सीमा से अधिक हो जाता है, तो तालिका का आकार बदल दिया जाता है (उदाहरण के लिए आप 4-बकेट तालिका में 5वें तत्व को लोड_फैक्टर = 1.0 के साथ सहेजने का प्रयास करते हैं)।

फलस्वरूप:

जब तक आप 2^32-तत्व हैश-टेबल तक नहीं पहुंच जाते, तब तक uint32_t या uint64_t कुंजी होने से बहुत कम प्रभाव पड़ेगा।

क्या यह बेहतर होगा, या यह और भी बुरा होगा क्योंकि सभी हैश अब 0x1000000001 के गुणक हैं?

जब तक आप 32-बिट ओवरफ़्लो (2^32) हैश-टेबल तक नहीं पहुंच जाते, तब तक इसका कोई प्रभाव नहीं पड़ेगा।

वृद्धिशील uint32_t और uint64_t के बीच अच्छा कुंजी रूपांतरण:

key64 = static_cast<uint64>(key32);

वृद्धिशील uint32_t और uint64_t के बीच खराब कुंजी रूपांतरण:

key64 = static_cast<uint64>(key32)<<32;

सबसे अच्छा यह है कि चाबियों को यथासंभव समान रखा जाए, एक ही कारक के साथ बार-बार हैश से परहेज किया जाए। जैसे नीचे दिए गए कोड में, सभी फ़ैक्टर 7 वाली कुंजियों का तब तक टकराव होगा जब तक कि उनका आकार बदलकर 16 बकेट नहीं कर दिया जाता।

https://onlinegdb.com/r1N7TNySv

#include <iostream>
#include <unordered_map>

using namespace std;

// Print to std output the internal structure of an unordered_map.
template <typename K, typename T>
void printMapStruct(unordered_map<K, T>& map)
{
    cout << "The map has " << map.bucket_count()<< 
        " buckets and max load factor: " << map.max_load_factor() << endl;
    
    for (size_t i=0; i< map.bucket_count(); ++i)
    {
        cout << "    Bucket " << i << ": ";
        for (auto it=map.begin(i); it!=map.end(i); ++it)
        {
            cout << it->first << " ";
        }
        cout << endl;
    }
    cout << endl;
}

// Print the list of bucket sizes by this implementation
void printMapResizes()
{
    cout << "Map bucket counts:"<< endl;
    unordered_map<size_t, size_t> map;
    
    size_t lastBucketSize=0;
    for (size_t i=0; i<1024*1024; ++i)
    {
        if (lastBucketSize!=map.bucket_count())
        {
            cout << map.bucket_count() << " ";
            lastBucketSize = map.bucket_count();
        }
        map.emplace(i,i);
    }
    cout << endl;
}

int main()
{
    unordered_map<size_t,size_t> map;
    
    printMapStruct(map);
    
    map.emplace(0,0);
    map.emplace(1,1);
    printMapStruct(map);
    
    map.emplace(72,72);
    map.emplace(17,17);
    printMapStruct(map);
    
    map.emplace(7,7);
    map.emplace(14,14);
    printMapStruct(map);
    
    printMapResizes();

    return 0;
}

बकेट काउंट पर ध्यान दें:

उपरोक्त उदाहरण में, बकेट काउंट इस प्रकार है:

1 3 7 17 37 79 167 337 709 1493 3209 6427 12983 26267 53201 107897 218971 444487 902483 1832561

ऐसा लगता है कि जानबूझकर प्राइम नंबरों की एक श्रृंखला का पालन करें (टकराव को कम करना)। मुझे इसके पीछे के कार्य की जानकारी नहीं है।

std::unordered_map<>bucket_count() डिफ़ॉल्ट रीहश के बाद

1
Adrian Maire 16 सितंबर 2020, 10:45