Podstawy tabel Hash?

Najpierw musisz zrozumieć, czym jest funkcja hash. Funkcja hash jest funkcją, która przyjmuje klucz (na przykład łańcuch o długości arbritrary) i zwraca liczbę możliwie unikalną . Ten sam klucz musi zawsze zwracać ten sam hash. Bardzo prosta funkcja hashowania łańcuchów w Javie może wyglądać jak

public int stringHash(String s) {
    int h = s.length();
    for(char c : s.toCharArray()) {
        h ^= c;
    }
    return h;
}

Możesz studiować dobrą funkcję hashową na http://www.azillionmonkeys.com/qed/hash.html

Teraz Mapa hash używa tej wartości do umieszczenia wartość do tablicy. Uproszczona metoda Javy:

public void put(String key, Object val) {
    int hash = stringHash(s) % array.length;
    if(array[hash] == null) {
        array[hash] = new LinkedList<Entry<String, Object> >();
    }
    for(Entry e : array[hash]) {
        if(e.key.equals(key)){
            e.value = val;
            return;
        }
    }
    array[hash].add(new Entry<String, Object>(key, val));
}

(Ta mapa wymusza unikalne klucze. Nie wszystkie mapy tak.)

Możliwe jest użycie dwóch różnych kluczy do tej samej wartości lub mapowania dwóch różnych skrótów do tego samego indeksu tablicy. Istnieje wiele technik radzenia sobie z tym. Najprostszym jest użycie listy linkowanej (lub drzewa binarnego)dla każdego indeksu tablicy. Jeśli funkcja hash jest wystarczająco dobra, nigdy nie będziesz potrzebował wyszukiwania liniowego.

Teraz poszukaj klucza:

public Object get(String key) {
    int hash = stringHash(key) % array.length;
    if(array[hash] != null) {
        for(Entry e : array[hash]) {
            if(e.key.equals(key))
                return e.value;
        }
    }

    return null;
}

Hashtables są asocjacyjne . Jest to ogromna różnica w stosunku do tablic, które są tylko liniowymi strukturami danych. Z tablicą możesz zrobić coś takiego:

int[] arr = ...
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i] + 1);
}

Zwróć uwagę, jak wydobywasz element z tablicy, określając dokładne przesunięcie pamięci (i). To kontrastuje z hashtablami, które pozwalają przechowywać pary klucz / wartość, a następnie pobierać wartość na podstawie klucza:

Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);

Z powyższej tabeli możemy wykonać następujące wywołanie:

int n = table.get("Chris");

...i bądź pewny, że {[4] } będzie wyceniane na 18.

" bardziej interesuje mnie sposób, w jaki tabele Hash wyszukują klucz i jak klucz jest generowany."

1. Hashowanie przekształca kluczowy obiekt na liczbę. To się nazywa "haszowanie" - robi haszowanie z obiektu. Zobacz Funkcja Hash . Na przykład sumowanie bajtów łańcucha jest standardową techniką hashowania. Obliczasz sumę modulo 2³² aby utrzymać hash do łatwego do opanowania rozmiaru. Hash zawsze daje tę samą odpowiedź. To jest O (1).

2. Liczba daje "slot" w HashTable. Biorąc pod uwagę dowolny obiekt kluczowy, wartość skrótu oblicza wartość skrótu. Wartość hash daje wtedy miejsce w tabeli. Zazwyczaj mod( hash, table size ). To jest O (1), również.

Transformacja z obiektu do wartości hash dzieje się to w jeden z tych powszechnych sposobów.

1. Jeśli jest to "prymitywny" obiekt o długości 4 bajtów, to jego natywną wartością jest liczba.

2. Adres obiektu wynosi 4 bajty, wtedy adres obiektu może być użyty jako wartość skrótu.

3. Prosta funkcja hashowa (MD5, SHA1, cokolwiek) gromadzi bajty obiektu, tworząc 4-bajtową liczbę. Zaawansowane skróty nie są prostymi sumami bajtów, prosta suma nie odzwierciedla wszystkich oryginalnych bitów wejściowych dość.

Slot w tabeli hash to mod (Liczba, rozmiar tabeli).

Jeśli ten slot ma żądaną wartość, jesteś skończony. Jeśli nie jest to pożądana wartość, musisz poszukać gdzie indziej. Istnieje kilka popularnych algorytmów sondowania, aby szukać wolnego miejsca w tabeli. / Align = "left" / Linear Quadratic to nieliniowe przeskakiwanie w poszukiwaniu wolnego miejsca. Generator liczb losowych (ze stałym ziarnem) może być użyty do wygenerowania seria sond, które rozłożą dane równomiernie, ale arbitralnie.

Algorytmy sondowania nie są O (1). Jeśli stół jest wystarczająco duży, szanse na kolizję są niskie, a sondy nie mają znaczenia. Jeśli stół jest za mały, dochodzi do kolizji i sondowania. W tym momencie staje się kwestią "dostrajania i poprawiania", aby zrównoważyć sondowanie i rozmiar stołu, aby zoptymalizować wydajność. Zwykle powiększamy stół.

Zobacz Tabela Hash .

Coś, czego jeszcze nie zauważyłem:

Punktem użycia tabeli hash nad tablicą jest wydajność.

Iteracja przez tablicę zazwyczaj zajmuje od O(1) do O(x), gdzie x jest liczbą elementów w tablicy. Jednak czas na znalezienie elementu będzie niezwykle zmienna, szczególnie jeśli mówimy o setkach tysięcy elementów w tablicy.

Odpowiednio ważona tabela hash zazwyczaj ma prawie stałą czas dostępu nieco ponad O(1), bez względu na to, ile elementów znajduje się w tabeli hash.

Nie chcesz używać tabeli hash dla 100 losowo generowanych liczb.

Dobrym sposobem myślenia o tabelach hash jest myślenie o parach wartości. Powiedzmy, że każdy ma numer legitymacji studenckiej. W programie przechowujesz informacje o uczniach (nazwiska, numery telefonów, rachunki itp.). Chcesz znaleźć wszystkie informacje o studencie, używając tylko podstawowych informacji (na przykład imienia i nazwiska lub legitymacji studenckiej).

Powiedzmy, że masz 10,000 studentów. Jeśli je przechowujesz wszystko w tablicy, następnie trzeba zapętlić całą tablicę porównując identyfikator ucznia każdego wpisu z tym, którego szukasz.

Jeśli zamiast tego "hashujesz" (patrz poniżej) numer legitymacji studenckiej do pozycji w tablicy, to musisz tylko wyszukać numer studenta, który ma ten sam hash. Dużo mniej pracy, aby znaleźć to, czego chciałeś.

W tym przykładzie powiedzmy, że legitymacje studenckie to tylko 6 cyfr. Nasza funkcja hash może być używana tylko przez dolne 3 cyfry numeru jako "hash key". W ten sposób 232145 jest zahaszowany do lokalizacji tablicy 145. Tak więc potrzebujesz tylko tablicy 999 elementów (każdy element jest listą uczniów).

To powinien być dobry początek dla ciebie. Powinieneś oczywiście przeczytać książkę tekstową lub Wikipedię, aby uzyskać tego rodzaju informacje. Ale zakładam, że już to zrobiłeś i jesteś zmęczony czytaniem.

Oto, w skrócie, jak działa tabela hash.

Wyobraź sobie, że masz bibliotekę pełną książek. Jeśli mielibyście przechowywać książki w tablicach, umieszczalibyście każdą książkę na półce, a kiedy ktoś poprosił was o znalezienie książki, przeglądalibyście wszystkie półki ... dość powoli. Jeśli ktoś powiedział "książka #12345" , można go znaleźć dość łatwo, choć.

Załóżmy, że zamiast tego powiesz, że jeśli Tytuł książki zaczyna się od "A", przechodzi do rzędu 1. Jeśli druga litera to "B", to wchodzi w rząd 1, regał 2. Jeśli trzecią literą jest "C", przechodzi ona do rzędu 1, regału 2, półki 3... i tak dalej, dopóki nie zidentyfikujesz pozycji książki. Wtedy, opierając się na tytule książki, możesz dokładnie wiedzieć, gdzie powinna być.

Teraz są pewne problemy w uproszczonym algorytmie "hashowania", który opisałem-niektóre półki będą przeciążone, podczas gdy inne będą puste, niektóre książki zostaną przypisane do tego samego miejsca.. tak więc prawdziwe funkcje hash są starannie skonstruowane, aby unikać takich problemy.

Ale to jest podstawowa idea.

Odpowiem na tę część o różnicy między tabelą hash a tablicą... ale ponieważ nigdy wcześniej nie zaimplementowałem algorytmu hashującego jakiegokolwiek importu, zostawię to komuś bardziej kompetentnemu:)

Tablica jest po prostu uporządkowaną listą obiektów. Sam przedmiot nie ma znaczenia... ważne jest to, że jeśli chcesz wyświetlić listę obiektów w kolejności wstawiania, zawsze jest ona taka sama (co oznacza, że pierwszy element Zawsze ma indeks 0).

As w przypadku hashtable jest to indeksowane przez klucze, a nie kolejność... Myślę, że podstawowe wyszukiwanie algorytmów haszujących da ci o wiele więcej wglądu niż ja... Wikipedia ma bardzo przyzwoity... to określa "bucket", do którego trafiają klucze w celu szybkiego wyszukiwania na dowolnych obiektach używanych jako klucze.

Co do zalet: jeśli kolejność wstawiania jest ważna, potrzebna jest tablica lub jakaś uporządkowana lista. Jeśli ważne jest szybkie wyszukanie dowolnego klawisza (z kluczami różnych funkcji skrótu), to hash stół ma sens.

[to jest odpowiedź na komentarz złożony przez me.yahoo.com/a above]

To zależy od funkcji hash. Załóżmy, że funkcja hash hashuje słowo zgodnie z długością słowa, klucz dla Chrisa będzie 5. Podobnie klucz dla yahoo będzie również 5. Teraz obie wartości (chris i yahoo) pójdą poniżej 5 (tj. w "wiadrze" z kluczem 5). W ten sposób nie musisz tworzyć tablicy równej wielkości Twoich danych.

Wydaje mi się, że odpowiedź na to pytanie jest dość jasna i na wiele różnych sposobów.

Chciałbym tylko dodać inną perspektywę (która może również zdezorientować nowego czytelnika)

Na poziomie najmniejszej abstrakcji tablice są tylko przylegającym blokiem pamięci. Z uwagi na adres początkowy (startAddress), rozmiar (sizeOfElement) i index pojedynczego elementu, adres elementu jest obliczany jako:

elementAddress = startAddress + sizeOfElement * index

Ciekawostką jest to, że tablice mogą być abstrakcyjne / przeglądane jako tabele skrótów z index jako kluczem i powyższą funkcją jako funkcją skrótu, która oblicza położenie wartości w O(1)

Tabela Hash jest strukturą danych, która jest tworzona do szybkiego wyszukiwania w górę.

Tabele hash nie są skuteczne, gdy liczba wpisów jest bardzo mała.

Odniesienie

Niektóre przykłady:

    import java.util.Collection;
    import java.util.Enumeration;
    import java.util.Hashtable;
    import java.util.Set;

    public class HashtableDemo {

    public static void main(String args[]) {

// Creating Hashtable for example

     Hashtable companies = new Hashtable();


// Java Hashtable example to put object into Hashtable
// put(key, value) is used to insert object into map

     companies.put("Google", "United States");
     companies.put("Nokia", "Finland");
     companies.put("Sony", "Japan");


// Java Hashtable example to get Object from Hashtable
// get(key) method is used to retrieve Objects from Hashtable

     companies.get("Google");


// Hashtable containsKey Example
// Use containsKey(Object) method to check if an Object exits as key in
// hashtable

     System.out.println("Does hashtable contains Google as key: "+companies.containsKey("Google"));


// Hashtable containsValue Example
// just like containsKey(), containsValue returns true if hashtable
// contains specified object as value

      System.out.println("Does hashtable contains Japan as value: "+companies.containsValue("Japan"));


// Hashtable enumeration Example
// hashtabl.elements() return enumeration of all hashtable values

      Enumeration enumeration = companies.elements();

      while (enumeration.hasMoreElements()) {
      System.out.println("hashtable values: "+enumeration.nextElement());
      }


// How to check if Hashtable is empty in Java
// use isEmpty method of hashtable to check emptiness of hashtable in
// Java

       System.out.println("Is companies hashtable empty: "+companies.isEmpty());


// How to find size of Hashtable in Java
// use hashtable.size() method to find size of hashtable in Java

      System.out.println("Size of hashtable in Java: " + companies.size());


// How to get all values form hashtable in Java
// you can use keySet() method to get a Set of all the keys of hashtable
// in Java

      Set hashtableKeys = companies.keySet();


// you can also get enumeration of all keys by using method keys()

      Enumeration hashtableKeysEnum = companies.keys();


// How to get all keys from hashtable in Java
// There are two ways to get all values form hashtalbe first by using
// Enumeration and second getting values ad Collection

      Enumeration hashtableValuesEnum = companies.elements();


      Collection hashtableValues = companies.values();


// Hashtable clear example
// by using clear() we can reuse an existing hashtable, it clears all
// mappings.

       companies.clear();
      }
     }

Wyjście:

Does hashtable contains Google as key: true

Does hashtable contains Japan as value: true

hashtable values: Finland

hashtable values: United States

hashtable values: Japan

Is companies hashtable empty: false

Size of hashtable in Java: 3