新增時(shí)

if( newTotalsize > curBucketNum) {找到能容納newTotalsize 的最近的桶個(gè)數(shù)__nif(__n > curBucketNum){則重新分配桶。 并復(fù)制舊桶中所有元素。} } 即，假設(shè)當(dāng)前桶個(gè)數(shù)為53. 當(dāng)前總元素是96個(gè)。 要插入一個(gè)時(shí)變?yōu)?7， 進(jìn)入第一個(gè)if。97個(gè)總元素時(shí)， 最近的桶個(gè)數(shù)__n也是97ul > curBucketNum， 進(jìn)入第二個(gè)if； 將當(dāng)前桶數(shù)從53擴(kuò)張到97. 類似， 當(dāng)總元素達(dá)到193時(shí)繼續(xù)擴(kuò)展到桶數(shù)為193.元素的所在桶的下標(biāo)計(jì)算方式是 hash(key)%curBucketNum。 stl中的hash_map只能加一把鎖、 加多把鎖會出現(xiàn)錯(cuò)誤【在同時(shí)插入可能引起擴(kuò)張時(shí)。】。 自實(shí)現(xiàn)的hash_map可以考慮多把鎖。static const unsigned long __stl_prime_list[_S_num_primes] ={53ul,???????? 97ul,???????? 193ul,?????? 389ul,?????? 769ul,1543ul,?????? 3079ul,?????? 6151ul,????? 12289ul,???? 24593ul,49157ul,????? 98317ul,????? 196613ul,??? 393241ul,??? 786433ul,1572869ul,??? 3145739ul,??? 6291469ul,?? 12582917ul,? 25165843ul,50331653ul,?? 100663319ul,? 201326611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul};inline unsigned long__stl_next_prime(unsigned long __n)//找到小于且最接近__n的質(zhì)數(shù)。{const unsigned long* __first = __stl_prime_list;const unsigned long* __last = __stl_prime_list + (int)_S_num_primes;const unsigned long* pos = std::lower_bound(__first, __last, __n);return pos == __last ? *(__last - 1) : *pos;}

總結(jié)

以上是生活随笔為你收集整理的hash_map 桶扩张逻辑的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。