Açık Adreslemeli Hashing (Open Addressing Hashing) Algoritması

1class OpenAddressingHashTable {
2  size: number;
3  table: (number | null)[];
4
5  constructor(size: number) {
6    this.size = size;
7    this.table = Array(size).fill(null);
8  }
9
10  insertLinearProbing(key: number, trace: string[]) {
11    let i = 0;
12    const h = key % this.size;
13    trace.push(`Linear Probing: ${key} ekleniyor. İlk hash indeksi: ${h}`);
14
15    while (i < this.size) {
16      const idx = (h + i) % this.size;
17      if (this.table[idx] === null) {
18        this.table[idx] = key;
19        trace.push(`  Boş hücre bulundu! İndeks ${idx} doldu.`);
20        return;
21      }
22      trace.push(`  Çakışma! İndeks ${idx} dolu (${this.table[idx]}). Sonraki indeks aranıyor.`);
23      i++;
24    }
25    trace.push('Tablo tamamen dolu, eklenemedi!');
26  }
27
28  insertDoubleHashing(key: number, trace: string[]) {
29    let i = 0;
30    const h1 = key % this.size;
31    const h2 = 1 + (key % (this.size - 2)); // size asal olmalıdır
32    trace.push(`Double Hashing: ${key} ekleniyor. h1=${h1}, h2 (adım)=\u0024{h2}`);
33
34    while (i < this.size) {
35      const idx = (h1 + i * h2) % this.size;
36      if (this.table[idx] === null) {
37        this.table[idx] = key;
38        trace.push(`  Boş hücre bulundu! İndeks ${idx} doldu.`);
39        return;
40      }
41      trace.push(`  Çakışma! İndeks ${idx} dolu (${this.table[idx]}). h2 (${h2}) adımı ile aranıyor.`);
42      i++;
43    }
44    trace.push('Tablo tamamen dolu, eklenemedi!');
45  }
46}