4 ms·

Is it even still a hash code/table in that case, technically? I thought the whole point of a hash table was the hash function "randomly" but reproducably assign

Is it even still a hash code/table in that case, technically? I thought the whole point of a hash table was the hash function "randomly" but reproducably assigning a position to items. This way, it's more some indexed storage with randomized positions.

chrisseaton 9y ago
It's an identity hash function. It's a hash of some arbitrary representation of the identity of the object.
Tarean 9y ago
Can't use the object content since that can change. So you need a unique identifier. Memory position can't be used because the gc moves objects around. Random number it is.
- twic 9y ago
  It's pretty much like using a surrogate key in a database.
- danbruc 9y ago
  Can't use the object content since that can change. It is not uncommon to use the state of an object to derive the hash code. It of course puts the burden to ensure that objects do not change in undesired ways while they are required to yield a stable hash code, for example while used as a key in a hash table, onto the developer. One common solution is to restrict the hash code calculation to immutable parts of the state, for example an ID. The advantage of deriving the hash code from the state is that you can use the hash code to speed up object equality tests, i.e. if the hash codes of two objects do not match, they can not be equal.
DougBTX 9y ago
> assigning a position 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?" The answer is that the "hash code" is indeed not the final position, instead it is the input to a function to compute the final position. So, lets say a hash table has 100 positions, then the hash table implementation will essentially do: var position = object.getHashCode() % 100; which converts the random number from getHashCode into a position within the hash table. Since the final "positions" are ints 0-99, the actual underlying storage would look a lot like a 100 element array. > This way, it's more some indexed storage with randomized positions. Summing up, basically yes, you could think of a hash table as indexed storage, where the positions are "randomised" by a modulus on the number of positions. Of course the "random" bit happens when the object hash code is generated, the rest is deterministic. In real life it looks like the minimum number of positions is at least 1022, and that number can change as entries get added to the hash table, but that's the gist of it.
- nojvek 9y ago
  I’ve spent days making hash tables in C. The module operator is really slow. But a bit shifting operator is much faster. Having hash tables that grow in sizes of two, or more precisely where you can just shave off some bits of a random number to get a position will yield the best performance. In JS, hash tables need to be growable Incase they get dense. In that instance you don’t want to compute object hash again since it’s expensive. You just want a cheap, here’s the new position.
- blauditore 9y ago
  > 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.
munificent 9y ago
> the hash function "randomly" but reproducably assigning a position to items Right, which is a pretty good description of what this does. It's random because it literally generates a pseudo-random number. And it's reproducible because it only generates it once and then stores it with the object to reuse it later. > This way, it's more some indexed storage with randomized positions. That's a great one-sentence description of a hash table. :)
- kevin_thibedeau 9y ago
  That's not reproducable. Hashes are reconstructed from the original data even if it no longer exists as a formal in memory object. This is just a random ID.
  - AgentME 9y ago
    Javascript Maps and Sets key off of the object's identity, not its contents.
    - kevin_thibedeau 9y ago
      That's all great. It isn't a hash, which by definition requires a hashing function applied to transform input data.
    - ninkendo 9y ago
      Shouldn’t they just call the attribute “objectIdentity” then? The fact that it’s used to access a hash table in some use cases doesn’t make it a “hash code”. You’d just as well call it an “equality checking code”, or name it after any other use case you could think of for a unique identifier. Ruby calls its equivalent construct “object_id” and that makes so much more sense.
  - munificent 9y ago
    For mutable objects in an OOP language, the object's identity is "the original data". The values that may happen to be stored in any other fields at various points in time are not part of the object's state and cannot affect the hash code. (If they could, mutating the object would change its hash code, which would be Very Bad.)

chrisseaton 9y ago

It's an identity hash function. It's a hash of some arbitrary representation of the identity of the object.

Tarean 9y ago

Can't use the object content since that can change. So you need a unique identifier. Memory position can't be used because the gc moves objects around. Random number it is.

twic 9y ago
It's pretty much like using a surrogate key in a database.
danbruc 9y ago
Can't use the object content since that can change. It is not uncommon to use the state of an object to derive the hash code. It of course puts the burden to ensure that objects do not change in undesired ways while they are required to yield a stable hash code, for example while used as a key in a hash table, onto the developer. One common solution is to restrict the hash code calculation to immutable parts of the state, for example an ID. The advantage of deriving the hash code from the state is that you can use the hash code to speed up object equality tests, i.e. if the hash codes of two objects do not match, they can not be equal.

DougBTX 9y ago

> assigning a position 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?" The answer is that the "hash code" is indeed not the final position, instead it is the input to a function to compute the final position. So, lets say a hash table has 100 positions, then the hash table implementation will essentially do: var position = object.getHashCode() % 100; which converts the random number from getHashCode into a position within the hash table. Since the final "positions" are ints 0-99, the actual underlying storage would look a lot like a 100 element array. > This way, it's more some indexed storage with randomized positions. Summing up, basically yes, you could think of a hash table as indexed storage, where the positions are "randomised" by a modulus on the number of positions. Of course the "random" bit happens when the object hash code is generated, the rest is deterministic. In real life it looks like the minimum number of positions is at least 1022, and that number can change as entries get added to the hash table, but that's the gist of it.

nojvek 9y ago
I’ve spent days making hash tables in C. The module operator is really slow. But a bit shifting operator is much faster. Having hash tables that grow in sizes of two, or more precisely where you can just shave off some bits of a random number to get a position will yield the best performance. In JS, hash tables need to be growable Incase they get dense. In that instance you don’t want to compute object hash again since it’s expensive. You just want a cheap, here’s the new position.
blauditore 9y ago
> 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.

munificent 9y ago

> the hash function "randomly" but reproducably assigning a position to items Right, which is a pretty good description of what this does. It's random because it literally generates a pseudo-random number. And it's reproducible because it only generates it once and then stores it with the object to reuse it later. > This way, it's more some indexed storage with randomized positions. That's a great one-sentence description of a hash table. :)

kevin_thibedeau 9y ago
That's not reproducable. Hashes are reconstructed from the original data even if it no longer exists as a formal in memory object. This is just a random ID.
- AgentME 9y ago
  Javascript Maps and Sets key off of the object's identity, not its contents.
  - kevin_thibedeau 9y ago
    That's all great. It isn't a hash, which by definition requires a hashing function applied to transform input data.
  - ninkendo 9y ago
    Shouldn’t they just call the attribute “objectIdentity” then? The fact that it’s used to access a hash table in some use cases doesn’t make it a “hash code”. You’d just as well call it an “equality checking code”, or name it after any other use case you could think of for a unique identifier. Ruby calls its equivalent construct “object_id” and that makes so much more sense.
- munificent 9y ago
  For mutable objects in an OOP language, the object's identity is "the original data". The values that may happen to be stored in any other fields at various points in time are not part of the object's state and cannot affect the hash code. (If they could, mutating the object would change its hash code, which would be Very Bad.)