看到這個(gè)題目，可能有些人會覺得奇怪——Object不是JS的基本數(shù)據(jù)類型么，有什么實(shí)現(xiàn)不實(shí)現(xiàn)的呢?如果你這么想的話，說明你沒有接觸過其它語言，一直都是在和JS打交道，編程世界那么大，你沒有出去看一看。C/C++/Java等語言是沒有這種json的數(shù)據(jù)類型的，其它一些有的：如在Pthyon里面叫做字典，在Ruby/Perl里面叫散列表，當(dāng)然這只是個(gè)名稱而已，本質(zhì)上可以當(dāng)作json類型。而C是“萬物之母”，C里面沒有的，就得通過某種方式實(shí)現(xiàn)。

并且JS里面的Object是如何查找屬性的，這個(gè)問題有人說是通過遍歷key的字符串查找的，也有人說是通過哈希查找的。究竟它是怎么存儲和查找的，能不能把Object當(dāng)作一個(gè)map來使用?如果無法從源碼的角度實(shí)際地看一下瀏覽器的實(shí)現(xiàn)，你的觀點(diǎn)可能就站不住腳，只能人云亦云。

Chrome自行開發(fā)了V8引擎，并被Node拿去當(dāng)解析器。本文將通過V8的源碼嘗試分析Object的實(shí)現(xiàn)。

1. V8的代碼結(jié)構(gòu)

v8的源碼位于 src/v8/src/ ，代碼層級相對比較簡單，但是實(shí)現(xiàn)比較復(fù)雜，為了能看懂，需要找到一個(gè)切入點(diǎn)，通過打斷點(diǎn)、加log等方式確定這個(gè)切入點(diǎn)是對的，如果這個(gè)點(diǎn)并不是關(guān)鍵的點(diǎn)，進(jìn)行到某一步的時(shí)候就斷了，那么由這個(gè)點(diǎn)出發(fā)嘗試去找其它的點(diǎn)。不斷驗(yàn)證，***找到一個(gè)最關(guān)鍵的地方，由這個(gè)地方由淺入深地?cái)U(kuò)展到其它地方，***形成一個(gè)體系。

以下，先說明JS Object的類圖。

2. JS Object類圖

V8里面所有的數(shù)據(jù)類型的根父類都是Object，Object派生HeapObject，提供存儲基本功能，往下的JSReceiver用于原型查找，再往下的JSObject就是JS里面的Object，Array/Function/Date等繼承于JSObject。左邊的FixedArray是實(shí)際存儲數(shù)據(jù)的地方。

3. 創(chuàng)建JSObject

在創(chuàng)建一個(gè)JSObject之前，會先把讀到的Object的文本屬性序列化成 constant_properties ，如下的data：

 

var data = {  
name: "yin",  
age: 18,  
"-school-": "high school"  
}; 

會被序列成：

 

../../v8/src/runtime/runtime-literals.cc 72 constant_properties:  
0xdf9ed2aed19: [FixedArray]  
– length: 6  
[0]: 0x1b5ec69833d1  
[1]: 0xdf9ed2aec51  
[2]: 0xdf9ed2aec71  
[3]: 18  
[4]: 0xdf9ed2aec91  
[5]: 0xdf9ed2aecb1  

它是一個(gè)FixedArray，一共有6個(gè)元素，由于data總共是有3個(gè)屬性，每個(gè)屬性有一個(gè)key和一個(gè)value，所以Array就有6個(gè)。***個(gè)元素是***個(gè)key，第二個(gè)元素是***個(gè)value，第三個(gè)元素是第二個(gè)key，第四個(gè)元素是第二個(gè)key，依次類推。Object提供了一個(gè)Print()的函數(shù)，把它用來打印對象的信息非常有幫助。上面的輸出有兩種類型的數(shù)據(jù)，一種是String類型，第二種是整型類型的。

FixedArray是V8實(shí)現(xiàn)的一個(gè)類似于數(shù)組的類，它表示一段連續(xù)的內(nèi)存，上面的FixedArray的length = 6，那么它占的內(nèi)存大小將是：

length * kPointerSize 

因?yàn)樗娴亩际菍ο蟮闹羔?或者直接是整型數(shù)據(jù)類型，如上面的18)，在64位的操作系統(tǒng)上，一個(gè)指針為8個(gè)字節(jié)，它的大小將是48個(gè)字節(jié)。它記錄了一個(gè)初始的內(nèi)存開始地址，使用元素index乘以指針大小作為偏移，加上開始地址，就可以取到相應(yīng)index的元素，這和數(shù)組是一樣的道理。只是V8自己封裝了一個(gè)，方便添加一些自定義的函數(shù)。

FixedArray主要用于表示數(shù)據(jù)的存儲位置，在它上面還有一個(gè)Map，這個(gè)Map用于表示數(shù)據(jù)的結(jié)構(gòu)。這里的Map并不是哈希的意思，更接近于地圖的意義，用來操作FixedArray表示的這段內(nèi)存。V8根據(jù) constant_properties的 length，去開辟相應(yīng)大小空間的Map：

 

Handle map = ComputeObjectLiteralMap(context, constant_properties,  
&is_result_from_cache); 

把這個(gè)申請后的Map打印出來：

 

../../v8/src/heap/heap.cc 3472 map is  
0x21528af9cb39: [Map]  
– type: JS_OBJECT_TYPE  
– instance size: 48  
– inobject properties: 3  
– back pointer: 0x3e2ca8902311  
– instance descriptors (own) #0: 0x3e2ca8902231  

從第4行加粗字體可以看到，它的大小確實(shí)和我們算的一樣。并且它還有一個(gè)叫做descriptors表示它的數(shù)據(jù)結(jié)構(gòu)。descriptor記錄了每個(gè)key-value對，以及它們在FixedArray里面的index. 后續(xù)對properties的操作基本上通過descriptor進(jìn)行。

有了這個(gè)map的對象之后，用它來創(chuàng)建一個(gè)JSObect：

 

Handle boilerplate =  
isolate->factory()->NewJSObjectFromMap(map, pretenure_flag); 

重新開辟一段內(nèi)存，把map的內(nèi)容拷過去。

由于map只是一段相應(yīng)大小的內(nèi)存空間，它的內(nèi)容是空的，所以接下來要設(shè)置它的properties：

 

for (int index = 0; index < length; index += 2) { 
  Handle<Object> key(constant_properties->get(index + 0)); 
  Handle<Object> value(constant_properties->get(index + 1)); 
  Handle<String> name = Handle<String>::cast(key); 
  JSObject::SetOwnPropertyIgnoreAttributes(boilerplate, name, 
                                          value, NONE); 
} 

通過上面的代碼，把properties設(shè)置到map的FixedArray里面，并且可以通過index用descriptors迅速地取出key-value。由于這個(gè)過程比較復(fù)雜，細(xì)節(jié)不展開討論。

在設(shè)置properties的同時(shí)，會初始化一個(gè)searchCache，這個(gè)cache支持哈希查找某個(gè)屬性。

4. 字符串哈希查找

在設(shè)置cache的時(shí)候，會先進(jìn)行查找是否已存在相同的屬性名，如果已經(jīng)有了就把它的value值覆蓋掉，否則把它添加到cache里面：

 

int DescriptorArray::SearchWithCache(Isolate* isolate, Name* name, Map* map) { 
  DescriptorLookupCache* cache = isolate->descriptor_lookup_cache(); 
  //找到它的index 
  int number = cache->Lookup(map, name); 
  //如果沒有的話 
  if (number == DescriptorLookupCache::kAbsent) { 
    //通過遍歷找到它的index 
    number = Search(name, number_of_own_descriptors); 
    //更新cache 
    cache->Update(map, name, number); 
  } 
  return number; 
} 

如上代碼的注釋，我們先來看一下這個(gè)Search函數(shù)是怎么進(jìn)行的：

template <SearchModesearch_mode, typename T> 
int Search(T* array, Name* name, int valid_entries, int* out_insertion_index) { 
  // Fast case: do linear search for small arrays. 
  const int kMaxElementsForLinearSearch = 8; 
  if (valid_entries <= kMaxElementsForLinearSearch) { 
    return LinearSearch<search_mode>(array, name, valid_entries, 
                                    out_insertion_index); 
  }   
  // Slow case: perform binary search. 
  return BinarySearch<search_mode>(array, name, valid_entries, 
                                  out_insertion_index); 
} 

 

如果屬性少于等于8個(gè)時(shí)，則直接線性查找即依次遍歷，否則進(jìn)行二分查找，在線性查找里面判斷是否相等，是用的內(nèi)存地址比較：

 

for (int number = 0; number < valid_entries; number++) { 
  if (array->GetKey(number) == name) return number; 
} 

因?yàn)閚ame都是用的上面第三點(diǎn)設(shè)置Map的時(shí)候傳進(jìn)來的name，因此初始化的時(shí)候相同的name都指向同一個(gè)對象。所以可以直接用內(nèi)存地址進(jìn)行比較，得到FixedArray的索引number。然后用key和number去update cache：

cache->Update(map, name, number); 

重點(diǎn)在于這個(gè)update cache。這個(gè)cache的數(shù)據(jù)結(jié)構(gòu)是這樣的：

 

static const int kLength = 64;  
struct Key {  
Map* source;  
Name* name;  
};  
Keykeys_[kLength];  
int results_[kLength]; 

它有一個(gè)數(shù)組keys_的成員變量存放key，這個(gè)數(shù)組的大小是64，數(shù)組的索引用哈希算出來，不同的key有不同的哈希，這個(gè)哈希就是它在數(shù)組里面的索引。它還有一個(gè)results_，存放上面線性查找出來的number，這個(gè)number就是內(nèi)存里面的偏移，有了這個(gè)偏移就可以很快地定位到它的內(nèi)容，所以放到results里面.

關(guān)鍵在于這個(gè)哈希是怎么算的。來看一下update的函數(shù)：

 

void DescriptorLookupCache::Update(Map* source, Name* name, int result) { 
  int index = Hash(source, name); 
  Key& key = keys_[index]; 
  key.source = source; 
  key.name = name; 
  results_[index] = result; 
} 

先計(jì)算哈希索引index，然后把數(shù)據(jù)存到results_和keys_這兩個(gè)數(shù)組的index位置。這個(gè)Hash函數(shù)是這樣的：

int DescriptorLookupCache::Hash(Object* source, Name* name) { 
  // Uses only lower 32 bits if pointers are larger. 
  uint32_tsource_hash = 
      static_cast<uint32_t>(reinterpret_cast<uintptr_t>(source)) >> 
      kPointerSizeLog2; 
  uint32_tname_hash = name->hash_field(); 
  return (source_hash ^ name_hash) % kLength; 
} 

先計(jì)算map和key的hash，map的hash即source_hash是用map的地址的低32位，為了統(tǒng)一不同指針大小的區(qū)別，而計(jì)算key的hash即name_hash，最核心的代碼應(yīng)該是以下幾行：

 

uint32_tStringHasher::AddCharacterCore(uint32_trunning_hash, uint16_t c) {  
running_hash += c;  
running_hash += (running_hash << 10);  
running_hash ^= (running_hash >> 6);  
return running_hash;  
} 

依次循環(huán)name的每個(gè)字符串做一些位運(yùn)算，結(jié)果累計(jì)給running_hash.

source_hash是用map的內(nèi)存地址，因?yàn)檫@個(gè)地址是唯一的，而name_hash是用的字符串的內(nèi)容，只要字符串一樣，那么它的hash值就一定一樣，這樣保證了同一個(gè)object，它的同個(gè)key值的索引值就一定一樣。source_hash和name_hash***異或一下，模以kLength = 64得到它在數(shù)組里面的索引。

這里自然而然會有一個(gè)問題，通過這樣的計(jì)算不能夠保證不同的name計(jì)算出來的哈希值一定不一樣，好的哈希算法只能讓結(jié)果盡可能隨機(jī)，但是無法做到一定不重復(fù)，所以這里也有同樣的問題。

先來看一下，它是怎么查找的：

 

int DescriptorLookupCache::Lookup(Map* source, Name* name) {  
int index = Hash(source, name);  
Key& key = keys_[index];  
if ((key.source == source) && (key.name == name)) return results_[index];  
return kAbsent;  
} 

先用同樣的哈希算法，算出同樣的index，取出key里面的map和name，和存儲的map和name進(jìn)行比較，如果相同則說明找到了，否則的話返回不存在-1的標(biāo)志。一旦不存在了又會執(zhí)行上面的update cache，先調(diào)Search找到它的偏移index作為result，如果index存在重新update cache。所以上面的問題就可以得到解答了，重復(fù)的哈希索引覆蓋了***個(gè)，導(dǎo)致查找***個(gè)的時(shí)候沒找找到，所以又去重新update，把那個(gè)索引值的數(shù)組元素又改成了***個(gè)的。因此，如果兩個(gè)重復(fù)的元素如果循環(huán)輪流訪問的話，就會造成不斷地查找index，不斷地更新搜索cache。但是這種情況還是比較少的。

如何保證傳進(jìn)來的具有相同字符串的name和原始的name是同一個(gè)對象，從而才能使它們的內(nèi)存地址一樣?一個(gè)辦法是維護(hù)一個(gè)Name的數(shù)據(jù)池，據(jù)有相同字符串的name只能存在一個(gè)。

上面的那個(gè)data它的三個(gè)name的index在筆者電腦上實(shí)驗(yàn)計(jì)算結(jié)果為：

• #name hash index = 62
• #age hash index = 32
• #-school- hash index = 51

有一個(gè)比較奇怪的地方是重復(fù)實(shí)驗(yàn)，它們的哈希值都是一樣的。并且具有相同屬性且順序也相同的object，它們的map地址就是一樣的。

如果一個(gè)元素的屬性值超過64個(gè)呢?那也是同樣的處理，后面設(shè)置的會覆蓋前面設(shè)置的。學(xué)過哈希的都知道，當(dāng)元素的個(gè)數(shù)大于容器容量的一半時(shí)，重復(fù)的概率將會大大增加。所以一個(gè)object的屬性的比較優(yōu)的***大小為32。一旦超過32，在一個(gè)：

 

for(var keyin obj){  
obj[key] //do sth.  
} 

for循環(huán)里面，這種查找的開銷將會很大。

那為什么它要把長度設(shè)置成64呢，如果改大了，不就可以減少重復(fù)率?但是這樣會造成更多的內(nèi)存消耗，即使一個(gè)Object只有一個(gè)屬性，它也會初始化一個(gè)這么大的數(shù)組，對于這種屬性比較少的object來說就很浪費(fèi)。所以取64，應(yīng)該是一個(gè)比較適中的值。

同時(shí)另一方面，經(jīng)常使用的那幾個(gè)屬性還是能夠很快通過哈希計(jì)算定位到它的內(nèi)容。并且這種場景還是很常見的，如獲取數(shù)組元素的lengh.

根據(jù)上面的討論，將Object當(dāng)作map來使用，并不是很合適，在如下的代碼里面：

 

var data = [10001, 10002/* 很多個(gè)元素 */]; 
var keys = { 
    "1000a": '' 
    "1000b": '' 
    /* 很多個(gè)屬性 */ 
} 
var exists = []; 
for(var i = 0; i < data.length; i++){ 
    if(typeof keys[data[i]] !== "undefined"){ 
        exists.push(data[i]); 
    } 
} 

由于在keys查找時(shí)，可能會存在大量沒有的元素，這樣就導(dǎo)致它哈希查找沒有找到，然后需要進(jìn)行線性查找/二分查找，結(jié)果也沒找到。所以它和哈希map還是有很多的差別的。這樣的效率雖然比不上直接使用一個(gè)哈希map，但至少它的效率要比寫一個(gè)數(shù)組，然后一個(gè)個(gè)去比較來得高效，怎么說它還是用的內(nèi)存地址進(jìn)行二分查找。

這里就體現(xiàn)了ES6新增了Map/Set類型的價(jià)值，它是一個(gè)真正的哈希Map。如果不能使用ES6的map，那么自行實(shí)現(xiàn)一個(gè)或者使用第三方的庫也是可取的。

在說Map之前，Object還有數(shù)字類型的屬性沒有討論。

5. 數(shù)字索引哈希查找

假設(shè)data變成：

 

var data = { 
       name: "yin", 
       age: 18, 
       "-school-": "high school", 
       1: "Monday", 
       2: "Thuesday", 
       "3": "Wednesday" 
   }; 

把生成的data Object打印出來是這樣的：

 

../../v8/src/runtime/runtime-literals.cc 105 boilerplate obj:  
0x3930221af3a9: [JS_OBJECT_TYPE]  
– map = 0x6712e19cc41 [FastProperties]  
– prototype = 0x27d71d20f19  
– elements = 0x2e1e1a56b579 [FAST_HOLEY_ELEMENTS]  
– properties = 0x2c2a4d782241 {  
#name: 0x3930221aec51 (data field at offset 0)  
#age: 18 (data field at offset 1)  
#-school-: 0x3930221aecb1 (data field at offset 2)  
}  
– elements = {  
0: 0x2c2a4d782351  
1: 0x3930221aecf9  
2: 0x3930221aed39  
3: 0x3930221aed79 
4-18: 0x2c2a4d782351  
} 

那些key為數(shù)字的存放在elements的數(shù)據(jù)結(jié)構(gòu)里面，elements和properties的區(qū)別在于——elements有獨(dú)立的一個(gè)哈希表，并且它不是覆蓋存放的，它會根據(jù)哈希值算元素的數(shù)組索引，判斷如果當(dāng)前索引已經(jīng)存在元素，則一直找到下一個(gè)空的位置來存放它：

 

uint32_tcapacity = Capacity(); 
 uint32_tentry = FirstProbe(hash, capacity); 
 uint32_tcount = 1; 
 // EnsureCapacity will guarantee the hash table is never full. 
 while (true) { 
   Object* element = KeyAt(entry); 
   if (!IsKey(isolate, element)) break; 
   entry = NextProbe(entry, count++, capacity); 
 } 
 return entry; 

為什么數(shù)字的key要單獨(dú)這么搞呢?如果把它當(dāng)成一個(gè)字符串的key按上面字符串處理的邏輯也是行得通的。原因可能是一方面如果key是數(shù)字，那在在算哈希值可以做一個(gè)優(yōu)化，另一方面數(shù)字的key可能會有很多個(gè)就像上面提的例子，使用者可能把object當(dāng)作一個(gè)map來用，所以為它作一個(gè)優(yōu)化。

可以說elements幾乎是一個(gè)真正意義的哈希表。

然后再來簡單看一下ES6的Map的實(shí)現(xiàn)

6. ES6 Map的實(shí)現(xiàn)

這里有一個(gè)比較有趣的事情，就是V8的Map的核心邏輯是用JS實(shí)現(xiàn)的，具體文件是在 v8/src/js/collection.js ，用JS來實(shí)現(xiàn)JS，比寫C++要高效多了，但是執(zhí)行效率可能就沒有直接寫C++的高，可以來看一下set函數(shù)的實(shí)現(xiàn)：

 

function MapSet(key, value) { 
  //添加一個(gè)log 
  %LOG("MapSet", key); 
  var table = %_JSCollectionGetTable(this); 
  var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table); 
  var hash = GetHash(key); 
  var entry = MapFindEntry(table, numBuckets, key, hash); 
  if (entry !== NOT_FOUND) return ...//return代碼省略 
  //如果個(gè)數(shù)大于capacity的二分之一，則執(zhí)行%MapGrow(this)代碼略 
  FIXED_ARRAY_SET(table, index, key); 
  FIXED_ARRAY_SET(table, index + 1, value); 
} 

第三行添加一個(gè)log函數(shù)，確認(rèn)確實(shí)是執(zhí)行這里的代碼。%開頭的LOG，表示它是一個(gè)C++的函數(shù)，這個(gè)代碼寫在runtime.h和runtime.cc里面。這些JS代碼***會被組裝成native code。在V8里，除了Map/Set之外，很多ES6新加的功能，都是用的JS實(shí)現(xiàn)的，如數(shù)組新加的很多函數(shù)。

上文介紹了Object是如何實(shí)現(xiàn)的，重點(diǎn)分析了V8是如何存儲一個(gè)Object的屬性，并用了一個(gè)真正的Map作為參照。***的結(jié)論是Object屬性主要是通過哈希查找的，但是它不太適合拿來當(dāng)作哈希Map使用，特別是當(dāng)key很多并且都是字符串的時(shí)候。

其它的瀏覽器引擎可能會有不同的實(shí)現(xiàn)，但是至少不會笨到直接用key的字符串進(jìn)行遍歷。筆者將嘗試在下一篇介紹Array的實(shí)現(xiàn)，特別是分析一下它的操作函數(shù)是如何實(shí)現(xiàn)的。