101–110 of 110 posts
Earlier quoted context omitted.
Doing constant modulo on an integer is very fast - we're talking a few CPU operations.
It won't be a compile-time constant unless your hash table is incapable of resizing. And modulo arithmetic on arbitrary values is slow (20-94 cycles of latency on Sandy Bridge).
Very interesting, thanks for sharing. "CRC32 collisions: codding collides with gnu". At first I read "coding" and I was all "haha this must be an easter egg of the implementation".
Earlier quoted context omitted.
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.…
Well, the quotes you had to put there say it all. You might expect the answer to be "no" if you didn't understand how infinity works.
Earlier quoted context omitted.
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 cha…
It's not meaningful to study hashes as compression, since compression is by definition reversible.
Earlier quoted context omitted.
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.…
Given the pigeonhole principle, and the observation that there are fewer strings of length K than strings of any length, you have that you cannot map every string into a unique hash. That's what I meant by "a straightforward application of the pigeonhole principle".
If you're dealing with an infinite set of hashes (I'm not sure what that would look like, but hey), then of course you need to take into account the limitations of the pigeonhole principle when dealing with infinite sets - specifically, that it only applies if you have a set of pigeons of a larger cardinality than your set of holes. [0,1] and [0,10] have the same cardinality.
Earlier quoted context omitted.
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.
Earlier quoted context omitted.
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).
Earlier quoted context omitted.
Yeah sure you could waste all the space you want why in the world would you do that? Using a linked list is slow and inefficient with memory usage especially when you can do the same thing with a byte array. Look up an algorithm called a Bloom Filter.
Bloom filters are not suitable as stand-in replacements for hash tables when you are representing the Set abstract data type. They are not deterministic, they treat objects with the same hash as identical, and they do not actually store values. Bloom filters are only useful (in this context) to augment a proper Set implementation, in which case they increase the memory cost, in exchange for decreasing (on average) th…