That's a bit pedantic, innit. It isn't strictly O(1) but with any reasonable implementation the collision resolution algorithm will make it have an amortized O(M), where M << N and therefore effectively constant.