Perchè molti linguaggi di programmazione hanno solo 2 strutture dati: array e hash?

Non c'è nulla che costringa in particolare un linguaggio ad avere array e hash come tipi di dati fondamentali. In effetti, molti non lo fanno (specialmente le lingue più vecchie). Tuttavia, ci sono alcuni concetti fondamentali coinvolti che indicano che questi tipi di mappature creano buone strutture di dati.

In primo luogo, la raccolta ordinata in cui si eseguono ricerche per numero di indice. Si tratta di una struttura molto comune che è molto utile nel caso in cui tu abbia un sacco di cose e tu voglia essere in grado di attraversarle una per una o cercare in alto da qualche indice. Il motivo principale per cui questo è così popolare è che la variazione in cui la raccolta è compatta e mappata su un'area contigua della memoria - l'array - è molto efficiente e veloce con l'hardware moderno. È questa efficienza che è il motivo per cui gli array sono molto comuni (anche se non universali). L'alternativa principale all'array è l'elenco collegato, anch'esso abbastanza comune; le liste concatenate hanno una ricerca lineare del tempo (mentre gli array hanno una ricerca a tempo costante) ma inserzioni e cancellazioni super-economiche dal centro della sequenza.

La seconda categoria principale di raccolta è una mappatura da valori di un tipo (che supporta un test di uguaglianza) a un altro tipo. Questo è un modo di realizzare un'intera classe di funzioni molto semplici in una struttura di dati basata sulla memoria ed è superbo per l'implementazione di tutti i tipi di altri tipi di dati di base. Il nome di queste cose varia (ad es. "Dizionario", "array associativo") così come la strategia di implementazione; le tre strategie di implementazione più comuni sono record / struct , l'albero di mappatura e la tabella hash. Le strutture sono molto comuni (e sono in effetti un ibrido parziale tra dizionari e array, in cui la chiave viene mappata su un offset in un blocco array / di memoria). Gli alberi erano molto comuni, ma sono diventati meno importanti in quanto risulta che tendono ad avere prestazioni sorprendentemente scarse (il loro pattern di accesso alla memoria risulta funzionare male con il modo in cui funzionano i predittori della memoria cache della CPU, il che è sfortunato). Le tabelle di hash, che erano relativamente rare qualche decennio fa, funzionano abbastanza bene: hanno schemi di accesso alla memoria ragionevoli e sono facili da implementare facilmente (il che non è assolutamente vero per gli alberi!). Il loro principale lato negativo è che non garantiscono l'ordine di iterazione (anche se ciò è risolvibile con una maggiore complessità nella progettazione della struttura dei dati).

Quindi, la vera cosa che le lingue stanno fornendo sono le mappe ℤ⁺ → α e α⁼ → β. Questi sono entrambi generalmente molto utili! Normalmente uno è fatto con gli array, perché sono facili da implementare e altamente efficienti per la ricerca (tipicamente l'operazione più comune), e l'altro è fatto normalmente con tabelle hash (o strutture), ancora una volta perché sono facili da implementare e di solito efficienti per la ricerca. Il motivo per cui queste due mappe particolari? Risultano essere sufficienti per creare moltissime altre strutture con un codice extra minimo (che a sua volta significa minimi errori extra).

Is there anything special about those datatypes that is necessary for the completeness of the language?

No.

Molte lingue non hanno hash come struttura dati fondamentale nella lingua. E infatti, ci sono esempi di lingue che non hanno né array né liste. (BCPL per esempio).

E molte lingue hanno altre strutture di dati fondamentali; per esempio. structs, unions, classes e così via.

La vera risposta è che c'è un compromesso complicato tra espressività, semplicità e implementabilità che il progettista di linguaggi deve fare. A seconda della natura e dello scopo della lingua, le diverse scelte sono più appropriate. Una delle scelte è se una particolare struttura di dati "utile" richiede il supporto linguistico o se è meglio fornita come una libreria (standard).

_{Il mio commento ha ricevuto molti voti positivi, quindi lo sto espandendo come risposta.}

La premessa di questa domanda prende una visione ristretta di ciò che i linguaggi di programmazione hanno effettivamente. Un sacco di lingue nella famiglia ML hanno liste piuttosto che matrici (semantica testa / coda invece di accesso casuale). E C non ha affatto hash hash . Inoltre, q / kdb + ha un contenitore tabella che riproduce un database simile a SQL in memoria.

Detto questo, tutti i linguaggi di programmazione pratica hanno loop e / o ricorsione. Questo tipo di flusso di controllo richiede che i dati possano essere indirizzati indirettamente.

Ad esempio, non posso dare un nome univoco a tutti i miei dati. Cioè, non posso chiamare le mie variabili alpha , bravo , charlie , ecc .; non solo esaurirò i nomi, ma non potrò nemmeno fare riferimento genericamente a una variabile in relazione a un'altra.

Quindi invece devo avere un indirizzamento indiretto, come x ₁ , x ₂ , x ₃ , ecc. Questa è una vera natura degli array! In alternativa, posso prendere una vista ricorsiva e indagare su first-of-xs e remainder-of-xs . Finché ho un indirizzamento indiretto, posso usare loop o ricorsioni.

Come @DonalFellows menziona nei commenti, ci sono modelli di calcolo che sono Turing completi e tuttavia non hanno indirizzamento indiretto Nessuno in realtà scrive il codice in questo modo.

Quindi, da un punto di vista pratico, credo che gli array o le liste siano necessari per la completezza in un linguaggio di programmazione poiché supportano i tradizionali meccanismi di controllo del flusso. Tutti gli altri contenitori come hash e le tabelle sono più per comodità.

Hai due scelte di base. Hai accesso diretto alla memoria (malloc con C e l'aritmetica del puntatore risultante) oppure devi fornire alcune strutture dati di base al programmatore.

La prima e più semplice struttura di dati è una lista di qualche tipo (sia implementata con un array o una lista collegata o qualche altra struttura di lista dietro le quinte).

Con una lista, si potrebbe chiedere al programmatore di scrivere la propria mappa / matrice associativa / struttura hashtable / dictonary. La maggior parte delle persone che hanno frequentato una classe di strutture di dati universitari lo ha fatto. Il problema è che molte persone lo hanno fatto male.

Per entrambi fare buon uso del computer (da non avere un'altra funzione hash scarsamente applicata) e l'ora del programmatore (per non dover scrivere ancora e ancora un'altra funzione hash scarsamente applicata - ripensare a C, di base e giorni FORTRAN ), molti progettisti di linguaggi hanno incorporato questa struttura nel linguaggio di base: o come struttura di base (perl %hash ) o come parte della libreria standard ( java.util.map ).

Questi finiscono davvero come le uniche due strutture di base necessarie (e in realtà, solo la possibilità di avere una lista / array / blocco di memoria indicizzabile è fondamentale). Con loro, si possono costruire set, alberi, skip list e tutto il resto delle complesse strutture dati che si possono sognare.