Co to jest tablica asocjacyjna?

Tablica asocjacyjna, zwana również tabelą skrótu 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 w razie potrzeby za każdym razem.

Użyta terminologia używana w odniesieniu do tablicy asocjacyjnej może być nieco inna niż to, co jest używane podczas mówienia.normalna tablica.Co zwykle nazywałoby się indeksem mdash;Numeryczna lokalizacja elementu wewnątrz tablicy mdash;nazywa się klucz.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 odnoszącym się do elementu w standardowej tablicy w strukturze danych.

w centrum każdej tablicy asocjacyjnej znajduje się 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 liczb całkowitych popularną metodą jest podzielenie kluczowej wartości według wielkości tablicy i użycie pozostałej części podziału, aby, miejmy nadzieję, uzyskaj unikalną wartość indeksu.

Funkcja skrótu może być znacznie bardziej złożonadla klawiszy, które są sznurkami.Niektóre metody obejmują dodanie wartości numerycznej 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 szeregu znaków.

W przypadku dużej liczby 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 do 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, tak że jest to lista powiązana, aby gdy więcej niż jeden klucz rozwiąże ten indeks tenLokalizacja, 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.