Table de hachage
Table de hachage (en anglais hash table) : structure de données qui associe des clés à des valeurs en calculant, pour chaque clé, un nombre (son hachage) qui désigne une case d'un tableau. Retrouver une clé ne demande qu'un calcul et une comparaison, quel que soit le nombre d'éléments : c'est ce qui rend rapides les tableaux associatifs d'awk, de Bash, ou les dictionnaires de Python. Deux clés qui tombent dans la même case (une collision) sont départagées par une liste ou une autre case ; quand la table se remplit, elle est agrandie et ses éléments redistribués.
Conséquence visible : l'ordre dans lequel for (k in t) parcourt un tableau d'awk suit la disposition interne des cases, pas l'ordre d'insertion ni l'ordre alphabétique ; il change d'une implémentation à l'autre, voire d'un jeu de données à l'autre. Une sortie destinée à un humain ou à un test se trie explicitement.