Java Data Structures Reference

Question

Czy każdy może podać mi referencje strony internetowej zawierającej podsumowanie głównych struktur danych Java i ich odpowiednią złożoność w czasie (w przypadku niektórych operacji, takich jak dodawanie, wyszukiwanie, usuwanie), np. Hashtable s to O (1) do znalezienia, natomiast LinkedList s to O (n). Niektóre szczegóły, takie jak użycie pamięci, również byłyby miłe.

Byłoby to bardzo pomocne przy myśleniu w strukturach danych o algorytmach.

Answer 1

Czy istnieje powód, aby sądzić, że implementacja Javy jest inny (w sensie złożoności) niż rodzajowe, implementacji języka agnostykiem? Innymi słowy, dlaczego nie tylko odnoszą się do ogólnego odniesienia na złożoność różnych struktur danych:

NIST Dictionary of Algorithms and Data Structures

Ale jeśli nalegać na Java specyficzne:

Java standard data structures Big O notation

Java Collections cheatsheet V2 (dead link, ale this is the first version of the cheatsheet)

Answer 2

Nie sądzę, aby istniała jakakolwiek strona internetowa opisująca to (brzmi to jak dobry pomysł na projekt). Myślę, że część problemu polega na tym, że bardzo ważne jest zrozumienie, w jaki sposób działa każdy z algorytmów. W przeważającej części brzmi to tak, jakbyś rozumiał Big-O, więc użyłbym tego jako swoich najlepszych domysłów. Wykonaj test porównawczy/profilowanie, aby zobaczyć, co działa szybciej/wolniej.

I, tak, Java docs powinien mieć większość tych informacji w java.util.

Answer 3

Najobszerniejsza Kolekcje Java opis jest tutaj

http://en.wikiversity.org/wiki/Java_Collections_Overview

Answer 4

Złożoność czasu i przestrzeni dla głównych klas kolekcji powinna odpowiadać strukturom danych znanym czasom xity. Nie sądzę, że jest w tym coś specyficznego dla Javy, np. (jak mówisz) wyszukiwanie hash powinno być O (1). Możesz wyglądać here lub here.

Answer 5

Znalazłem bardzo użyteczną stronę The Collections Framework, w szczególności Outline of the Collections Framework, gdzie każdy interfejs/klasę jest opisywana bezproblemowo. Niestety nie ma informacji big-O.

Answer 6

Nie widziałem tego konkretnego zasobu wspomnianego tutaj, znalazłem go bardzo przydatny w przeszłości. Poznaj swoje komplikacje!

http://bigocheatsheet.com/