Ի՞նչ է հեշ աղյուսակը։

Հեշ աղյուսակ (կամ ասոցատիվ զանգված, բառարան) տվյալների կառուցվածք է, որը իրականացնում է ասոցատիվ զանգվածի ինտերֆեյսը, այսինքն՝ այն թույլ է տալիս պահել " բանալի-արժեք" զույգեր և արագ որոնել արժեքը ըստ բանալիի:

Աշխատանքի սկզբունքը հիմնված է հեշ-ֆունկցիայի օգտագործման վրա, որը փոխում է բանալին ինդեքս (հեշ) զանգվածի ներսում:

Հիմնական գործողությունները՝

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 հաճախ նախընտրելի է, քանի որ աջակցում է ցանկացած տիպի բանալիներ և պահպանում է ներդրման կարգը:

Լավ հեշ-ֆունկցիայի հատկություններ՝

• Արագ հաշվարկ:
• Բաժանման հավասար բաշխում տարբեր բանալիների համար:
• Կոլիզիաների նվազեցում: