字元串類型-實現方法

字元串是一種常用的基礎數據類型，一般用兩個雙引號""或者單引號""包裹，比如"this is a string", "good idea!"，常用的字元串操作有：

• 新建字元串

• 取字元串長度

• 比較兩個字元串大小

• 拼接、拆分、格式化字元串

字元串的操作比較簡單，本文主要介紹字元串的底層實現，包括字元串的創建、管理、回收等，以如下代碼為例：

創建了三個字元串對象，分別存入s1、s2、s3，其中s1和s3為相同的字元串，下面分別介紹具體實現。

字元串創建

典型的創建一個字元串的方法：

• 計算字元串所需長度

• 分配對應長度的空間

• 拷貝內容

對應的代碼為：

這裡使用memcpy而沒有用strcpy，因為strcpy不適用於二進位數據，用memcpy可以同時滿足c字元串和二進位數據。末尾加上""是為了兼容c字元串函數。

字元串管理

如果任意創建字元串而不加管理，在運行期必將創建大量的字元串對象，其中有相當一部分是冗餘重複的，比如s1和s3，如何解決重複字元串的問題呢？

字元串池（string pool）可用於保證相同的字元串只創建一份（內化），實現方法是：

在原有基礎上增加了查找步驟，考慮到字元串操作非常頻繁，問題演變為如何高效的實現字元串池查找。

查找演算法一直都是編程的關注熱點，總結起來分為三類：

• 順序查找，從頭到尾依次遍歷，複雜度為O(N)

• 二分查找，每次將問題規模減半，複雜度為O(logN)

• 索引查找，根據索引位置定位，複雜度為O(1)

顯然，索引查找的效率最高，若使用索引查找，就需要將字元串轉換為索引值，轉換方法大部分人應該都想到了，使用哈希函數。

字元串的哈希函數有不少，網上有專門分析各個哈希函數的性能的文章，感興趣的可以搜索「字元串hash演算法」。

Lua里使用JS Hash演算法，該演算法代碼如下：

考慮到對長字元串的每個字元計算hash值，本身就是一種負擔，為減少計算次數，設置step步長為length除以32加1，這樣可以提升hash函數性能。

接下來就是實現一個哈希表，有兩種哈希衝突解決方法：

（1）開放地址法，Lua在table的內部實現里使用開放地址法解決衝突（後續專門介紹）

（2）鏈地址法，Lua在字元串池里使用鏈地址法解決衝突

根據上面的分析，一個字元串對象除了基本的char*、length兩個欄位外，還需要記錄hash值，以及用於記錄下一個衝突對象的next指針，再結合gc狀態，可以定義出字元串類型為：

哈希表採用數組加鏈表方式實現，即每個數組元素為一個鏈表，如下：

GCLinkedList為自定義的鏈表類，capacity為datas數組大小，每個數組元素為一個GCList。

初始化

• 用minsize作為capacity，比如設定哈希表初始大小為64

添加

• 用value.hash % capacity計算字元串在數組的索引

• insert_head將新字元串插入鏈表頭部位置

• 若已有元素數量超過capacity，容量翻倍

查找

• 用value.hash % capacity計算字元串在數組的索引

• 遍歷鏈表，查找相等的字元串，若找到返回已有字元串的指針

• 否則，返回空

收縮

• 若已有元素數量小於capacity的1/4，且capacity大於minsize的3倍，容量縮小一倍

重分配

• 當觸發擴容或收縮條件時，需要重分配內存

• 根據新size創建新表

• 遍歷舊錶，計算每個元素在新表的新位置，添加到新表

• 釋放舊錶

完成哈希表後，創建字元串的方法可以更新為先檢查，再創建，代碼如下：

字元串回收

當執行gc時，垃圾字元串需要被自動回收，在《標記清除演算法》一節里介紹gc的基本原理，只需要將未標記的字元串從哈希表裡移除即可，具體步驟為：

• 遍歷運行棧，標記引用對象

• 遍歷全局對象表，標記引用對象

• 從哈希表里獲取未標記的字元串對象，存入freeStrings鏈表

• 釋放freeStrings里的所有字元串

• 檢查哈希表是否需要收縮空間

性能優化

Lua的字元串實現很優秀，但在某些情況下，還有提升的空間，比如下面這段代碼：

統計執行200w次tostring操作的耗時，實際運行8.66s。

由於每次創建字元串時，都要先檢查哈希表，再new一個字元串對象，顯然比較耗時。在實際運行中，經常會有短字元串操作，比如將數值轉換為字元串、拼接http url請求字元串、添加table key等場景。如果針對短字元串做一些簡單的優化，避免查表和new操作，可以顯著提升執行效率。

優化方法是在Object類型增加16位元組短字元串，且作為值類型處理，具體參考llamavm實現：

shortstr即為16位元組短字元串，若字元串長度不足16，直接存入shortstr，避免了hash表查詢和分配內存操作。經過測試，優化後的vm執行耗時為5.209s，提升了40%。

關於字元串類型的底層實現介紹到這裡，文中相關代碼來自llamavm源碼，原理同Lua源碼。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！