Complessità di esecuzione della tabella hash (inserimento, ricerca ed eliminazione)

Perché continuo a vedere complessità di runtime diverse per queste funzioni su una tabella hash?

Su wiki, la ricerca e l’eliminazione sono O (n) (ho pensato che il punto delle tabelle hash avrebbe avuto una ricerca costante, quindi qual è il punto se la ricerca è O (n)).

In alcune note del corso di qualche tempo fa, vedo una vasta gamma di complessità a seconda di alcuni dettagli, incluso uno con tutto O (1). Perché dovrebbe essere utilizzata qualsiasi altra implementazione se riesco a ottenere tutto O (1)?

Se sto usando tabelle standard di hash in un linguaggio come C ++ o Java, cosa posso aspettarmi dalla complessità del tempo?