Harici Arama ve Hashing (External Searching & Hashing) Algoritması

1class ExtendibleBucket {
2  localDepth: number = 1;
3  keys: number[] = [];
4  capacity: number;
5  constructor(capacity: number) {
6    this.capacity = capacity;
7  }
8}
9
10class ExtendibleHashingSimulator {
11  globalDepth: number = 1;
12  directory: ExtendibleBucket[];
13  bucketCapacity: number;
14
15  constructor(capacity: number) {
16    this.bucketCapacity = capacity;
17    this.directory = [
18      new ExtendibleBucket(capacity), // 0
19      new ExtendibleBucket(capacity)  // 1
20    ];
21  }
22
23  insert(key: number, trace: string[]) {
24    const hashBits = key % 32; // Simüle hash
25    let idx = hashBits & ((1 << this.globalDepth) - 1);
26    let bucket = this.directory[idx];
27
28    trace.push(`${key} ekleniyor (Hash bitleri: ${hashBits.toString(2)}). Hedef Kova indeksi: ${idx}`);
29
30    if (bucket.keys.length < this.bucketCapacity) {
31      bucket.keys.push(key);
32      trace.push(`Kova dolmadığı için eleman eklendi. Kova içeriği: [${bucket.keys.join(', ')}]`);
33      return;
34    }
35
36    // Kova Dolu, Bölünme gerek
37    trace.push(`Kova dolu! Kova bölünmesi başlatılıyor (Local depth: ${bucket.localDepth}, Global depth: ${this.globalDepth})`);
38
39    if (bucket.localDepth === this.globalDepth) {
40      // Dizin genişletme
41      trace.push(`Local depth === Global depth olduğundan dizin ikiye katlanıyor.`);
42      const oldSize = this.directory.length;
43      for (let i = 0; i < oldSize; i++) {
44        this.directory.push(this.directory[i]);
45      }
46      this.globalDepth++;
47    }
48
49    // Yeni kova oluştur
50    const newBucket = new ExtendibleBucket(this.bucketCapacity);
51    bucket.localDepth++;
52    newBucket.localDepth = bucket.localDepth;
53
54    // Elemanları yeniden dağıt
55    const allKeys = [...bucket.keys, key];
56    bucket.keys = [];
57
58    const mask = 1 << (bucket.localDepth - 1);
59    const dIdx = hashBits & ((1 << this.globalDepth) - 1);
60
61    // Dizin göstergelerini güncelle
62    const dirSize = this.directory.length;
63    for (let i = 0; i < dirSize; i++) {
64      if (this.directory[i] === bucket) {
65        if ((i & mask) !== 0) {
66          this.directory[i] = newBucket;
67        }
68      }
69    }
70
71    // Dağıt
72    for (const k of allKeys) {
73      const kHash = k % 32;
74      const kIdx = kHash & ((1 << this.globalDepth) - 1);
75      this.directory[kIdx].keys.push(k);
76    }
77
78    trace.push(`Yeniden dağıtım tamamlandı. Global Depth: ${this.globalDepth}`);
79  }
80}