0

Ok, I need a hashing function to meet the following requirements. The idea is to be able to link together directories that are part of the same logical structure but stored in different physical areas of the file system.

I need to implement it in Java, it must be consistent across execution sessions and it can return a long.

I will be hashing directory names / strings. This should work so that "somefolder1" and "somefolder2" will return different hashes, as would "JJK" and "JJL". I'd also like some idea of when clashes are likely to occur.

Any suggestions?

Thanks

Improve this question

4 Answers 4

Reset to default
4

Well, nearly all hashing functions have the property that small changes in the input yield large changes in the output, meaning that "somefolder1" and "somefolder2" will always yield a different hash.

As for clashes, just look at how large the hash output is. Java's own hashcode() returns an int, therefore you can expect clashes more often than with MD5 or SHA-1, for example which yield 128 and 160 bit, respectively.

You shouldn't try creating such a function from scratch, though.

However, I didn't quite understand whether collisions shouldn't ever occur with your use case or whether they are acceptable if rare. For linking folders I'd definitely use a guarenteed-to-be-unique identifier instead of something that might occur more than once.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Clashes are unlikely - the max number of directories at the same level might be 10,000, so my feeling was 64 bits should be enough. What guaranteed-to-be-unique options do I have? I would need to use the hash as an indexed column in a db (not a PK though) ..
2

You haven't described under what circumstances different strings should return the same hash.

In general, I would approach designing a hashing function by first implementing the equality function. That should show you which bits of data you need to include in the hash, and which should be discarded. If the equality between two different bits of data is complicated (e.g. case-insensitivity) then hopefully there will be a corresponding hash function for that particular comparison.

Whatever you do, don't assume that equal hashes mean equal keys (i.e. that hashing is unique) - that's always a cause of potential problems.

Improve this answer

7 Comments

You haven't described under what circumstances different strings should return the same hash. The honest answer is I don't know! My guess is once a string is over a certain length - say 14 chars - because most directories will be short in name. Is that a reasonable requirement?
@flesh: Not really. When do you want to treat two strings as being equal? What do you need over and above the normal hashCode method of Java's String class?
The honest answer is I'm completely new to Java, so, if for the requirements I'm suggesting above, Java's String hashCode is the best fit (including it being reliable through sessions so I can use it as an id) then great. Otherwsie, as I asked the other poster above, what guaranteed-to-be-unique options do I have bearing in mind I need to use the hash as an indexed column in a db (not a PK or unique though). Incidentally, when does string.hashCode treat two strings as equal? .. thanks for the advice.
You don't have any sensible guaranteed-to-be-unique options, really. String.hashCode treats two strings as equal when they are equal - when they're the same sequence of characters. But please don't use hash codes as IDs in a database... hashing is not meant to be used that way.
@Jon Skeet: "But please don't use hash codes as IDs in a database". Well, git uses SHA-256 hashes as IDs. I suppose it just depends on how much faith you have in there never being collisions.
|
1

Java's String hashcode will give you an int, if you want a long, you could take the least-significant 64 bits of the MD5 sum for the String.

Collisions could occur, your system must be prepared for that. Maybe if you give a little more detail as to what the hash codes will be used for, we can see if collisions would cause problems or not.

Improve this answer

Comments

1

With a uniformly random hash function with M possible values, the odds of a collision happening after N hashes are 50% when 

N = .5 + SQRT(.25 - 2 * M * ln(.5))

Look up the birthday problem for more analysis.

You can avoid collisions if you know all your keys in advance, using perfect hashing.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.