Tablica asocjacyjna, zwana także tablicą mieszającą lub mapą mieszającą, jest podobna do tablicy standardowej, z wyjątkiem tego, że indeks tablicy może być łańcuchem zamiast liczby całkowitej. W wielu aplikacjach bazodanowych i innych programach obsługujących duże ilości danych tablica asocjacyjna jest istotnym elementem pomagającym w efektywnym sortowaniu i dostępie do informacji. Rdzeniem tablicy asocjacyjnej jest standardowa tablica, która jest indeksowana liczbami całkowitymi, jak zwykle. Specjalny algorytm zwany funkcją mieszającą konwertuje indeks ciągu na indeks liczby całkowitej w celu znalezienia wartości. Jest to spójna konwersja, więc rzeczywisty indeks liczb całkowitych nigdy nie musi być przechowywany, ale zamiast tego jest obliczany z ciągu w razie potrzeby za każdym razem.
Terminologia używana w odniesieniu do tablicy asocjacyjnej może nieco różnić się od używanej w odniesieniu do tablicy normalnej. To, co normalnie nazwałoby się indeksem — numeryczną lokalizacją elementu wewnątrz tablicy — nazywa się kluczem. Dane powiązane z kluczem nazywane są wartością. Oznacza to, że w tablicy asocjacyjnej klucz jest powiązany z wartością, która koreluje z indeksem odwołującym się do elementu w standardowej tablicy w strukturze danych.
Sercem każdej tablicy asocjacyjnej jest funkcja skrótu. Jest to algorytm używany do określenia indeksu liczbowego wartości na podstawie klucza. Istnieje kilka typów funkcji skrótu, niektóre przeznaczone do działania na klawiszach będących liczbami całkowitymi, a niektóre przeznaczone do działania na klawiszach będących łańcuchami. W przypadku klucza liczb całkowitych popularną metodą jest podzielenie wartości klucza przez rozmiar tablicy i wykorzystanie pozostałej części dzielenia, aby, miejmy nadzieję, uzyskać unikalną wartość indeksu.
Funkcja skrótu może być znacznie bardziej złożona w przypadku kluczy będących ciągami. Niektóre metody obejmują dodanie wartości liczbowej każdego znaku w ciągu, a następnie podzielenie go przez pewną liczbę lub użycie tylko kilku pierwszych znaków ciągu w celu uzyskania unikalnej liczby. Istnieje wiele sposobów na wyprowadzenie liczby z ciągu znaków.
Gdy mamy do czynienia z dużą liczbą par klucz-wartość w tablicy asocjacyjnej, jeden problem, który może się pojawić, nazywa się kolizją. Kolizja ma miejsce, gdy indeks całkowity uzyskany z klucza jest identyczny z indeksem całkowitym innego klucza. Te dwa klucze w efekcie wskazują ten sam indeks w tablicy wartości. Istnieją różne rozwiązania kolizji, głównie dlatego, że istnieje duże prawdopodobieństwo wystąpienia kolizji w większości praktycznych zastosowań.
Jednym z rozwiązań kolizji jest to, aby każdy indeks wartości był właściwie połączoną listą, tak aby w przypadku, gdy więcej niż jeden klucz odnosi się do tej lokalizacji indeksu, lokalizacja może zawierać więcej niż jedną wartość. Nazywa się to tworzeniem łańcuchów i jest prostym sposobem radzenia sobie z kolizją, ale może również spowolnić czas potrzebny na odzyskanie informacji. Inną metodą radzenia sobie z kolizją jest sondowanie liniowe. Gdy wystąpi kolizja, sondowanie liniowe działa poprzez poruszanie się po tablicy wartości, aż do znalezienia nieużywanego indeksu. To rozwiązanie może pomóc w utrzymaniu równomiernego rozmieszczenia danych w tablicy asocjacyjnej, ale może również wydłużyć czas potrzebny na wyszukanie wartości.