Una tabella hash può implementare una relazione che non può essere vista come una mappatura?

Innanzi tutto, ciò a cui ti riferisci come tabella hash è in realtà una mappa . Questo è il nome generico per questo tipo di struttura dati; una mappa hash implica un'implementazione specifica (una che utilizza una funzione hash). Una firma minima della Mappa Tipo di dati astratti (ADT) è simile alla seguente:

find: forall (k, v). k v map * k -> v opt
insert: forall (k, v). k v map * k * v -> k v map
empty: forall (k, v). k v map

Quanto sopra sta dicendo che map è un type-constructor (anche chiamato tipo di tipo superiore ) che accetta un paio di tipi (k, v) e produce un nuovo tipo denotato k v map . Le tre funzioni elencate sono polimorfiche , che è evidente dalla quantificazione del tipo forall (k, v) . Ciò significa che il find è parametrizzato da un pait di tipi.

La corrispondenza tra il tipo map e una funzione è evidente nella nomenclatura - le funzioni sono spesso chiamate mappature.

Chiaramente, come hai capito, ogni map con le chiavi di tipo k e i valori di tipo v induce una funzione da k a v . Per dimostrarlo, possiamo semplicemente dimostrare una funzione polimorfica che converte da una all'altra (questa è chiamata trasformazione naturale nella teoria delle categorie, il polimorfismo di questa funzione è ciò che è significativo):

map_to_func: forall (k, v): k v map -> (k -> v)
map_to_func m = \key -> case find(m, key) of Some v -> v | None -> loop forever

Se m è totale - nel senso che ogni chiave può essere trovata nella mappa - allora anche map_to_func m è totale. Ma se m non ha un valore per ogni chiave, allora il risultato è una funzione parziale, il cui risultato è indefinito (calcolo non sospeso) per alcuni input.

Nota a margine: la tua definizione di funzione è leggermente errata. Per affermare una funzione è necessario che ogni elemento del dominio si riferisca a non più di un elemento nel codominio; infatti, ogni elemento nel dominio deve riguardare esattamente un elemento nel codominio.

Direi "no", proprio perché le condizioni in cui si verificano le collisioni di hash sorgeranno al di fuori della semantica dell'implementazione della tabella hash: la sua gestione interna dei bucket, ecc.

In effetti, queste condizioni sono intrinsecamente contingenti, solo, all'algoritmo di hash utilizzato per il tipo di chiave della tabella hash.

L'unico modo in cui vedo una tabella hash potrebbe implementare tale relazione fedelmente è se la relazione stessa è definita esattamente come la mappatura in hash da dell'algoritmo hash tipo di chiave, ma suppongo che questo diventi un punto controverso.

Certo, ma probabilmente non vuoi.

Solo per ottenere una terminologia corretta: come dici tu nella domanda, le tabelle hash sono comunemente usate per implementare i mapping. Una cosa che implementa una mappatura è comunemente chiamata mappa. A seconda del linguaggio di programmazione in cui stai scrivendo quella cosa, una mappa potrebbe essere un tipo di dati astratto, una classe o qualcosa di simile. (Ad esempio, in Java, java.util.Map è un'interfaccia.) Dal momento che non so in quale lingua ci si trova, dirò semplicemente ADT / classe. Dato che stai chiedendo di usare le tabelle hash per implementare cose diverse dai mapping, presumo che stiamo definendo la "tabella hash" come la struttura dei dati grezzi con i bucket, non un'astrazione di livello superiore che ti limita a mappare le operazioni.

Niente ti impedisce di usare le tabelle hash per implementare cose diverse dai mapping. È solo che le mappature sono quelle che sono le tabelle di hash.

Dici di voler implementare una relazione, che è definita come una raccolta di coppie ordinate. Il modo ovvio per implementare quello sarebbe di fare una ADT / classe per rappresentare una coppia ordinata, quindi memorizzarne le istanze in un set, supponendo che tu abbia già una classe ADT / per rappresentare un set.

Ma hai ragione che c'è una sovrapposizione tra quella e una mappa implementata usando una tabella hash. Come sapete, le funzioni di hash hanno collisioni nel caso generale, quindi il codice che implementa una mappa utilizzando una tabella hash deve memorizzare un insieme di coppie (chiave, valore) per ogni codice hash (o per ciascun bucket, per essere più precisi) . E se (diciamo) "trovami tutti gli elementi in T che sono collegati a un dato elemento in S" sarà un'operazione comune che potrebbe avere senso implementare una relazione usando una tabella hash, come descrivi. Il trucco è che il codice per quell'operazione findby (s) dovrà restituire un sottoinsieme delle coppie (chiave, valore) nel bucket dove key = s, in contrasto con una mappa (che sarebbe restituire la prima coppia (chiave, valore) dove key = s) o la tabella hash raw (dove il bucket è un insieme di coppie (chiave, valore) dove truncate (hash (chiave)) = truncate (hash (s ))).

Il problema è che altre operazioni come "trovami tutti gli elementi in S relativi a un dato elemento in T" saranno più difficili. E ottenere la semantica di una relazione giusta sarà abbastanza difficile senza affrontare le idiosincrasie delle tabelle hash.