Tablice haszujące

Termin zajęć: 10/11 maj 2011

Do przygotowania teoria na temat:

  1. Rodzaje haszowania
    • haszowanie bezpośrednie
    • haszowanie modularne
    • haszowanie przez mnożenie
    • haszowanie uniwersalne
  2. Problem konfliktów podczas haszowania
  3. Sposoby rozwiązywania konfliktów
    • Metoda łańcuchowa
    • Metoda adresowania otwartego

Przykładowe zadania

Poniżej mają Państwo przykładowe zadania z haszowania. W razie znalezienia błędów, prosimy o informację.

Zadanie 1
Tablica TAB jest tablicą haszującą w której konflikty są rozwiązywane za pomocą liniowego adresowania otwartego. Zakładamy że tablica ma rozmiar m=7 i jest początkowo pusta. Pomocnicza funkcja haszująca jest funkcją haszowania modularnego, natomiast funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: k(x) = x*4. Napisz wzór pomocniczej funkcji haszującej oraz przedstaw stan tablicy TAB po każdym wstawieniu wartości w następującej kolejności: 5, 3, 7, 10, 2.
Rozwiązanie

  • h(k,i) = (h'(k)+i)%m
  • h'(k) = k%m
  • TAB = 7, 10, 2, NIL, NIL, 3, 5

Zadanie 2
Tablica TAB jest tablicą haszującą w której konflikty są rozwiązywane za pomocą liniowego adresowania otwartego. Zakładamy że tablica ma rozmiar m=7 i jest początkowo pusta. Pomocnicza funkcja haszująca jest funkcją haszowania modularnego, natomiast funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: k(x) = 3x+1. Napisz wzór pomocniczej funkcji haszującej oraz przedstaw stan tablicy TAB po każdym wstawieniu wartości w następującej kolejności: 2, 5, 9, 1, 3.
Rozwiązanie

  • h(k,i) = (h'(k)+i)%m
  • h'(k) = k%m
  • TAB = 2, 9, 5, 3, 1, NIL, NIL

Zadanie 3
Tablica TAB jest tablicą haszującą w której konflikty są rozwiązywane za pomocą kwadratowego adresowania otwartego h(k,i) = (h'(k) + i² + i)%m. Zakładamy że tablica ma rozmiar m=8 i jest początkowo pusta. Pomocnicza funkcja haszująca jest funkcją haszowania modularnego, natomiast funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: k(x) = 2x+1. Przedstaw stan tablicy TAB po każdym wstawieniu wartości w następującej kolejności: 2.5, 2, 9, 5, 1.
Rozwiązanie

  • h'(k) = k%m
  • TAB = NIL, 5, NIL, 9, NIL, 2, 2.5, 1

Zadanie 4
Dane jest uniwersum możliwych kluczy: U = {2,3,4,5,6,7,8}. Zaproponuj funkcję k(x) wyliczającą klucz na podstawie wartości elementu, której przeciwdziedziną jest zbiór Y=U. Następnie wyznacz uniwersalną klasę funkcji haszujących. Dla wybranej funkcji należącej do wyznaczonej rodziny oblicz jej wartości dla każdego klucza należącego do uniwersum. Zakładamy że wartościami elementów mogą być tylko liczby naturalne oraz że rozmiar tablicy haszującej wynosi m=8.
Przykładowe rozwiązanie

  • k(x) = (x%7)+2
  • p = 11
  • Zp = {0,1,…,10}
  • Z*p = {1,2,…,10}
  • Wybieramy np. a=3, b=1.
    • h(k)=[(3*k+1)%11]%8

Zadanie 5
Tablica TAB jest tablicą haszującą o rozmiarze m=12 w której konflikty są rozwiązywane metodą łańcuchową. Funkcja haszująca jest modularną funkcją haszującą. Zakładając że indeksowanie tablicy rozpoczyna się od 1 oraz że funkcja obliczająca klucz ma postać k(x)=2x+4 podaj przynajmniej 5 różnych wartości elementów, które mogą być zapisane w tablicy pod indeksem 7.
Rozwiązanie

  • h(k) = (k%12)+1
  • (k%12)+1 = 7
  • k%12 = 6 ⇒ k = 12i+6, gdzie i={0,1,…}
  • 12i+6 = 2x+4
  • 12i+2 = 2x
  • 6i+1 = x, gdzie i={0,1,…}
  • Co nam generuje ciąg wartości których docelowy indeks to 7.

Zadanie 6
Tablica TAB jest tablicą haszującą w której konflikty są rozwiązywane za pomocą metody łańcuchowej. Haszowanie jest wykonywane przez mnożenie dla A=0.4. Zakładamy że tablica ma rozmiar m=8 i jest początkowo pusta. Funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: k(x)=x+8. Napisz wzór funkcji haszującej oraz przedstaw stan tablicy TAB po każdym wstawieniu wartości w następującej kolejności: 3, 1, 7, 11, 4.
Rozwiązanie
* Po przetworzeniu powyższych wartości przez funkcję k(x), powstaje następujący zbiór kluczy
k = {11,9,15,19,12}

  • h(k) = floor(8*(0.4k%1))
  • TAB = [7], NIL, NIL, [3], [1, 11], NIL, [4], NIL
pl/dydaktyka/asd/cwiczenia/2011-hashing.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0