[lkml]   [2001]   [Feb]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [rfc] Near-constant time directory index for Ext2
Followup to:  <>
By author: Martin Mares <>
In newsgroup:
> Hello!
> > To have O(1) you've to have the number of hash entries > number of files and a
> > really good hasing function.
> No, if you enlarge the hash table twice (and re-hash everything) every time the
> table fills up, the load factor of the table keeps small and everything is O(1)
> amortized, of course if you have a good hashing function. If you are really
> smart and re-hash incrementally, you can get O(1) worst case complexity, but
> the multiplicative constant is large.

Not true. The rehashing is O(n) and it has to be performed O(log n)
times during insertion. Therefore, insertion is O(log n).

<> at work, <> in private!
"Unix gives you enough rope to shoot yourself in the foot."
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:17    [W:0.120 / U:6.116 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site