Maps

There are two kinds of maps: HashMap and BTreeMap. The main difference between them is how they order themselves in memory. They have similar methods to insert and retrieve elements, but their performance changes a lot depending on the operation.

HashMap creates an index, where for every key a hash points to the element. That way, you do not need to check the whole key for every new insert/delete/get operation. You simply hash it and search it in the index. If it exists, it can be retrieved, modified, or deleted; if it doesn't, it can be inserted. It is pretty fast to insert new elements. It's as simple as adding it to the index. Retrieving it is also pretty much the same: just get the value if the hashed index exists; all operations are done in O(1). You cannot append one HashMap to another, though, because their hashing algorithms will be different, or at least be in different states.

BTreeMap, on the other hand, does not create indexes. It maintains an ordered list of elements and, that way, when you want to insert or get a new element, it does a binary search. Check whether the key is bigger than the key in the middle of the list. If it is, divide the second half of the list into two and try it again with the element of the middle of the second half; if it's not, do the same with the first half.

That way, you don't have to compare each element with all elements in the map, and you can quickly retrieve them. Adding new elements is a similarly costly algorithm, and all operations can be done in O(log n). You can also append another BTreeSet to this one, and the elements will be reordered for the search to be as fast as possible.