Hash map（哈希表）
哈希表（hash map）是一种将键（key）映射到值（value）的数据结构，其插入、查找和删除的摊还时间复杂度（amortized time）均为 O(1)。该映射是无序的。
Open3D 支持在 CPU 和 GPU 上进行并行哈希运算，键和值都以 Tensor 的形式组织，我们以一批键和/或值作为输入。
- 键（Keys）：Open3D 的哈希表支持多维键。由于精度问题，不建议将浮点数作为键。默认情况下，我们支持最高 6 维的整数坐标。对于更高维度，你可以修改宏定义并从源码编译，对应的代码片段位于以下文件中：
#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）：Open3D 的哈希表支持任意维度和数据类型的值。
- 设备（Devices）：同时支持 CPU 和 CUDA。CPU 哈希表基于 TBB 实现，而 CUDA 哈希表基于 stdgpu 实现。
import open3d.core as o3cimport numpy as np
capacity = 10device = o3c.Device('cpu:0')一个简单的示例
Section titled “一个简单的示例”我们首先创建一个从整数到整数的简单哈希表。
我们会指定一个初始估计容量（capacity）。当发生插入时，该容量会自动调整。然后我们指定键和值的元素形状（element shape），对应于每个独立元素的形状。
hashmap = o3c.HashMap(capacity, key_dtype=o3c.int64, key_element_shape=(1,), value_dtype=o3c.int64, value_element_shape=(1,), device=device)接下来我们展示如何插入一批（key, value）键值对。你需要准备两个 tensor：
keys 张量包含所有的键。
- keys 张量必须与哈希表位于同一设备上。
- keys 张量的形状为
key_element_shape并在其前面加上N。
例如：
- 如果
key_element_shape == ()，则keys.shape == (N,)； - 如果
key_element_shape == (3,)，则keys.shape == (N, 3)； - 如果
key_element_shape == (8, 8, 8)，则keys.shape == (N, 8, 8, 8)。
vals 张量包含所有的值。
- vals 张量必须与哈希表位于同一设备上。
- vals 张量的形状为
value_element_shape并在其前面加上N。
例如：
- 如果
value_element_shape == ()，则vals.shape == (N,)； - 如果
value_element_shape == (3,)，则vals.shape == (N, 3)； - 如果
value_element_shape == (8, 8, 8)，则vals.shape == (N, 8, 8, 8)。
# Prepare a batch of 7 key/values, each a int64 elementkeys = 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)这里，masks 表示某个（key, value）键值对是否成功插入。值为 True 的掩码表示插入成功，False 表示插入被跳过。
插入失败只会在出现重复键时发生。
如果存在重复键，可以保证只有其中一个重复键及其对应的值会被插入。也就是说，对于一组重复键，有且仅有一个会得到 True 掩码。
由于插入是并行执行的，无法保证哪个重复键会被插入。也就是说，对于一组重复键，我们无法预先知道哪个键会得到 True 掩码。
使用高级索引，我们可以获取哪些键被成功插入：
print('masks: \n', masks)print('inserted keys: \n', keys[masks])masks: [True True True True True False False]Tensor[shape={7}, Bool, CPU:0, 0x5571293a85a0]inserted keys: [[100], [200], [400], [800], [300]]Tensor[shape={5, 1}, 1}, Int64, CPU:0, 0x557128c4f760]接下来，我们看看 buf_indices 的用法。在我们的哈希表中，键和值存储在连续的缓冲区张量（buffer tensor）中，可以通过索引方便地访问。我们没有返回对向量化编程不太友好的迭代器（iterator），而是返回这样的缓冲区索引。
由于并发的原因，这些索引不一定与输入索引相同。此外，由于底层实现的原因，索引默认以 int32 存储。使用高级索引时需要先转换为 int64。
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}, Int64, CPU:0, 0x5571293ae6d0]inserted keys: [[100], [200], [400], [800], [300]]Tensor[shape={5, 1}, 1}, Int64, CPU:0, 0x5571284a73b0]inserted values: [[1], [2], [4], [8], [3]]Tensor[shape={5, 1}, 1}, Int64, CPU:0, 0x5571284a6f50]查询（query）操作遵循类似的约定。需要注意的是，由于该操作是只读的，允许重复键，并且会被正确返回。
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}, 1}, Int64, CPU:0, 0x5571293a3ae0]found valid values: [[1], [3], [2], [1]]Tensor[shape={4, 1}, 1}, Int64, CPU:0, 0x5571293ae6d0]哈希表中的活动条目
Section titled “哈希表中的活动条目”有时我们对所有活动条目（active entries）感兴趣。可以通过以下方式实现：
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)同样，由于并发的原因，顺序无法保证，但键值之间的对应关系当然会保持不变。
我们可以类似地删除（erase）键。其行为与插入类似：
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}, Bool, CPU:0, 0x5571292dd430]erased keys: [[100]]Tensor[shape={1, 1}, 1}, Int64, CPU:0, 0x5571284a6a10]现在我们可以看到活动条目已经发生了变化：
print_active_entries(hashmap)all active keys: [[300], [200], [400], [800]]Tensor[shape={4, 1}, 1}, Int64, CPU:0, 0x5571293a9ad0]all active values: [[3], [2], [4], [8]]Tensor[shape={4, 1}, 1}, Int64, CPU:0, 0x5571293b1d10]在某些情况下，我们知道某个键已被占用，但不知道关联的值——我们更希望之后就地计算并修改它。这可以通过一系列操作来实现：
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 broadcastingbuf_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}, 1}, Int64, CPU:0, 0x5571284a6b00]all active values: [[3], [10], [2], [4], [0], [8]]Tensor[shape={6, 1}, 1}, Int64, CPU:0, 0x5571284a6a60]重哈希与预留
Section titled “重哈希与预留”当多次插入后超出初始容量时，会自动触发重哈希（rehashing），此时哈希表的容量会翻倍。重哈希会改变已插入键值对的位置（即缓冲区索引），因此下游应用需要更新缓冲区索引。
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: 6capacity: 10size: 9capacity: 10all active keys: [[300], [1500], [700], [1000], [200], [400], [1200], [0], [800]]Tensor[shape={9, 1}, 1}, Int64, CPU:0, 0x5571293b4d80]all active values: [[3], [-1], [7], [10], [2], [4], [12], [0], [8]]Tensor[shape={9, 1}, 1}, Int64, CPU:0, 0x5571293b64d0]size: 12capacity: 20all active keys: [[1700], [300], [1500], [700], [1000], [200], [1800], [400], [1200], [1600], [0], [800]]Tensor[shape={12, 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}, 1}, Int64, CPU:0, 0x5571293b8250]重哈希比较耗时，因为它需要扩大哈希表容量、收集所有活动条目，并将它们重新插入哈希表。如果我们事先知道所需容量，就可以预先分配一块内存，从而避免重哈希：
hashmap.reserve(100)print('size:', hashmap.size())print('capacity:', hashmap.capacity())size: 12capacity: 100在实际应用中，我们希望将坐标映射到复杂的数据结构，例如将一个体素（voxel）的位置映射到它的颜色和权重。这可以通过多值哈希表（multi-valued hash map）来实现。
它不是多重映射（multimap），不允许重复键。可以通过以下方式构造一个多值哈希表：
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))([1 0 2] Tensor[shape={3}, Int32, CPU:0, 0x5571293b83f0], [True True True] Tensor[shape={3}, Bool, CPU:0, 0x5571293bab60])随后，我们可以用略有不同的流程进行查询并按索引访问：
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}, 1}, Int32, CPU:0, 0x5571293c47c0]found colors: [[0 255 0]]Tensor[shape={1, 3}, 1}, UInt8, CPU:0, 0x5571293c47a0]found weights: [[0.9]]Tensor[shape={1, 1}, 1}, Float32, CPU:0, 0x5571284a6540]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}, 1}, Int32, CPU:0, 0x5571293b1d40]active value 0: [[0 255 0], [255 0 0], [255 255 0]]Tensor[shape={3, 3}, 1}, UInt8, CPU:0, 0x5571293c5610]active value 1: [[0.9], [0.3], [0.1]]Tensor[shape={3, 1}, 1}, Float32, CPU:0, 0x5571293c56d0]哈希集合（hash set）是哈希表的简化形式，我们不关心值。它保留了哈希表的大部分操作，可用于去除重复项。
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}, 1}, Int64, CPU:0, 0x5571284a6b00]