5 ms·

If it is a random number it is not an identity hash function. It is just a position. And in my terminology this makes no sense here, as you normally hash the id

by onli 9y ago

If it is a random number it is not an identity hash function. It is just a position. And in my terminology this makes no sense here, as you normally hash the id/content of the thing you want to store, which is not happening if you return something unrelated to the object. What am I missing? Edit: https://github.com/multiformats/multihash/issues/13 https://github.com/multiformats/multihash/issues/13 suggests this is a replacement for using the content of the object, which is not available, to replace the step of hashing something. Is that it? Then it would be a replacement for a replacement of a hash, and not a hash anymore.

chrisseaton 9y ago
Objects in some programming languages (like JavaScript, but not like others such as Haskell) have an identity value. This is an abstract value. It's a theoretical thing. We pretend it's there but it's not like a usual value. It's not something you can actually see or calculate with. You can just compare them. A hash function takes a value or a compound value and produces a simpler integer from it. An identity hash function takes an identity value and produces a simpler integer from it. Based on all these definitions, returning a random integer, as long as you store it and return it again the next time, is an identity hash function. > you normally hash the id/content of the thing you want to store That's what we're doing. You've said it yourself. We hash the id (identity) of the thing you want to store. You could call the identity the content of the object as well if you wanted to. It's not about replacing the actual content on the object, because JavaScript maps are, by design and by definition (23.1.3.6, 7.2.10), explicitly identity maps. They don't want to consider the content of an object, except for this abstract identity content. I'm not sure if you're arguing I'm mistaken, or the that the whole idea is wrong. But this is what many languages do and it's all very conventional terminology and practice.
- gpderetta 9y ago
  > An identity hash function takes an identity value and produces a simpler integer from it I would expect an identity hash function to be exactly that: i.e. a trivial function that takes a value and returns that value unmodified (i.e. the identity function). It happens to describe well this case because the input to the has function itself is the unique identifier and as it is already uniformly distributed, the has function can just return it unmodified.
  - chrisseaton 9y ago
    In this context, an 'identity hash function' means that it's a 'hash function for an identity value'. It doesn't mean 'a hash function that is an identity function'. It's confusing!
  - dfox 9y ago
    In the simple case of using memory location as object identity (ie. in system without moving GC) and typical textbook hashtable implementation simply using the pointer as hash value is highly suboptimal, because heap pointers do not have remotely uniform distribution (low order bits are always zero due to allignment constraints, high order bits tend to be constant and usually also zero...). On the other hand you can use more advanced hashtable design that is explicitly tuned for non-uniform hash value distribution. See CPythons dict for cannonical example of that, although it's motivations are somewhat different (the major reason is that in CPython even real hash values of object's content are intentionally non-uniform to allow for simple way of causing integer-valued floats to have same hash value as ints of same value).
- onli 9y ago
  Thanks for explaining, also to the others. > I'm not sure if you're arguing I'm mistaken, or the that the whole idea is wrong. But this is what many languages do and it's all very conventional terminology and practice. Neither, I just felt the terminology not fitting, I'd have called it id generation and left out the hash. V8 is generating the hash/id in the hash function, not doing something directly with the input or computing it (as in, calculating) from the input, right? Like if the hash terminology was added because one came from hash tables. I guess what I meant is that using and storing a random number here feels like a trick to fulfill the contract of a hash function without actually implementing one, since those usually look different (but I'm more used to see cryptographic hash functions). My definition of a hash function includes returning a word of fixed length, in practice that is not relevant here because the numerical representation is the same (001 = 01 = 1). But apart from that I can see now that the shown scheme fulfills the contract of a non-cryptographic hash function, the storing of the id and the virtual identity make it somehow fit.
  - chrisseaton 9y ago
    > not doing something directly with the input or computing it (as in, calculating) from the input, right? It is doing something directly with the input and calculating something, if you make the leap to consider that the input object has a hidden abstract value which represents the object's identity.
    - onli 9y ago
      Big leap for me. But thanks, this helped understanding why it is called that way :)
munificent 9y ago
A hash function takes some state and produces a nicely-distributed random-ish number from it. Given the same state, it produces the same hash. I think you're OK with that definition of a hash function, right? In a mutable object-oriented language like JavaScript, two objects with the same properties are not the same object. Conversely, an object before and after mutating a property is still the same object. Thus, the "state" that matters for hashing is the object's identity, not its properties. Thus, V8's hash function produces a hash value given the identity of some object. Since there are no useful bits associated with "identity" that V8 can use to produce a hash value, it has to synthesize some at object creation time by calling rand. (If V8 didn't move objects in memory during GC, then the object's address in memory would be a good candidate for its identity. Indeed, in language implementations where objects don't move, the address is often used as an input to the hash function.)
- onli 9y ago
  So I actually looked up in my text book from way back how the course I learned this stuff in defined hash functions. I wanted to understand why this felt so wrong. According to that book a hash function is merely a mapping of a String (could also be called a word) of arbitrary length to a fixed length String, no requirement for having a nice distribution or ranomdishness. I guess this helps the V8 terminology, if one remembers that the fixed length part can be somewhat ignored when looking at numerical values. > Thus, V8's hash function produces a hash value given the identity of some object So if I got that right V8 is using the identity of an object as hash function, but since the identity is a virtual concept it replaces the identity with a randomly generated number - or is it later on doing something with that identity value? If not still feels strange to call that a hash, but I think I have to agree that it is a valid hash function given the definition.
  - munificent 9y ago
    > a mapping of a String (could also be called a word) of arbitrary length to a fixed length String Right. It takes a longer sequence of bits and reduces it to a shorter sequence of bits, with a resulting chance for collision. > since the identity is a virtual concept it replaces the identity with a randomly generated number It's not replacing anything. Here's another way to think of it. V8 needs this function: int getHash(Object object) { ... } Given a reference to some object, it returns a hash code for it, based on the identity of the object. The requirements are: 1. Returned values should be nicely distributed over the number space. 2. If you same object in, you must get the same hash code out. Even if the object is mutated between calls. This sounds like a reasonable definition of a hash function, right? If all this function had access to was the object's properties and it had to be pure (couldn't modify anything), it's actually impossible to implement this function. (This, strangely enough, touches on fundamental ideas around mutability, identity, and equality.) So V8 relaxes the requirement that the function be pure. getHash() then generates a random number for the object, stuffs it in some hidden chunk of memory inside the object (what the linked article is about) and declares by fiat that that number is now the hash code for that object's otherwise-intangible identity.
skybrian 9y ago
Hash codes aren't actually exposed in JavaScript. It's an implementation detail. The only requirement is that key lookup is consistent with equals [1]. For a string key, the hashcode field is probably a cached hash of the value, since that's how an equality comparison works. Most objects are only equal to themselves, are mutable, and get moved in memory, so storing a unique identifier is the only way to know if it's the same object that you saw before. For a hash code, the identifier doesn't need to be unique since all that matters is that it's consistently placed in the same bucket. All you need is to store a sufficiently long random number. [1] SameValueZero equality as defined at https://developer.mozilla.org/en-US/docs/Web/JavaScript/Equality_comparisons_and_sameness https://developer.mozilla.org/en-US/docs/Web/JavaScript/Equa...
- SloopJon 9y ago
  Upvoted for pointing out that this random number isn't necessarily unique. There can be collisions, just as with a conventional hash.
gpderetta 9y ago
> you normally hash the id/content of the thing the random number /is/ the id. You can think of it as the unique address of the object in some other memory mapping. The hash function just happens to be the identity function in this case.
- sfink 9y ago
  No it isn't. This is not a unique id. Two different objects could easily have the same hash value. People are mixing up the mathematical term "identity function", meaning a function that maps its input directly to its output, with object identity. I have never heard this usage of the phrase, as in a function that takes an object identity as input.

by onli 9y ago

chrisseaton 9y ago

Objects in some programming languages (like JavaScript, but not like others such as Haskell) have an identity value. This is an abstract value. It's a theoretical thing. We pretend it's there but it's not like a usual value. It's not something you can actually see or calculate with. You can just compare them. A hash function takes a value or a compound value and produces a simpler integer from it. An identity hash function takes an identity value and produces a simpler integer from it. Based on all these definitions, returning a random integer, as long as you store it and return it again the next time, is an identity hash function. > you normally hash the id/content of the thing you want to store That's what we're doing. You've said it yourself. We hash the id (identity) of the thing you want to store. You could call the identity the content of the object as well if you wanted to. It's not about replacing the actual content on the object, because JavaScript maps are, by design and by definition (23.1.3.6, 7.2.10), explicitly identity maps. They don't want to consider the content of an object, except for this abstract identity content. I'm not sure if you're arguing I'm mistaken, or the that the whole idea is wrong. But this is what many languages do and it's all very conventional terminology and practice.

gpderetta 9y ago
> An identity hash function takes an identity value and produces a simpler integer from it I would expect an identity hash function to be exactly that: i.e. a trivial function that takes a value and returns that value unmodified (i.e. the identity function). It happens to describe well this case because the input to the has function itself is the unique identifier and as it is already uniformly distributed, the has function can just return it unmodified.
- chrisseaton 9y ago
  In this context, an 'identity hash function' means that it's a 'hash function for an identity value'. It doesn't mean 'a hash function that is an identity function'. It's confusing!
- dfox 9y ago
  In the simple case of using memory location as object identity (ie. in system without moving GC) and typical textbook hashtable implementation simply using the pointer as hash value is highly suboptimal, because heap pointers do not have remotely uniform distribution (low order bits are always zero due to allignment constraints, high order bits tend to be constant and usually also zero...). On the other hand you can use more advanced hashtable design that is explicitly tuned for non-uniform hash value distribution. See CPythons dict for cannonical example of that, although it's motivations are somewhat different (the major reason is that in CPython even real hash values of object's content are intentionally non-uniform to allow for simple way of causing integer-valued floats to have same hash value as ints of same value).
onli 9y ago
Thanks for explaining, also to the others. > I'm not sure if you're arguing I'm mistaken, or the that the whole idea is wrong. But this is what many languages do and it's all very conventional terminology and practice. Neither, I just felt the terminology not fitting, I'd have called it id generation and left out the hash. V8 is generating the hash/id in the hash function, not doing something directly with the input or computing it (as in, calculating) from the input, right? Like if the hash terminology was added because one came from hash tables. I guess what I meant is that using and storing a random number here feels like a trick to fulfill the contract of a hash function without actually implementing one, since those usually look different (but I'm more used to see cryptographic hash functions). My definition of a hash function includes returning a word of fixed length, in practice that is not relevant here because the numerical representation is the same (001 = 01 = 1). But apart from that I can see now that the shown scheme fulfills the contract of a non-cryptographic hash function, the storing of the id and the virtual identity make it somehow fit.
- chrisseaton 9y ago
  > not doing something directly with the input or computing it (as in, calculating) from the input, right? It is doing something directly with the input and calculating something, if you make the leap to consider that the input object has a hidden abstract value which represents the object's identity.
  - onli 9y ago
    Big leap for me. But thanks, this helped understanding why it is called that way :)

munificent 9y ago

A hash function takes some state and produces a nicely-distributed random-ish number from it. Given the same state, it produces the same hash. I think you're OK with that definition of a hash function, right? In a mutable object-oriented language like JavaScript, two objects with the same properties are not the same object. Conversely, an object before and after mutating a property is still the same object. Thus, the "state" that matters for hashing is the object's identity, not its properties. Thus, V8's hash function produces a hash value given the identity of some object. Since there are no useful bits associated with "identity" that V8 can use to produce a hash value, it has to synthesize some at object creation time by calling rand. (If V8 didn't move objects in memory during GC, then the object's address in memory would be a good candidate for its identity. Indeed, in language implementations where objects don't move, the address is often used as an input to the hash function.)

onli 9y ago
So I actually looked up in my text book from way back how the course I learned this stuff in defined hash functions. I wanted to understand why this felt so wrong. According to that book a hash function is merely a mapping of a String (could also be called a word) of arbitrary length to a fixed length String, no requirement for having a nice distribution or ranomdishness. I guess this helps the V8 terminology, if one remembers that the fixed length part can be somewhat ignored when looking at numerical values. > Thus, V8's hash function produces a hash value given the identity of some object So if I got that right V8 is using the identity of an object as hash function, but since the identity is a virtual concept it replaces the identity with a randomly generated number - or is it later on doing something with that identity value? If not still feels strange to call that a hash, but I think I have to agree that it is a valid hash function given the definition.
- munificent 9y ago
  > a mapping of a String (could also be called a word) of arbitrary length to a fixed length String Right. It takes a longer sequence of bits and reduces it to a shorter sequence of bits, with a resulting chance for collision. > since the identity is a virtual concept it replaces the identity with a randomly generated number It's not replacing anything. Here's another way to think of it. V8 needs this function: int getHash(Object object) { ... } Given a reference to some object, it returns a hash code for it, based on the identity of the object. The requirements are: 1. Returned values should be nicely distributed over the number space. 2. If you same object in, you must get the same hash code out. Even if the object is mutated between calls. This sounds like a reasonable definition of a hash function, right? If all this function had access to was the object's properties and it had to be pure (couldn't modify anything), it's actually impossible to implement this function. (This, strangely enough, touches on fundamental ideas around mutability, identity, and equality.) So V8 relaxes the requirement that the function be pure. getHash() then generates a random number for the object, stuffs it in some hidden chunk of memory inside the object (what the linked article is about) and declares by fiat that that number is now the hash code for that object's otherwise-intangible identity.

skybrian 9y ago

Hash codes aren't actually exposed in JavaScript. It's an implementation detail. The only requirement is that key lookup is consistent with equals [1]. For a string key, the hashcode field is probably a cached hash of the value, since that's how an equality comparison works. Most objects are only equal to themselves, are mutable, and get moved in memory, so storing a unique identifier is the only way to know if it's the same object that you saw before. For a hash code, the identifier doesn't need to be unique since all that matters is that it's consistently placed in the same bucket. All you need is to store a sufficiently long random number. [1] SameValueZero equality as defined at https://developer.mozilla.org/en-US/docs/Web/JavaScript/Equality_comparisons_and_sameness https://developer.mozilla.org/en-US/docs/Web/JavaScript/Equa...

SloopJon 9y ago
Upvoted for pointing out that this random number isn't necessarily unique. There can be collisions, just as with a conventional hash.

gpderetta 9y ago

> you normally hash the id/content of the thing the random number /is/ the id. You can think of it as the unique address of the object in some other memory mapping. The hash function just happens to be the identity function in this case.

sfink 9y ago
No it isn't. This is not a unique id. Two different objects could easily have the same hash value. People are mixing up the mathematical term "identity function", meaning a function that maps its input directly to its output, with object identity. I have never heard this usage of the phrase, as in a function that takes an object identity as input.