Skip to content

Maps

Quote

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” — Linus Torvalds

Operation HashMap LinkedHashMap IdentityHashMap WeakHashMap EnumMap TreeMap ConcurrentHashMap ConcurrentSkipListMap
Get \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\)
Contains \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\)
Next \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(h / n)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(h / n)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(h / n)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(h / n)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Operation dict
k in d \(\color{white} \fcolorbox{limegreen}{forestgreen} {Θ(1)}\) → \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\)
Copy \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\)
Get item \(\color{white} \fcolorbox{limegreen}{forestgreen} {Θ(1)}\) → \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\)
Set item \(\color{white} \fcolorbox{limegreen}{forestgreen} {Θ(1)}\) → \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\)
Delete item \(\color{white} \fcolorbox{limegreen}{forestgreen} {Θ(1)}\) → \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\)
Iteration \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\)

Maps are a collection of key-value pairs.

var map = [
    5: 1,
    10: 2,
    20: 3,
]

var unmodifiableMap = Collections.unmodifiableMap(map)

Map<Integer, Integer> map = new HashMap<>();
map.put(1, 2);
map.put(2, 3);
map.put(3, 4);

Map<Integer, Integer> unmodifiableMap = Collections.unmodifiableMap(map);

const map =
    new Map([
        [5, 1],
        [10, 2],
        [20, 3],
    ]);

val map =
    mutableMapOf(
        5 to 1,
        10 to 2,
        20 to 3
    )

val unmodifiableMap = map.toMap()

map = {
    5: 1,
    10: 2,
    20: 3,
}

const map =
    new Map<number, number>([
        [5, 1],
        [10, 2],
        [20, 3],
    ]);

block-beta
  columns 2
  block:keys
    columns 1
    k1["5"] k2["10"] k3["15"] k4["20"]
  end
  block:vals
    columns 1
    v1["3"] v2["6"] v3["5"] v4["8"]
  end

  k1 --> v1
  k2 --> v2
  k3 --> v3
  k4 --> v4

Which one to use?

  • HashMap is the fastest to iterate.
  • Use LinkedHashMap when the insertion order matters.
  • Use TreeMap when the natural order matters.
  • Use WeakHashMap for in-memory caching.
  • Use ConcurrentHashMap for thread-safe operations.