4 ms·

> I think what you're asking is "this getHashCode function always returns a random number within a large range, but a hash table has a small set of positions, s

> I think what you're asking is "this getHashCode function always returns a random number within a large range, but a hash table has a small set of positions, so isn't this more like a sparse array rather than a hash table?" No, that was not really my question. FWIW, the same problem often exists for actual hash tables too: For example, the Java hashCode method returns a 32-bit number that needs to be mapped first too. My question is whether a (non-deterministic) random "hash" function can still be called as such, and therefore the structure a hash table.

DougBTX 9y ago
Ah, thanks for the clarification, my mistake. If that hasn't been answered elsewhere, then the important part is that the hash code for a particular object is always constant, every call to getHashCode for that object returns the same value, so in a sense it is deterministic (the same object always hashes to the same value, which is all the hash table cares about) even if the actual number was initially generated using a non-deterministic process.
twic 9y ago
I believe this is ultimately a question of lexicography: what do the terms "hash code" and "hash table" mean? The name "hash code" comes (UIAVMM!) from the idea of chopping an input into little bits and mashing them all together, just like you'd do to potatoes or beef to make hash browns or steak haché. I imagine the name "hash table" comes from the fact that is typically probed using a hash code. In fact, i would be interested to know if the first hash tables had separate steps of hashing and input and reducing it to a table index, as modern ones do, or whether the input was hashed directly to an index. An "identity hash" like this is clearly not made that way. However, lexicography is not etymology. If you want to know what a word means, you have to look at how people use it. In the Java world, at least, anything that comes out of hashCode() is a hash code, even if it's not made by traditional hashing. And universally, the data structure implementing a map by reducing keys to indices into a table and then dealing with collisions somehow is known as a hash table.

DougBTX 9y ago

Ah, thanks for the clarification, my mistake. If that hasn't been answered elsewhere, then the important part is that the hash code for a particular object is always constant, every call to getHashCode for that object returns the same value, so in a sense it is deterministic (the same object always hashes to the same value, which is all the hash table cares about) even if the actual number was initially generated using a non-deterministic process.

twic 9y ago

I believe this is ultimately a question of lexicography: what do the terms "hash code" and "hash table" mean? The name "hash code" comes (UIAVMM!) from the idea of chopping an input into little bits and mashing them all together, just like you'd do to potatoes or beef to make hash browns or steak haché. I imagine the name "hash table" comes from the fact that is typically probed using a hash code. In fact, i would be interested to know if the first hash tables had separate steps of hashing and input and reducing it to a table index, as modern ones do, or whether the input was hashed directly to an index. An "identity hash" like this is clearly not made that way. However, lexicography is not etymology. If you want to know what a word means, you have to look at how people use it. In the Java world, at least, anything that comes out of hashCode() is a hash code, even if it's not made by traditional hashing. And universally, the data structure implementing a map by reducing keys to indices into a table and then dealing with collisions somehow is known as a hash table.