6 ms·
Like I said, feel free to analyze the implementation (Or just look in the JavaDoc (https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html https://docs
by exabrial 10y ago
Like I said, feel free to analyze the implementation (Or just look in the JavaDoc (https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html https://docs.oracle.com/javase/8/docs/api/java/util/HashMap....) Given the hash function was known (it was a String) his answer of O(n) is incorrect, it is indeed O(1). If you violate the API and put something like "return 1" as your hashcode() you will get O(n), but this was not the case for this interview question.
I think the big misunderstanding in most of these answers is assuming a fixed amount of buckets are used in Java's implementation. That is not correct, the put() method will rehash your table if it grows too big. (meaning that on average put() is O(1) but has a very real possibility of being O(n).