Tabele mieszające VS tablice asocjacyjne

Ostatnio czytałem o tablicach skrótów w bardzo znanej książce „ Wprowadzenie do algorytmów ”. Nie używałem ich jeszcze w żadnych prawdziwych aplikacjach, ale chcę. Ale nie wiem, jak zacząć.
Czy ktoś może mi dać kilka przykładów jego użycia, na przykład jak zrealizować aplikację słownikową (taką jak ABBYY Lingvo) za pomocą tablic mieszających?
I na koniec chciałbym wiedzieć, jaka jest różnica między tablicami mieszającymi a tablicami asocjacyjnymi w PHP, chodzi mi o to, jakiej technologii powinienem używać iw jakich sytuacjach?
Jeśli się mylę (przepraszam), popraw mnie, bo tak naprawdę zaczynam od tablic mieszających i mam o nich tylko podstawową (teoretyczną) wiedzę.
Wielkie dzięki.

W PHP tablice asocjacyjne są implementowane jako tabele skrótów, z odrobiną dodatkowej funkcjonalności.

Jednak technicznie rzecz biorąc, tablica asocjacyjna nie jest identyczna z tablicą haszującą - jest po prostu zaimplementowana częściowo z tablicą haszującą za kulisami. Ponieważ większość jego implementacji to hashtable, może zrobić wszystko, co może hashtable - ale może też zrobić więcej.

Na przykład możesz zapętlić tablicę asocjacyjną za pomocą pętli for, czego nie możesz zrobić z tablicą haszującą.

Więc chociaż są podobne, tablica asocjacyjna może w rzeczywistości zrobić nadzbiór tego, co może zrobić tablica haszy - więc nie są dokładnie tym samym. Pomyśl o tym jak o tabelach mieszających i dodatkowej funkcjonalności.

Przykłady kodu:

Używanie tablicy asocjacyjnej jako tablicy hashy :

$favoriteColor = array();
$favoriteColor['bob']='blue';
$favoriteColor['Peter']='red';
$favoriteColor['Sally']='pink';
echo 'bob likes: '.$favoriteColor['bob']."\n";
echo 'Sally likes: '.$favoriteColor['Sally']."\n";
//output: bob likes blue
//        Sally likes pink

Przechodzenie przez tablicę asocjacyjną :

$idTable=array();
$idTable['Tyler']=1;
$idTable['Bill']=20;
$idTable['Marc']=4;
//up until here, we're using the array as a hashtable.

//now we loop through the array - you can't do this with a hashtable:
foreach($idTable as $person=>$id)
    echo 'id: '.$id.' | person: '.$person."\n";

//output: id: 1 | person: Tyler
//        id: 20 | person: Bill
//        id: 4 | person: Marc

Zwróć uwagę szczególnie na to, że w drugim przykładzie kolejność każdego elementu (Tyler, Bill Marc) jest utrzymywana na podstawie kolejności, w jakiej zostały wprowadzone do tablicy. Jest to główna różnica między tablicami asocjacyjnymi a tablicami mieszającymi. Tablica haszująca nie utrzymuje żadnego połączenia między przechowywanymi elementami, podczas gdy tablica asocjacyjna PHP tak (można nawet posortować tablicę asocjacyjną PHP).

Tablice php SĄ w zasadzie tablicami mieszającymi

Różnica między tablicą asocjacyjną a tablicą mieszającą polega na tym, że tablica asocjacyjna jest typem danych, podczas gdy tablica mieszająca jest implementacją danych. Oczywiście typ tablicy asocjacyjnej jest bardzo ważny w wielu obecnych językach programowania: Perl, Python, PHP itp. Tablica mieszająca jest głównym sposobem implementacji tablicy asocjacyjnej, ale nie jedynym sposobem. A tablice asocjacyjne są głównym zastosowaniem tablic mieszających, ale nie jedynym. Więc nie chodzi o to, że są takie same, ale jeśli masz już tablice asocjacyjne, zwykle nie powinieneś się martwić o różnicę.

Ze względu na wydajność ważne może być, aby wiedzieć, że tablice asocjacyjne w Twoim ulubionym języku są implementowane jako skróty. Może być ważne, aby mieć pojęcie o ogólnych kosztach tej implementacji. Tabele z skrótami są wolniejsze i zajmują więcej pamięci niż tablice liniowe, jak widać w C.

Perl łączy te dwie koncepcje ze sobą, nazywając tablice asocjacyjne „hashami”. Podobnie jak wiele funkcji Perla, nie jest całkiem zła, ale jest niechlujna.

Tablica w PHP jest w rzeczywistości uporządkowaną mapą, bez możliwości haszowania. Główna różnica między mapą a hashtable polega na niemożności zapamiętania kolejności, w jakich elementy zostały dodane. Z drugiej strony tabele skrótów są znacznie szybsze niż mapy. Złożoność pobierania elementu z mapy to O (nlogn), a z tablicy hashy O (1).

Tablica asocjacyjna to tablica, w której nie uzyskujesz dostępu do elementów przez indeks, ale przez klucz. Sposób, w jaki to działa wewnętrznie, zależy od implementacji (nie ma reguły, jak to musi działać). Tablica asocjacyjna może być zaimplementowana przez tablicę haszującą (większość implementacji to zrobi), ale może być również zaimplementowana przez jakąś strukturę drzewa lub listę pomijania lub algorytm po prostu iteruje po wszystkich elementach w tablicy i szuka klucza pasuje (byłoby to bardzo wolne, ale działa).

Tabela skrótów to sposób na przechowywanie danych, w których wartości są skojarzone z kluczami i gdzie zamierzasz znaleźć wartości dla kluczy w (zwykle prawie) stałym czasie. Brzmi to dokładnie tak, jak oczekujesz od tablicy asocjacyjnej, dlatego przez większość czasu do implementacji tych tablic używane są tablice skrótów, ale nie jest to obowiązkowe.