Messages in this thread | | | From | "H. Peter Anvin" <> | Subject | Re: [rfc] Near-constant time directory index for Ext2 | Date | 21 Feb 2001 14:14:20 -0800 |
| |
Followup to: <20010221223238.A17903@atrey.karlin.mff.cuni.cz> By author: Martin Mares <mj@suse.cz> 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 -- <hpa@transmeta.com> at work, <hpa@zytor.com> 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 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/
| |