order of hashmap/hashtable in BIG-O Notation

Order or complexity of any hash implemented data structure in java is O(1).

O(1)  means the time to retrieve an element from the data structure is always almost equals to constant. However poor implementation of hashing can lead to the complexity of O(n).

In O(1) complexity, the elements of the data structure are distributed across the buckets evenly.

In O(n) complexity, the elements of the data structure are all stored in one bucket (very poor hashing implementation).

Note: However SUN will revisit the user given hash code to avoid O(n) complexity, to get more into the details look at detailed hashmap implementation