È ordinato un array associativo?

1

Un array associativo ha molti nomi simili in comune, hash, keymap, mappa, tabella, indice.

È una mappa di chiavi e valori ma non riesco a trovare una definizione attendibile della frase che mi dice se una mappa deve avere l'ordine di essere un array associativo.

  • Qual è una definizione affidabile del termine "Array associativo"?
  • È stato ordinato un array associativo?

Personalmente ho sempre creduto di dover essere ordinato perché in JavaScript rivendichiamo che gli oggetti non sono array associativi perché gli oggetti sono mappe non ordinate di chiavi e valori. Comunque potrei averlo citato senza un riferimento o una fonte.

    
posta Raynos 30.08.2011 - 20:29
fonte

3 risposte

8

La definizione di wikipedia sembra corretta e abbastanza generale:

collection of unique keys and a collection of values, where each key is associated with one value (or set of values)

Non una parola sull'ordine. Questo dovrebbe essere perfetto, poiché ci sono molti buoni modi per implementare strutture dati che sono array associativi perfetti, solo senza il requisito "ordinato" (se fosse lì). Non ho mai sentito qualcuno reclamare una "mappa ad albero" (come alcune API chiamano perché usa internamente un albero binario bilanciato) o hashtable non è un array associativo perché è ordinato o meno. Inoltre, la maggior parte del codice non interessa se le chiavi sono ordinate.

Personally I've always believed they have to be ordered because in JavaScript we claim Objects are not associative arrays because Objects are un-ordered maps of keys and values.

Quella logica ("AA deve essere ordinato perché gli Oggetti non sono AA perché gli Oggetti non sono ordinati") sembra un po 'circolare. Chi siamo noi e perché stai sostenendo questo? Gli oggetti Javascript sono chiaramente tabelle hash e le tabelle hash sono chiaramente array associativi di cui sopra e praticamente tutte le altre definizioni. Non sono ordinati, sì, ma questo non cambia il fatto che sono collezioni che associano le stringhe agli oggetti.

E anche se si è riusciti a trovare una fonte attendibile che definisce gli array associativi da ordinare, ci sono un sacco di persone e testi là fuori che non vanno su tale presupposto. Per sicurezza, dovresti aggiungere esplicitamente il requisito "ordinato" quando è importante e ometterlo ogni volta che non ha importanza (il che è sorprendentemente spesso).

    
risposta data 30.08.2011 - 20:36
fonte
1

Sembra che ci siano due (2) domande, o forse due interpretazioni per la tua domanda che potresti prendere:

  1. Gli array associativi, così come sono definiti in un senso teorico implicano qualsiasi tipo di ordinamento

  2. Esiste un ordinamento sottostante degli elementi in un'implementazione dell'array associativo nella lingua XYZ?

Dato che la tua domanda sfoggia l'etichetta indipendente dalla lingua, allora vorrebbe naturalmente favorire la prima interpretazione. E la risposta è: no, gli array associativi, per definizione, non implicano alcun tipo di ordinamento degli elementi .

È tuttavia vero che in un'implementazione specifica, la struttura dei dati utilizzata per implementare la funzionalità dell'array associativo potrebbe avere qualche ordinamento sottostante degli elementi, e potrebbe anche essere il caso che un programmatore intelligente potrebbe trarre vantaggio da tale ordinamento ( supponendo che sia esposto o raggiungibile dal programmatore) nel processo di scrittura di un programma.

Il problema con questo, tuttavia, è che tale implementazione o trucco intelligente sarebbe utile solo nel linguaggio specifico, e probabilmente usando un compilatore specifico su un'architettura specifica, e come tale non rappresenta alcuna cosa che potrebbe essere utilizzata per qualsiasi utilizzo di un array associativo.

    
risposta data 30.08.2011 - 22:39
fonte
0

Alcuni sono, altri no. Alcuni sistemi di mappatura chiave per valore dipendono dall'ordine, come gli alberi di ricerca binari. Alcuni come le mappe di hash non sono ordinati. Non c'è niente di inerente all'associazione che implica l'ordine.

    
risposta data 30.08.2011 - 22:59
fonte

Leggi altre domande sui tag