Re: [rfc] Near-constant time directory index for Ext2

[H. Peter Anvin]

Followup to:  <[EMAIL PROTECTED]>
By author:    Martin Mares <[EMAIL PROTECTED]>
In newsgroup: linux.dev.kernel
>
> 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).

        -hpa
-- 
<[EMAIL PROTECTED]> at work, <[EMAIL PROTECTED]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/