Co to jest tablica asocjacyjna?
Tablica asocjacyjna, zwana także tablicą skrótu lub mapą skrótu, jest podobna do tablicy standardowej, z tym wyjątkiem, że indeks tablicy może być łańcuchem zamiast liczby całkowitej. W wielu aplikacjach bazodanowych i innych programach zajmujących się dużymi ilościami danych tablica asocjacyjna jest istotnym elementem pomagającym w wydajnym sortowaniu i uzyskiwaniu dostępu do informacji. Rdzeniem tablicy asocjacyjnej jest standardowa tablica indeksowana liczbami całkowitymi, jak to zwykle bywa. Specjalny algorytm zwany funkcją skrótu konwertuje indeks łańcucha na indeks liczb całkowitych w celu znalezienia wartości. Jest to spójna konwersja, więc rzeczywisty indeks liczb całkowitych nigdy nie musi być przechowywany, ale jest obliczany za pomocą ciągu za każdym razem za każdym razem.
Terminologia stosowana w odniesieniu do tablicy asocjacyjnej może nieznacznie różnić się od terminologii używanej w przypadku tablicy normalnej. To, co normalnie nazywane jest indeksem - numeryczna lokalizacja 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ślania liczbowego indeksu wartości na podstawie klucza. Istnieje kilka rodzajów funkcji skrótu, niektóre przeznaczone do działania na klawiszach, które są liczbami całkowitymi, a niektóre do działania na klawiszach, które są ciągami znaków. W przypadku klucza całkowitego popularną metodą jest podzielenie wartości klucza przez rozmiar tablicy i użycie pozostałej części podziału, aby, miejmy nadzieję, uzyskać unikalną wartość indeksu.
Funkcja skrótu może być znacznie bardziej złożona dla kluczy będących ciągami znaków. 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, aby uzyskać unikalny numer. Istnieje wiele sposobów uzyskania liczby z ciągu znaków.
W przypadku dużej liczby par klucz-wartość w tablicy asocjacyjnej jeden problem, który może się pojawić, nazywa się kolizją. Kolizja ma miejsce, gdy indeks liczb całkowitych uzyskany z klucza jest identyczny z indeksem liczb całkowitych innego klucza. Te dwa klucze następnie skutecznie wskazują ten sam indeks w tablicy wartości. Istnieją różne rozwiązania kolizji, głównie dlatego, że ma duże prawdopodobieństwo wystąpienia w większości praktycznych zastosowań.
Jednym z rozwiązań kolizji jest fakt, że każdy indeks wartości jest faktycznie połączoną listą, dzięki czemu, gdy więcej niż jeden klucz rozpoznaje tę lokalizację indeksu, lokalizacja może zawierać więcej niż jedną wartość. Nazywa się to łańcuchem i jest prostym sposobem radzenia sobie z kolizją, chociaż może również spowolnić czas potrzebny na odzyskanie informacji. Inną metodą radzenia sobie z kolizją jest sondowanie liniowe. Kiedy dochodzi do kolizji, 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 równomiernym rozłożeniu danych w tablicy asocjacyjnej, ale może także wydłużyć czas potrzebny na wyszukanie wartości.