Хэш таблицасы эмне?

Хэш таблица (же ассоциативдүү массив, сөздүк) — бул маалымат структурасы, ал ассоциативдүү массив интерфейсин ишке ашырып, " ачкыч-маани" жуптарын сактоого жана ачкыч боюнча маанини тез издөөгө мүмкүндүк берет.

Ишке ашыруу принциби хэш-функцияны колдонууга негизделген, ал ачкычты массивдин (же бакеттин) ичинде индекске (хэшке) айлантат.

Негизги операциялар:

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 көбүнесе артыкчылыкка ээ, анткени ал бардык түрдөгү ачкычтарды колдойт жана салынган тартибин сактайт.

Жакшы хэш-функциянын касиеттери:

• Жылдам эсептөө.
• Таркатуу бирдей болушу үчүн ар кандай ачкычтар үчүн хэштердин тең бөлүштүрүлүшү.
• Коллизияларды минималдаштыруу.