Map / Dict / Hash Table

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

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

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}

Clone

JavaScript

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

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');

Go

Use a two-value assignment:

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

Contains Value

JavaScript

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

Count Elements

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());

Get Values

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]}`);
}

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 }