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

From: Davide Libenzi (
Date: Wed Feb 21 2001 - 16:59:03 EST

On 21-Feb-2001 Martin Mares wrote:
> 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.

My personal preference goes to skiplist coz it doesn't have fixed ( or growing
) tables to handle. You've simply a stub of data togheter with FS data in each
And performance ( O(log2(n)) ) are the same for whatever number of entries.

- Davide

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

This archive was generated by hypermail 2b29 : Fri Feb 23 2001 - 21:00:25 EST