Quando parliamo di complessità asintotiche generalmente consideriamo molto grande n. Ora per la gestione delle collisioni in una tabella hash alcuni dei metodi sono l'hashing con catena & sondaggio lineare. In entrambi i casi possono accadere due cose (che ti aiuteranno a rispondere alla tua domanda): 1. Potresti aver bisogno di ridimensionare la tabella hash a causa del suo riempimento 2. Possono verificarsi collisioni.
Nel peggiore dei casi dipenderà dal modo in cui è stata implementata la tabella hash, ad esempio nel sondaggio lineare non si trova il numero, si continua a muoversi e il numero cercato era alla fine. Arriva il momento peggiore nel caso O (n). Venendo alla tecnica di hashing incatenato, quando accade una collisione, per gestirli affermiamo di aver memorizzato le chiavi in un albero binario bilanciato, quindi il tempo di esecuzione peggiore sarebbe O (log n).
Ora, nel migliore dei casi, penso che non ci sia confusione, in entrambi i casi sarebbe O (1).
O (n) accadrebbe nel peggiore dei casi e non nel caso medio di una tabella di hash ben progettata. Se ciò dovesse accadere, in media le tabelle hash non troveranno un posto in Data Structures perché allora gli alberi bilanciati in media ti darebbero O (log n) sempre e ON TOP OF THAT conserverà anche l'ordine.
Mi spiace dirlo ma sfortunatamente il tuo amico ha ragione. Il tuo caso potrebbe accadere negli scenari peggiori.
Vedi anche qui per le cose più informativo vale a dire il tempo di esecuzione ammortizzato: Time complexity of Hash table
vorrei aggiungere alla Yavar risposta: ricordate, che O (1) non è un op. Potrebbe essere una grande costante, ma non importa se non è derivata da una variabile come n. Anche se è necessario passare attraverso 20 nodi per inserire un hash, è ancora un O (1). Ovviamente, questo funziona per la tabella hash solo se alcune condizioni sono vere, ma per una tabella hash ben progettata che è O (1) in media – Archeg