[小心得]多層次對象屬性查找-非遞歸

層次（嵌套）結構是一種，常見、好理解且易於使用的數據結構，多用於保存配置信息，定義路由表，儲存各種狀態，而且這種KV存儲的方式在查找上也是具有天然優勢。

舉個例子，現代前端開發中在定義路由配置信息的時候，我們通常會使用層次結構來實現，為什麼會這樣呢？

試想一下，假設我們採取下面這種方式定義：

好處是：單層，key就是path易於查找；壞處也顯而易見：有層級關係但未體現，path要手動定義完整，維護代價高。

那假設我們採用多層級（嵌套）結構來定義：

好處和壞處恰好與前者相反，但我們更加傾向於易於理解、編寫和維護，其它的事情交給程序去做，那麼問題來了：如何進行高效的匹配查找呢？

思路：

1. 確定問題為樹的節點查找問題
2. 多層級結構轉化為單層級結構
3. 實現一個樹節點深度遍歷演算法
4. 出於性能考慮選擇非遞歸實現

演算法實現：

/** * 多層對象 => 單層對象（非遞歸深度遍歷） * @param obj 需要遍歷的對象 * @param char 鍵的連字元號 * @returns {{}} */function nonRecursiveDeepLoop (obj, char = .) { let arr = [] let dict = {} const goIn = (obj) => { return obj && obj instanceof Object && Object.keys(obj).length } const getTopArr = (obj, p) => { let arr = [] for (let k in obj) { let v = obj[ k ] arr.push({ k, v, parent: p }) } return arr } if (goIn(obj)) { let stack = getTopArr(obj, ) // 最頂層（root）父節點為空 let item while (stack.length) { item = stack.shift() if (goIn(item.v)) { let p if (item.parent) { p = item.parent + char + item.k } else { p = item.k } stack = getTopArr(item.v, p).concat(stack) } else { arr.push(item) } } } arr.forEach(({ k, v, parent }) => { let key = [ parent, k ].filter((d) => d).join(char) dict[ key ] = v }) return dict}

最終效果預覽：

完整代碼示例請戳：https://codepen.io/360vislab/pen/yvaRoG

推薦閱讀：