How is opEquals used in toHash

[Simen Kjærås]

On Tuesday, 18 May 2021 at 10:14:26 UTC, PinDPlugga wrote:
> But what I do not understand is why opEquals is necessary and 
> where in the implementation of toHash it plays its role? Since 
> area1 and area2 have different static arrays of Points I 
> understand why `typeid(points).getHash(&points)` would produce 
> different values for each, but it seems like the opEquals 
> should play a part in making them produce the same hash.

opEquals plays no part in how toHash does its thing, but it's 
important for how AAs work. When there's a hash collision, the 
colliding items are placed in a bucket, which is generally 
iterated linearly to find the matching element, using opEquals. 
Example code:

     ```d
     struct S {
         int i;
         size_t toHash() const nothrow @safe { return 3; }
         bool opEquals(ref const S rhs) const { return i == rhs.i; 
}
     }

     unittest {
         int[S] a;
         a[S(1)] = 3;
         a[S(2)] = 4; // Hash collision - both return 3
         assert(a.length == 2); // But they're both there
         assert(S(1) in a);
         assert(S(2) in a);
         int b = a[S(1)];
         int c = a[S(2)];
         assert(b == 3);
         assert(c == 4);
     }
     ```

And pseudocode for how an AA works:

     ```d
     struct AA(K, V) {
         import std.typecons : Tuple;
         alias Pair = Tuple!(K, "key", V, "value");
         alias Bucket = Pair[];

         Bucket[] buckets;

         this(int bucketCount) {
             buckets.length = bucketCount;
         }

         void opIndexAssign(V value, K key) {
             // Use hash to find correct bucket
             size_t hash = key.toHash();
             size_t index = hash % buckets.length;
             Bucket bucket = buckets[index];

             foreach (e; bucket) {
                 if (e.key == key) { // Check for duplicates with 
opEquals
                      e.value = value; // Overwrite existing
                      return;
                 }
             }

             bucket ~= Pair(key, value);
             // Array could reallocate when appended to,
             // so assign it back to the bucket list
             buckets[index] = bucket;
         }

         V opIndex(K key) {
             // Use hash to find correct bucket
             size_t hash = key.toHash();
             size_t index = hash % buckets.length;
             Bucket bucket = buckets[index];

             foreach (e; bucket) {
                 if (e.key == key) { // Check with opEquals
                     return e.value;
                 }
             }
             throw new Exception("Key not found");
         }
     }

     unittest {
         AA!(S, int) a = AA!(S, int)(24);
         a[S(1)] = 3;
         a[S(2)] = 4;
         assert(a[S(1)] == 3);
         assert(a[S(2)] == 4);
     }
     ```

This omits plenty of details, but should give some idea how AAs 
work.

--
   Simen