如何進行v8源碼解析hashmap，相信很多沒有經(jīng)驗的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。

創(chuàng)新互聯(lián)長期為成百上千客戶提供的網(wǎng)站建設服務，團隊從業(yè)經(jīng)驗10年，關注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為漣水企業(yè)提供專業(yè)的網(wǎng)站建設、成都網(wǎng)站建設，漣水網(wǎng)站改版等技術服務。擁有10年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

hashmap是哈希表的實現(xiàn)。

#ifndef V8_HASHMAP_H_
#define V8_HASHMAP_H_

namespace v8 { namespace internal {


// Allocator defines the memory allocator interface
// used by HashMap and implements a default allocator.
class Allocator BASE_EMBEDDED {
public:
 virtual ~Allocator()  {}
 virtual void* New(size_t size)  { return Malloced::New(size); }
 virtual void Delete(void* p)  { Malloced::Delete(p); }
};


class HashMap {
public:
 static Allocator DefaultAllocator;

 typedef bool (*MatchFun) (void* key1, void* key2);

 // Dummy constructor.  This constructor doesn't set up the hash
 // map properly so don't use it unless you have good reason.
 HashMap();

 // initial_capacity is the size of the initial hash map;
 // it must be a power of 2 (and thus must not be 0).
 HashMap(MatchFun match,
         Allocator* allocator = &DefaultAllocator,
         uint32_t initial_capacity = 8);

 ~HashMap();

 // HashMap entries are (key, value, hash) tripplets.
 // Some clients may not need to use the value slot
 // (e.g. implementers of sets, where the key is the value).
 struct Entry {
   void* key;
   void* value;
   uint32_t hash;  // the full hash value for key
 };

 // If an entry with matching key is found, Lookup()
 // returns that entry. If no matching entry is found,
 // but insert is set, a new entry is inserted with
 // corresponding key, key hash, and NULL value.
 // Otherwise, NULL is returned.
 Entry* Lookup(void* key, uint32_t hash, bool insert);

 // Empties the hash map (occupancy() == 0).
 void Clear();

 // The number of (non-empty) entries in the table.
 uint32_t occupancy() const  { return occupancy_; }

 // The capacity of the table. The implementation
 // makes sure that occupancy is at most 80% of
 // the table capacity.
 uint32_t capacity() const  { return capacity_; }

 // Iteration
 //
 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) {
 //   ...
 // }
 //
 // If entries are inserted during iteration, the effect of
 // calling Next() is undefined.
 Entry* Start() const;
 Entry* Next(Entry* p) const;

private:
 Allocator* allocator_;
 MatchFun match_;
 Entry* map_;
 // 可分配的元素個數(shù)
 uint32_t capacity_;
 // 已分配的元素個數(shù)
 uint32_t occupancy_;
 // 數(shù)組末地址
 Entry* map_end() const  { return map_ + capacity_; }
 Entry* Probe(void* key, uint32_t hash);
 void Initialize(uint32_t capacity);
 void Resize();
};


} }  // namespace v8::internal

#endif  // V8_HASHMAP_H_


   
     
 
    
    

hashmap.cc

   
     
 
    
   
// Copyright 2008 Google Inc. All Rights Reserved.
// redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "v8.h"

#include "hashmap.h"

namespace v8 { namespace internal {

/*
 判斷x是不是有且僅有一位是1.如果是則下面的式子成立。
 假設x的第n位是1，x - 1后，n的左邊位都是0，右邊都是1，n變成0.
 00001000 => 00000111,再和x與，n以及n的右邊位是肯定為0的。右邊就看
 n的左邊的位就可以了。
*/
static inline bool IsPowerOf2(uint32_t x) {
 ASSERT(x != 0);
 return (x & (x - 1)) == 0;
}

// 內(nèi)存分配器
Allocator HashMap::DefaultAllocator;

// 默認構造函數(shù)
HashMap::HashMap() {
 allocator_ = NULL;
 match_ = NULL;
}

// 初始化屬性，分配內(nèi)存
HashMap::HashMap(MatchFun match,
                Allocator* allocator,
                uint32_t initial_capacity) {
 allocator_ = allocator;
 match_ = match;
 Initialize(initial_capacity);
}

// 析構函數(shù)，釋放內(nèi)存
HashMap::~HashMap() {
 if (allocator_) {
   allocator_->Delete(map_);
 }
}

// 查找或插入一個元素
HashMap::Entry* HashMap::Lookup(void* key, uint32_t hash, bool insert) {
 // Find a matching entry.
 // 找到key和hash對應的索引。
 Entry* p = Probe(key, hash);
 // 找到則返回
 if (p->key != NULL) {
   return p;
 }

 // No entry found; insert one if necessary.
 // 沒有找到判斷是否需要插入
 if (insert) {
   p->key = key;
   p->value = NULL;
   p->hash = hash;
   // 更新使用的元素個數(shù)
   occupancy_++;

   // Grow the map if we reached >= 80% occupancy.
   // 分配的元素過多，重新分配內(nèi)存，否則導致沖突頻繁，影響效率
   if (occupancy_ + occupancy_/4 >= capacity_) {
     Resize();
     // 重新查找對應的元素
     p = Probe(key, hash);
   }

   return p;
 }

 // No entry found and none inserted.
 return NULL;
}

//
void HashMap::Clear() {
 // Mark all entries as empty.
 // 最后一個元素的末地址
 const Entry* end = map_end();
 // 遍歷數(shù)組，清空key字段
 for (Entry* p = map_; p < end; p++) {
   p->key = NULL;
 }
 // 分配出去的元素個數(shù)為0
 occupancy_ = 0;
}

// 用于迭代
HashMap::Entry* HashMap::Start() const {
 // Next函數(shù)的for執(zhí)行了p++，所以這里要回退一個元素，見Next函數(shù)
 return Next(map_ - 1);
}


HashMap::Entry* HashMap::Next(Entry* p) const {
 // 最后一個元素的末地址
 const Entry* end = map_end();
 ASSERT(map_ - 1 <= p && p < end);
 /*
   遍歷數(shù)組，返回遇到的第一個key非空的節(jié)點，
   p++，所以初始化的時候，p指向第一個元素的第一個元素
 */
 for (p++; p < end; p++) {
   if (p->key != NULL) {
     return p;
   }
 }
 return NULL;
}

// 根據(jù)key和hash找到哈希表中可用的索引，hash值由調(diào)用方提供
HashMap::Entry* HashMap::Probe(void* key, uint32_t hash) {
 ASSERT(key != NULL);

 ASSERT(IsPowerOf2(capacity_));
 // capacity_ - 1防止溢出，實現(xiàn)回環(huán)  
 Entry* p = map_ + (hash & (capacity_ - 1));
 // 最后一個元素的末地址
 const Entry* end = map_end();
 ASSERT(map_ <= p && p < end);
 // 至少有一個非NULL，使p->key != NULL成立
 ASSERT(occupancy_ < capacity_);  // guarantees loop termination
 /*
   如果key等于空說明這個項還沒被使用，則返回，
   如果key非空，并且hash和key都匹配，則返回。
   hash值不相等或者名字不match,則查找下一個可用的元素，即開放地址法
 */
 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) {
   p++;
   // 到底了，從頭開始
   if (p >= end) {
     p = map_;
   }
 }

 return p;
}

// 申請一個Entry* 數(shù)組
void HashMap::Initialize(uint32_t capacity) {
 ASSERT(IsPowerOf2(capacity));
 map_ = reinterpret_cast(allocator_->New(capacity * sizeof(Entry)));
 if (map_ == NULL) V8::FatalProcessOutOfMemory("HashMap::Initialize");
 capacity_ = capacity;
 // 初始化內(nèi)存數(shù)據(jù)
 Clear();
}

// 擴展
void HashMap::Resize() {
 // 先保存舊地址的指針
 Entry* map = map_;
 uint32_t n = occupancy_;
 // 重新分配一個更大的數(shù)組
 // Allocate larger map.
 Initialize(capacity_ * 2);

 // Rehash all current entries.
 // 重新計算當前哈希表中的元素的位置，n的作用是遷移完n個可用退出循環(huán)了，不需要遍歷到底
 for (Entry* p = map; n > 0; p++) {
   if (p->key != NULL) {
     // 把舊的元素插入到新的數(shù)組中，因為map_更新了，里面是空的，所以會一直插入新的元素到map_
     Lookup(p->key, p->hash, true)->value = p->value;
     n--;
   }
 }
 // 釋放舊的地址
 // Delete old map.
 allocator_->Delete(map);
}


} }  // namespace v8::internal

看完上述內(nèi)容，你們掌握如何進行v8源碼解析hashmap的方法了嗎？如果還想學到更多技能或想了解更多相關內(nèi)容，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！