1
SGI STL使用單獨的鏈接來實現哈希表。它包含一個桶向量，每個元素是桶列表的第一個節點鏈接。有時候，如果插入哈希表的元素太多，我們必須調整矢量的大小。但是，我們應該什麼時候調整矢量大小？SGI STL可以這樣做：比較新元素的數量與舊矢量的大小。如果前者較大，則調整矢量大小。 vector的元素只是存儲桶列表的第一個節點鏈接！但是存儲桶linklist可以包含很多元素，爲什麼它沒有考慮這個問題？STL哈希表調整大小
以下是SGI STL源代碼（來自enter link description here）：
template <class _Val, class _Key, class _HashFcn,
class _ExtractKey, class _EqualKey, class _Alloc>
class hashtable {
public:
typedef _Key key_type;
typedef _Val value_type;
typedef _HashFcn hasher;
typedef _EqualKey key_equal;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
hasher hash_funct() const { return _M_hash; }
key_equal key_eq() const { return _M_equals; }
private:
typedef _Hashtable_node<_Val> _Node;
#ifdef __STL_USE_STD_ALLOCATORS
public:
typedef typename _Alloc_traits<_Val,_Alloc>::allocator_type allocator_type;
allocator_type get_allocator() const { return _M_node_allocator; }
private:
typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator;
_Node* _M_get_node() { return _M_node_allocator.allocate(1); }
void _M_put_node(_Node* __p) { _M_node_allocator.deallocate(__p, 1); }
# define __HASH_ALLOC_INIT(__a) _M_node_allocator(__a),
#else /* __STL_USE_STD_ALLOCATORS */
public:
typedef _Alloc allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
private:
typedef simple_alloc<_Node, _Alloc> _M_node_allocator_type;
_Node* _M_get_node() { return _M_node_allocator_type::allocate(1); }
void _M_put_node(_Node* __p) { _M_node_allocator_type::deallocate(__p, 1); }
# define __HASH_ALLOC_INIT(__a)
#endif /* __STL_USE_STD_ALLOCATORS */
private:
hasher _M_hash;
key_equal _M_equals;
_ExtractKey _M_get_key;
vector<_Node*,_Alloc> _M_buckets;//Here！！！！！
size_type _M_num_elements;
請參閱私人元件_M_buckets。
和矢量調整代碼SGI STL的：
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
::resize(size_type __num_elements_hint)
{
const size_type __old_n = _M_buckets.size();
if (__num_elements_hint > __old_n) {
const size_type __n = _M_next_size(__num_elements_hint);
if (__n > __old_n) {
vector<_Node*, _All> __tmp(__n, (_Node*)(0),
_M_buckets.get_allocator());
__STL_TRY {
for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
_Node* __first = _M_buckets[__bucket];//Here！！
while (__first) {
size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
_M_buckets[__bucket] = __first->_M_next;
__first->_M_next = __tmp[__new_bucket];
__tmp[__new_bucket] = __first;
__first = _M_buckets[__bucket];
}
}
_M_buckets.swap(__tmp);
}
和易於鬥載體：
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
{
_Node* __cur = _M_buckets[__n];
if (__cur == __first)
_M_erase_bucket(__n, __last);
else {
_Node* __next;
for (__next = __cur->_M_next;
__next != __first;
__cur = __next, __next = __cur->_M_next)
;
while (__next != __last) {
__cur->_M_next = __next->_M_next;
_M_delete_node(__next);
__next = __cur->_M_next;
--_M_num_elements;
}
}
}
我們可以看到，向量的元素是第一存儲桶鏈表的節點鏈接！
我的問題是，爲什麼SGI STL這樣做？Thx！
由於現有矢量不足以容納所有新元素，因此需要重新定位以容納新元素。 –
@AlokSave vector的元素只是bucket列表中的第一個節點鏈接!!!!但linklist可以包含很多元素，爲什麼它沒有想到這個？ – XiaJun
無論如何，你指的是哪一類？ hash_map，hash_set，unordered_map，unordered_set，hash_table？哪個版本？請（a）顯示代碼或（b）鏈接到相關文檔頁 – sehe