Int2Int
Simple map for Int to Int relations. Designed for small to medium maps with a low amount of entries (<1000).
As there is no way to specify invalid values, a return value of 0 is given when the mapping does not exist. While it does mostly comply to the MutableMap interface, it is not implemented for performance reasons and for simplicity. It is designed to be used as a drop in replacement for a Map when the key is an Int and the value is an Int.
Implemented as a dual sorted array with binary search for fast lookups. Here is a summary of the performance characteristics:
get(key: Int):
Best/Average Case: 𝑂(log 𝑛). Searching is performed using a binary algorithm.
set(key: Int, value: Int):
Best/Average Case: 𝑂(log 𝑛) for the binary search and 𝑂(1) for the insertion without resizing.
Worst Case: 𝑂(log 𝑛) for the binary search and 𝑂(𝑛) for the insertion with array shifting and resizing.