David Rasch said the following on 5/14/04 1:13 PM:
With an inode -> filename hash, couldn't this be done linearly O(N) ?
Check each file against the hash looking for a file already using this
inode?
Theoretically, but the data structures could get tricky. You'd need to
sure the hashing function was large enough so that there weren't collisions.
But, since the inode is a number, the perfect (as far as no collisions go)
hashing function is the identity function. But, then how do you store it.
If you allocate an array for all possible values, then yes, you can do
it O(N) by just checking that bucket but at the cost of a huge amount
of memory. With each bit you lower the hash function you decrease memory
requirements but also increase the number of things you must check to
avoid collisions. It would be interesting to see the curve that
results from this tradeoff. You have to pay somewhere, be it memory or
operations.
Cheers,
Tanner
--
Tanner Lovelace | Don't move! Or I'll fill ya full of... little
[EMAIL PROTECTED] | yellow bolts of light! - Commander John Crichton
--
TriLUG mailing list : http://www.trilug.org/mailman/listinfo/trilug
TriLUG Organizational FAQ : http://trilug.org/faq/
TriLUG Member Services FAQ : http://members.trilug.org/services_faq/
TriLUG PGP Keyring : http://trilug.org/~chrish/trilug.asc
