Wprowadzenie do funkcji mieszania w Javie
Ponieważ wiemy, że Java jest językiem obiektowym, powinien istnieć mechanizm opisujący stan obiektu, bez względu na to, jak duży może być obiekt. W celu spełnienia tego wymagania powstała funkcja mieszania w Javie.
Co to jest funkcja mieszania?
Funkcję skrótu można zdefiniować jako funkcję, która zwraca wartość całkowitą odpowiadającą obiektowi. Funkcja skrótu zawsze zwraca tę samą wartość całkowitą dla tego samego obiektu. Wartość całkowita zwracana przez funkcję skrótu nazywa się wartością skrótu. Oto ważne punkty dotyczące funkcji skrótu:
- Zawsze zwraca liczbę całkowitą (4 bajty) dla obiektu.
- Nie możemy obliczyć stanu obiektu na podstawie wartości skrótu, ponieważ funkcje skrótu mają charakter nieodwracalny.
- Dwa równe obiekty będą miały tę samą wartość skrótu.
- Dwa nierówne obiekty nie zawsze mają różne wartości skrótu.
Zastosowania funkcji skrótu
Oto typowe zastosowania funkcji skrótu:
1. Struktury danych
Prawie każdy język programowania zawiera struktury danych oparte na haszowaniu. Na przykład java zawiera tabelę skrótu, mapę skrótu, zestaw skrótu, struktury danych zestawu drzew, które są oparte na funkcji skrótu. Podstawą tych struktur danych jest projektowanie Key-Value, w którym każdy klucz jest unikalny, podczas gdy taka sama wartość może istnieć dla wielu kluczy.
2. Wiadomość podsumowanie
Ten algorytm jest wykorzystywany do sprawdzania integralności danych. Ten algorytm przyjmuje komunikat o dowolnej długości jako dane wejściowe i generuje dane o stałej długości (128-bitowe) jako dane wyjściowe. Przykłady algorytmów przetwarzania wiadomości obejmują MD2, MD4, MD5 i MD6.
3. Bezpieczny algorytm mieszania
Ten algorytm służy do bezpieczeństwa danych i jest wykorzystywany w aplikacjach i protokołach, takich jak Secure Socket Layer (SSL). SHA-0, SHA-1, SHA-2 i SHA-3 są powszechnymi kategoriami algorytmu bezpiecznego mieszania.
4. Weryfikacja i przechowywanie hasła
Rozważmy scenariusz logowania, w którym po wprowadzeniu hasła w celu uwierzytelnienia użytkownika obliczana jest wartość skrótu wprowadzonego hasła i przesyłana przez sieć do serwera, na którym przechowywany jest skrót oryginału. Odbywa się to w celu zapewnienia, że wąchanie nie zostanie wykonane, gdy hasło zostanie wysłane od klienta do serwera.
5. Działanie kompilatora
Ponieważ w języku programowania używane są różne słowa kluczowe, w celu rozróżnienia między tymi słowami kluczowymi a identyfikatorami, kompilator używa zestawu skrótów, który jest implementowany za pomocą tabeli skrótów do przechowywania wszystkich tych słów kluczowych i identyfikatorów.
6. Algorytm Rabin-Karp
Jest to algorytm wyszukiwania, który wykorzystuje haszowanie do wyszukiwania jednego lub więcej wzorców w danym ciągu. Jest to jeden z najczęściej używanych algorytmów.
7. Interfejsy porównywalne i porównawcze
Te interfejsy zawierają funkcje używane do porównywania dwóch obiektów jednocześnie. Zwracana wartość tych funkcji może być ujemna, zerowa lub dodatnia w zależności od tego, czy dany obiekt jest mniejszy, równy lub większy niż obiekt, z którym porównujemy. Komparator wewnętrzny i porównywalne interfejsy używają funkcji skrótu do porównywania obiektów między sobą.
8. Kolejka priorytetowa
Kolejka priorytetowa różni się od normalnej kolejki zgodnej z kolejnością FIFO (First in First out). W kolejce priorytetowej elementy są ułożone w niestandardowej kolejności na podstawie ich priorytetu, który jest wewnętrznie implementowany za pomocą porównywarki i komparatora, których stażyści opierają się na funkcjach skrótu.
Projektowanie funkcji mieszania
Oto kilka ogólnych zasad projektowania funkcji skrótu:
- Funkcję skrótu należy skutecznie ocenić.
- Wartości skrótu obliczone na podstawie funkcji skrótu powinny być równomiernie rozmieszczone, co pomaga uniknąć kolizji.
- Język programowania Java zapewnia ogólną funkcję haszującą za pomocą metody hashCode () w nadklasie Object.
public int hashCode ()(
//Logic goes here
)
Hash Collision in Java
Zderzenie mieszania występuje, gdy dwa lub więcej obiektów zwraca tę samą wartość skrótu. Weźmy przykład mapy mieszania Java, która przechowuje dane w parach klucz-wartość. Kiedy umieścimy obiekt na mapie skrótu, wartość skrótu klucza jest obliczana i na podstawie tej lokalizacji kubełków wartości skrótu do znalezienia obiektu wartości. Obiekty o różnych wartościach skrótu muszą przejść do różnych segmentów. Gdy dwa lub więcej obiektów ma tę samą wartość skrótu, są one przechowywane w tej samej lokalizacji segmentu przy użyciu dodatkowej struktury danych zwanej listą połączoną. Wszystkie obiekty o tej samej wartości skrótu są powiązane ze sobą za pomocą połączonej listy. Ten mechanizm nazywa się łańcuchem. Oto sposoby radzenia sobie z kolizjami to funkcja skrótu:
- Tworzenie łańcuchów: Jak już wspomniano, idea tworzenia łańcuchów polega na utworzeniu połączonej listy obiektów o tej samej wartości skrótu. Łańcuch jest prostą techniką, ale wymaga dodatkowego narzutu pamięci.
- Otwarte adresowanie: w tej technice wszystkie elementy są przechowywane w tabeli skrótów, w której każdy wpis zawiera rekord lub NULL. Gdy element jest przeszukiwany, każdy wpis w tablicy skrótów jest przeszukiwany w celu znalezienia żądanego rekordu, aż do znalezienia wymaganego rekordu lub stwierdzenia, że rekord nie istnieje w tabeli.
Zalety haszowania
Oto zalety haszowania:
- Porównaj zawartość dwóch plików łatwo i wydajnie, bez ich otwierania.
- Funkcje skrótu służą do sprawdzania integralności pliku.
- Dzięki skrótowi operacja wyszukiwania w strukturach danych stała się szybsza.
- Funkcje skrótu odgrywają istotną rolę w bezpieczeństwie danych, ponieważ większość algorytmów i protokołów bezpieczeństwa wykorzystuje haszowanie.
- Hashing przekształca dane w krótszą wartość lub klucz o stałej długości, który reprezentuje oryginalny ciąg, który można wysłać przez sieć.
Wady haszowania
Oprócz zalet istnieją również pewne ograniczenia mieszania:
- Mieszania nie można zaimplementować do sortowania danych.
- Nie można praktycznie uniknąć kolizji skrótu, co z kolei prowadzi do nieefektywności.
Polecane artykuły
Jest to przewodnik po funkcji mieszania w Javie. Tutaj omawiamy zastosowania funkcji skrótu wraz z zaletami i wadami. Możesz także przejrzeć następujące artykuły, aby dowiedzieć się więcej -
- Deklaracja i inicjalizacja VB.Net
- Program Java przedstawiający HashMap i TreeMap
- Typy mieszania w DBMS
- Techniki steganografii
- Tablice w programowaniu Java
- Hashmap w Javie