Słownik kontra lista

Więc wpadłem na Dictionary<int, int>dzisiaj w pracy. Wydawało mi się to dziwne, ponieważ prawdopodobnie użyłbym List<int>zamiast tego. Czy jest jakaś różnica i czy byłby przypadek użycia, w którym jedna struktura byłaby preferowana względem drugiej?

Użyłbyś a, Dictionary<int, int>jeśli twoje indeksy mają specjalne znaczenie oprócz samego umiejscowienia pozycyjnego.

Bezpośrednim przykładem, który przychodzi mi na myśl, jest przechowywanie kolumny identyfikatora i kolumny int w bazie danych. Na przykład, jeśli masz [person-id]kolumnę i [personal-pin]kolumnę, możesz umieścić je w Dictionary<int, int>. W ten sposób pinDict[person-id]otrzymasz kod PIN, ale indeks jest znaczący, a nie tylko pozycja w List<int>.

Ale tak naprawdę, za każdym razem, gdy masz dwie powiązane listy liczb całkowitych, może to być odpowiednia struktura danych.

Pomyśl Listo tablicy Dictionaryjak o tablicy mieszającej . Używałbyś tylko Dictionary, gdybyś musiał mapować (lub kojarzyć) znaczące klucze do wartości, podczas gdy Listtylko mapował (lub kojarzył) pozycje (lub indeksy) z wartościami.

Powiedzmy na przykład, że chcesz zachować związek między wiekiem osoby a jej wzrostem. Możesz użyć a, Dictionary<int, int>aby zmapować wiek (an int) osoby na jej wzrost (an int):

Dictionary<int, int> personHeightMap = new Dictionary<int, int>();

personHeightMap.Add(21, 185);
personHeightMap.Add(31, 174);

int height = personHeightMap.ContainsKey(21) ? personHeightMap[21] : -1;

Niezbyt przydatny przykład, ale chodzi o to, że nie byłbyś w stanie zrobić tego tak elegancko, Listponieważ musiałby przechowywać te wartości na miejscu.

Semantycznie, Dictionary<int, T>ai List<T>są bardzo podobne, oba są kontenerami o swobodnym dostępie w środowisku .NET. Aby użyć listy jako zamiennika słownika, potrzebujesz specjalnej wartości w swoim typie T(np. null) Do reprezentowania pustych miejsc na liście. Jeśli Tnie jest typu zerowalnego int, możesz użyć int?zamiast tego, lub jeśli tylko chcesz przechowywać wartości dodatnie, możesz również użyć specjalnej wartości, takiej jak -1, aby reprezentować puste miejsca.

Który wybierzesz, powinien zależeć od zakresu kluczowych wartości. Jeśli twoje klucze Dictionary<int, T>znajdują się w przedziale całkowitym, bez wielu przerw między nimi (na przykład 80 wartości z [0, ... 100]), to a List<T>będzie bardziej odpowiednie, ponieważ dostęp do indeksu jest szybszy i w tym przypadku jest mniej pamięci i czasu.

Jeśli twoje kluczowe wartości to 100 intwartości z zakresu takiego jak [0, ..., 1000000], to List<T>potrzebna jest pamięć do przechowywania 1000000 wartości T, gdzie słownik będzie potrzebował pamięci rzędu wielkości około 100 wartości T, 100 wartości int (plus pewien narzut, w rzeczywistości oczekujemy około 2 razy więcej pamięci do przechowywania tych 100 kluczy i wartości). W tym drugim przypadku słownik będzie bardziej odpowiedni.

Jak ktokolwiek może uznać je za równoważne?

Słownik jest rzadki i pozwala na losowe wstawianie, ale sprawia, że ​​przechodzenie w kolejności jest problemem, lista nie jest rzadka, a wstawianie poza kolejnością jest drogie, z natury zapewnia przechodzenie w kolejności.

Byłoby bardzo niewiele sytuacji, w których jedna nie byłaby dramatycznie lepsza od drugiej.

Poza tym: inne języki programowania określają ten typ struktury danych jako mapę, a nie słownik.

Jeśli twoje dane można w znaczący sposób zdefiniować jako pary klucz / wartość, Słownik zapewni znacznie szybszy dostęp, jeśli będziesz musiał znaleźć wartość za pomocą jej klucza.

Załóżmy na przykład, że masz listę klientów. Każdy klient zawiera takie dane, jak nazwa i adres oraz unikalny numer klienta. Załóżmy, że masz także listę przetwarzanych zamówień. Każde zamówienie będzie zawierało szczegóły tego, co jest robione, i będzie musiało zawierać numer klienta osoby, która je zamówiła.

Kiedy zamówienie jest gotowe do wysyłki, musisz znaleźć adres, na który chcesz je wysłać. Jeśli klienci są zapisani jako zwykła lista, musisz przeszukać całą listę, aby znaleźć klienta z odpowiednim numerem klienta. Zamiast tego możesz przechowywać klientów w Słowniku, podając numer klienta jako klucz. Słownik pozwoli teraz wyciągnąć właściwego klienta w jednym kroku, bez konieczności wyszukiwania.

Słownik używa haszowania do wyszukiwania danych. Słownik najpierw obliczył wartość skrótu dla klucza i ta wartość skrótu prowadzi do docelowego segmentu danych. Następnie każdy element w wiadrze należy sprawdzić pod kątem równości. Ale tak naprawdę lista będzie szybsza niż słownik przy wyszukiwaniu pierwszego elementu, ponieważ nic nie trzeba przeszukiwać w pierwszym kroku. Ale w drugim kroku lista musi przejrzeć pierwszy element, a następnie drugi element. Dlatego każdy krok zajmuje coraz więcej czasu. Im większa lista, tym dłużej trwa.

Więcej o .... Słownik Vs Lista z przykładem.

Jeśli dany kod przechowuje dwa zestawy skorelowanych wartości, klasa Dictionary zapewnia indeksowany sposób wyszukiwania wartości według klucza. Jeśli istnieje tylko jeden zestaw wartości, ale do tego zestawu należy uzyskać dostęp losowo (być może w celu sprawdzenia istnienia klucza w zestawie), a wartości są unikalne, zestaw HashSet może być najlepszą klasą zestawu do użycia.

To świetne odpowiedzi, które wydają się obejmować podstawy.

Kolejną kwestią, którą przedstawię, jest to, że słowniki (w języku C #) są bardziej złożone z punktu widzenia kodowania. Posiadanie zarówno list, jak i słowników w tej samej bazie kodu utrudnia utrzymanie kodu, ponieważ obie metody mają subtelne różnice w wykonywaniu podstawowych operacji, takich jak wyszukiwanie i zestawianie danych obiektu. Moim zdaniem jest to, że o ile nie potrzebujesz słownika z uzasadnionego powodu, skorzystaj z listy.