Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2019 mgr Jerzy Wałaszek
I LO w Tarnowie

Haszowanie z wykorzystaniem list jednokierunkowych

SPIS TREŚCI
Tematy pomocnicze

Problem

W ciągu łańcuchów należy wyszukać zadany łańcuch w najkrótszym czasie.

Rozwiązanie

Haszowanie (ang. hashing) jest metodą szybkiego wyszukiwania danych w tablicach. Polega to na tym, iż mamy tzw. funkcję haszującą (ang. hash function), która dla danego zestawu danych tworzy liczbę zwaną haszem (ang. hash). Liczbę tą używamy jako indeks w tablicy haszowanej (ang. hash table) do dostępu do danych. Podstawowym problemem haszowania jest kolizyjność. Polega ona na tym, iż funkcja haszująca tworzy te same wartości dla wielu różnych danych. Takie ograniczenie jest konieczne, ponieważ w przypadku przeciwnym hasz przyjmowałby wartości z bardzo dużego zakresu, a to z kolei przekładałoby się na tablicę o bardzo dużym rozmiarze, zwykle większym, niż może pomieścić pamięć komputera. Co więcej, większość komórek takiej tablicy nie byłaby wcale wykorzystana. Dobór odpowiedniej funkcji haszującej jest zagadnieniem bardzo trudnym i nie będziemy się tym zajmować w tym artykule.

Proponowane tutaj rozwiązanie nazywane jest porcjowaniem (ang. bucket hashing). Polega ono na tym, iż funkcja haszująca jest tak dobrana, aby tworzyła te same wartości dla określonych grup danych, które nazywamy porcjami. Elementami tablicy haszowanej są listy jednokierunkowe. Gdy wstawiamy element danych do tablicy, to postępujemy wg następującej metody:

Wyznaczamy wartość haszu na podstawie danych. Jeśli dopuszczamy duplikaty, to dane dopisujemy na początku listy, która znajduje się w komórce tablicy haszowanej o indeksie równym haszowi. W takim przypadku klasa złożoności jest równa O(1). Jeśli nie dopuszczamy duplikatów, to musimy przeglądnąć listę aż do końca. Jeśli nie znajdziemy na niej naszych danych, to dopisujemy je na końcu listy. Inaczej operację przerywamy.

Jeśli funkcja haszująca będzie dobrze dobrana, to rozmiar porcji nie powinien być zbyt duży i klasa złożoności wyniesie O(m), gdzie m jest rozmiarem porcji.

Odczyt tablicy haszowanej wygląda następująco:

Obliczamy wartość haszu dla poszukiwanych danych. Poszukiwanie rozpoczynamy na liście, która znajduje się w komórce tablicy haszowanej o indeksie równym wyliczonemu haszowi. Zwracamy adres elementu listy zawierającego poszukiwane dane lub nil, jeśli lista tych danych nie zawiera. Operacja ma klasę złożoności równa O(m), gdzie m jest rozmiarem porcji (przy założeniu, że lista nie zawiera duplikatów).

Algorytm wstawiania danych do tablicy haszowanej metodą porcjowania

Elementy tablicy haszowanej są listami jednokierunkowymi. Każdy element listy zawiera pole next, które wskazuje następny element, oraz pole data, w którym przechowywane są dane.

obrazek

Wejście:

d  –  dane, które chcemy umieścić w tablicy haszowanej
T  – tablica haszowana list
n  – rozmiar tablicy, n obrazek N

Wyjście:

Tablica T z wstawionymi danymi d.

Zmienne pomocnicze:
p, r  –  wskaźniki elementu listy
h  –  przechowuje wartość haszu, h obrazek N
hf(x, n)  – oblicza indeks w tablicy T na podstawie danych x i liczby komórek n.
Lista kroków dla wersji z duplikatami:
K01: Utwórz nowy element listy  
K02: p ← adres nowego elementu  
K03: (pdata) ← d dane umieszczamy w nowym elemencie
K04: h ← hf(d, n) obliczamy hasz
K05: (pnext) ← T [ h ] element dodajemy na początek listy
K06: T [ h ] ← p  
K07: Zakończ  

Lista kroków dla wersji bez duplikatów:

K01: h ← hf(d, n) obliczamy hasz
K02: pT [ h ] przeszukujemy listę
K03: Jeśli p = nil, to idź do K08  
K04: Jeśli (pdata) = d, to zakończ duplikat, kończymy
K05: Jeśli (pnext) = nil, to idź do K08 dotarliśmy do końca listy, wychodzimy z pętli
K06: p ← (pnext) przechodzimy do następnego elementu
K07: Idź do K04 wracamy na początek pętli
K08: Utwórz nowy element  
K09: r ← adres nowego elementu  
K10: (rdata) ← d inicjujemy pola nowego elementu
K11: (rnext) ← nil  
K12 Jeśli p = nil, to T [ h ] ← r
Inaczej (pnext) ← r
dodajemy element na koniec listy
K13: Zakończ  

Algorytm wyszukiwania danych w tablicy haszowanej metodą porcjowania

Wejście:

d  –  dane do wyszukania w tablicy haszowanej
T  – tablica haszowana list
n  – rozmiar tablicy, n obrazek N

Wyjście:

Adres elementu listy zawierającego dane d lub nil, jeśli w tablicy nie ma takich danych.

Zmienne pomocnicze:
p  –  wskaźnik elementu listy
h  – przechowuje wartość haszu, h obrazek N
hf(x, n)  – oblicza indeks w tablicy T na podstawie danych x i liczby komórek n.

Lista kroków:

K01: h ← hf(d, n) obliczamy hasz
K02: pT [ h ] p ustawiamy na pierwszy element listy
K03: Dopóki (pnil) obrazek ((pdata) ≠ d), wykonuj p ← (pnext) szukamy danych
K04: Zakończ z wynikiem p  

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program ma na celu przetestowanie efektywności haszowania z porcjowaniem. Tworzy on 10-cio elementową tablicę haszowaną list łańcuchów. Następnie generuje 35 losowych łańcuchów 4-ro znakowych z liter od A do Z, po czym umieszcza je na listach w tablicy haszowanej.

Po wypełnieniu tablicy jej zawartość jest wyświetlana w oknie konsoli – wartość haszu jest zawsze równa indeksowi komórki, która zawiera listę z danym łańcuchem.

W drugiej części program generuje wszystkie łańcuchy 4-znakowe z liter od A do Z, a następnie wyszukuje je w tablicy haszowanej, wyświetlając kolejno: łańcuch, wartość haszu hf(), liczbę obiegów pętli wyszukującej c. Zwróć uwagę na pozycje, dla których liczba obiegów c jest równa zero – te łańcuchy znaleziono od razu za pierwszym podejściem. Liczba obiegów c wskazuje pozycję danego łańcucha na liście.

Zwiększając rozmiar tablicy, zmniejszamy wielkość porcji, a zatem zmniejszamy czas potrzebny na odszukanie danych.

Pascal
// Haszowanie z porcjowaniem
// Data: 16.06.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program hashing;

// Definicja elementu listy
//-------------------------
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    data  : string;
  end;

// Funkcja haszująca
//------------------
function hf(s : string) : cardinal;
var
  h, i : cardinal;
begin
  h := 0;
  for i := 1 to length(s) do
    h := 31 * h + (ord(s [ i ]) - 65);
  hf := h mod 10;
end;

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************
var
  T : array [ 0..9 ] of PslistEl;
  p, r : PslistEl;
  i, j, h, c : cardinal;
  s : string;
  test : boolean;
begin
  randomize;

  // Zerujemy tablicę haszowaną
  for i := 0 to 9 do T [ i ] := nil;

  // Tablicę wypełniamy łańcuchami
  for i := 1 to 35 do
  begin
    // Generujemy losowy łańcuch z 4 znaków A-Z
    s := '';
    for j := 1 to 4 do s := s + char(65 + random(26));

    // Łańcuch umieszczamy na odpowiedniej liście
    h := hf(s);
    p := T [ h ];
    test := true;

    if p <> nil then
      while true do
      begin
        if p^.data = s then
        begin
          test := false;    // duplikat
          break;
        end;
        if p^.next = nil then break;
        p := p^.next;
      end;

    if test then
    begin
      new(r);
      r^.data := s;
      r^.next := nil;
      if p = nil then T [ h ] := r else p^.next := r;
    end;
  end;

  // Wypisujemy tablicę
  for i := 0 to 9 do
  begin
    write('T [ ', i, ' ] = ');
    p := T [ i ];
    while p <> nil do
    begin
      write(p^.data, ' ');
      p := p^.next;
    end;
    writeln;
  end;

  writeln;

  // Generujemy wszystkie łańcuchy 4-ro znakowe i szukamy ich w tablicy

  s := 'AAAA';

  repeat
    h := hf(s);
    c := 0;
    p := T [ h ];
    while (p <> nil) and (p^.data <> s) do
    begin
      inc(c);
      p := p^.next;
    end;

    if p <> nil then writeln(s, ' hf = ', h, ' c = ', c);

    for i := 4 downto 1 do
    begin
      s [ i ] := char(ord(s [ i ]) + 1);
      if s [ i ] <= 'Z' then break;
      s [ i ] := 'A';
    end;

  until s = 'AAAA';

  // Usuwamy listy z pamięci

  for i := 0 to 9 do
    while T [ i ] <> nil do
    begin
      p := T [ i ];
      T [ i ] := p^.next;
      p^.data := '';
      dispose(p);
    end;

  writeln;

end.
C++
// Haszowanie z porcjowaniem
// Data: 16.06.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

// Definicja elementu listy
//-------------------------
struct slistEl
{
  slistEl * next;
  string data;
};

// Funkcja haszująca
//------------------
unsigned int hf(string s)
{
  unsigned int h, i;

  h = 0;
  for(i = 0; i < s.length(); i++)
    h = 31 * h + s [ i ] - 65;
  return h % 10;
}

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************
int main()
{
  slistEl * T [ 10 ], * p, * r;
  unsigned int i, j, h, c;
  string s;
  bool t;

  srand(time(NULL));

  // Zerujemy tablicę haszowaną
  for(i = 0; i < 10; i++) T [ i ] = NULL;

  // Tablicę wypełniamy łańcuchami
  for(i = 0; i < 35; i++)
  {
    // Generujemy losowy łańcuch z 4 znaków A-Z
    s = "";
    for(j = 0; j < 4; j++) s += 65 + (rand() % 26);

    // Łańcuch umieszczamy na odpowiedniej liście
    h = hf(s);
    p = T [ h ];
    t = true;

    if(p)
      while(true)
      {
        if(p->data == s)
        {
          t = false;
          break;
        }
        if(!p->next) break;
        p = p->next;
      }

    if(t)
    {
      r = new slistEl;
      r->data = s;
      r->next = NULL;
      if(!p) T [ h ] = r;
      else p->next = r;
    }
  }

  // Wypisujemy tablicę
  for(i = 0; i < 10; i++)
  {
    cout << "T [ " << i << " ] = ";
    p = T [ i ];
    while(p)
    {
      cout << p->data << " ";
      p = p->next;
    }
    cout << endl;
  }

  cout << endl;

  // Generujemy wszystkie łańcuchy 4-ro znakowe i szukamy ich w tablicy

  s = "AAAA";

  do
  {
    h = hf(s);
    c = 0;
    p = T [ h ];
    while(p && (p->data != s))
    {
      c++;
      p = p->next;
    }

    if(p) cout << s << " hf = " << h << " c = " << c << endl;

    for(i = 4; i > 0; i--)
    {
      s [ i - 1 ] = s [ i - 1 ] + 1;
      if(s [ i - 1 ] <= 'Z') break;
      s [ i - 1 ] = 'A';
    }
  } while(s != "AAAA");

  // Usuwamy listy z pamięci

  for(i = 0; i < 10; i++)
    while((p = T [ i ]))
    {
      T [ i ] = p->next;
      p->data = "";
      delete p;
    }

  cout << endl;

  return 0;
}
Basic
' Haszowanie z porcjowaniem
' Data: 16.06.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Definicja elementu listy
'-------------------------
Type slistEl
  next As slistEl Ptr
  data As String
End Type

' Funkcja haszująca
'------------------
Function hf(s As String) As UInteger

  Dim As UInteger h, i

  h = 0
  For i = 0 To Len(s)
    h = 31 * h + Asc(Mid(s, i, 1)) - 65
  Next
  Return h Mod 10
End Function

'**********************
'*** PROGRAM GŁÓWNY ***
'**********************

Dim As slistEl Ptr T(9), p, r
Dim As UInteger i, j, h, c, test
Dim As String s

Randomize

' Zerujemy tablicę haszowaną
For i = 0 To 9: T(i) = 0: Next

' Tablicę wypełniamy łańcuchami
For i = 1 To 35
  ' Generujemy losowy łańcuch z 4 znaków A-Z
  s = ""
  For j = 1 To 4: s += Chr(65 + Int(Rnd() * 26)): Next

  ' Łańcuch umieszczamy na odpowiedniej liście
  h = hf(s)
  p = T(h)
  test = 1
  
  If p Then
    While 1
      If p->data = s Then
        test = 0       ' Duplikat
        Exit While
      End If
      If p->next = 0 then Exit While
      p = p->Next
    Wend
  End If
  
  If test = 1 Then
    r = new slistEl
    r->data = s
    r->next = 0
    If p = 0 Then T(h) = r: Else p->next = r
  End If
Next

' Wypisujemy tablicę
For i = 0 To 9
  Print Using "T [ & ] = ";i;
  p = T(i)
  While p
    Print Using "& ";p->data;
    p = p->Next
  Wend
  Print
Next

Print

' Generujemy wszystkie łańcuchy 4-ro znakowe i szukamy ich w tablicy

s = "AAAA"

Do
  h = hf(s)
  c = 0
  p = T(h)
  While (p <> 0) AndAlso (p->data <> s)
    c += 1
    p = p->Next
  Wend

  if p Then Print Using "& hf = & c = &";s;h;c

  For i = 4 To 1 Step -1
    Mid(s, i, 1) = Chr(Asc(Mid(s, i, 1)) + 1)
    If Mid(s, i, 1) <= "Z" Then Exit For
    Mid(s, i, 1) = "A"
  Next
Loop Until s = "AAAA"

' Usuwamy listy z pamięci

For i = 0 To 9
  While T(i)
    p = T(i)
    T(i) = p->Next
    p->data = ""
    delete p
  Wend
Next

Print

End
Wynik:
T [ 0 ] = GWAC XFIO
T [ 1 ] = IKBM VTGZ SNKU HFCR JJVW NXDW DWVF
T [ 2 ] = NAMR
T [ 3 ] = UQTS GXUE EJOG ADTL
T [ 4 ] = QJMH JMJE BWBA
T [ 5 ] = WTOU GNND
T [ 6 ] = IUGM NQFM ODTK
T [ 7 ] = JQBL UPUC ZUUW CDLL
T [ 8 ] = RMHM JCTI BWXM MJRA
T [ 9 ] = APTP BIHN SAQP GIZK SGMN

ADTL hf = 3 c = 3
APTP hf = 9 c = 0
BIHN hf = 9 c = 1
BWBA hf = 4 c = 2
BWXM hf = 8 c = 2
CDLL hf = 7 c = 3
DWVF hf = 1 c = 6
EJOG hf = 3 c = 2
GIZK hf = 9 c = 3
GNND hf = 5 c = 1
GWAC hf = 0 c = 0
GXUE hf = 3 c = 1
HFCR hf = 1 c = 3
IKBM hf = 1 c = 0
IUGM hf = 6 c = 0
JCTI hf = 8 c = 1
JJVW hf = 1 c = 4
JMJE hf = 4 c = 1
JQBL hf = 7 c = 0
MJRA hf = 8 c = 3
NAMR hf = 2 c = 0
NQFM hf = 6 c = 1
NXDW hf = 1 c = 5
ODTK hf = 6 c = 2
QJMH hf = 4 c = 0
RMHM hf = 8 c = 0
SAQP hf = 9 c = 2
SGMN hf = 9 c = 4
SNKU hf = 1 c = 2
UPUC hf = 7 c = 1
UQTS hf = 3 c = 0
VTGZ hf = 1 c = 1
WTOU hf = 5 c = 0
XFIO hf = 0 c = 1
ZUUW hf = 7 c = 2
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2019 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.