[Newbies] Collection>>Includes:...

[Damien Cassou]

cdrick wrote:
> 
> 
> 2006/8/7, stéphane ducasse <ducasse at iam.unibe.ch 
> <mailto:ducasse at iam.unibe.ch>>:
> 
>     Hi florent
> 
>     Read K. Beck idiom on redefining = normally you MUST also redefine hash
> 
>     the pattern Kent suggested was
> 
> 
>     Book>>= anBook
>             (self author = anBook author ) and: [self name = anBook
>     name]     (a)
> 
>     Book>>hash
>             self author hash bitXor: self  name hash     (b)
> 
> 
> I'm aware of that... but I just don't understand what's: 'hash bitXor:'
> 
> why (a) is not sufficient ?
> 
> hash tables doesn't talk to me too much ;). 
> What I imagine is that bitXOr gives a logical (byte) representation ?  
> and these are used in a table (hash) to access objects (pointers)?

Set and Dictionaries have a special ways of storing objects. They 
compute a position in an array from a number calculated on the object. 
This number is returned from the #hash method sent on the object and 
manipulated to have an index in the array (using a modulo operator for 
example).

http://en.wikipedia.org/wiki/Hash_table

As an example, you want to store aBook in an empty hash table.

aHashTable add: aBook


image the hash table has an array of size 10 filled with nil because the 
table is empty.

So, when adding, the hash table will compute the index in which the 
object will be stored:


HashTable>>computeIndexFor: anObject
   ^ anObject hash \\ self array size

\\ is the implementation of the modulo function which basically returns 
a number between 0 and the parameter based on the receiver.

Then, the add: method is:

HashTable>>add: anObject
   self array
     at: (self computeIndexFor: anObject)
     put: anObject.

This is very very simplified but the idea is there in my opinion.

Now, you should find how the hash table can store more than 10 objects. 
Hint: the array does not have to be resized (but sometimes it will for 
efficiency).


Is it clearer ? Feel free to ask more