# HashtableLookup — MindSpore Signal+ 使用手册 alpha 文档

# HashtableLookup

根据输入的键值在已排序的键数组中执行二分查找，返回对应的字符串值以及查找命中标记。

虽然名为 HashtableLookup，但实际使用二分查找（bsearch）算法，而非哈希表。要求 keys_tensor 必须已按升序排序。

\[\begin{split}\forall i \in [0, input\_size), \quad \begin{cases} \text{if } \exists j \in [0, keys\_size) \text{ s.t. } keys[j] = input[i], & \begin{cases} output[i] \leftarrow values[j] \\ hits[i] \leftarrow 1 \end{cases} \\[10pt] \text{else}, & \begin{cases} output[i] \leftarrow \text{空字符串} \\ hits[i] \leftarrow 0 \end{cases} \end{cases}\end{split}\]

输入：

  - input_tensor - 要查找的键数组地址（int32类型）。

  - keys_tensor - 已排序的键数组地址（int32类型，必须按升序排序）。

  - values_tensor - 值数组地址（字符串tensor，与keys_tensor一一对应）。

  - input_size - 输入键数组的元素个数。

  - keys_size - 键数组的元素个数（等于values_tensor中字符串的个数）。

  - core_mask（可选） - 核掩码（仅适用于共享存储版本）。

输出：

  - output_tensor - 查找结果输出地址（字符串tensor，与input_tensor长度相同）。

  - hits_tensor - 命中标记输出地址（uint8类型，1表示找到，0表示未找到）。

支持平台：

  `FT78NE` `MT7004`

备注

- FT78NE 支持int32键类型，字符串值类型

- MT7004 支持int32键类型，字符串值类型

- keys_tensor 必须已按升序排序，否则查找结果不正确

- 使用二分查找算法，时间复杂度为 O(log n)

- 如果查找失败，output_tensor 对应位置为空字符串，hits_tensor 对应位置为0

共享存储版本：

void i32_hashtablelookup_s(int *input_tensor, int *keys_tensor, void *values_tensor, void *output_tensor, uint8_t *hits_tensor, int input_size, int keys_size, int core_mask)

  C调用示例：

       1//FT78NE示例
       2#include <stdio.h>
       3#include <hashtablelookup.h>
       4
       5int main(int argc, char* argv[]) {
       6    int *input_tensor = (int *)0xA0000000;   //input在DDR空间
       7    int *keys_tensor = (int *)0xB0000000;    //已排序的键数组
       8    void *values_tensor = (void *)0xC0000000;        //字符串值数组
       9    void *output_tensor = (void *)0xD0000000;        //输出字符串数组
      10    uint8_t *hits_tensor = (uint8_t *)0xE0000000;    //命中标记数组
      11    int input_size = 100;                            //输入键的个数
      12    int keys_size = 50;                              //键值对的个数
      13    int core_mask = 0xff;
      14
      15    i32_hashtablelookup_s(input_tensor, keys_tensor, values_tensor,
      16                          output_tensor, hits_tensor, input_size,
      17                          keys_size, core_mask);
      18    return 0;
      19}

私有存储版本：

void i32_hashtablelookup_p(int *input_tensor, int *keys_tensor, void *values_tensor, void *output_tensor, uint8_t *hits_tensor, int input_size, int keys_size)

  C调用示例：

       1//FT78NE示例
       2#include <stdio.h>
       3#include <hashtablelookup.h>
       4
       5int main(int argc, char* argv[]) {
       6    int *input_tensor = (int *)0x10810000;   //input在L2空间
       7    int *keys_tensor = (int *)0x10820000;    //已排序的键数组
       8    void *values_tensor = (void *)0x10830000;        //字符串值数组
       9    void *output_tensor = (void *)0x10840000;        //输出字符串数组
      10    uint8_t *hits_tensor = (uint8_t *)0x10850000;    //命中标记数组
      11    int input_size = 100;                            //输入键的个数
      12    int keys_size = 50;                              //键值对的个数
      13
      14    i32_hashtablelookup_p(input_tensor, keys_tensor, values_tensor,
      15                          output_tensor, hits_tensor, input_size,
      16                          keys_size);
      17    return 0;
      18}