@Override
  public long get(long key) {
    long chunk = key >>> 8;
    if (chunk >= offsets.size()) {
      return MISSING_VALUE;
    }

    // use the "offsets" index to narrow search space to <256 values
    long lo = offsets.getLong(chunk);
    long hi = Math.min(keys.size(), chunk >= offsets.size() - 1 ? keys.size() : offsets.getLong(chunk + 1)) - 1;

    while (lo <= hi) {
      long idx = (lo + hi) >>> 1;
      long value = keys.getLong(idx);
      if (value < key) {
        lo = idx + 1;
      } else if (value > key) {
        hi = idx - 1;
      } else {
        // found
        return values.getLong(idx);
      }
    }
    return MISSING_VALUE;
  }
A longlong map that stores keys and values sorted by key and does a binary search to lookup values.
planetiler-core/src/main/java/com/onthegomap/planetiler/collection/SortedTableLongLongMap.java