अंतिम अद्यतन：2026-10-12

STL hashtable हैश तालिका

0.प्रस्तावना

हैश तालिका, unordered_map तथा unordered_set आदि के अंतर्निहित कंटेनर के रूप में कार्य करती है; gcc2.9 के बाद से इसका सोर्स कोड आकार काफी बढ़ गया है!

इस बार भी पढ़ा गया कोड gcc4.9.1 ही है। कोड की मात्रा बहुत अधिक है, अतः सब कुछ विस्तार से नहीं खोलेंगे; मुख्य रूप से अंतर्निहित हैशिंग की कला तथा तकनीक का अध्ययन करेंगे — लगता है ये दोनों शब्द काफी तुकबंदी करते हैं, हहा, अब मुख्य विषय में प्रवेश करते हैं~

1.Hashtable से परिचय

पहले Hashtable के सोर्स कोड पर एक नज़र डालते हैं:

template<typename _Key, typename _Value, typename _Alloc,
    typename _ExtractKey, typename _Equal,
    typename _H1, typename _H2, typename _Hash,
    typename _RehashPolicy, typename _Traits>
class _Hashtable
: 　public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
    public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,  _H1, _H2, _Hash, _RehashPolicy, _Traits>,
    public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>,
    public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,_H1, _H2, _Hash, _RehashPolicy, _Traits>,
    public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,_H1, _H2, _Hash, _RehashPolicy, _Traits>,
    private __detail::_Hashtable_alloc<typename __alloctr_rebind<_Alloc,__detail::_Hash_node<_Value,_Traits::__hash_cached::value> >::__type>
{
};

जिन्होंने क्लास टेम्प्लेट नहीं सीखा वे एकदम अनभिज्ञ हो जाएँगे — केवल टेम्प्लेट पैरामीटर गिनते ही सिर चकरा जाएगा...

और इसकी इनहेरिटेंस — एक ही बार में इतने सारे पिता (बेस क्लास) निकाल दिए...

नीचे इसके बेस क्लासों का एक-एक करके विश्लेषण करेंगे, फिर हैश तालिका पर लौटेंगे।

2._Hashtable_base

इसमें टिप्पणी इस प्रकार है:

Helper class adding management of _Equal functor to _Hash_code_base type.

हेल्पर क्लास, जो फंक्टर _Equal के प्रबंधन को _Hash_code_base में जोड़ती है।

कोड की तुलना करते ही इसका अर्थ स्पष्ट हो जाता है:

template<typename _Key, typename _Value,
    typename _ExtractKey, typename _Equal,
    typename _H1, typename _H2, typename _Hash, typename _Traits>
struct _Hashtable_base
: public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, _Traits::__hash_cached::value>,
private _Hashtable_ebo_helper<0, _Equal>
{

};

_Hash_code_base तथा _Hashtable_base की तुलना करें — दोनों में केवल एक _Equal का अंतर है; इसी से यह वाक्य समझाया जा चुका।

इसकी बेस क्लासें दो हैं:

__detail::_Hash_code_base
__detail::_Hashtable_ebo_helper

आइए इन दोनों क्लासों का और गहराई से पीछा करें!

2.1 _Hash_code_base

इस क्लास का अंतिम पैरामीटर __cache_hash_code यह दर्शाता है कि hash code कैश किया जाएगा या नहीं।

template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash,bool __cache_hash_code>
struct _Hash_code_base;

कैश किए जाने या न होने के आधार पर, इसके पार्शियल स्पेशलाइज़्ड संस्करण प्राप्त होते हैं:

• रेंज हैशिंग का उपयोग (वास्तव में वही, जिसे हम सामान्यतः मॉड्यूलो-विभाजन विधि कहते हैं), hash code कैश नहीं।

template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
: private _Hashtable_ebo_helper<0, _ExtractKey>,
private _Hashtable_ebo_helper<1, _Hash>
}

- रेंज हैशिंग का उपयोग (वास्तव में वही, जिसे हम सामान्यतः मॉड्यूलो-विभाजन विधि कहते हैं), hash code कैश करते हुए।

इस पार्शियल स्पेशलाइज़ेशन के लिए कैशिंग आवश्यक नहीं है, इसलिए कोड में केवल घोषणा (declaration) है, परिभाषा (definition) नहीं!

template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;

- हैश फंक्शन तथा रेंज हैश फंक्शन दोनों मौजूद, hash code कैश नहीं।

template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
_Default_ranged_hash, false>
: private _Hashtable_ebo_helper<0, _ExtractKey>,
private _Hashtable_ebo_helper<1, _H1>,
private _Hashtable_ebo_helper<2, _H2>
{
};

- उपरोक्त वाले का hash code कैश करने वाला रूप

template<typename _Key, typename _Value, typename _ExtractKey,
    typename _H1, typename _H2>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
            _Default_ranged_hash, true>
: private _Hashtable_ebo_helper<0, _ExtractKey>,
    private _Hashtable_ebo_helper<1, _H1>,
    private _Hashtable_ebo_helper<2, _H2>
{

उपरोक्त _H1 तथा _H2 से आप निश्चित रूप से भ्रमित होंगे, नीचे देखिए:

(1) Default range hashing function (डिफ़ॉल्ट रेंज हैश फंक्शन)

h1=hash<key>

नीचे वाला यही है:

h2(h1(key),N)=h1(key)%N

विस्तृत विवरण आगे देखा जा सकता है।

struct _Mod_range_hashing
{
    typedef std::size_t first_argument_type;
    typedef std::size_t second_argument_type;
    typedef std::size_t result_type;

    result_type
    operator()(first_argument_type __num,
            second_argument_type __den) const noexcept
    { return __num % __den; }
};

भले ही इसे struct से परिभाषित किया गया है, लोग इसे क्लास समझेंगे — वास्तव में इसमें () ऑपरेटर ओवरलोड किया गया है, अतः यह एक फंक्टर (functor) ही है।

ऊपर का तत्व हैश तालिका डेटा स्ट्रक्चर में उसी से मेल खाता है जिसे हम सब जानते हैं — विखंडन फंक्शन (hash function): मॉड्यूलो-विभाजन विधि।

f(__num) = __num mod __den(__den<=__num)

इसके बाद, _Default_ranged_hash:

struct _Default_ranged_hash { };

यह केवल एक मार्कर के रूप में है — डिफ़ॉल्ट रूप से पूर्व-गणनीत रेंज हैश फंक्शन (Default ranged hash function):

h(k, N) = h2(h1(k), N),

अतः यहाँ तक अंतर्निहित हैश तालिका का विखंडन फंक्शन स्पष्ट है — डिफ़ॉल्ट रूप में यही होता है। और अभी उल्लिखित मार्कर इसलिए आया क्योंकि टाइप H1 तथा H2 के ऑब्जेक्ट्स को मिलाकर H बनाने में अतिरिक्त कॉपी ऑपरेशन खर्च होता है, इसीलिए यह मार्कर पेश किया गया।

इस प्रकार ऊपर उल्लिखित _H1 तथा _H2 की व्याख्या पूरी हुई — ये क्रमशः उपरोक्त दोनों फंक्शन्स से संगत हैं।

(2) rehash ऑपरेशन

इसके तुरंत बाद एक अन्य महत्वपूर्ण चीज़ है जिसे rehash कहते हैं। आप rehash को अच्छी तरह जानते होंगे — जब हैश तालिका में टकराव एक निश्चित स्तर तक पहुँच जाता है, तो key को पुनः उचित स्थान पर रखने की आवश्यकता होती है। हैश तालिका का अंतर्निहित सोर्स कोड भी यही करता है — यहाँ इसे एक rehash policy में लपेटा गया है:

struct _Prime_rehash_policy
{
   //...
};

rehash ऑपरेशन में उल्लेख है: बकेट का आकार (bucket size) डिफ़ॉल्ट रूप से प्रायः न्यूनतम अभाज्य संख्या होता है, ताकि लोड फैक्टर (load factor — कंटेनर के वर्तमान एलिमेंट्स की संख्या तथा बकेट्स की संख्या का अनुपात) पर्याप्त छोटा रहे। लोड फैक्टर हैश तालिका के भरे होने की मात्रा को मापता है; अधिकतम लोड फैक्टर का डिफ़ॉल्ट मान 1.0 है.

_Prime_rehash_policy(float __z = 1.0)
: _M_max_load_factor(__z), _M_next_resize(0) { }


> rehash计算下一个素数桶

जब हैश टकराव होता है, तब rehash कैसे होता है?

 inline std::size_t
_Prime_rehash_policy::
_M_next_bkt(std::size_t __n) const
{
    const unsigned long* __p = std::lower_bound(__prime_list, __prime_list + _S_n_primes, __n);
    _M_next_resize = 
        static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
return *__p;
}

हैश टकराव होने पर यह फंक्शन n से छोटी न होने वाली एक अभाज्य संख्या लौटाता है, जो अगला बकेट बनती है।

अभाज्य संख्याओं की तालिका

अभाज्य संख्या कैसे खोजी जाती है? ऊपर एक __prime_list दिखा, तो उसे खोजने निकले — libstdc++v3/src/shared/hashtable-aux.cc में सभी अभाज्य संख्याओं की तालिका मिल गई। इसमें कुल 256+1+49 या 256+49 प्रविष्टियाँ हैं। यदि sizeof(unsigned long)!=8 है तो 256+1+49, अन्यथा 256+49।

extern const unsigned long __prime_list[] = // 256 + 1 or 256 + 48 + 1
  {
    2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
    37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
    83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul，
    // 后面还有很多
  }

अतः सब कुछ बिल्कुल स्पष्ट है: lower_bound द्वारा उपरोक्त तालिका में दिए गए मान n से बड़ी या बराबर पहली अभाज्य संख्या खोजी जाती है।

enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };

एलिमेंट के संगत बकेट की गणना

अधिकतम लोड फैक्टर से न्यूनतम बकेट्स की गणना की जाती है, फिर बकेट्स के आधार पर प्रत्येक एलिमेंट के संगत न्यूनतम अभाज्य बकेट की गणना होती है।

inline std::size_t
_Prime_rehash_policy::
_M_bkt_for_elements(std::size_t __n) const
{
    // 获取最小的桶
    const float __min_bkts = __n / _M_max_load_factor;
    // 获取最小素数p
    const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
                        + _S_n_primes, __min_bkts);
    _M_next_resize =
        static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
    return *__p;
}

_Hashtable_ebo_helper वही EBO खाली बेस क्लास है जिसे हमने पहले सीखा था।

_Map_base मुख्यतः पार्शियल स्पेशलाइज़ेशन के माध्यम से ऑपरेटर [] तथा at के ओवरलोड कार्यान्वित करता है।

｀_Insert｀ मुख्यतः इंसर्शन संबंधी कार्य पूरे करता है।

｀_Rehash_base｀ मुख्यतः उपरोक्त rehash में अधिकतम लोड फैक्टर मान का संचरण पूरा करता है।

｀_Equality_base｀ मुख्यतः क्लास _Equality को सार्वजनिक टाइप्स तथा फंक्शन्स प्रदान करता है।

अब तक _Hashtable द्वारा इनहेरिट की गई उपरोक्त सभी क्लासों की व्याख्या पूरी हो चुकी है।

2.hashtable में लिंक्ड लिस्ट का नोड स्ट्रक्चर

hash node की बेस क्लास — इसमें केवल पॉइंटर की घोषणा शामिल है।

struct _Hash_node_base
{
    _Hash_node_base* _M_nxt;

    _Hash_node_base() noexcept : _M_nxt() { }

    _Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { }
};

नोड मान रखने वाली क्लास उपरोक्त बेस क्लास को इनहेरिट करती है

template<typename _Value>
struct _Hash_node_value_base : _Hash_node_base
{
    typedef _Value value_type;

    __gnu_cxx::__aligned_buffer<_Value> _M_storage;

    _Value*
    _M_valptr() noexcept
    { return _M_storage._M_ptr(); }

    const _Value*
    _M_valptr() const noexcept
    { return _M_storage._M_ptr(); }

    _Value&
    _M_v() noexcept
    { return *_M_valptr(); }

    const _Value&
    _M_v() const noexcept
    { return *_M_valptr(); }
};

पहले उल्लेख हुआ था कि नोड में hash code होगा या नहीं; अतः नोड में hash code रहना चाहिए, और उसका विशिष्ट कार्यान्वयन नीचे है:

/**
*  Primary template struct _Hash_node.
*/
template<typename _Value, bool _Cache_hash_code>
struct _Hash_node;

/**
*  Specialization for nodes with caches, struct _Hash_node.
*
*  Base class is __detail::_Hash_node_value_base.
*/
template<typename _Value>
struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value>
{
    std::size_t  _M_hash_code;

    _Hash_node*
    _M_next() const noexcept
    { return static_cast<_Hash_node*>(this->_M_nxt); }
};

/**
*  Specialization for nodes without caches, struct _Hash_node.
*
*  Base class is __detail::_Hash_node_value_base.
*/
template<typename _Value>
struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value>
{
    _Hash_node*
    _M_next() const noexcept
    { return static_cast<_Hash_node*>(this->_M_nxt); }
};

यहाँ तक बात एकदम स्पष्ट है: नोड दो प्रकार के होते हैं — hash code सहित तथा उसके बिना; पास किए गए टेम्प्लेट पैरामीटर के अनुसार संगत पार्शियल स्पेशलाइज़्ड संस्करण कॉल होता है।

3.इटरेटर

इटरेटर बेस क्लास using सिंटैक्स का उपयोग दिखाती है — यह सिंटैक्स typedef जैसा है; आगे की परिभाषाओं में सीधे __node_type सिंटैक्स से परिभाषित किया जा सकता है। _M_incr फंक्शन लिंक्ड लिस्ट का अगला नोड प्राप्त करता है।

/// Base class for node iterators.
template<typename _Value, bool _Cache_hash_code>
struct _Node_iterator_base
{
    using __node_type = _Hash_node<_Value, _Cache_hash_code>;

    __node_type*  _M_cur;

    _Node_iterator_base(__node_type* __p) noexcept
    : _M_cur(__p) { }

    void
    _M_incr() noexcept
    { _M_cur = _M_cur->_M_next(); }
};

नोड इटरेटर: नीचे के कोड के अध्ययन से दो बातें सीखने को मिलती हैं: - पहला: using का उपयोग - hashtable का इटरेटर forward_iterator श्रेणी का है - ++, --, *, -> ये चार ऑपरेटर ओवरलोड किए गए हैं

template<typename _Value, bool __constant_iterators, bool __cache>
struct _Node_iterator
: public _Node_iterator_base<_Value, __cache>
{
private:
    using __base_type = _Node_iterator_base<_Value, __cache>;
    using __node_type = typename __base_type::__node_type;

public:
    typedef _Value                  value_type;
    typedef std::ptrdiff_t              difference_type;
    typedef std::forward_iterator_tag           iterator_category;

    using pointer = typename std::conditional<__constant_iterators,
                    const _Value*, _Value*>::type;

    using reference = typename std::conditional<__constant_iterators,
                        const _Value&, _Value&>::type;

    _Node_iterator() noexcept
    : __base_type(0) { }

    explicit
    _Node_iterator(__node_type* __p) noexcept
    : __base_type(__p) { }

    reference
    operator*() const noexcept
    { return this->_M_cur->_M_v(); }

    pointer
    operator->() const noexcept
    { return this->_M_cur->_M_valptr(); }

    _Node_iterator&
    operator++() noexcept
    {
        this->_M_incr();
        return *this;
    }

    _Node_iterator
    operator++(int) noexcept
    {
        _Node_iterator __tmp(*this);
        this->_M_incr();
        return __tmp;
    }
};

4.hashtable के महत्वपूर्ण आंतरिक स्ट्रक्चर का सूक्ष्म अध्ययन

आंतरिक स्ट्रक्चर इस प्रकार है: प्रत्येक एलिमेंट में एक सिंगल लिंक्ड लिस्ट रखी जाती है, और उसी लिस्ट पर एलिमेंट्स के इंसर्शन, खोज तथा डिलीशन जैसे ऑपरेशन किए जाते हैं। प्रत्येक एलिमेंट को बकेट (bucket) कहा जाता है। निर्माण के समय अंतर्निहित रूप से पहले H1 से key का hash code निकाला जाता है, फिर मॉड्यूलो-विभाजन विधि H2 द्वारा उसका संगत बकेट प्राप्त किया जाता है।

template<typename _Key, typename _Value, typename _Alloc,
    typename _ExtractKey, typename _Equal,
    typename _H1, typename _H2, typename _Hash,
    typename _RehashPolicy, typename _Traits>
class _Hashtable
private:
    __bucket_type*      _M_buckets;  //_ Hash_node_base *
    size_type           _M_bucket_count;    // bucket 节点个数
    __node_base     _M_before_begin;    // _NodeAlloc::value_type
    size_type           _M_element_count;   // //hashtable中list节点个数
    _RehashPolicy       _M_rehash_policy;  // rehash策略
    __bucket_type       _M_single_bucket;  // 只需要一个桶用
};

hashtable के कुछ महत्वपूर्ण फंक्शन्स:

begin फंक्शन

iterator
begin() noexcept
{ return iterator(_M_begin()); }

_M_begin कॉल होता है:

_M_before_begin को एक head नोड की तरह सोच सकते हैं — पहला नोड उसका अगला नोड ही है।

__node_type*
_M_begin() const
{ return static_cast<__node_type*>(_M_before_begin._M_nxt); }

end फंक्शन

चूँकि यह सिंगल लिंक्ड लिस्ट है, अंतिम लौटा देना ही पर्याप्त है।

iterator
end() noexcept
{ return iterator(nullptr); }

size तथा empty फंक्शन

size_type
size() const noexcept
{ return _M_element_count; }

bool
empty() const noexcept
{ return size() == 0; }

बकेट्स की संख्या

size_type
bucket_count() const noexcept
{ return _M_bucket_count; }

लोड फैक्टर की गणना

वर्तमान एलिमेंट्स की संख्या को बकेट्स की संख्या से भाग देना

float
load_factor() const noexcept
{
    return static_cast<float>(size()) / static_cast<float>(bucket_count());
}

बकेट के index की गणना

पास किए गए key से बकेट का index प्राप्त किया जाता है।

size_type
bucket(const key_type& __k) const
{ return _M_bucket_index(__k, this->_M_hash_code(__k)); }

_Hash_code_base में निम्नलिखित कार्यान्वयन है:

और _M_h1 जो लौटाता है वह _H1 है; जब यह न पता हो कि _H1 क्या है, तो unordered_map में खोजने पर पता चलता है कि _Hash=hash<_Key> है। इसलिए नीचे का फंक्शन गणितीय रूप में यह है: h1(k) द्वारा hash code प्राप्त किया जाता है।

बकेट का hash code लौटाता है।

__hash_code
_M_hash_code(const _Key& __k) const
{ return _M_h1()(__k); }

बकेट का index लौटाता है।

_M_bucket_index की परिभाषा उसी फ़ाइल में आगे मिलती है:

size_type
_M_bucket_index(const key_type& __k, __hash_code __c) const
{ return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }

हम __hash_code_base में _M_bucket_index खोजते रहते हैं, और उसे bits/hashtable_policy.h में पाया जा सकता है:

std::size_t
_M_bucket_index(const _Key&, __hash_code __c,
        std::size_t __n) const
{ return _M_h2()(__c, __n); }

उपरोक्त h1 की खोज की तरह, unordered_map में पाया जा सकता है कि _H2 डिफ़ॉल्ट रूप से _Mod_range_hashing अपनाता है; अब इसका सोर्स कोड देखिए:

struct _Mod_range_hashing
{
    typedef std::size_t first_argument_type;
    typedef std::size_t second_argument_type;
    typedef std::size_t result_type;

    result_type
    operator()(first_argument_type __num,
            second_argument_type __den) const noexcept
    { return __num % __den; }
};

संगत गणितीय रूप h2(c,n) है।

अतः उपरोक्त bucket द्वारा बकेट का index प्राप्त करने का संगत गणितीय रूप है:

h(k,hash(k))=h(k,hash(k),n)=h(k,hash(k)%n)

जो वास्तव में अंततः यही है:

hash(k)%n

यही बकेट के index की गणना है।

संबंधित विषय

• STL array सोर्स कोड विश्लेषण | C++那些事
• STL string गहन विश्लेषण | C++那些事
• STL string इंटरव्यू प्रश्न विस्तृत व्याख्या | C++那些事
• STL deque सोर्स कोड विश्लेषण | C++那些事
• STL खाली बेस क्लास ऑप्टिमाइज़ेशन EBO | C++那些事
• STL स्वहस्त लिखी हैश तालिका कार्यान्वयन | C++那些事
• STL इटरेटर सोर्स कोड विश्लेषण | C++那些事
• STL list सोर्स कोड विश्लेषण | C++那些事
• STL map तथा multimap | C++那些事
• STL queue तथा stack सोर्स कोड विश्लेषण | C++那些事

टिप्पणियाँ