Klasa Hashtable w Java

Opublikowano w grupie Poland
Klasa Java Hashtable jest jednym z najstarszych elementów środowiska Java Collection Framework. Jest to implementacja matematycznej struktury danych - tablicy z haszowaniem. W tablicy z haszowaniem Java znajdują się pojemniki, w których przechowywane są pary klucz/wartość. Hashtable jest bardzo podobna do HashMap. Najważniejsza różnica pomiędzy nimi polega na tym, że Hashtable jest zsynchronizowana, a HashMap nie.

Hashtable (hash table) jako struktura danych w Java

Klasa Java Hashtable to jest struktura danych, w której dane przechowywane są jako tablica. Każda wartość danych posiada unikalną wartość odpowiadającego jej klucza. Jeśli znasz klucz, możesz bardzo szybko uzyskać dostęp do żądanych informacji. Tak więc, operacje wstawiania i wyszukiwania są szybkie i niezależne od wielkości danych. Tablica z haszowaniem składa się z tablicy do przechowywania danych i funkcji skrótu do generowania indeksu, w którym powinien znajdować się przechowywany element. Czym jest haszowanie? W Javie jest to reguła, która mapuje obiekt do zestawu znaków (kod haszowania). Zwykle tego rodzaju funkcja konwertuje duży fragment danych na niewielką wartość całkowitą. Funkcje haszujące mogą być różne, ale wszystkie mają określone właściwości:
  • Określony obiekt ma określony kod haszowania.
  • Dwa równe obiekty mają takie same kody haszowania. Odwrotna sytuacja jest nieprawdziwa.
  • Jeśli dwa kody haszowania są różne, obiekty na pewno nie są równe.
  • Różne obiekty mogą mieć ten sam kod haszowania. To bardzo rzadkie wydarzenie nazywa się kolizją. Wykorzystanie odpowiedniej funkcji haszującej minimalizuje prawdopodobieństwo wystąpienia kolizji.
Wynikiem zastosowania funkcji haszujących do obiektu nazywa się hashCode (kod haszowania).Klasa Hashtable w Java - 1

Hashtable w Javie

Klasa Hashtable jest implementacją struktury danych tablicy haszującej. Wprawdzie ta kolekcja została utworzona wcześniej niż Java Collection Framework, ale później została w niej uwzględniona. Podobnie jak wszystkie "wczesne" kolekcje (z języka Java 1.0), tablica haszująca jest synchronizowana (prawie wszystkie metody są oznaczone jako zsynchronizowane). Z tego powodu Hashtable ma poważne problemy z wydajnością. Dlatego też, począwszy od Java 1.2, w większości przypadków zaleca się korzystanie z innych implementacji interfejsu Map ze względu na ich brak synchronizacji. HashMap jest zwykle najbardziej odpowiednim zamiennikiem. Klasa Hashtable<K,V> składa się z kluczy i wartości. Przechowuje klucze w oparciu o zasadę haszowania. Pary klucz-wartość przechowywane są w "pojemnikach" Pojemniki razem tworzą "tabelę", rodzaj wewnętrznej tablicy. Hashtable używa kodu haszowania klucza do określenia pojemnika, na który ma być mapowana para klucz/wartość. Funkcja haszująca oblicza lokalizację pojemnika na podstawie kodu haszowania klucza. Funkcja ta zwraca liczbę całkowitą dla obiektu. Jak tłumaczyliśmy powyżej, dwa równe obiekty mają ten sam kod haszowania, podczas gdy dwa nierówne obiekty mogą nie zawsze mieć różne kody haszowania. Różne obiekty umieszczone w tablicy z haszowaniem mogą mieć ten sam kod haszowania. Aby rozwiązać ten problem (kolizję), tablica z haszowaniem używa tablicy list. Wszelkie pary, mapujące do tego samego pojemnika, są zapisywane na liście, a odniesienie do listy zapisywane jest w indeksie tablicy.

Konstruktory Java hashtable w Java

  • Hashtable() jest domyślnym konstruktorem. Tworzy pustą hashtable. (Domyślna pojemność początkowa = 11, współczynnik obciążenia = 0,75).
  • Hashtable(int size) tworzy tablicę z haszowaniem o określonym rozmiarze.
  • Hashtable(int size, float fillRatio) tworzy tablicę z haszowaniem o określonym rozmiarze i współczynniku wypełnienia.
  • Hashtable(Map m) tworzy tablicę z haszowaniem z takimi samymi mapowaniami, jak przekazany Map.

Deklaracja Hashtable

Klasa Java Hashtable implementuje interfejsy Map, Cloneable i Serializable. Rozszerza klasę Dictionary.

Hashtable.java
public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable
K to typ kluczy obsługiwanych przez mapę. V to typ odwzorowanych wartości. Przykład:

Hashtable<Student, Integer> myHTable = new Hashtable<>();

Jak zaimportować Javę hashtable

Java hashtable znajduje się w pakiecie java.util. Dlatego też użyj import java.util.Hashtable; w swoim kodzie. Zwykle otrzymujesz na ten temat wskazówkę od swojego IDE.

Główne operacje Hashtable

Główne operacje klasy Hashtable to pobieranie, wstawianie do kolekcji i usuwanie. Oto te trzy operacje:
  • Object get(Object key) zwraca wartość obiektu, który ma określony klucz. Zwraca null, jeśli nie znajdzie takiego klucza.
  • Object put(Object key, Object value) mapuje określony klucz na określoną wartość. Ani klucz, ani wartość nie może być null.
  • Object remove(Object key) usuwa wpis (klucz i odpowiadającą mu wartość) z tablicy z haszowaniem.
Oto kolejne ważne operacje:
  • int size() zwraca liczbę wpisów w tablicy haszującej.
  • boolean contains(Object value) sprawdza, czy określona wartość znajduje się w tablicy z haszowaniem. Jeśli tak, metoda zwraca true, w przeciwnym razie zwraca false.
  • boolean containsValue(Object value) sprawdza, czy określona wartość znajduje się w tablicy z haszowaniem. Jeśli tak, metoda zwraca true, w przeciwnym razie zwraca false.
  • void clear() usuwa wszystkie wpisy z tablicy z haszowaniem.
  • boolean containsKey(Object key) zwraca true, jeśli określony klucz istnieje w tablicy z haszowaniem, w przeciwnym razie zwraca false.
  • boolean isEmpty() zwraca true, jeśli tablica z haszowaniem jest pusta lub false, jeżeli zawiera co najmniej jeden klucz.
  • void rehash() zwiększa rozmiar tablicy z haszowaniem i ponownie rehaszuje wszystkie jej klucze.
Klasa Hashtable w Java - 2

Implementacja tablicy z haszowaniem, kod Java:

Utwórzmy klasę Student:

import java.util.Date;
public class Student {
   String nazwisko;
   String imię;
   String drugieImię;
   Long birthday; // Long zamiast long jest używane przez parsery Gson/Jackson json i różne bazy danych ORM

   public Student(String surname, String name, String secondName, Date birthday ){
       this.surname = surname;
       this.name = name;
       this.secondName = secondName;
       this.birthday = birthday == null ? 0 : birthday.getTime();
   }

   @Override
   public int hashCode(){
       //TODO: sprawdź wartości null
       return (surname + name + secondName + birthday).hashCode();
   }
   @Override
   public boolean equals(Object other_) {
       Student other = (Student)other_;
       return (surname == null || surname.equals(other.surname) )
               && (name == null || name.equals(other.name))
               && (secondName == null || secondName.equals(other.secondName))
               && (birthday == null || birthday.equals(other.birthday));
   }
}
Oto przykład Hashtable w Javie. Umieśćmy dwa obiekty klasy Student w tablicy z haszowaniem, a następnie usuńmy i sprawdźmy jakieś parametry.

public class HashTableExample {
   public static void main(String[] args) {
 
       Hashtable<Student, Integer> myHTable = new Hashtable<>();
       Student sarah1 = new Student("Sarah","Connor", "Jane", null);
       Student john = new Student("John","Connor", "Kyle", new Date(1985, 02-1, 28)); // data nie istnieje
       myHTable.put(john,1);
       myHTable.put(sarah1,0);
       System.out.println(myHTable.get(john));
       System.out.println(myHTable.isEmpty());
       System.out.println(myHTable.size());
       System.out.println(myHTable.contains(1));
       myHTable.remove(john);
       System.out.println(myHTable.contains(0));
       System.out.println(myHTable.contains(1));
       System.out.println(myHTable.containsKey(sarah1));
   }
}
Wynikiem działania programu jest:

1
false
2
true
true
false
true

HashMap vs Hashtable

  • Hashtable jest podobny do HashMap w Javie. Najbardziej znaczącą różnicą jest to, że Hashtable jest synchronizowany, a HashMap nie. Dlatego Hashtable jest wolniejszy niż HashMap właśnie z powodu synchronizacji.
  • Poza problemem synchronizacji, Hashtable nie pozwala na użycie null jako wartości lub klucza. HashMap zezwala na jeden klucz i wiele wartości null.
  • Hashtable dziedziczy klasę Dictionary, podczas gdy HashMap dziedziczy klasę AbstractMap.
  • HashMap może być przemierzana przez Iterator. Hashtable może być przemierzana nie tylko przez Iterator, ale także Enumerator.

Przykład tablicy z haszowaniem Java (Klucz null Hashtable vs HashMap)

Oto fragment kodu do zademonstrowania, kiedy null jest używany jako klucz i wartość w HashMap i Hashtable

// Przykład hashtable i hashmap Java z pustym kluczem

try {
  System.out.println("Hashtable");
  Hashtable hashTable = new Hashtable();
  hashTable.put(null, new Object());
  } catch(Exception ex) {
    ex.printStackTrace();
  }
  System.out.println("HashMap");
  HashMap hashMap = new HashMap();
  hashMap.put(null, new Object());
  System.out.println("Jak widzisz, w HashMapie nie ma żadnych wyjątków z pustym kluczem.");
}
Wynikiem działania programu zawierającego ten fragment jest:
java.lang.NullPointerException at java.base/java.util.Hashtable.put(Hashtable.java:480) at Character.main(Character.java:58) HashMap Jak widzisz, w HashMapie nie ma żadnych wyjątków z pustym kluczem

Wniosek

Tak naprawdę nie będziesz często używał Hashtable w rzeczywistych projektach, ale możesz łatwo natknąć się na tę strukturę danych w projektach starych. W każdym razie ważne jest, aby zrozumieć, jakie struktury danych ma Java i jak one działają, przynajmniej w przypadku rozmów kwalifikacyjnych. Obiekty HashMap są zwykle używane zamiast Hashtable ze względu na ich podobieństwo. HashMap jest bardziej wydajny (nie jest zsynchronizowany) i może mieć null jako klucz.
Ten artykuł przeczytasz także po angielsku.
Read the English version of this article to become an expert on the Java Hashtable class. Hash tables are the best kind of hash! :)
Komentarze
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION