從一道前端面試題引發的原理性探究

来源:https://www.cnblogs.com/w3cfed/archive/2020/04/05/vue-react-key.html

作者 | Function | 前端時空 Vue 和 React 中的 key 到底有什麼用? key 是給每一個 vnode 的唯一 id,依靠 key,我們的 diff 操作可以更準確、更快速。 對於簡單列表頁渲染來說 diff 節點也更快,但會產生一些隱藏的副作用,比如可能不會產生過渡效果,或 ...


作者 | Function | 前端時空

Vue 和 React 中的 key 到底有什麼用?

key 是給每一個 vnode 的唯一 id,依靠 key,我們的 diff 操作可以更準確、更快速。 對於簡單列表頁渲染來說 diff 節點也更快,但會產生一些隱藏的副作用,比如可能不會產生過渡效果,或者在某些節點有綁定數據(表單)狀態,會出現狀態錯位。)

diff 演算法的過程中,先會進行新舊節點的首尾交叉對比,當無法匹配的時候會用新節點的 key 與舊節點進行比對,從而找到相應舊節點。

你以為這樣回答,面試官就能放過你。Too young,To simple。下麵是面試官的反問三連擊:

為什麼更準確??

因為帶 key 就不是就地復用了,在 sameNode 函數 a.key === b.key 對比中可以避免就地復用的情況。所以會更加準確,如果不加 key,會導致之前節點的狀態被保留下來,會產生一系列的 bug。

為什麼更快速?

key 的唯一性可以被 Map 數據結構充分利用,相比於遍歷查找的時間複雜度 O(n),Map 的時間複雜度僅僅為 O(1)。

為什麼 Map 數據結構會更快?

Map / Set / WeakSet / WeakMap 就是使用隱藏的 Hash code 優化哈希表

ECMAScript 2015 引入了幾個新的數據結構,例如 Map,Set,WeakSet和 WeakMap,所有這些結構都在後臺使用哈希表。下麵詳細介紹了V8 v6.3+ 如何將 key 存儲在哈希表中的最新進展。

哈希碼 Hash code

散列函數用於將給定的 key 映射到哈希表中的特定位置。一個哈希碼是給定的 key 運行此散列函數的運算結果。
hashCode = hashFunc(key)

在 V8 中,哈希碼只是一個隨機數,與對象值無關。因此,我們無法重新計算它,這意味著我們必須存儲它。

以前,對於那些把 JavaScript 對象作為 key 的情況,V8 將哈希碼作為私有符號(private symbol)存儲在對象上。V8 中的私有符號類似於Symbol,只是它不可枚舉,也不會不會泄漏到用戶空間 JavaScript 中。也就是說這個 symbol 只在 V8 引擎內部使用,用戶的 JavaScript 代碼訪問不到。

function GetObjectHash(key) {
  let hash = key[hashCodeSymbol];
  if (IS_UNDEFINED(hash)) {
    hash = (MathRandom() * 0x40000000) | 0;
    if (hash === 0) hash = 1;
    key[hashCodeSymbol] = hash;
  }
  return hash;
}

之所以行之有效,是因為在將對象添加到哈希表之前,我們不必為哈希碼欄位保留記憶體。當對象被添加到哈希表時,才把新的私有符號存儲在對象上。

與使用內聯緩存(IC)系統進行的任何其他屬性查找一樣,V8 還可以優化哈希碼符號查找,從而為哈希碼提供非常快速的查找。當鍵具有相同的隱藏類時,這對於單態內聯緩存查找非常有效。但是,大多數現實世界的代碼都不遵循這種模式,並且鍵通常具有不同的隱藏類,導致散列碼的復態內聯緩存查找變慢。

私有符號方法的另一個問題是,它在存儲哈希碼時觸發了密鑰的隱藏類轉換。這導致不僅對哈希代碼查找也為上鍵和其他財產查找差的多形態代碼去優化從優化代碼。

JavaScript 對象支持存儲

V8 的 JavaScript 對象(JSObject)使用 2 個 word(除了它的頭部):一個 word 用於存儲指向元素存儲的指針,另一個 word 用於存儲指向屬性存儲的指針。
  • word (computer architecture)

元素存儲用於像數組索引的屬性,而屬性存儲用於其鍵為字元串或符號的屬性。有關這些的更多信息,請參見 Camillo Bruni 的 V8 博客文章。

const x = {};
x[1] = 'bar';      // ← stored in elements
x['foo'] = 'bar';  // ← stored in properties

隱藏哈希碼 Hiding the hash code

存儲哈希碼最簡單的方法是將 JavaScript 對象的大小擴展一個字,並將散列碼直接存儲在對象上。但是,對於那些沒有添加到哈希表中的對象,這會浪費記憶體。相反,我們可以嘗試將散列碼存儲在元素存儲或屬性存儲中。

元素存儲是一個包含其長度和所有元素的數組。在這裡沒有太多的工作要做,因為可以把哈希碼存儲在一個保留的槽中(比如第 0 個索引),不過,當我們不使用這個對象作為哈希表中的關鍵字時,仍然會浪費記憶體。

讓我們看看屬性存儲。有兩種數據結構用作屬性存儲:數組字典

與元素存儲中使用的數組不同,元素存儲不具有上限,而屬性存儲中使用的數組的上限為 1022 個值。由於性能原因,V8 在超過此限制時則轉換為使用字典模式。(我略微簡化了這一點 - V8 也可以在其他情況下使用字典,但是可以存儲在數組中的值的數量有一個固定的上限。)

因此,屬性存儲有三種可能的狀態:

  • 空(沒有屬性)
  • 數組(最多可以存儲 1022 個值)
  • 字典

1、屬性存儲是空的

對於空的情況,我們可以直接在 JSObject 的偏移量上存儲哈希碼。

2、屬性存儲是一個數組

V8 表示小於 231 的整數(在 32 位系統上)更加高效,如 Smi。在一個 Smi 中,最低有效位是用來區別指針的 tag,而其餘的 31 位保存實際的整數值。

通常,數組將它們的長度存儲為 Smi。既然我們知道這個數組的最大容量只有 1022 個,我們只需要 10 個比特就可以存儲這個長度。我們可以使用剩下的 21 位來存儲哈希碼!

3、屬性支持存儲是一個字典

對於字典的情況,我們將字典大小增加1個字,以便將哈希碼存儲在字典起始位置的專用槽中。在這種情況下,我們可能會浪費掉一個字的存儲空間,因為這個比例增長的大小並不像數組那麼大。

通過這些更改,哈希碼查找不再需要經過複雜的 JavaScript 屬性查找機制。

性能改進

SixSpeed 對 Map 和 Set 的基準測試,這些變化導致了 5〜50% 的性能提升。

這一變化也導致 ARES6 中的基準測試提高了 5%。

這也導致 Emberperf 基準測試套件中測試的 Ember.js 提高了 18%。

探究總結

掌握一門技術併合理使用它的最好辦法就是深入理解這項技術背後的工作原理

參考資料

https://v8.dev/blog/hash-code

您的分享是我們最大的動力!

更多相關文章
  • 先安裝zsh 安裝oh my zsh 手動安裝 自動安裝 ` 不管使用手動 自動安裝,完成後都需要重啟。oh my zsh才能生效。 修改主題 挑選你喜歡的主題:https://github.com/robbyrussell/oh my zsh/wiki/Themes ...
  • Redis是一個開源的、基於記憶體的數據結構存儲器,可以用作資料庫、緩存和消息中間件 Redis最常用的功能 緩存 分散式鎖 ...
  • 創建3台虛擬機 主機為桌面版 其他為迷你版本 ******************************常用命令、進程名稱****************************啟動集群命令: start-all.sh啟動zookeeper: zkServer.sh start 啟動journal ...
  • 統計一個表的數據量是經常遇到的需求,但是不同的表設計及不同的寫法,統計性能差別會有較大的差異,下麵就簡單通過實驗進行測試(大家測試的時候註意緩存的情況,否則影響測試結果)。 1、 準備工作 為了後續測試工作的進行,先準備幾張用於測試的表及數據,為了使測試數據具有參考意義,建議測試表的數據量大一點,以 ...
  • 簡介 Flutter Fly是什麼?Flutter Fly是一款開源的Flutter 項目,非常適合初學者進行學習。App內集成了160+Flutter基礎控制項的詳細介紹及用法,內容來源於: "http://laomengit.com/" 。 歡迎頁: 首頁、控制項頁面、詳情頁及搜索頁面: 我: Ap ...
  • 質數是指在大於1的自然數中,除了1和它自身外沒有其他因數的自然數。 一、標記法,flag初始值為true,當n%i 0時(1<i<n),說明n不是質數,此時flag值為false且迴圈終止;當n%i != 0 時,flag的值始終為true,此時會輸出n是質數。 <!DOCTYPE html> <h ...
  • 1 <!DOCTYPE html> 2 <html lang="en"> 3 <head> 4 <meta charset="UTF-8"> 5 <meta name="viewport" content="width=device-width, initial-scale=1.0"> 6 <tit ...
  • Vue.js作為目前最熱門最具前景的前端框架之一,其提供了一種幫助我們快速構建並開發前端項目的新的思維模式。本文旨在幫助大家認識Vue.js,並詳細介紹使用vue-cli腳手架工具快速的創建Vue項目,以及對項目目錄結構的解釋說明,使大家清晰的瞭解Vue項目的開發流程。 ...
一周排行
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...