Map / Dict / Hash Table

Last Updated: 2024-01-20

Abstractions

Java LinkedHashMap = python collections.OrderedDict: remembers the order that keys were first inserted
Java TreeMap: red-black tree based, sorted by the keys, log(n) for all actions; no python equivalent

C++

Standard Library:

std::map: Similar to absl::btree_map, provided by the standard but significantly less performant.
std::unordered_map: Similar to absl::flat_hash_map, provided by the standard but significantly less performant.

Abseil:

absl::flat_hash_map: an unordered collection that maps each (unique) key to a not-necessarily-unique value;
absl::node_hash_map: Similar to absl::flat_hash_map, but uses separate allocations for the key and value, thus providing pointer stability;
absl::btree_map: an ordered collection that maps each (unique) key to a not-necessarily-unique value;

Rust

std::collections::HashMap
std::collections::BTreeMap

Java

HashMap

Python

dict

Go

map

JavaScript

object

Hack

dict<TKey, TValue>

Basics: Creat, Set, Get

C++

// map<char, int> m
m['a'] = 1;

Go

// create
m := make(map[string]int)

// get
v := m["Answer"]
v, ok := m["Answer"]

// set
m["Answer"] = 42

// delete
delete(m, "Answer")

Rust

let mut m = HashMap::new();

m.insert('a', 1);

Java

// create
Map<Character, Integer> m = new HashMap<>();

// set value
m.put('a', 1);

// get value
m.get('a');

JavaScript

// create
const a = {};

// set value
a['key'] = 'value';

// get value
a['key'];

// get or else:
//   if 'key' is not in the object, return 0
a['key'] || 0;

Python

Normal dict:

a = {}
a.get('key', 0)

defaultdict: will "default" a value if that key has not been set yet.

>>> import collections
>>> d = collections.defaultdict(lambda: 1)
>>> d
defaultdict(<function <lambda> at 0x104c64f28>, {})
>>> d[1]
1

No default lambda provided will throw exception

>>> c = collections.defaultdict()
>>> c[1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 1

Here lambda: 1 is the same as the parameterless function f that does this

def f():
  return 1

Ruby

>> fruit['b']
=> "banana"

Symbol:

>> dimensions[:depth]
=> 250

Get:

>> fruit['d'] = 'date'
=> "date"

Hack

// set
$d['baz'] = 2;

// remove
unset($d['baz']);

Initialization

JavaScript

Object Spread Properties

var a = 1,
  b = 2,
  c = 3;
var x = { x: 4, y: 5, z: 6 };

var obj = { a, b, c, ...x };

console.log(obj); //{a: 1, b: 2, c: 3, x: 4, y: 5, z: 6};

Object Spread is "last one in wins"

> a = {b : 1, c: 2}
{b: 1, c: 2}
> x = {y : 3, z : 4, c: 5}
{y: 3, z: 4, c: 5}
> n = {...a, ...x}
{b: 1, c: 5, y: 3, z: 4}

Hack

$d = dict['foo' => 1];

Ruby

>> fruit = { 'a' => 'apple', 'b' => 'banana', 'c' => 'coconut' }
=> {"a"=>"apple", "b"=>"banana", "c"=>"coconut"}

symbol

>> dimensions = { width: 1000, height: 2250, depth: 250 }
=> {:width=>1000, :height=>2250, :depth=>250}

Clone

JavaScript

let clone = Object.assign({}, obj);

Hack

$d = dict($keyed_container);

Contains Key

JavaScript

in operator matches all object keys, including those in the object's prototype chain.

if ('key' in obj) {
  // ...
}

.hasOwnProperty('key') checks any object's own keys:

obj.hasOwnProperty('key');

Hack

C\contains_key($d, 'foo')

Go

Use a two-value assignment:

if item, ok := m[key]; ok {
  // ...
}

Contains Value

JavaScript

Object.values(obj).includes('foo');

Hack

C\contains($d, 2)

Count Elements

Hack

C\count($d)

Type of

Hack

is_dict($d)

Get Keys

Go

Use for k := range m to get keys; the iteration order is not specified, to get sorted keys:

m := make(map[int]int)
var keys []int
for k := range m {
  keys = append(keys, k)
}
sort.Ints(keys)
for _, k := range keys {
  // ...
}

Python

Get keys of a dict:

d.keys()

JavaScript

Object.keys(obj);

Java

Map<Integer, String> map = new HashMap<>();

List<Integer> result = map.entrySet().stream()
    .map(x -> x.getKey())
    .collect(Collectors.toList());

Hack

Map

$m->keys()

Hack Arrays dict:

Vec\keys($dict)

Get Values

Hack

$vec = vec($dict);

Iteration

JavaScript

Use Object.keys(obj), Object.values(obj) and Object.entries(obj), e.g.

for (const [key, value] of Object.entries(obj)) {
  // ...
}

Use for ... in ...:

for (const key in object) {
  console.log(`${key}: ${object[key]}`);
}

Hack

$dict = dict[];
...
foreach ($dict as $key => $value) {
  ...
}

Destructuring

JavaScript

const { children, location } = this.props;

Object Rest Properties

var { a, b, c, ...x } = { a: 1, b: 2, c: 3, x: 4, y: 5, z: 6 };

console.log(a); // 1
console.log(b); // 2
console.log(c); // 3

console.log(x); // { x: 4, y: 5, z: 6 }

Convert To Other Collections

dict to Map

new Map($d)

dict to array

Arrays::fromDict($d)

dict keys to Vector

Vector::fromKeysOf($d)

dict keys to Set

Set::fromKeysOf($d)

dict keys to array

array_keys($d)

dict values to Vector

new Vector($d)

dict values to Set

new Set($d)

dict values to array

array_values($d)