Messages in this thread |  | | | Date | Wed, 21 Feb 2001 22:32:38 +0100 | | From | Martin Mares <> | | Subject | Re: [rfc] Near-constant time directory index for Ext2 |
| |
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.
> To be sincere, here is pretty daylight :)
:) Martin - 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/
|  |