首页 文章

实现哈希表

提问于
浏览
4

几天前我开始阅读关于实现各种数据结构的内容,并开始讨论哈希表并陷入特定点 .

我对如何实现哈希表的理解:将密钥K传递给哈希函数H,哈希函数H返回哈希表K,HK . HK应该至少是一个uint32_t来解释碰撞,我们有一个大小为X的数组,该项存储在这个数组的索引HK ..但是,这不需要预先分配的长度为uint32_t的数组(或者H的返回值是什么)?假设我们不将数据本身存储在该数组中,而是将ptr存储到数据中,那么我们需要一个长度为uint32_t的ptr_t数组..这看起来很浪费,在64位上意味着内存使用量:2 ^ 32 * 8 = 34359738368字节或~32GB仅用于数据的ptrs数组,这显然不是它在现实生活中实际实现的方式 .

那么我错过了什么?

4 回答

  • 2

    这取决于实施 . 这有三种基本方法:

    1)使用小型哈希 . 因此,不使用32位散列,而是使用8位散列 .

    2)使用多级散列 . 因此,例如,12位散列可以确定条目进入哪个“桶”,但是仅当完整的32位散列匹配时才发生冲突 . 每个存储桶都存储在链表或类似结构中 . (也许是为了在其中搜索完整的32位哈希而优化的 . )

    3)使用稀疏阵列 . 这些是不需要为未填充的插槽实际存储空白空间的数据结构 . (在实践中,它可能是完全不同的东西,例如树,但它就像一个有效搜索的稀疏数组 . )

  • 1

    您应该构造您的哈希表,以便它可以扩展 . 有一些方法可以做到这一点 . 阅读this会有所帮助 . 在此示例中,使用链接列表 . 如果没有空值,您还需要扩展表 . 如果你不经常扩展它,你就是正常的 .

  • 4

    实际上,你有一个较小的,固定数量的桶的数组,它们使用链接(导致链表)或探测(最坏的例子:如果采用hash(x),尝试hash(x)1)对冲突 . 你把你的uint32和mod拿到桶大小,最简单的情况 .

    你可以定义一个加载因子 - 一旦你得到N%的数组已经满了,我们就会说,我们将把数组的大小加倍,然后将所有内容重新组合到新数组中 . 比方说,使用率在50%到75%之间 .

    好吧,你说不是那么贵吗?嗯,不是真的 . 假设您每次都将数组的大小加倍 . 因此,您添加N个项目,最后一个项目会触发副本 . N在O(1)处添加,然后添加一个O(N)副本 . 但等待 - O(N)/ N平均为O(1),因此,假设您的负载系数明智地选择,则平均加成的平均成本仍为O(1) .

  • 2

    哈希表的典型实现是链表列表 . 链表可以很容易地换成另一个数据结构,所以从现在开始我们称之为 Bucket .

    这个想法很简单:

    class HashTable {
    public:
    
    
    private:
      std::vector<Bucket*> _array;
    };
    

    然后,你取HK并减少它以使其适合数组,通常使用模数: HK % size(_array) ,它给出了要使用的桶的索引 .

相关问题