Hash map#
A hash map is a data structure that maps keys to values with amortized O(1) insertion, find, and deletion time. The map is unordered.
Open3D allows parallel hashing on CPU and GPU with keys and values organized as Tensors, where we take a batch of keys and/or values as input.
Keys: The Open3D hash map supports multi-dimensional keys. Due to precision issue, floating-point is not recommended to be regarded as keys. By default we support up to 6D coordinates in integer. For higher dimensions, you may modify the macros and compile from source in this file within this snippet:
#define DIM_SWITCHER(DTYPE, DIM, ...) \
if (DIM == 1) { \
INSTANTIATE_TYPES(DTYPE, 1) \
return __VA_ARGS__(); \
} else if (DIM == 2) { \
INSTANTIATE_TYPES(DTYPE, 2) \
return __VA_ARGS__(); \
} else if (DIM == 3) { \
INSTANTIATE_TYPES(DTYPE, 3) \
return __VA_ARGS__(); \
} else if (DIM == 4) { \
INSTANTIATE_TYPES(DTYPE, 4) \
return __VA_ARGS__(); \
} else if (DIM == 5) { \
INSTANTIATE_TYPES(DTYPE, 5) \
return __VA_ARGS__(); \
} else if (DIM == 6) { \
INSTANTIATE_TYPES(DTYPE, 6) \
return __VA_ARGS__(); \
} else { \
utility::LogError( \
"Unsupported dim {}, please modify {} and compile from " \
"source", \
DIM, __FILE__); \
}
Values: The Open3D hash map supports values in arbitrary dimensions and data types.
Devices: Both CPU and CUDA are supported. The CPU hashmap is based on TBB, while the CUDA hash map is based upon stdgpu.
[1]:
import open3d.core as o3c
import numpy as np
capacity = 10
device = o3c.Device('cpu:0')
A simple example#
We first create a simple hash map from integers to integers.
We specify an initial estimated capacity. This capacity will be automatically adjusted when insertion occurs. Then we specify the element shape of keys and values, corresponding to the shape of each individual element.
[2]:
hashmap = o3c.HashMap(capacity,
key_dtype=o3c.int64,
key_element_shape=(1,),
value_dtype=o3c.int64,
value_element_shape=(1,),
device=device)
Insertion#
Next we show how to insert a batch of (key, value) pairs. You’ll need to prepare two tensors:
The keys tensor contains all keys.
The
keystensor must be on the same device as the hash map.The shape of the
keystensor iskey_elment_shapewithNprefixed to the front.
For example
if
key_element_shape == (),keys.shape == (N,);if
key_element_shape == (3,),keys.shape == (N, 3).;if
key_element_shape == (8, 8, 8),keys.shape == (N, 8, 8, 8).
The vals tensor contains all values.
The
valstensor must be on the same device as the hash map.The shape of the
valstensor isval_elment_shapewithNprefixed to the front.
For example
if
val_elment_shape == (),vals.shape == (N,);if
val_elment_shape == (3,),vals.shape == (N, 3).;if
val_elment_shape == (8, 8, 8),vals.shape == (N, 8, 8, 8).
[3]:
# Prepare a batch of 7 key/values, each a int64 element
keys = o3c.Tensor([[100], [200], [400], [800], [300], [200], [100]],
dtype=o3c.int64,
device=device)
vals = o3c.Tensor([[1], [2], [4], [8], [3], [2], [1]],
dtype=o3c.int64,
device=device)
buf_indices, masks = hashmap.insert(keys, vals)
Here, masks indicates whether a (key, value) pair is successfully inserted. A mask of value True means the insertion is successful and False if the insertion is skipped.
Unsuccessful insertion only happens when there are duplicated keys.
If there are duplicated keys, it is guaranteed that only one of the duplicated keys and its corresponding value will be inserted. That is, for a set of duplicated keys, one and only one will get a True mask.
Since the insertion runs in parallel, there is no guarantee which one of the duplicated keys will be inserted. That is, for a set of duplicated keys, we don’t know which key gets the True mask.
Using advanced indexing, we can obtain which keys are inserted:
[4]:
print('masks: \n', masks)
print('inserted keys: \n', keys[masks])
masks:
[True True True True True False False]
Tensor[shape={7}, stride={1}, Bool, CPU:0, 0x5571293a85a0]
inserted keys:
[[100],
[200],
[400],
[800],
[300]]
Tensor[shape={5, 1}, stride={1, 1}, Int64, CPU:0, 0x557128c4f760]
Next, let’s look at the usage of buf_indices. In our hash map, keys and values are stored in contiguous buffer tensors that could be conveniently accessed by indices. Instead of returning iterators that are less friendly to vectorized programming, we return such buffer indices.
These indices are not necessarily the same as input indices due to concurrency. Also, the indices are by default stored in int32 due to the underlying implementations. A conversion to int64 is required for advanced indexing.
[5]:
buf_keys = hashmap.key_tensor()
buf_vals = hashmap.value_tensor()
buf_indices = buf_indices[masks].to(o3c.int64)
print('buffer indices: \n', buf_indices)
inserted_keys = buf_keys[buf_indices]
inserted_vals = buf_vals[buf_indices]
print('inserted keys: \n', inserted_keys)
print('inserted values: \n', inserted_vals)
buffer indices:
[0 1 3 4 2]
Tensor[shape={5}, stride={1}, Int64, CPU:0, 0x5571293ae6d0]
inserted keys:
[[100],
[200],
[400],
[800],
[300]]
Tensor[shape={5, 1}, stride={1, 1}, Int64, CPU:0, 0x5571284a73b0]
inserted values:
[[1],
[2],
[4],
[8],
[3]]
Tensor[shape={5, 1}, stride={1, 1}, Int64, CPU:0, 0x5571284a6f50]
Query#
The query operation follows the similar convention. Note as the operation is read-only, duplicate keys are allowed and will be returned properly.
[6]:
query_keys = o3c.Tensor([[1000], [100], [300], [200], [100], [0]],
dtype=o3c.int64,
device=device)
buf_indices, masks = hashmap.find(query_keys)
valid_keys = query_keys[masks]
buf_indices = buf_indices[masks].to(o3c.int64)
valid_vals = hashmap.value_tensor()[buf_indices]
print('found valid keys: \n', valid_keys)
print('found valid values: \n', valid_vals)
found valid keys:
[[100],
[300],
[200],
[100]]
Tensor[shape={4, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293a3ae0]
found valid values:
[[1],
[3],
[2],
[1]]
Tensor[shape={4, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293ae6d0]
Active entries in the hash map#
Sometimes we are interested in all the active entries. This can be achieved by:
[7]:
def print_active_entries(hashmap):
active_buf_indices = hashmap.active_buf_indices().to(o3c.int64)
active_keys = hashmap.key_tensor()[active_buf_indices]
print('all active keys:\n', active_keys)
active_vals = hashmap.value_tensor()[active_buf_indices]
print('all active values:\n', active_vals)
Again, due to concurrency, the order is not guaranteed, but the key-value correspondence will be of course preserved.
Erase#
We can similarly erase keys. The behavior is similar to insert:
[8]:
erase_keys = o3c.Tensor([[100], [1000], [100]], dtype=o3c.int64, device=device)
masks = hashmap.erase(erase_keys)
print('erase masks:\n', masks)
print('erased keys:\n', erase_keys[masks])
erase masks:
[True False False]
Tensor[shape={3}, stride={1}, Bool, CPU:0, 0x5571292dd430]
erased keys:
[[100]]
Tensor[shape={1, 1}, stride={1, 1}, Int64, CPU:0, 0x5571284a6a10]
Now we can see that active entries have been changed:
[9]:
print_active_entries(hashmap)
all active keys:
[[300],
[200],
[400],
[800]]
Tensor[shape={4, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293a9ad0]
all active values:
[[3],
[2],
[4],
[8]]
Tensor[shape={4, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293b1d10]
Activate#
In some cases, we know a key is occupied, but do not know the associated value - we prefer to compute and modify it in-place afterwards. This can be achieved by a chain of operations:
[10]:
activate_keys = o3c.Tensor([[1000], [0]], dtype=o3c.int64, device=device)
buf_indices, masks = hashmap.activate(activate_keys)
buf_vals = hashmap.value_tensor()
# Note the assigned tensor has to be strictly in the shape of (N, 1) due to broadcasting
buf_vals[buf_indices[masks].to(o3c.int64)] \
= o3c.Tensor([[10], [0]],
dtype=o3c.int64,
device=device)
print_active_entries(hashmap)
all active keys:
[[300],
[1000],
[200],
[400],
[0],
[800]]
Tensor[shape={6, 1}, stride={1, 1}, Int64, CPU:0, 0x5571284a6b00]
all active values:
[[3],
[10],
[2],
[4],
[0],
[8]]
Tensor[shape={6, 1}, stride={1, 1}, Int64, CPU:0, 0x5571284a6a60]
Rehashing and reserve#
Rehashing will be automatically triggered when the initial capacity is exceeded after multiple insertions, where the capacity of the hash map is doubled. Rehashing will change the location (i.e. buffer indices) of the inserted key-value pairs, so an update of the buffer indices in the downstream applications is required.
[11]:
print('size:', hashmap.size())
print('capacity:', hashmap.capacity())
keys = o3c.Tensor([[700], [1200], [1500]], dtype=o3c.int64, device=device)
vals = o3c.Tensor([[7], [12], [-1]], dtype=o3c.int64, device=device)
buf_indices, masks = hashmap.insert(keys, vals)
print('size:', hashmap.size())
print('capacity:', hashmap.capacity())
print_active_entries(hashmap)
keys = o3c.Tensor([[1600], [1700], [1800]], dtype=o3c.int64, device=device)
vals = o3c.Tensor([[16], [17], [18]], dtype=o3c.int64, device=device)
buf_indices, masks = hashmap.insert(keys, vals)
print('size:', hashmap.size())
print('capacity:', hashmap.capacity())
print_active_entries(hashmap)
size: 6
capacity: 10
size: 9
capacity: 10
all active keys:
[[300],
[1500],
[700],
[1000],
[200],
[400],
[1200],
[0],
[800]]
Tensor[shape={9, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293b4d80]
all active values:
[[3],
[-1],
[7],
[10],
[2],
[4],
[12],
[0],
[8]]
Tensor[shape={9, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293b64d0]
size: 12
capacity: 20
all active keys:
[[1700],
[300],
[1500],
[700],
[1000],
[200],
[1800],
[400],
[1200],
[1600],
[0],
[800]]
Tensor[shape={12, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293b6410]
all active values:
[[17],
[3],
[-1],
[7],
[10],
[2],
[18],
[4],
[12],
[16],
[0],
[8]]
Tensor[shape={12, 1}, stride={1, 1}, Int64, CPU:0, 0x5571293b8250]
Rehashing is slow, as it increases the hash map capacity, collects all the active entries, and insert them back to the hash map. If we know the capacity beforehand, we can pre-allocate a chunk of memory and avoid rehashing:
[12]:
hashmap.reserve(100)
print('size:', hashmap.size())
print('capacity:', hashmap.capacity())
size: 12
capacity: 100
Multi-valued hash map#
In real-world applications, we want to map coordinates to complex data structures, e.g. a voxel position to its color and weight. This can be achieved by a multi-valued hash map.
This is not a multimap and does not allow duplicate keys. A multi-valued hash map can be constructed by
[13]:
mhashmap = o3c.HashMap(capacity,
key_dtype=o3c.int32,
key_element_shape=(3,),
value_dtypes=(o3c.uint8, o3c.float32),
value_element_shapes=((3,), (1,)),
device=device)
voxel_coords = o3c.Tensor([[0, 1, 0], [-1, 2, 3], [3, 4, 1]],
dtype=o3c.int32,
device=device)
voxel_colors = o3c.Tensor([[0, 255, 0], [255, 255, 0], [255, 0, 0]],
dtype=o3c.uint8,
device=device)
voxel_weights = o3c.Tensor([[0.9], [0.1], [0.3]],
dtype=o3c.float32,
device=device)
mhashmap.insert(voxel_coords, (voxel_colors, voxel_weights))
[13]:
([1 0 2]
Tensor[shape={3}, stride={1}, Int32, CPU:0, 0x5571293b83f0],
[True True True]
Tensor[shape={3}, stride={1}, Bool, CPU:0, 0x5571293bab60])
We can then query and access by indices with a slightly different routine:
[14]:
query_coords = o3c.Tensor([[0, 1, 0]], dtype=o3c.int32, device=device)
buf_indices, masks = mhashmap.find(query_coords)
valid_keys = query_coords[masks]
buf_indices = buf_indices[masks].to(o3c.int64)
valid_colors = mhashmap.value_tensor(0)[buf_indices]
valid_weights = mhashmap.value_tensor(1)[buf_indices]
print('found coordinates:\n', valid_keys)
print('found colors:\n', valid_colors)
print('found weights:\n', valid_weights)
found coordinates:
[[0 1 0]]
Tensor[shape={1, 3}, stride={3, 1}, Int32, CPU:0, 0x5571293c47c0]
found colors:
[[0 255 0]]
Tensor[shape={1, 3}, stride={3, 1}, UInt8, CPU:0, 0x5571293c47a0]
found weights:
[[0.9]]
Tensor[shape={1, 1}, stride={1, 1}, Float32, CPU:0, 0x5571284a6540]
[15]:
def print_active_multivalue_entries(mhashmap):
active_buf_indices = mhashmap.active_buf_indices().to(o3c.int64)
active_keys = mhashmap.key_tensor()[active_buf_indices]
print('all active keys:\n', active_keys)
n_buffers = len(mhashmap.value_tensors())
for i in range(n_buffers):
active_val_i = mhashmap.value_tensor(i)[active_buf_indices]
print('active value {}\n:'.format(i), active_val_i)
print_active_multivalue_entries(mhashmap)
all active keys:
[[0 1 0],
[3 4 1],
[-1 2 3]]
Tensor[shape={3, 3}, stride={3, 1}, Int32, CPU:0, 0x5571293b1d40]
active value 0
: [[0 255 0],
[255 0 0],
[255 255 0]]
Tensor[shape={3, 3}, stride={3, 1}, UInt8, CPU:0, 0x5571293c5610]
active value 1
: [[0.9],
[0.3],
[0.1]]
Tensor[shape={3, 1}, stride={1, 1}, Float32, CPU:0, 0x5571293c56d0]
Hash set#
Hash set is a simplified hash map where we do not care about the values. It preserves most of the operations in a hash map, and could be useful for removing duplicates.
[16]:
hashset = o3c.HashSet(capacity,
key_dtype=o3c.int64,
key_element_shape=(1,),
device=device)
keys = o3c.Tensor([1, 3, 5, 7, 5, 3, 1], dtype=o3c.int64,
device=device).reshape((-1, 1))
hashset.insert(keys)
keys = o3c.Tensor([5, 7, 9, 11], dtype=o3c.int64, device=device).reshape(
(-1, 1))
hashset.insert(keys)
def print_active_keys(hashset):
active_buf_indices = hashset.active_buf_indices().to(o3c.int64)
active_keys = hashset.key_tensor()[active_buf_indices]
print('active keys:\n', active_keys)
print_active_keys(hashset)
active keys:
[[5],
[9],
[1],
[3],
[11],
[7]]
Tensor[shape={6, 1}, stride={1, 1}, Int64, CPU:0, 0x5571284a6b00]