The map uses a binary search tree (BST) structure internally. Because of this choice of internal representation, the KeyType for the keys stored in a Map must define a natural ordering through a less function and/or <, operator so that the keys can be compared and ordered. The ValueType does not need to provide any such natural ordering. Constructor Map() O(1) Initializes a new empty map that associates keys and values of the specified types. Methods clear() O(N) Removes all entries from this map. containsKey(key) O(log N) Returns true if there is an entry for key in this map. equals(map) O(N) Returns true if the two maps contain the same elements. get(key) O(log N) Returns the value associated with key in this map. isEmpty() O(1) Returns true if this map contains no entries. keys() O(N) Returns a Vector copy of all keys in this map. mapAll(fn) O(N) Iterates through the map entries and calls fn(key, value) for each one. put(key, value) O(log N) Associates key with value in this map. remove(key) O(log N) Removes any entry for key from this map. size() O(1) Returns the number of entries in this map. toString() O(N) Converts the map to a printable string representation. values() O(N) Returns a Vector copy of all values in this map. Operators map[key] O(log N) Selects the value associated with key. map1 == map1 O(N) Returns true if map1 and map2 contain the same elements. map1 != map2 O(N) Returns true if map1 and map2 are different. ostream <,<, map O(N) Outputs the contents of the map to the given output stream. istream >,>, map O(N log N) Reads the contents of the given input stream into the map. Source.