Τι είναι ένας πίνακας κατακερματισμού;

Ο πίνακας κατακερματισμού (ή συσχετιστικός πίνακας, λεξικό) είναι μια δομή δεδομένων που υλοποιεί το διεπαφή του συσχετιστικού πίνακα, δηλαδή επιτρέπει την αποθήκευση ζευγών "κλειδί-τιμή" και την ταχεία αναζήτηση της τιμής με το κλειδί.

Η λειτουργία βασίζεται στη χρήση μιας συνάρτησης κατακερματισμού, η οποία μετατρέπει το κλειδί σε δείκτη (κατακερματισμό) μέσα στον πίνακα (ή δοχείο).

Βασικές λειτουργίες:

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; // Μετατροπή σε 32bit ακέραιο
  }
  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 συχνά προτιμάται, καθώς υποστηρίζει κλειδιά οποιουδήποτε τύπου και διατηρεί την σειρά εισαγωγής.

Ιδιότητες καλής συνάρτησης κατακερματισμού:

• Γρήγορος υπολογισμός.
• Ομοιόμορφη κατανομή των κατακερματισμών για διαφορετικά κλειδιά.
• Ελαχιστοποίηση συγκρούσεων.