Le tabelle hash sono strutture di dati abbastanza complicate e, a seconda di come le implementerai, le prestazioni varieranno. Inoltre, alcune implementazioni possono essere facilmente ingannate per entrare nel peggiore dei casi. Indipendentemente dal modo in cui si implementa una tabella hash, il caso peggiore per l'inserimento e il recupero sarà O(n) . Tuttavia, le tabelle hash hanno ancora una complessità molto interessante per il caso media , specialmente quando si usa il concatenamento per la risoluzione delle collisioni che analizzerò nel resto di questa risposta.

In primo luogo, un po 'di terminologia. Una tabella hash è composta da k bucket (posizioni di memoria) e contiene% coppie chiave-valore% co_de. Ora possiamo calcolare il fattore di carico n . Questo fattore di carico anche approssimativamente (per il piccolo f = n/k ) corrisponde alla probabilità che quando inseriamo un elemento, il bucket indirizzato sia già in uso. ^[1] Il load factor f è anche il numero previsto di elementi in un secchio! Pertanto, il recupero per una tabella hash non è in f ma in realtà O(1) in media - il caso peggiore O(f) è ancora valido.

^{[1]: Per essere precisi, la probabilità di almeno una collisione dopo l'inserimento di un elemento è O(n) a causa del paradosso del compleanno.}

Per essere veramente pedante, il caso medio è pc = 1 - (1 - 1/k)n per un O(f) = O(n/k) = O(n) fisso. Questo è male, poiché sconfigge l'intero punto di utilizzo di una tabella hash. Pertanto, le implementazioni utilizzano ridimensionamento dinamico per limitare il fattore di carico a un valore costante, in genere k . Ogni volta che il nostro fattore di carico raggiunge quel limite, riallociamo la tabella hash per raddoppiare quella dimensione fmax = 0.7 ± 0.1 , che dimezza anche il fattore di carico! Ogni riallocazione è k , ma si verifica solo ogni O(n) inserzioni. Pertanto, mentre ogni singolo inserimento può richiedere fino a 1/n , il costo distribuito su tutti gli inserimenti è O(n) - la complessità ammortizzata . È quindi corretto affermare che una tabella hash con concatenamento e ridimensionamento dinamico ha una complessità amortizzata di O(1) nel caso medio di inserimento e recupero.

Ci sono ancora alcune ipotesi qui: la funzione di hash deve essere uniforme (cioè, deve usare il suo intero codominio con probabilità approssimativamente uguale), e deve avere un costo trascurabile. Per i tipi di chiavi di dimensioni variabili, questo potrebbe non essere fornito, in modo che sarebbe più corretto affermare che l'inserimento e il recupero sono O(1) . Tuttavia, questa complessità è indipendente dalla struttura dei dati, ma piuttosto una proprietà dei dati, quindi dovremmo (principalmente) ignorarla durante l'analisi della struttura dei dati.

Il tuo argomento si basa sul principio pigeonhole ed è corretto, ma non significativo.

So, unless there is some special information about the special nature of the strings to be hashed, one cannot choose a hash function that is guaranteed to work for a chained hash table.

Funzionerà qualsiasi funzione di hash che soddisfi determinate proprietà. Infatti, poiché la funzione hash viene utilizzata per derivare un indice bucket, non ha un codominio della dimensione O(h(key)) ma in realtà solo della dimensione 264 . Tuttavia, sono previste collisioni di hash e possono essere risolte in modo da mantenere la complessità di k . Per risolvere una collisione hash, la chiave non cancellata viene memorizzata insieme al valore nel bucket. Al momento del recupero, la chiave di recupero viene confrontata con la chiave memorizzata per l'uguaglianza. Se un bucket contiene più di una voce, la confrontiamo con tutte le chiavi memorizzate. Questa è effettivamente una ricerca lineare, ma come mostrato sopra è O(1) in media quando si utilizza il ridimensionamento dinamico e gestisce correttamente le collisioni di hash.

Given a specific hashing scheme […], is it possible to choose a sequence of strings […] such that the time to insert increases linearly with the number of strings?

Sì, se attiviamo il caso peggiore in modo tale che tutte le stringhe abbiano lo stesso hash. Per esempio. quando utilizza O(1) come funzione di hash (che non è consigliabile poiché non è un hash uniforme sulla maggior parte dei dati) , quindi l'utilizzo di molte stringhe della stessa lunghezza delle chiavi nella tabella verrà mappato allo stesso bucket, indipendentemente dalla dimensione della tabella hash. Poiché questo potrebbe essere utilizzato negli attacchi denial-of-service, alcune implementazioni di hash table utilizzano funzioni hash casuali in cui il caso peggiore non può essere previsto da un utente malintenzionato. Questo non è possibile in C ++, ma strlen() ti consente di fornire una funzione di hash personalizzata come parametro template se sei a conoscenza di alcune proprietà delle tue chiavi.

Ma ancora una volta, questo è solo il caso peggiore. Come accennato in precedenza, la discussione sulla complessità media presuppone che la funzione di hash sia effettivamente uniforme.

Stack Overflow spiega lo sfondo in un modo che potrebbe aiutarti a capire perché lo standard solo dice "è così". La proposta la discute in lieve dettaglio (ricerca per ' complessità in scala ').

Control of Hash Resizing

The time required for looking up an element by key k is c1 + c2 n, where c1 and c2 are constants, and where n is the number of elements in the bucket indexed by k's hash code. If the hash function is well chosen, and elements are evenly distributed between buckets, this is approximately c1 + c2 N/B, where N is the number of elements in the container and B is the bucket count. If the bucket count is taken as a constant, then the asymptotic complexity for element lookup is O(N).

To maintain average case complexity O(1) for lookup, the bucket count must grow as elements are added to the hash table; on average the bucket count must be proportional to N. Another way of putting this is that the load factor, N/B, must be approximately constant. ...

La tua seconda domanda è semplice, ogni schema di hashing che restituisce la stessa costante ogni volta che richiederà un inserimento benna ogni volta e con un inserimento di tempo lineare (tramite la scelta dello schema del bucket) ottieni un tempo lineare.

Cplusplus.com ^* afferma quanto segue su std::undered_map::operator[] § Complessità :

Average case: constant.

Worst case: linear in container size.

May trigger a rehash if an element is inserted (not included in the complexity above).

Si afferma che su media la complessità è O (1) ; ma nel peggiore dei casi, come con i tuoi identificatori costruiti per generare collisioni di hash, le prestazioni potrebbero essere lineari come te stesso.

Inoltre quando reserving più spazio di bucket_count * max_load_factor a rehash viene attivato. insert e map["key"] = value possono anche innescare un rehash. complessità rehash'es è:

In case of rehash,

Average case: linear in container size.

Worst case: quadratic in container size.

TLDR

L'OP è corretto sulla complessità. Lo standard afferma questo, il PO l'ha trascurato. Sì, è possibile costruire una sequenza di chiavi che genererebbe prestazioni terribili; security.SE potrebbe avere qualcosa di utile da dire al riguardo.

Questo è il link a standard internazionale C ++ - n3242.pdf (ovvero ISO / IEC 14882: 2011 )

^{*) Non sono sicuro che Cplusplus.com sia il riferimento canonico per ISO/IEC 14882: 2011 ma sembrano seguirlo abbastanza da vicino}