Co to jest tablica asocjacyjna?
Tablica asocjacyjna, zwana również tabelą skrótów lub mapą skrótu, jest podobna do standardowej tablicy, z wyjątkiem indeksu tablicy może być ciągami zamiast całkowitej. W wielu aplikacjach do bazy danych oraz w innych programach dotyczących dużych ilości danych tablica asocjacyjna jest istotnym elementem pomagającym w skutecznym sortowaniu i dostępu do informacji. U podstaw tablicy asocjacyjnej znajduje się standardowa tablica, która jest indeksowana z liczbami całkowitych, jak zwykle tak było. Specjalny algorytm nazywany funkcją skrótu przekształca indeks ciągu w indeks całkowitego, aby znaleźć wartość. Jest to spójna konwersja, więc rzeczywisty wskaźnik liczby całkowitych nigdy nie musi być przechowywany, ale zamiast tego jest obliczany z łańcucha za każdym razem.
terminologia używana w odniesieniu do tablicy asocjacyjnej może być nieco inna niż to, co jest używane podczas mówienia o normalnej tablicy. To, co zwykle nazywałoby się indeksem - numeryczna lokalizacja elementu wewnątrz tablicy - nazywa sięklawisz. Dane powiązane z kluczem nazywane są wartością. Oznacza to, że w ramach tablicy asocjacyjnej klucz jest powiązany z wartością, która koreluje z indeksem odnoszą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 numerycznego wartości opartej na kluczu. Istnieje kilka rodzajów funkcji skrótu, niektóre zaprojektowane do działalności na klawiszach, które są liczbami całkowitymi, a niektóre zaprojektowane do pracy na klawiszach, które są strunami. W przypadku klucza całkowitego popularną metodą jest podzielenie kluczowej wartości według wielkości tablicy i użycie pozostałej części podziału, miejmy nadzieję, uzyskaj unikalną wartość indeksu.
Funkcja skrótu może być znacznie bardziej złożona w przypadku klawiszy, które są strunami. Niektóre metody obejmują dodanie wartości numerycznej każdego znaku w ciągu, a następnie podzielenie jej przez pewną liczbę,lub używając tylko kilku pierwszych znaków łańcucha, aby uzyskać unikalny numer. Istnieje wiele sposobów na uzyskanie liczby z serii znaków.
W związku z dużą ilością par kluczowych w tablicy asocjacyjnej jeden problem, który może się pojawić, nazywa się kolizja. Kolizja ma miejsce, gdy wskaźnik liczb całkowitych pochodzący z klucza jest identyczny z indeksem liczb całkowitych innego klucza. Te dwa klucze skutecznie wskazują na ten sam wskaźnik w tablicy wartości. Istnieją różne rozwiązania kolizji, głównie dlatego, że ma ono duże prawdopodobieństwo, że w większości praktycznych zastosowań.
Jednym z rozwiązań do kolizji jest posiadanie każdego indeksu wartości faktycznie jest powiązaną listą, aby gdy więcej niż jeden klucz rozwiąże tę lokalizację indeksu, lokalizacja może pomieścić więcej niż jedną wartość. Nazywa się to łańcuchem i jest prostym sposobem radzenia sobie z kolizją, choć może również spowolnić czas potrzebny na pobranie informacji. Inną metodą radzenia sobie z kolizją nazywa się sondowanie liniowe.Gdy nastąpi zderzenie, sondowanie liniowe działa, przechodząc przez tablicę wartości, aż do znalezienia niewykorzystanego indeksu. To rozwiązanie może pomóc w równomiernym rozpowszechnianiu danych w tablicy asocjacyjnej, ale może również zwiększyć czas potrzebny do wyszukiwania wartości.