Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Which hashing algorithm is best for uniqueness and speed?

programmers.stackexchange.com

Post reply on HN
Print view View original

91–100 of 110 posts

Re: Which hashing algorithm is best for uniqueness and speed?

#91

Post by gizzlon »

SoftwareMaven wrote: post #60
gizzlon wrote: post #42

Earlier quoted context omitted.

I was indeed thinking of lossless compression: In practice it compresses almost all its input. If the the output length does not have to be constant, it's fine that some input actually gets inflated. As long as it compresses the average input. But in this case the output length might have to be constant? If that's the case, you are of course correct.

Lossless compression doesn't compress random data. You will still have the same number of bits in and out.

Who says the input is necessarily random? ;)

Re: Which hashing algorithm is best for uniqueness and speed?

#92

Post by andreasvc »

mseebach wrote: post #30
IgorPartola wrote: post #26

Honest question: why not use 2-3 different hash algorithms to minimize collisions if you are simply after uniqueness (e.g.: verifying that a downloaded file is correct)? As for hash tables, can't you guarantee uniqueness by using only reversible operations? I remember reading a lengthy post about this on HN, but can't find the link anymore.

> As for hash tables, can't you guarantee uniqueness by using only reversible operations? This is called a perfect hash and its appropriateness depends on the input data. The problem is that the problem domains where hashes are practical are where a very large space of inputs needs to fit into a finite number of buckets such that lookups are fast. For that to work with a perfect hash, you need an infinite number of b…

A perfect hash is able to avoid collisions when given the set of all possible keys in advance; it is not related to reversibility. The latter contradicts the very idea of a hash function, and would conceptually be a lossless compression technique.

Re: Which hashing algorithm is best for uniqueness and speed?

#93

Post by pwaring »

tmeasday wrote: post #88
marcusf wrote: post #21

Earlier quoted context omitted.

I find stuff like this terribly interesting, so please elaborate. Any journal or so that is recommended for someone curious?

I'm not active in the field right now, so I can't give specifics (the comment was more borne out of frustration with people putting in so much effort 'reinventing the wheel' in an academic sense). But if I was you, I'd start with Knuth (he, as another commenter mentioned, covers hashes in great detail), head to the references, and then use Google Scholar to find well-cited recent articles that reference the important…

Unfortunately though, a lot of the papers that turn up in Google Scholar are behind paywalls. It is very expensive to get hold of academic papers if you don't work/study somewhere with an institutional licence (anything from $10 upwards per paper).

Re: Which hashing algorithm is best for uniqueness and speed?

#94

Post by marcusf »

tmeasday wrote: post #88
marcusf wrote: post #21

Earlier quoted context omitted.

I find stuff like this terribly interesting, so please elaborate. Any journal or so that is recommended for someone curious?

I'm not active in the field right now, so I can't give specifics (the comment was more borne out of frustration with people putting in so much effort 'reinventing the wheel' in an academic sense). But if I was you, I'd start with Knuth (he, as another commenter mentioned, covers hashes in great detail), head to the references, and then use Google Scholar to find well-cited recent articles that reference the important…

Thanks very much! Might be finally time to cough up the dough for TAOCP then and take it from there.

Re: Which hashing algorithm is best for uniqueness and speed?

#95

Post by mseebach »

andreasvc wrote: post #92
mseebach wrote: post #30

Earlier quoted context omitted.

> As for hash tables, can't you guarantee uniqueness by using only reversible operations? This is called a perfect hash and its appropriateness depends on the input data. The problem is that the problem domains where hashes are practical are where a very large space of inputs needs to fit into a finite number of buckets such that lookups are fast. For that to work with a perfect hash, you need an infinite number of b…

A perfect hash is able to avoid collisions when given the set of all possible keys in advance; it is not related to reversibility. The latter contradicts the very idea of a hash function, and would conceptually be a lossless compression technique.

Any reversible hash would be a perfect hash - not the other way around. That's all I'm saying.

That said, there's nothing in the definition of hash functions that require them to be compressing or non-reversible - although they would typically have to be to be useful.

Re: Which hashing algorithm is best for uniqueness and speed?

#96

Post by terangdom »

mseebach wrote: post #55
Jabbles wrote: post #48

Earlier quoted context omitted.

Certainly, if you are hashing a large amount of data then a single modulo operation isn't going to cost a lot. But if you're just hashing an English word, possibly even a URL, I'm not so sure. You could shift or mask the result (as described above) to use a table size of any power of 2 to avoid the modulo.

Doing constant modulo on an integer is very fast - we're talking a few CPU operations.

IIrc changing a modulo to an and roughly doubled the performance of my hashtable.

Re: Which hashing algorithm is best for uniqueness and speed?

#97

Post by terangdom »

pjscott wrote: post #80
masklinn wrote: post #9

Earlier quoted context omitted.

> isn't slow better in this case? No, guy's looking for a hash table hash, not a cryptographic one. For a hash table you're looking for low collisions and high throughput (so your hash table is fast) first and foremost.

Even for cryptographic hashes, fast is what you want most of the time. Look at it this way: when you connect to a web site via SSL, all the data you send will be hashed for authentication. Do you really want this to be slow?

Cryptographic hashes should be as fast as possible while not sacrificing collision resistance. Hashtable hashes should be as collision resistant as possible while not sacrificing speed.

Sort of anyway.

Re: Which hashing algorithm is best for uniqueness and speed?

#98

Post by andreasvc »

mseebach wrote: post #95
andreasvc wrote: post #92

Earlier quoted context omitted.

A perfect hash is able to avoid collisions when given the set of all possible keys in advance; it is not related to reversibility. The latter contradicts the very idea of a hash function, and would conceptually be a lossless compression technique.

Any reversible hash would be a perfect hash - not the other way around. That's all I'm saying. That said, there's nothing in the definition of hash functions that require them to be compressing or non-reversible - although they would typically have to be to be useful.

I agree with the first point, but I think compressing and non-reversible are necessary conditions for a given function to be called a hash function; if they weren't, any mathematical function would do, wouldn't it?

One could see a hash function as an (extremely) lossy compression method. However, lossy compression only makes sense when you can exploit features of the domain, e.g., psychoacccoustics with sound, or characteristics of human vision with photos; perceptual hashes come to mind here.

Re: Which hashing algorithm is best for uniqueness and speed?

#99

Post by its_so_on »

dllthomas wrote: post #83
its_so_on wrote: post #46

Earlier quoted context omitted.

Fair enough. The proof is that you can't shave even a single bit off of every output, so that given any file that's 1024 bytes, you can hash it to 1023 bytes. Not possible unless you're hiding that entropy somewhere (filename etc).

The proof is straightforward application of the pigeonhole principle. Input strings are your pigeons, hashes are your holes.

what you've just said says nothing about the length of the hashes, which was my point. You would have to say something like "all possible inputs of a certain length are your pigeons, and these same possibilities(1) are the holes"

(1)this time interpreted as the hash of one and only one of the same list of possible inputs

The proof is not so straightforward, because it's not always true when you expect it to be true. For example, can you hash, reversibly and uniquely, all the numbers between 0 and 10 (real) to all the numbers between 0 and 1?

You would expect the answer to be "no" since there are "more real numbers from 0 to 10 than from 0 to 1". But that's actually not necessarily true the way you might expect, and the answer is actually "yes you can". Simply geometrically establish a coordinate plane like this

   a

   0 b 1

   0       10
so that point (a) has a well-defined coordinate, say (0,1) the 0 from the second line is at the origin, the 1 at the second line is at (1,0) and the bottom 0 is at (0,-1) with the bottom 10 being wherever the ray passing through a and passing through (1,0) - enough to uniquely identify the ray - has the y-value of -1.

Now to get the hash simply move 'b' to wherever between 0 and 1 you're trying to hash, solve for the ray that passes through a and that point, and solve for the x-value of the ray where it has y-value of -1.

Through elementary proof which should be obvious, you'll see that any b casts a distinct ray (which is easily reversible introducing a c into line 3), and you can solve for it if you like.

I'm not saying that you're wrong, but I think the proof isn't as "obvious" and straightforward as you're saying. It doesn't apply to just anything, but to the specific case of the impossibility of hashing distinct length inputs uniquely into a discrete space defined by a uniformly shorter length of bits.

Post reply on HN