动态哈希->类标签

Question

我有：

const unsigned int hash_1 = 0xaf019b0c;
const unsigned int hash_2 = 0xf864e55c;  
const unsigned int hash_3 = 0xfaea8ed5;

哈希值来自自动生成的标头。这些哈希值间接与标签 1、2、3 关联。标签通过简单的编译时生成的 id 与类关联。这样我就可以 GetTag() 并获取 Class1 的 int 标签。

我的目标是简化哈希->标签关联。最好是编译时生成且访问时间为 O(1)。在这种情况下，内存不是问题。我无法使用任何第三方软件。

我尝试了以下方法：

template<uint32 t>  size_t GetTagByHash() { return 0; }

使用特定的实现，例如：

template<> size_t GetTagByHash<hash_1>() { return GetTag<Class1>(); }

但是这种实现很难使用，因为如果我有一个局部变量 uint32 my_hash; ，编译器无法确定它在编译中具有什么值-time，则编译器无法解析要调用的 GetTagByHash() 的正确实现。

Answer 1

据我了解，您的问题是如何使用运行时值和编译时值进行查找。

你确实有两个问题。首先，您想使用什么算法来进行查找，其次，您如何告诉 C++ 来实现它？

使用哪种算法是一个不太明显的问题；您有一个有效随机数的列表，并且您想要在该列表中查找某些内容并返回关联的标签。也许您想要某种哈希表，但首先，我将展示一些更简单的示例 - 对于少量哈希可能更好：一个简单的 O(N) 查找，用伪代码表示：

if i = N return tag_N
else if i = N-1 ...
...
else if i = 1 return tag_1
else return tag_0

现在，您如何判断C++ 能做到这一点吗？您必须创建所有哈希标签的列表以及执行此操作的说明。这是一个简单的方法：

template<int i> struct lookup
{
  int result(int j) { return 0; }
};

const unsigned int hash_1 = 0xaf019b0c;
template<> struct lookup<1>
{
  int result(int j)
  {
    if (j == hash_1)
      return GetTag<Class1>();
    return lookup<0>::result(j);
  }
};

const unsigned int hash_2 = 0xf864e55c;
template<> struct lookup<2>
{
  int result(int j)
  {
    if (j == hash_2)
      return GetTag<Class2>();
    return lookup<1>::result(j);
  }
};

等等。然后，最后，你可以

int hash_lookup(int j)
{
  return lookup<last_hash_number>::result(j);
}

写出所有这些相同的定义，虽然很痛苦，所以最好让 C++ 来做这件事——而且，要做到这一点，你需要以这样的方式定义哈希值：被迭代。让我们这样做：

template<int> struct hash_tag {
  static const int value = 0;
  typedef type void;
};

#define SET_HASH(I, VALUE, CLASS)   \
template<> struct hash_tag<(I)>     \
{                                   \
  static const int value = (VALUE); \
  typedef type (CLASS);             \
}

SET_HASH(1, 0xaf019b0c, Class1);
SET_HASH(2, 0xf864e55c, Class2);
SET_HASH(3, 0xfaea8ed5, Class3);

// Define a general recursive lookup struct.
template<int i> struct lookup
{
  int result(int j)
  {
    if (j == hash_tag<i>::value)
      return GetTag<hash_tag<i>::type>;
    return lookup<i-1>::result(j);
  }
};

// Make sure the recursion terminates.
template<> struct lookup<0>
{
  int result(int) { return 0; }
};

然后，您像以前一样使用它。

现在，让我们回到第一个问题——您实际上想使用什么算法来进行查找？这种迭代 O(N) 查找的优点是它易于编程，并且不需要在运行时对任何数据结构进行任何初始化——您只需调用它即可。然而，正如所指出的，它的复杂度是 O(N)。另一种选择是使用 std::map 对象；您可以使用类似的递归定义在运行时初始化它，然后使用它。这可能看起来像这样：

// Make a typedef to save some typing.
typedef std::map<unsigned int, size_t> Map_type;
typedef std::pair<unsigned int, size_t> Map_value;

// Define a recursion to add hashes to the map.
template<int i> struct add_hash
{
  void add(Map_type& hashmap)
  {
    hashmap.insert(
      Map_value(hash_tag<i>::value, 
                GetTag<hash_tag<i>::type>));
    add_hash<i-1>::add(hashmap);
  }
};

// Make sure the recursion terminates.
template<> struct lookup<0>
{
  void add(Map_type&) {}
};

// Now, create a class to initialize the std::map and do lookup.
class Hash_lookup
{
  Hash_lookup() { add_hash<last_hash_number>(map_); }
  int result(unsigned int j) { return map_[j]; }
private:
  Map_type map_;
}

就个人而言，我可能会将其与您的 GetTagByHash<> 想法结合起来，并为 Hash_loop 提供我所描述的“运行时计算结果”函数，以及“编译时计算结果”函数采用模板参数而不是函数参数。但是，一般来说，这是进行运行时查找的基本思想 - 将要查找的值放入一组模板化类中，您可以在编译时递归地迭代这些类，然后使用该递归迭代来定义查找函数或初始化可用于执行查找的运行时结构。