Tree結(jié)構(gòu)優(yōu)化案例，用空間換時間，竟快100倍！
背景：
因?qū)镜讓哟a進一步優(yōu)化，對公共代碼審核與優(yōu)化。所以這次對樹結(jié)構(gòu)下手了！來讓我們一起看看如何手撕這顆樹。
源方法：
不多說了直接開撕代碼
閱讀代碼
首先，我斗膽帶著大家讀一讀，看下我與大家的理解是不是一致的。
在方法中，首先判斷輸入的集合是否為空，如果為空，則直接返回一個空集合。
然后，通過循環(huán)遍歷每一個節(jié)點，找到它的所有子節(jié)點，并將子節(jié)點添加到父節(jié)點的子節(jié)點集合中。為了避免父節(jié)點是它本身的情況，使用了一個selfIdEqSelfParent集合來記錄所有滿足這個條件的節(jié)點的id。
最后，找出所有的根節(jié)點，即沒有父節(jié)點的節(jié)點，并將它們添加到根節(jié)點集合中。
問題點
在找到父節(jié)點的子節(jié)點時，使用了雙重循環(huán)遍歷的方式，導致時間復雜度較高。對于n個節(jié)點的樹形結(jié)構(gòu)，時間復雜度為O(n^2)。可以考慮使用更高效的算法來構(gòu)建樹形結(jié)構(gòu)，例如使用哈希表來記錄每個節(jié)點的id和對應的節(jié)點對象，然后通過一次循環(huán)就可以找到每個節(jié)點的父節(jié)點和子節(jié)點。
自循環(huán)判斷的邏輯存在問題。代碼中使用了selfIdEqSelfParent集合來記錄所有父節(jié)點是自己的節(jié)點的id。但是在循環(huán)遍歷時，只記錄了第一個滿足條件的父節(jié)點的id，并沒有在后續(xù)判斷中對其他滿足條件的節(jié)點進行處理。如果有多個節(jié)點的父節(jié)點都是自己，可能會導致構(gòu)建出錯誤的樹形結(jié)構(gòu)。
使用了通配符?來表示子節(jié)點的id的類型，但是沒有使用實際的類型參數(shù)。這樣可能導致在使用該方法時出現(xiàn)類型不匹配的問題。
優(yōu)化后：
閱讀代碼
首先，我們檢查輸入的樹列表是否為空。如果為空，直接返回一個空的集合。
然后，我們創(chuàng)建一個哈希表childrenMap，用于存儲每個節(jié)點的子節(jié)點集合。對樹列表中的每個節(jié)點進行遍歷，我們獲取該節(jié)點的父節(jié)點id。如果childrenMap中不存在該父節(jié)點id對應的子節(jié)點集合，我們創(chuàng)建一個新的空集合，并將該父節(jié)點id與其子節(jié)點集合放入childrenMap中。然后，將當前節(jié)點添加到其父節(jié)點的子節(jié)點集合中。
接下來，我們再次遍歷樹列表中的每個節(jié)點。對于每個節(jié)點，我們檢查它的id是否在childrenMap中存在對應的子節(jié)點集合。如果存在，我們將該子節(jié)點集合設置為當前節(jié)點的子節(jié)點集合。
在構(gòu)建完所有的子節(jié)點集合之后，我們開始找出根節(jié)點集合。我們創(chuàng)建一個空的根節(jié)點集合trees，以及一個id的集合allIds用于存儲所有的節(jié)點id。首先，我們遍歷樹列表，將每個節(jié)點的id加入allIds中。然后，再次遍歷樹列表，檢查每個節(jié)點的父節(jié)點id是否在allIds中存在。如果不存在，說明該節(jié)點是一個根節(jié)點，我們將其添加到根節(jié)點集合中。
最后，我們返回得到的根節(jié)點集合。
這樣，我們就完成了樹形結(jié)構(gòu)的構(gòu)建，并返回了根節(jié)點集合。
時間復雜度分析
這段代碼的時間復雜度是O(n)，其中n是樹中節(jié)點的數(shù)量。
首先，對于第一個for循環(huán)，我們將每個節(jié)點的父節(jié)點和它自身的映射存儲在一個哈希表中。該循環(huán)遍歷了樹列表中的每個節(jié)點，所以時間復雜度是O(n)。
然后，我們再次遍歷樹列表中的每個節(jié)點，檢查是否存在與其id匹配的子節(jié)點集合。在每次迭代中，檢查哈希表是否包含當前節(jié)點的id，并訪問哈希表以獲得子節(jié)點集合。這些操作的時間復雜度都是O(1)，因為哈希表的訪問是常量時間復雜度。所以，該循環(huán)的時間復雜度也是O(n)。
然后，我們找出根節(jié)點集合。我們首先遍歷樹列表，將所有節(jié)點的id存儲在一個集合中。然后再次遍歷樹列表，檢查每個節(jié)點的父節(jié)點id是否在集合中存在。這些操作的時間復雜度都是O(1)。所以這一部分的時間復雜度也是O(n)。
綜上所示，整個方法的時間復雜度是O(n)。
測試
本次采樣數(shù)據(jù)共3423條。由之前417毫秒提升至4毫秒。
源代碼：
優(yōu)化后：
