Sekcja CFDictionary z Collections Programming Topics for Core Foundation (który należy przyjrzeć się, jeśli chcesz poznać więcej) stwierdza:
Słownik-Przedmiotem CFDictionary typu, to mieszania oparte kolekcja, której klucze dostęp do jego wartości jest arbitralny, programowo zdefiniowane fragmenty danych (lub wskaźniki do danych). Chociaż kluczem jest zwykle ciąg (lub, w Core Foundation, obiekt CFString), to może to być dowolna wartość mieszcząca się w rozmiarze wskaźnika - liczba całkowita, odniesienie do obiektu Core Foundation, nawet wskaźnik do struktury danych (jest to mało prawdopodobne).
To co wikipedia ma do powiedzenia na temat tabel hash:
Idealnie, funkcja mieszania należy mapować każdy możliwy klucz do wyjątkowej indeksu szczeliny, ale ten ideał jest rzadko osiągalne w praktyce (chyba hash keys są ustalone, tzn. Nowe wpisy nigdy nie są dodawane do tabeli po jej utworzeniu). Zamiast tego, większość projektów tabel mieszania zakłada, że zderzenia mieszania o wartości - różne klucze, które odwzorowują tę samą wartość mieszania - wystąpią i muszą zostać w jakiś sposób uwzględnione. W dobrze zwymiarowanej tabeli mieszania średni koszt (liczba instrukcji) dla każdego wyszukiwania wynosi niezależnie od liczby elementów przechowywanych w tabeli. Wiele projektów tabeli mieszania umożliwia również dowolne wstawianie i usuwanie par klucz-wartość o wartościach stałych , przy stałym średnim (w rzeczywistości, zamortyzowanym) koszcie na operację .
Wydajność zależy więc od jakości skrótu. Jeśli jest dobry, dostęp do elementów powinien być operacją O (1) (tj. Nie zależy od liczby elementów).
EDIT:
W rzeczywistości po przeczytaniu ponadto Kolekcje Programowanie tematy dla Fundacji Core apple daje odpowiedź na pytanie:
Czas dostępu do wartości w obiekcie CFDictionary jest gwarantowane być w najgorszym O (log N) dla każdej implementacji, ale często jest O (1) (stały czas). Operacje wstawiania lub usuwania są zwykle również w stałym czasie, ale w najgorszych przypadkach są O (N * log N). Jest to szybszy dostęp do wartości za pomocą klucza niż bezpośredni dostęp do nich. Słowniki mają tendencję do używania znacznie większej ilości pamięci niż tablica z numerem o tej samej liczbie wartości.
NSDictionary jest w zasadzie strukturą tabeli mieszania, więc Big-O dla wyszukiwania to O (1). Jednakże, aby uniknąć ponownego przydzielania (i uzyskania złożoności O (1)), należy użyć dictionaryWithCapacity:, aby utworzyć nowy słownik o odpowiednim rozmiarze w odniesieniu do rozmiaru zbioru danych.
Korzystanie ze słownikaWithCapacity będzie w normalnym przypadku zapewniać minimalny wzrost wydajności. W rzeczywistości doktorzy Apple mówią, że to tylko wskazówka. Porównałem z NSArray rozmiarami od 10 do 10 000 000 i nie znalazłem znaczącej przewagi. Główną wadą jest czas i myślenie o wydatkach na kalkulację, która jest lepsza. – zaph
Nie można zagwarantować, że nie będzie kolizji w tabeli, niezależnie od wielkości stołu. –
Wyczyść! Dzięki! ;) –
Fakt, że pokazuje O (log N) lub O (1) sprawia, że zastanawiam się, czy mają implementację czerwonego drzewa czarnego, czy też log N powoduje duplikowanie łańcucha. –
@JustinMeiners Najgorszy przypadek dotyczy konfliktów hashowych – JustSid