Stephane CHAZELAS wrote:
> 2008-05-04, 19:35(+02), Dave B:
> [...]
>
>>FWIW, GNU awk (the only awk I have access to the sources ATM) seems to use
>>hash tables.
>>According to http://www.gnu.org/manual/gawk/html_node/internals.html,
>>lookups are performed using the assoc_lookup() function. Looking at the
>>sources (gawk 3.1.5), the function is in array.c, lines 483-562. The hash
>>function itself is at lines 331-414 in the same file.
>
> [..]
>
> From reading the code in the heirloom toolchest, looks like the
> original awk from 1979 (and nawk) by A, W and K also used hash
> tables.
>
> So does mawk.
>

And some brief timing tests with gawk seem to confirm linear complexity.

Janis