Ҳадиса чӣ гуна аст?

Ҳештабл (ё асосиативӣ массив, луғат) структураи додаҳоест, ки интерфейси массиви асосиативиро иҷро мекунад, яъне имкон медиҳад, ки ҷуфтҳои "калид-арзиш" нигоҳ дошта шаванд ва ҷустуҷӯи арзишро бо калид тез анҷом диҳад.

Принсипи кор асос ёфтааст ба истифодаи функсияи ҳеш, ки калидро ба индекс (ҳеш) дар дохили массив (ё коса) табдил медиҳад.

Оммалҳои асосӣ:

1. Вуруд: Ҳеши калид ҳисоб карда мешавад ва ҷуфт "калид-арзиш" ба косаи дахлдор ҷойгир карда мешавад.
2. Баъдтар: Ҳеши калид ҳисоб карда мешавад, косаи дахлдор ёфта мешавад ва ҷуфт тоза карда мешавад.
3. Ҷустуҷӯ: Ҳеши калид ҳисоб карда мешавад, косаи дахлдор ёфта мешавад ва ҷуфти бо калиди дархостшуда ҷустуҷӯ мешавад.

Ҳештаблҳо одатан дар миёнаи коркарди баланд барои вуруд, тоза ва ҷустуҷӯ (дар ҳолати идеалӣ $O(1)$) самаранок мебошанд. Аммо дар ҳолати бадтарин (бо шумораи зиёди коллизияҳо, вақте ки калидҳои гуногун ба як индекс табдил меёбанд) самаранокӣ метавонад то $O(n)$ кам шавад.

Стратегияҳои гуногун барои ҳалли коллизияҳо вуҷуд доранд:

• Методҳои занҷир (Separate Chaining): Дар ҳар коса рӯйхати (масалан, рӯйхати пайвастшуда) элементҳо бо ҳамон ҳеш нигоҳ дошта мешавад.
• Нигоҳдории кушод (Open Addressing): Ҳангоми коллизия ҷустуҷӯи ҷойи озод мувофиқи алгоритми пешакӣ муайяншуда (хаттӣ, квадратикии зонд) анҷом дода мешавад.

Масалан (ба соддагӣ):

// Масалан функсияи ҳеши содда
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    hash = hash & hash; // Табдил ба 32-бит
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Метод занҷирҳо
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Санҷиши мавҷудияти калид барои навсозии арзиш
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        return this.buckets[index][i][1];
      }
    }
    return undefined; // Калид ёфт нашудааст
  }

  delete(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true; // Маҳкам тоза шуд
      }
    }
    return false; // Калид ёфт нашудааст
  }
}

// Истифода
const myHashTable = new HashTable(50);
myHashTable.insert("apple", 10);
myHashTable.insert("banana", 20);
console.log(myHashTable.get("apple")); // 10
myHashTable.delete("banana");
console.log(myHashTable.get("banana")); // undefined

Дар JavaScript, объектҳо ({}) ва харитаҳо (Map) намунаҳои иҷрои ҳештабл мебошанд. Map одатан афзалият дорад, зеро он клучҳои ҳар гуна навъҳоро дастгирӣ мекунад ва тартиби воридшударо нигоҳ медорад.

Хусусиятҳои хуби функсияи ҳеш:

• Ҳисоб кардани зуд.
• Тарази баробар дар байни клучҳои гуногун.
• Минимизатсияи коллизияҳо.