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.

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

program hashing;

// Definicja elementu listy
//-------------------------
type
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    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 PSLel;
  p, r : PSLel;
  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.

// 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 SLel
{
  SLel * 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()
{
  SLel * 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 SLel;
      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;
}

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

' Definicja elementu listy
'-------------------------
Type SLel
  next As SLel 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 SLel 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 SLel
    r->data = s
    r->next = 0
    If p = 0 Then
      T(h) = r
    Else
      p->next = r
    End If
  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)
  Wile(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