Programowanie średniozaawansowane #13: kolekcje

Korzystanie z tablic posiada jedną zasadniczą wadę. Mianowicie za każdym razem musisz wiedzieć, ile maksymalnie potrzeba w niej elementów. Nie można stworzyć tablicy bez wpisania jej rozmiaru i nawet jeśli wypełnisz jedną komórkę danymi, to i tak wirtualna maszyna Javy zarezerwuje dużo więcej pamięci niż faktycznie używasz. Dodatkowo, jeżeli osiągniesz zakres tablicy, to trzeba będzie stworzyć kolejną większą i przekopiować elementy pierwszej do drugiej. Nie ma to wielkiego sensu, więc w praktyce rzadko będziesz używać tej struktury. Na szczęście są już w Javie zaimplementowane klasy, które ułatwiają znacznie przechowywanie obiektów.

Wymienię teraz trzy najczęściej używane struktury danych w Javie:

  1. tablica dynamiczna
  2. mapa
  3. zbiór

Zanim przejdę do konkretnej implementacji każdej z nich, opowiem Ci jakie są różnice między nimi i kiedy warto je używać.

Jest jedna cecha wspólna dla każdej kolekcji: nie przechowują typów prostych. Także jeśli już musisz je używać (pamiętaj, że z każdego typu prostego łatwo zrobić jego typ „obiektowy”*), to niestety trzeba będzie wtedy użyć klasycznej tablicy.

Tablica dynamiczna

Jej podstawową cechą jest prostota użycia. Tablica dynamiczna używa tak naprawdę (tak jak reszta kolekcji) znaną Ci tablicę. Jest jednak ona ukryta w jej implementacji, więc możesz właściwie o niej zapomnieć. To co warto wiedzieć o tablicy dynamicznej to:

  • to najpopularniejsza i najczęściej używana struktura danych w języku Java,
  • tablica dynamiczna (lub czasem nazywana listą) nie posiada rozmiaru (limitu przechowywanych elementów**),
  • nie ma możliwości odnoszenia się do konkretnego indeksu jak w przypadku zwykłej tablicy,
  • kolejne elementy dodawane są na koniec listy (ich kolejność ma znaczenie),
  • może posiadać duplikowane elementy,
  • manipulacja elementami (usuwanie ze środka listy) jest bardziej czasochłonne niż usuwanie z jej końca.

Mapa

W tym przypadku omawiam najpopularniejszą jej implementację, czyli HashMap. Struktura ta służy do przechowywania klucza wraz z jego wartością. Dobrym przykładem jej użycia może być cennik usług, gdzie do nazwy (klucz) będzie przypisana jej cena (wartość). Klucz w tym przypadku powinien być unikalny. Pozostałe właściwości:

  • ponieważ klucz jest unikalny, tylko jeden z nich może być nullem (ale wiele wartości mogą być nullowych),
  • jest strukturą nieuporządkowaną,
  • do wartości odwołujesz się poprzez klucz.

Zbiór

Tutaj także jest wiele implementacji tej struktury. Na razie skupię się na najpopularniejszej – HashSet. W użyciu zbiór jest bardzo podobny do listy dynamicznej (przechowywane są tylko wartości). Jednak implementacja jest bardziej skomplikowana.

  • korzysta z mechanizmu haszowania do przechowywania danych, co czyni ją bardzo wydajną strukturą,
  • wszystkie elementy muszą być unikalne (tak jak w przypadku kluczy w HashMap),
  • pozwala na przechowywanie wartości null.
  • jest także strukturą nieuporządkowaną
  • przydatna do szybkiego wyszukiwania elementów.

To oczywiście nie wszystkie struktury danych jakie istnieją w Javie, ale te trzy powyższe są zdecydowanie najczęściej używane. Skoro już je znasz, to możesz zapomnieć o używaniu klasycznej tablicy. Jest to bardzo wydajna struktura, ale niestety trudna w obsłudze. Będziesz jej używać tylko, gdy będzie Ci bardzo zależeć na wydajności (czyli raczej nigdy)  albo do przechowywania stałych (z reguły ich liczba jest mała i rzadko się zmienia). Od teraz jedną z najczęściej używanych przez Ciebie klas będzie ArrayList, czyli klasa implementująca tablicę dynamiczną. Więcej o niej dowiesz się w kolejnej lekcji.

*Pamiętasz lekcję o typach opakowujących?

**W praktyce jej rozmiar jest ukryty przed programistą i wyliczany samoistnie, więc nie musisz się nim przejmować.

Dodaj komentarz