Re: [Pharo-project] Two objects with same hash
On Sep 23, 2011, at 1:08 PM, Denis Kudriashov wrote:
Hello,
I use hash message to generate unique object id. (unique between current memory objects). And I catch situation when two objects has same hash value. Objects has been created in loop almost at same time.
So my question - is it really possible?
Yes, easily, as there are only 12 bits for the hash, there are only 4096 different hash values. This means that a hash is *not* at all a UUID, and all hashing data structures need to be optimized for the case of hash collision, as it will happen a lot. Marcus -- Marcus Denker -- http://marcusdenker.de
On Fri, 23 Sep 2011, Marcus Denker wrote:
On Sep 23, 2011, at 1:08 PM, Denis Kudriashov wrote:
Hello,
I use hash message to generate unique object id. (unique between current memory objects). And I catch situation when two objects has same hash value. Objects has been created in loop almost at same time.
So my question - is it really possible?
Yes, easily, as there are only 12 bits for the hash, there are only 4096 different hash values.
This means that a hash is *not* at all a UUID, and all hashing data structures need to be optimized for the case of hash collision, as it will happen a lot.
Not all hashed collections, just those which rely on identityHash. Also, they are not fully optimized. Significant improvements can be done with a new primitive. Levente
Marcus
-- Marcus Denker -- http://marcusdenker.de
Thank you for all your responses. I will use UUID. Another assumption: I know there is a trick to get object memory address. Can it be used for object identity? (inside memory of objects) * * 2011/9/23 Marcus Denker <marcus.denker@inria.fr>
On Sep 23, 2011, at 1:08 PM, Denis Kudriashov wrote:
Hello,
I use hash message to generate unique object id. (unique between current memory objects). And I catch situation when two objects has same hash value. Objects has been created in loop almost at same time.
So my question - is it really possible?
Yes, easily, as there are only 12 bits for the hash, there are only 4096 different hash values.
This means that a hash is *not* at all a UUID, and all hashing data structures need to be optimized for the case of hash collision, as it will happen a lot.
Marcus
-- Marcus Denker -- http://marcusdenker.de
On Fri, Sep 23, 2011 at 3:02 PM, Denis Kudriashov <dionisiydk@gmail.com>wrote:
Thank you for all your responses. I will use UUID.
Another assumption: I know there is a trick to get object memory address.
which one?
Can it be used for object identity? (inside memory of objects)
* * 2011/9/23 Marcus Denker <marcus.denker@inria.fr>
On Sep 23, 2011, at 1:08 PM, Denis Kudriashov wrote:
Hello,
I use hash message to generate unique object id. (unique between current memory objects). And I catch situation when two objects has same hash value. Objects has been created in loop almost at same time.
So my question - is it really possible?
Yes, easily, as there are only 12 bits for the hash, there are only 4096 different hash values.
This means that a hash is *not* at all a UUID, and all hashing data structures need to be optimized for the case of hash collision, as it will happen a lot.
Marcus
-- Marcus Denker -- http://marcusdenker.de
-- Mariano http://marianopeck.wordpress.com
I am sure I see It in some block bost. But dont remember 2011/9/23 Mariano Martinez Peck <marianopeck@gmail.com>
On Fri, Sep 23, 2011 at 3:02 PM, Denis Kudriashov <dionisiydk@gmail.com>wrote:
Thank you for all your responses. I will use UUID.
Another assumption: I know there is a trick to get object memory address.
which one?
Can it be used for object identity? (inside memory of objects)
* * 2011/9/23 Marcus Denker <marcus.denker@inria.fr>
On Sep 23, 2011, at 1:08 PM, Denis Kudriashov wrote:
Hello,
I use hash message to generate unique object id. (unique between current memory objects). And I catch situation when two objects has same hash value. Objects has been created in loop almost at same time.
So my question - is it really possible?
Yes, easily, as there are only 12 bits for the hash, there are only 4096 different hash values.
This means that a hash is *not* at all a UUID, and all hashing data structures need to be optimized for the case of hash collision, as it will happen a lot.
Marcus
-- Marcus Denker -- http://marcusdenker.de
-- Mariano http://marianopeck.wordpress.com
Maybe It is some example of NativeBoost 2011/9/23 Denis Kudriashov <dionisiydk@gmail.com>
I am sure I see It in some block bost. But dont remember
2011/9/23 Mariano Martinez Peck <marianopeck@gmail.com>
On Fri, Sep 23, 2011 at 3:02 PM, Denis Kudriashov <dionisiydk@gmail.com>wrote:
Thank you for all your responses. I will use UUID.
Another assumption: I know there is a trick to get object memory address.
which one?
Can it be used for object identity? (inside memory of objects)
* * 2011/9/23 Marcus Denker <marcus.denker@inria.fr>
On Sep 23, 2011, at 1:08 PM, Denis Kudriashov wrote:
Hello,
I use hash message to generate unique object id. (unique between current memory objects). And I catch situation when two objects has same hash value. Objects has been created in loop almost at same time.
So my question - is it really possible?
Yes, easily, as there are only 12 bits for the hash, there are only 4096 different hash values.
This means that a hash is *not* at all a UUID, and all hashing data structures need to be optimized for the case of hash collision, as it will happen a lot.
Marcus
-- Marcus Denker -- http://marcusdenker.de
-- Mariano http://marianopeck.wordpress.com
On Fri, Sep 23, 2011 at 3:22 PM, Denis Kudriashov <dionisiydk@gmail.com>wrote:
I am sure I see It in some block bost. But dont remember
Ok, but GC can move objects arround. If you stick to that value as #hash then you dictionaries will be screw...you would need a rehash. But you don't know when to trigger it ;)
2011/9/23 Mariano Martinez Peck <marianopeck@gmail.com>
On Fri, Sep 23, 2011 at 3:02 PM, Denis Kudriashov <dionisiydk@gmail.com>wrote:
Thank you for all your responses. I will use UUID.
Another assumption: I know there is a trick to get object memory address.
which one?
Can it be used for object identity? (inside memory of objects)
* * 2011/9/23 Marcus Denker <marcus.denker@inria.fr>
On Sep 23, 2011, at 1:08 PM, Denis Kudriashov wrote:
Hello,
I use hash message to generate unique object id. (unique between current memory objects). And I catch situation when two objects has same hash value. Objects has been created in loop almost at same time.
So my question - is it really possible?
Yes, easily, as there are only 12 bits for the hash, there are only 4096 different hash values.
This means that a hash is *not* at all a UUID, and all hashing data structures need to be optimized for the case of hash collision, as it will happen a lot.
Marcus
-- Marcus Denker -- http://marcusdenker.de
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
Yes, I know. I just use generated object id to create unique file to archive object. I generate id by current date and time "yyyyMMddHHmmssSSS + object hash". But It is my mistake. Now I use "yyyyMMddHHmmssSSS + UUID" (I need date parameter too). And I think id like "yyyyMMddHHmmssSSS + object address" is good too for my purpose. 2011/9/23 Mariano Martinez Peck <marianopeck@gmail.com>
On Fri, Sep 23, 2011 at 3:22 PM, Denis Kudriashov <dionisiydk@gmail.com>wrote:
I am sure I see It in some block bost. But dont remember
Ok, but GC can move objects arround. If you stick to that value as #hash then you dictionaries will be screw...you would need a rehash. But you don't know when to trigger it ;)
2011/9/23 Mariano Martinez Peck <marianopeck@gmail.com>
On Fri, Sep 23, 2011 at 3:02 PM, Denis Kudriashov <dionisiydk@gmail.com>wrote:
Thank you for all your responses. I will use UUID.
Another assumption: I know there is a trick to get object memory address.
which one?
Can it be used for object identity? (inside memory of objects)
* * 2011/9/23 Marcus Denker <marcus.denker@inria.fr>
On Sep 23, 2011, at 1:08 PM, Denis Kudriashov wrote:
Hello,
I use hash message to generate unique object id. (unique between current memory objects). And I catch situation when two objects has same hash value. Objects has been created in loop almost at same time.
So my question - is it really possible?
Yes, easily, as there are only 12 bits for the hash, there are only 4096 different hash values.
This means that a hash is *not* at all a UUID, and all hashing data structures need to be optimized for the case of hash collision, as it will happen a lot.
Marcus
-- Marcus Denker -- http://marcusdenker.de
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
On 23 September 2011 16:32, Denis Kudriashov <dionisiydk@gmail.com> wrote:
Yes, I know.
I just use generated object id to create unique file to archive object. I generate id by current date and time "yyyyMMddHHmmssSSS + object hash". But It is my mistake. Now I use "yyyyMMddHHmmssSSS + UUID" (I need date parameter too). And I think id like "yyyyMMddHHmmssSSS + object address" is good too for my purpose.
AFAIK, UUID generation algorithm already includes a current time inside. Which means that your addition of date/time actually superfluous.
2011/9/23 Mariano Martinez Peck <marianopeck@gmail.com>
On Fri, Sep 23, 2011 at 3:22 PM, Denis Kudriashov <dionisiydk@gmail.com> wrote:
I am sure I see It in some block bost. But dont remember
Ok, but GC can move objects arround. If you stick to that value as #hash then you dictionaries will be screw...you would need a rehash. But you don't know when to trigger it ;)
2011/9/23 Mariano Martinez Peck <marianopeck@gmail.com>
On Fri, Sep 23, 2011 at 3:02 PM, Denis Kudriashov <dionisiydk@gmail.com> wrote:
Thank you for all your responses. I will use UUID.
Another assumption: I know there is a trick to get object memory address.
which one?
Can it be used for object identity? (inside memory of objects)
2011/9/23 Marcus Denker <marcus.denker@inria.fr>
On Sep 23, 2011, at 1:08 PM, Denis Kudriashov wrote:
Hello,
I use hash message to generate unique object id. (unique between current memory objects). And I catch situation when two objects has same hash value. Objects has been created in loop almost at same time.
So my question - is it really possible?
Yes, easily, as there are only 12 bits for the hash, there are only 4096 different hash values.
This means that a hash is *not* at all a UUID, and all hashing data structures need to be optimized for the case of hash collision, as it will happen a lot.
    Marcus
-- Marcus Denker -- http://marcusdenker.de
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
-- Best regards, Igor Stasenko.
On 23. sep. 2011, at 16:47, Igor Stasenko <siguctua@gmail.com> wrote:
On 23 September 2011 16:32, Denis Kudriashov <dionisiydk@gmail.com> wrote:
Yes, I know.
I just use generated object id to create unique file to archive object. I generate id by current date and time "yyyyMMddHHmmssSSS + object hash". But It is my mistake. Now I use "yyyyMMddHHmmssSSS + UUID" (I need date parameter too). And I think id like "yyyyMMddHHmmssSSS + object address" is good too for my purpose.
AFAIK, UUID generation algorithm already includes a current time inside. Which means that your addition of date/time actually superfluous.
No. The plugin (when it works) generates type 4 UUIDs, which is purely random bytes from dev/urandom (with some bitfields identifying version). The fallback code uses current time as part of a PRNG seed, but also attempts to achieve a type 4 UUID. Cheers, Henry
participants (6)
-
Denis Kudriashov -
Henrik Johansen -
Igor Stasenko -
Levente Uzonyi -
Marcus Denker -
Mariano Martinez Peck