Hashtbl.create複雜性

Question

我在某處讀到說Hashtbl.create的複雜性是O（nlogn）。

我認爲這很奇怪，因爲Hashtbl是作爲數組實現的，Array.create的複雜度是O（n）。所以，我看着源代碼：

let rec power_2_above x n = 
    if x >= n then x 
    else if x * 2 > Sys.max_array_length then x 
    else power_2_above (x * 2) n 

let create ?(random = !randomized) initial_size = 
    let s = power_2_above 16 initial_size in 
    let seed = if random then Random.State.bits (Lazy.force prng) else 0 in 
    { initial_size = s; size = 0; seed = seed; data = Array.make s Empty } 

看來，我第一次發現上面的* initial_size最小2功率*然後形成陣列出來。這聽起來不像O（n logn）......我在想像O（2 **（logn +1））。

任何想法？

謝謝。

Answer 1

n在你的例子中是什麼意思？在數組的情況下，我們說它的創建是O(n)，其中n是數組元素的數量。在散列表的情況下，初始化的底層數組的大小爲O(n)，但這裏的n與散列表元素的（未來）數量無關，僅與初始大小參數有關。

您可能總是傳遞大小1或您喜歡的任何常數，並且哈希表必須更經常地調整大小，這是一個代價高昂但分期付款的操作：小得可笑的初始大小隻會影響常數乘法因子你的運行時間，而不是算法的複雜性。一個可笑的大的初始大小會在時間和內存上造成巨大的持續開銷（並且可能在32位架構上失敗，或者如果你沒有足夠的內存）。