Messages in this thread | | | Date | Wed, 21 Feb 2001 13:59:03 -0800 (PST) | From | Davide Libenzi <> | Subject | Re: [rfc] Near-constant time directory index for Ext2 |
| |
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 direntry. 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 majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |