面試的時候遇到HashMap的實現原理,數組+鏈表+紅黑樹，這個大部分人都知道
問題來了，什么時候會鏈表轉紅黑樹，什么時候紅黑樹會轉鏈表
看一下jdk1.8的HashMap源碼
注意到其實就是，大于等于7的時候轉樹，和小于等于6的時候轉鏈表
那么為什么是這兩個數呢？先要說一下查找的平均長度
鏈表就是順序查找，紅黑樹可以看作就是標準的二叉樹，適合二分查找
順序查找
對于n個數，每個數字查找概率相等，那么有? 推導：(1+2+3+4+5+n )/n =(n+1)*n/2n=（n+1）/2?
二分查找，假設是滿二叉樹, n與d(樹高)的關系, 有公式: n = (2^d) - 1
1+2*2+3*4+4*8....d*2的d-1次方
d=log（n+1）?
對于高度為2,總結點數是3的二叉排序樹(滿二叉樹),查找成功的平均查找長度為:
ASL = (1*1 + 2*2) / 3
對于高度為3,總結點數是7的二叉排序樹(滿二叉樹),查找成功的平均查找長度為:
ASL = (1*1 + 2*2 + 3*4) / 7
對于高度為h,總結點數是n的二叉排序樹(滿二叉樹),查找成功的平均查找長度為:
ASL = ( 1*1 + 2*2 + 3*4 + ... + h*2^(h-1) ) / n [等式1]
對于[等式1]里的1*1 + 2*2 + 3*4 + ... + h*2^(h-1)
該數列有h項: 1*2^0, 2*2^1, 3*2^2, ... , h*2^(h-1)
其總和:
S = 1*2^0 + 2*2^1 + 3*2^2 + ... + h*2^(h-1) [等式2]
等式兩邊同乘以2,有:
2*S = 1*2^1 + 2*2^2 + 3*2^3 + ... + (h-1)*2^(h-1) + h*2^h [等式3]
用[等式3]減去[等式2]有:
S = h*2^h - (2^0 + 2^1 + 2^2 + 2^3 + ... + 2(h-1)) [等式4]
其中(2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(h-1))是等比數列求和,設:
M = (2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(h-1))
等式兩邊同乘以2,有: 2*M = (2^1 + 2^2 + 2^3 + ... + 2^h)
兩個等式相減,有: M = 2^h - 1
將M代入[等式4]有:
S = h * 2^h - (2^h - 1) = (h-1) * 2^h + 1 [等式5]
因為 h = log2(n+1),將h代入[等式5],有:
S = [ log2(n+1) - 1 ] * 2^[log2(n+1)] + 1
= [ log2(n+1) - 1 ] * (n+1) + 1
= (n+1) * log2(n+1) - n
也就是
S = ( 1*1 + 2*2 + 3*4 + ... + h*2^(h-1) ) = (n+1) * log2(n+1) - n
將上述S代入[等式1],有:
ASL = [(n+1) * log2(n+1) - n] / n
= [(n+1)/n] * log2(n+1) - 1
ASL = [(n+1)/n] * log2(n+1) - 1 [公式1]
其時間復雜度是: O(log2(n))
用圖來表示
所以，任意大于1的自然數的情況下，二叉樹的查找長度均小于順序查找
那么為什么hashmap 要<=6的情況下，轉鏈表 >=7的情況下轉紅黑樹？（只能是這么感覺底層開發(fā)人員用的公式是這樣的log(n)/log(2)+1,至于為什么是這樣，暫時沒搞清楚。。難道是單純的bug嗎？）
