Nincs keresgélés, hanem hasító függvény van és ennek a funkciója egyszerűen megérthető. Ez nem egy új találmány ahogy maga az awk sem. :)
A példádban levő hagyományos tömb címzés az részhalmaza az asszociatív tömböknek, ha a a kulcsok csak int-ek lehetnek a hasító függvény pedig ennyit csinál: érték helye a memóriában = tömb címe + kulcs * kulcs által elfoglalt memória.
Ha a hasító függvény nem lenne jobb mint egy hagyományos keresés akkor nem lenne értelme :)