Il modo più semplice per rappresentare tre stati, dove si può tenere una coppia chiave / valore, e gli altri due sono marcatori vuoti

Il Probing lineare è intrinsecamente limitato e ha prestazioni non ottimali e non c'è modo di aggirare questi problemi. L'unico buon uso per le tabelle hash di analisi lineare è quando ci si trova in un ambiente con limitazioni di memoria e non si possono eseguire assegnazioni, o quando si ha una perfetta funzione di hash e si può quindi sapere che non si verificheranno collisioni.

Se davvero devi fornire la cancellazione, allora il tuo approccio ternario ha un senso. In Java, useremmo null per un bucket gratuito e lo stato del bucket per contrassegnarlo come occupato o eliminato. Per esempio:.

class Bucket<K, V> {
  K key;
  V value;
  boolean occupied;
  Bucket(K key, V value) {
    this.key = key;
    this.value = value;
    occupied = true;
  }
  void free() {
    key = value = null;
    occupied = false;
  }
}

Bucket<K, V> buckets[] = ...;

V get(K key) {
  int i = hash(key);
  for (; i < buckets.length; ++i) {
    Bucket b = buckets[i];
    if (b == null) break;
    if (b.occupied && b.key == key) return b.value;
  }
  throw ...;
}

void delete(K key) {
  int i = hash(key);
  for (; i < buckets.length; ++i) {
    Bucket b = buckets[i];
    if (b == null) break;
    if (b.occupied && b.key == key) b.free();
  }
}

Un'alternativa sarebbe quella di fare in modo che ciascun segmento si colleghi al prossimo segmento con lo stesso hash, che è in effetti un elenco collegato pre-assegnato. Nota che ogni Bucket ha bisogno di due puntatori: uno per il prossimo bucket per lo stesso hash di questa voce e uno per l'inizio dell'elenco per l'hash di questo bucket - che è necessario dal momento che quando un bucket viene riempito, la voce può appartenere a un elenco diverso e non a questo hash. In realtà, questo non sta usando più l'indirizzamento aperto. Ha le limitazioni di capacità di indirizzamento aperto poiché ogni bucket può contenere solo un valore, ma tutte le altre proprietà sono equivalenti alla tecnica dell'elenco collegato della risoluzione delle collisioni.

Esempio di struttura:

hashTable.put("a", 1) // hash(a) = 1
hashTable.put("b", 1) // hash(b) = 1
hashTable.put("c", 2) // hash(c) = 2
hashTable.put("d", 1) // hash(d) = 1
hashTable.put("e", 3) // hash(e) = 3

// 0: start: / next: 3 key: "b" value: 1
// 1: start: 1 next: 0 key: "a" value: 1
// 2: start: 2 next: / key: "c" value: 2
// 3: start: 4 next: / key: "d" value: 1
// 4: start: / next: / key: "e" value: 3

Schizzo algoritmi:

class Bucket<K, V> {
  K key = null;
  V value = null;
  Bucket<K, V> next = null;
  Bucket<K, V> start = null;
}

Bucket<K, V> buckets[] = ...;
// initialize buckets[] with empty buckets

V get(K key) {
  Bucket<K, V> b = buckets[hash(key)].start;
  for (; b != null; b = b.next) {
    if (b.key == key) return b.value;
  }
  throw ...;
}

void put(K key, V value) {
  Bucket<K, V> b = buckets[hash(key)];

  // case: first item in bucket
  if (b.start == null) {
    b.key = key;
    b.value = value;
    b.start = b;
    return;
  }

  // find bucket with key
  Bucket<K, V> p = null;
  b = b.start;
  for (; b != null; p = b, b = b.next) {
    // overwrite entry
    if (b.key == key) {
      b.value = value;
      return;
    }
  }

  // enter a new bucket into this list:
  b = getNextFreeBucket();
  p.next = b;
  b.key = key;
  b.value = value;
}

void delete(K key) {
  Bucket<K, V> p = null;
  Bucket<K, V> b = buckets[hash(key)].start;
  for (; b != null; p = b, b = b.next) {
    if (b.key == key) {
      b.key = null;
      b.value = null;
      if (p != null) p.next = b.next;
      b.next = null;
      return;
    }
  }
}

Cocoa NSDictionary utilizza un array contenente i valori hash (che è comunque utile, perché in questo modo la ricerca di una chiave non richiede il calcolo di alcun codice hash eccetto quello della chiave cercata), con due valori hash speciali riservato per indicare una cella inutilizzata e utilizzata in precedenza. Questi valori speciali non sono costanti ma memorizzati nella tabella hash. Se si tenta di aggiungere una coppia chiave / valore in cui il codice hash corrisponde a uno di questi due valori speciali (che sarebbe molto, molto raro), il codice seleziona due altri valori speciali in modo casuale finché non ne sceglie due che non sono utilizzati nell'hash tabella, quindi sostituisce tutti i valori speciali.

Non so quanto sia buono questo approccio, ma è usato da ogni singola applicazione su circa un miliardo di dispositivi, quindi è meglio che sia buono.

1. Ho i miei dubbi sul tracciamento occupato vs eliminato.

   Forse dovresti spostare gli elementi che arrivano dopo l'elemento eliminato di uno in basso, in modo simile a quello che fai quando elimini nel mezzo di un array come collezione. Per determinare quanti elementi hai bisogno di eliminare potresti usare una condizione simile a quella che usi per determinare quando la scansione lineare è terminata.

2. Per implementare il tuo primo approccio (diverse classi), vedo diversi modi per sostituire la corrispondenza del modello:

   • Aggiungi un metodo abstract State getState() in cui lo stato è un enum della classe base che quindi sovrascrivi nelle classi derivate. Quindi puoi switch sul suo risultato.
   • L'operatore instanceof
   • Poiché i valori speciali sono senza stato, è possibile creare istanze canoniche e confrontarle con esse (opere di uguaglianza di riferimento).

   Il primo di questi è l'approccio OOP corretto, quindi è probabilmente la scelta migliore per un compito a casa.

3. Come variante del tuo secondo approccio, è possibile cambiare colonna-ordine-maggiore . In questo modo non è necessario allocare un oggetto per slot, solo alcuni per collezione.

   Qualcosa come

   public class Dictionary<K, V>
   {
       K[] keys;
       V[] values;
       State[] states;
   }
   

   Ma non userei questo approccio in un compito a casa. Il potenziale guadagno in termini di prestazioni non vale la pena.

Invece di analizzare l'array, preferisco tenere un elenco collegato (contenente gli indici di slot) per ciascun bucket e un elenco collegato per gli slot liberi. Molto più semplice e migliore prestazione. Ma se i compiti richiedono l'approccio stupido, non può essere aiutato.