Contact noury because I do not remember. But having a little builder is also nice.
On Fri, Oct 6, 2017 at 4:15 PM, Vitor Medina Cruz <vitormc...@gmail.com> wrote: > Stephane > > "Vitor why don't you take it as a small project to propose a solution for > Pharo." > > I will try :) I like the idea of using a Trait. > > > Em 6 de out de 2017 05:01, "Stephane Ducasse" <stepharo.s...@gmail.com> > escreveu: > > Here is what I extracted from older emails > > From David Allouche in Pharo-dev to see if > The ==hash== method is used in Pharo to separate objects in > bucket-based data structures. > > > !! Property > > It must have one required property which is required data integrity: > > !!!! A. > Objects that are equal according to ==\=== must have equal hashes. > > > It should have two desirable properties that are required to support > the algorithmic assumptions of bucket-based data structures: > > !!!! B. > Objects that are not equal should have different hashes. Ideally, the > probability of hash collision should by 1/N where N is the size of > hash value space. > > !!!! C. The hash values should spread as much as possible over their > value space. For example: ProtoObject>>#identityHash. > > > > > How these two desirable properties can be implemented depends on the > actual distribution of the values used to compute the hash. > > An object can safely use XOR hashing if its instance variables are all > different objects that already provide a hash method with these two > properties. > > @@todo check following sentence because the use of singleton is obscure > > For example, an object whose behaviour is defined by several of > singleton delegates of different classes that do not override > Object>>#hash. > > But if the instance variables are not guaranteed to have those > properties, it is necessary to more thoroughly "mix the bits". For > example the method ==hash== of ==SequenceableCollection== illustrates > this point. > > > [[[ > SequenceableCollection >> hash > | hash | > hash := self species hash. > 1 to: self size do: [:i | hash := (hash + (self at: i) hash) hashMultiply]. > ^ hash > ]]] > > > The mixing of the bits is done by the combination of addition and > ==hashMultiply==. The value of ==species hash== does not need to be > processed by ==hashMultiply==, because it is probably computed by the > method =identityHash== of ==ProtoObject==, and that already provides > property C. > > !!! When we should not use XOR > > ==LayoutFrame== is a particularly good example of a data structure > that should not use XOR hashing. Its instance variables provide none > of the required properties: > > - ==SmallInteger>>hash== is just ==^self==. > - In addition, common ==LayoutFrame== instances tend to use pairs of > identical values in their instance variables. Like ==0@0 corner: > 1@1==, or ==Margin fromNumber: 10==. > > A good hash function for LayoutFrame needs to: > > - Get hashes for each instance variable that provides properties A and B. > - Combine them in a way that is order-sensitive (to maintain property > B) and that does some extra mixing (to provide property C). > > Now, we can assume that common values for the instance variables will > be instances of ==SmallInteger==, ==Float==, or ==Fraction==. > > You can see in ==Fraction>>hash==, that a comment mentions the > assumption that the fraction is already reduced, that is what makes it > acceptable to use bitXor. > > The hash of ==SmallInteger== does provide properties A and B, but not > property C. The hash of ==Float== is harder to understand, but tests > show that it provides distinct values for 0.5, 0.25 and 0.125. So it > hopefully provides B for the range of values of interest to > ==LayoutFrame==. > > Another class that has similar hashing constraints to ==LayoutFrame== > is ==Point==. Its ==hash== method is: > > [[[ > Point >> hash > "Hash is reimplemented because = is implemented." > ^(x hash hashMultiply + y hash) hashMultiply > ]]] > > It does not include species in the computation, which is less than > ideal because it favours collisions with objects of different species > that have a similar content and a the same hash algorithm. > > Finally, it is probably not necessary or useful to use the accessors > to get to the instance variables. > > So a good implementation for LayoutFrame is > > [[[ > LayoutFrame >> hash > | hash | > hash := self species hash > hash := (hash + leftFraction hash) hashMultiply > hash := (hash + leftOffset hash) hashMultiply > hash := (hash + topFraction hash) hashMultiply > hash := (hash + topOffset hash) hashMultiply > hash := (hash + rightFraction hash) hashMultiply > hash := (hash + rightOffset hash) hashMultiply > hash := (hash + bottomFraction hash) hashMultiply > hash := (hash + bottomOffset hash) hashMultiply > ^ hash > ]]] > > On Fri, Oct 6, 2017 at 9:59 AM, Stephane Ducasse > <stepharo.s...@gmail.com> wrote: >> Noury also proposed a trait to avoid to systematically have to implement >> hash. >> Vitor why don't you take it as a small project to propose a solution for >> Pharo. >> >> On Thu, Oct 5, 2017 at 6:34 PM, Vitor Medina Cruz <vitormc...@gmail.com> >> wrote: >>> Yes, canEqual implementation also make #= be commutative. >>> >>> On Tue, Oct 3, 2017 at 11:11 AM, Denis Kudriashov <dionisi...@gmail.com> >>> wrote: >>>> >>>> >>>> 2017-10-02 17:30 GMT+02:00 Denis Kudriashov <dionisi...@gmail.com>: >>>>> >>>>> >>>>> 2017-10-02 17:13 GMT+02:00 Vitor Medina Cruz <vitormc...@gmail.com>: >>>>>> >>>>>> I am sorry, not species, but #isKindOf istead of #= to compare >>>>>> classes. >>>>> >>>>> >>>>> It is bad idea. #= should be transitive. >>>> >>>> >>>> Oh, I used wrong word, shame on me :). I tried to say commutative. >>>> >>>>> >>>>> How you will generate it with isKindOf: logic? You need to know common >>>>> parent. >>>>> >>>>> Also I not remember cases where I was needed two instances of different >>>>> classes to be equal. >>>>> And I can imaging the problems which it will lead to. >>>>> >>>>>> >>>>>> >>>>>> On Mon, Oct 2, 2017 at 11:57 AM, Denis Kudriashov >>>>>> <dionisi...@gmail.com> >>>>>> wrote: >>>>>>> >>>>>>> >>>>>>> 2017-10-02 16:37 GMT+02:00 Sean P. DeNigris <s...@clipperadams.com>: >>>>>>>> >>>>>>>> >>>>>>>> Two questions/comments about the generated code: >>>>>>>> 1. #= >>>>>>>> ... >>>>>>>> self class = anObject class "should compare #species >>>>>>>> instead?" >>>>>>>> ifFalse: [ ^ false ]. >>>>>>>> ... >>>>>>>> Typically, I've seen #species instead of #class in the guard >>>>>>>> statement. >>>>>>>> Should we change it to that? >>>>>>> >>>>>>> >>>>>>> I doubt that it is important for domain classes. Because I never saw >>>>>>> the user of #species which is not a kind of Collection. And for >>>>>>> collections >>>>>>> this refactoring is not valid anyway. >>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> 2. #hash >>>>>>>> ^ var1 hash bitXor: (var2 hash bitXor: var3 hash) >>>>>>>> Is this implementation always safe? It's what I usually hand roll >>>>>>>> based on >>>>>>>> what I've seen, but Andres Valloud wrote a whole (large) book on >>>>>>>> hashing, so >>>>>>>> I've always wondered if I was missing something… >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> ----- >>>>>>>> Cheers, >>>>>>>> Sean >>>>>>>> -- >>>>>>>> Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html >>>>>>>> >>>>>>> >>>>>> >>>>> >>>> >>> > >
