Pentru aceasta metoda functia hash este $h(x) = [M * {x*A}]$. Aici $A$ este un numar pozitiv subunitar, $0 < A < 1$, iar prin ${x*A}$ se intelege partea fractionara a lui $x*A$, adica $x*A - [x*A]$. De exemplu, daca alegem $M = 1234$ si $A = 0.3$, iar $x = 1997$, atunci avem $h(x) = [1234 * {599.1}] = [1234 * 0.1] = 123$. Se observa ca functia $h$ produce numere intre $0$ si $M-1$. Intr-adevar $0 ≤ {x*A} < 1$ <tex>\Rightarrow</tex> $0 ≤ M * {x*A} < M$.
In acest caz, valoarea lui $M$ nu mai are o mare importanta. O putem deci alege cat de mare ne convine, eventual o putere a lui 2. In practica, s-a observat ca dispersia este mai buna pentru unele valori ale lui A si mai proasta pentru altele. Donald Knuth propune valoarea <tex> A = \frac{\sqrt{5}-1}{2} \approx 0.618034 </tex>.
In acest caz, valoarea lui $M$ nu mai are o mare importanta. O putem deci alege cat de mare ne convine, eventual o putere a lui $2$. In practica, s-a observat ca dispersia este mai buna pentru unele valori ale lui $A$ si mai proasta pentru altele. Donald Knuth propune valoarea <tex> A = \frac{\sqrt{5}-1}{2} \approx 0.618034 </tex>.
Ca o ultima precizare necesara la acest capitol, mentionam ca functia de cautare e bine sa nu intoarca pur si simplu 0 sau 1, dupa cum cheia cautata a mai aparut sau nu inainte intre datele de intrare. E recomandabil ca functia sa intoarca un pointer la zona de memorie in care se afla prima aparitie a cheii cautate. Vom da acum un exemplu in care aceasta valoare returnata este utila. Daca, in cazul prezentat mai sus al unui program de sah, se ajunge la o anumita pozitie P dupa ce albul a pierdut dreptul de a face rocada, aceasta pozitie va fi retinuta in hash. Retinerea nu se va face nicidecum efectiv (toata tabla), pentru ca s-ar ocupa foarte multa memorie. Se va memora in loc numai un pointer la pozitia respectiva din lista de pozitii analizate. Pe langa economia de memorie in cazul cheilor de mari dimensiuni, mai exista si alt avantaj. Sa ne inchipuim ca, analizand in continuare tabla, programul va ajunge la aceeasi pozitie P, dar in care albul are inca dreptul de a face rocada. E limpede ca aceasta varianta este mai promitatoare decat precedenta, deoarece albul are o libertate mai mare de miscare. Se impune deci fie stergerea vechii pozitii P din lista si adaugarea noii pozitii, fie modificarea celei vechi prin setarea unei variabile suplimentare care indica dreptul albului de a face rocada. Aceasta modificare este usor de facut, intrucat cautarea in hash va returna chiar un pointer la pozitia care trebuie modificata. Bineinteles, in cazul in care pozitia cautata nu se afla in hash, functia de cautare trebuie sa intoarca NULL.
Ca o ultima precizare necesara la acest articol, mentionam ca functia de cautare e bine sa nu intoarca pur si simplu $0$ sau $1$, dupa cum cheia cautata a mai aparut sau nu inainte intre datele de intrare. E recomandabil ca functia sa intoarca un pointer la zona de memorie in care se afla prima aparitie a cheii cautate. Vom da acum un exemplu in care aceasta valoare returnata este utila. Daca, in cazul prezentat mai sus al unui program de sah, se ajunge la o anumita pozitie $P$ dupa ce albul a pierdut dreptul de a face rocada, aceasta pozitie va fi retinuta in hash. Retinerea nu se va face nicidecum efectiv (toata tabla), pentru ca s-ar ocupa foarte multa memorie. Se va memora in loc numai un pointer la pozitia respectiva din lista de pozitii analizate. Pe langa economia de memorie in cazul cheilor de mari dimensiuni, mai exista si alt avantaj. Sa ne inchipuim ca, analizand in continuare tabla, programul va ajunge la aceeasi pozitie $P$, dar in care albul are inca dreptul de a face rocada. E limpede ca aceasta varianta este mai promitatoare decat precedenta, deoarece albul are o libertate mai mare de miscare. Se impune deci fie stergerea vechii pozitii $P$ din lista si adaugarea noii pozitii, fie modificarea celei vechi prin setarea unei variabile suplimentare care indica dreptul albului de a face rocada. Aceasta modificare este usor de facut, intrucat cautarea in hash va returna chiar un pointer la pozitia care trebuie modificata. Bineinteles, in cazul in care pozitia cautata nu se afla in hash, functia de cautare trebuie sa intoarca $NULL$.
In incheiere, prezentam un exemplu de functie de dispersie pentru cazul tablei de sah.
== code(c) |
const int M = 9973; // Numarul de "intrari".
typedef struct {
char b_T[8][8]; // Tabla de joc, cu 0 <= T[i][j] <= 12.
// Tabla de joc, cu 0 <= T[i][j] <= 12.
char b_T[8][8];
char b_CastleW, b_CastleB; // Ultimii doi biti ai lui b_CastleW
// indica daca albul are dreptul de a
// efectua rocada mare, respectiv pe cea
// mica. Analog pentru b_CastleB.
char b_Side; // 0 sau 1, dupa cum la mutare este albul.
// sau negrul.
char b_EP; // 0..8, indicand coloana (0..7) pe care
// partea la mutare poate efectua o
// captura "en passant". 8 indica ca nu
// exista aceasta posibilitate.
// Ultimii doi biti ai lui b_CastleW indica daca albul are dreptul de a
// efectua rocada mare, respectiv pe cea mica. Analog pentru b_CastleB.
char b_CastleW, b_CastleB;
int b_NMoves; // Numarul de mutari efectuate.
// 0 sau 1, dupa cum la mutare este albul sau negrul.
char b_Side;
// 0..8, indicand coloana (0..7) pe care partea la mutare poate efectua o
// captura "en passant". 8 indica ca nu exista aceasta posibilitate.
char b_EP;
// Numarul de mutari efectuate.
int b_NMoves;
} Board;
Board B;
int h3(Board *B) {
int i, j;
// Valoarea initiala a lui S este un numar pe 17 biti care
// inglobeaza toate variabilele suplimentare pe langa T.
// S se va lua apoi modulo M.
