hash values and equality

[MRAB]

On 20/05/2011 20:01, Christian Heimes wrote:
> Am 20.05.2011 17:50, schrieb MRAB:
>> Is this strictly true? I thought that the hash value, an integer, is
>> moduloed (Is that how you spell it? Looks weird!) with the number of
>> array elements to give an index into the array, so different hashes
>> could give the same index, and objects with different hashes could be
>> stored in the same 'bucket'.
>
> I don't think 'moduloed' is an existing word but your description is
> mostly correct. The hash of the object and length of the hash table are
> used to calculate the position in the hash table. However Python's
> implementation doesn't use buckets to reduce memory usage and pointer
> dereferencing. If a slot in the hash table is already filled with an
> object that is not equal to the new object (a collision), the hash is
> shifted and the new slot is checked. The implementation detail is well
> described in Modules/dictobject.c.
>
A brief search on the web found a use of the word in 1982.