CODEWITHSUNDEEP
hashtableocamlcomplexity-theory
xysun
xysun

Reputation: 2015

Hashtbl.create complexity

I read somewhere saying the complexity of Hashtbl.create is O(nlogn).

I thought it strange since Hashtbl are implemented as arrays and Array.create has complexity O(n). So I looked into the source code:

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 }

Looks to me first it finds the smallest 2-power above the *initial_size* then making an array out of it. This does not sound like O(n logn)... I'm thinking something like O(2**(logn +1)).

Any ideas?

Thanks.

Upvotes: 0

Views: 244

Answers (1)

gasche
gasche

Reputation: 31469

What does n mean in your example? In the case of an array, we say that its creation is O(n) where n is the number of elements of the array. In the case of a hashtable, there is an underlying array initialized of size O(n), but n here is not related to the (future) number of elements of the hash table, only to the initial size parameter.

You may always pass size 1 or any constant of your liking, and the hash table will have to be resized more often, which is a costly but amortized operation: a ridiculously small initial size will only affect the constant multiplicative factor of your running time, not its algorithm complexity. A ridiculously large initial size will cause a huge constant overhead in time and memory (and possibly fail on a 32bits architecture, or if you don't have enough memory).

Upvotes: 1

Related Questions