`std :: vector`的快速哈希函数

Question

我实现了这个解决方案来获取哈希值vector<T>:

namespace std
{
    template<typename T>
    struct hash<vector<T>>
    {
        typedef vector<T> argument_type;
        typedef std::size_t result_type;
        result_type operator()(argument_type const& in) const
        {
            size_t size = in.size();
            size_t seed = 0;
            for (size_t i = 0; i < size; i++)
                //Combine the hash of the current vector with the hashes of the previous ones
                hash_combine(seed, in[i]);
            return seed;
        }
    };
}

//using boost::hash_combine
template <class T>
inline void hash_combine(std::size_t& seed, T const& v)
{
    seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

但是这个解决方案根本无法扩展:拥有vector<double>1000万个元素,它需要超过2.5秒(根据VS).

是否存在此场景的快速哈希函数？

请注意,从向量引用创建哈希值不是一个可行的解决方案,因为相关内容unordred_map将在不同的运行中使用,另外两个vector<double>具有相同的内容但不同的地址将被不同地映射(此应用程序的不期望的行为).

Answer 1

注: 由于 每个 的 意见,你会得到通过优化编译25-50x加速.首先,这样做.然后,如果它仍然太慢,请参阅下文.

我认为你无能为力.你必须触摸所有元素,并且组合函数的速度和它一样快.

一种选择可以是并行化散列函数.如果你有8个核心,你可以运行8个线程到每个散列1/8的向量,然后在最后组合8个结果值.对于非常大的向量,同步开销可能是值得的.

Answer 2

MSVC旧的hashmap使用的方法是不经常采样.

这意味着隔离的更改不会显示在您的哈希中,但您要避免的是读取和处理整个80 MB的数据以便对您的向量进行哈希处理.不读一些字是非常不可避免的.

你应该做的第二件事是不专注std::hash于所有vector的,这可能会使你的程序格式不正确(正如我不记得的缺陷解决方案所暗示的那样),至少是一个糟糕的计划(因为std肯定会允许自己添加向量的散列组合和散列).

当我编写自定义哈希时,我通常使用ADL(Koenig Lookup)来扩展它.

namespace my_utils {
  namespace hash_impl {
    namespace details {
      namespace adl {
        template<class T>
        std::size_t hash(T const& t) {
          return std::hash<T>{}(t);
        }
      }
      template<class T>
      std::size_t hasher(T const& t) {
        using adl::hash;
        return hash(t);
      }
    }
    struct hash_tag {};
    template<class T>
    std::size_t hash(hash_tag, T const& t) {
      return details::hasher(t);
    }
    template<class T>
    std::size_t hash_combine(hash_tag, std::size_t seed, T const& t) {
      seed ^= hash(t) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }
    template<class Container>
    std::size_t fash_hash_random_container(hash_tag, Container const& c ) {
      std::size_t size = c.size();
      std::size_t stride = 1 + size/10;
      std::size_t r = hash(hash_tag{}, size);
      for(std::size_t i = 0; i < size; i += stride) {
        r = hash_combine(hash_tag{}, r, c.data()[i])
      }
      return r;
    }
    // std specializations go here:
    template<class T, class A>
    std::size_t hash(hash_tag, std::vector<T,A> const& v) {
      return fash_hash_random_container(hash_tag{}, v);
    }
    template<class T, std::size_t N>
    std::size_t hash(hash_tag, std::array<T,N> const& a) {
      return fash_hash_random_container(hash_tag{}, a);
    }
    // etc
  }
  struct my_hasher {
    template<class T>
    std::size_t operator()(T const& t)const {
      return hash_impl::hash(hash_impl::hash_tag{}, t);
    }
  };
}

现在my_hasher是一个普遍的哈希.它使用在my_utils::hash_impl(用于std类型)中声明的散列,或者hash用于散列给定类型的自由函数来散列事物.如果做不到,它会尝试使用std::hash<T>.如果失败,则会出现编译时错误.

hash在您想要散列的类型的命名空间中编写一个自由函数往往不如不得不开始std并专注std::hash于我的经验而烦人.

它以递归方式理解向量和数组.做元组和对需要更多的工作.

它对所述载体和阵列进行约10次采样.

(注意:hash_tag这既是一个笑话,也是一种强制ADL并防止必须hash在hash_impl命名空间中转发声明特殊化的方法,因为该要求很糟糕.)

抽样的价格是你可能会遇到更多的冲突.

如果您拥有大量数据,另一种方法是将它们哈希一次,并跟踪它们何时被修改.要执行此方法,请为您的类型使用copy-on-write monad接口,以跟踪散列是否是最新的.现在一个矢量被哈希一次; 如果你修改它,哈希就会被丢弃.

可以进一步使用随机访问哈希(可以很容易地预测当您以哈希方式编辑给定值时会发生什么),并调解对向量的所有访问.这很棘手.

你也可以对哈希进行多线程处理,但我猜你的代码可能是内存带宽限制的,多线程在那里也没什么用处.值得尝试.

您可以使用比平面向量(类似于树)更高级的结构,其中值的更改以类似哈希的方式冒泡到根哈希值.这将为所有元素访问添加lg(n)开销.同样,您必须将原始数据包装在控件中,以使散列保持最新(或者,跟踪哪些范围是脏的并且需要更新).

最后,因为您一次使用1000万个元素,请考虑转移到强大的大型存储解决方案,如数据库或您拥有的内容.在地图中使用80兆字节的密钥对我来说似乎很奇怪.