HashMap and collisions?

General JUCE discussion
1

I am planning to use a HashMap for <String, int> pairs. I.e. the String is the key and the int is the value .

From looking at the code, it seems the HashMap is not taking care of collisions? The "set" function reads as follows (taken from juce_HashMap.h):

    void set (KeyTypeParameter newKey, ValueTypeParameter newValue)
    {
        const ScopedLockType sl (getLock());
        const int hashIndex = generateHashFor (newKey);

        HashEntry* const firstEntry = hashSlots.getUnchecked (hashIndex);

        for (HashEntry* entry = firstEntry; entry != nullptr; entry = entry->nextEntry)
        {
            if (entry->key == newKey)
            {
                entry->value = newValue;
                return;
            }
        }

        hashSlots.set (hashIndex, new HashEntry (newKey, newValue, firstEntry));
        ++totalNumItems;

        if (totalNumItems > (getNumSlots() * 3) / 2)
            remapTable (getNumSlots() * 2);
    }

The thing is: if two different string keys happen to generate the same hashIndex, then the first entry gets overwritten, right? Or maybe/hopefully I am misreading the code?

2

You are misreading the code.

The HashMap is a classic chained hash table (an array of linked list entries).

  1. Compute the hash index.
  2. Fetch the first entry at the hash index in the array (could be nullptr).
  3. Search for an existed item with the same key in the linked list at the hash index (and just update it if any).
  4. If not, create and insert a new entry in front of the linked list. This entry points to the previously first entry (that could be nullptr).