HashGraph—Scalable Hash Tables Using a Sparse Graph Data Structure
HashGraph—Scalable Hash Tables Using a Sparse Graph Data Structure
复制标题
HashGraph—使用稀疏图数据结构的可扩展哈希表
DOI：
10.1145/3460872
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Oded Green
中科院分区：
文献类型：
--
作者：
Oded Green
在本文中，我们介绍HashGraph，这是一种用于构建哈希表的新的可伸缩方法，它使用来自稀疏图表示的概念-因此，名称为HashGraph。HashGraph引入了一种新的方法来处理散列冲突，该方法不使用“开放寻址”或“分离链接”，但它具有这两种方法的优点。HashGraph目前适用于静态输入。动态图形数据结构的最新进展表明，HashGraph也可以扩展到动态输入。我们证明了HashGraph可以在不损失性能的情况下处理每个条目的大量哈希值。最后，我们给出了一种新的值查找查询算法。我们将HashGraph与几种最先进的实现进行了实验比较，发现当输入是唯一的时，它的性能平均为它们的2倍，当输入包含重复项时，它的性能高达40倍。本文中的HashGraph实现是针对NVIDIA图形处理器的。HashGraph可以在NVIDIA GV100 GPU上以每秒25亿个密钥的速度构建哈希表，并且可以几乎相同的速度进行查询。
In this article, we introduce HashGraph, a new scalable approach for building hash tables that uses concepts taken from sparse graph representations—hence, the name HashGraph. HashGraph introduces a new way to deal with hash-collisions that does not use “open-addressing” or “separate-chaining,” yet it has the benefits of both these approaches. HashGraph currently works for static inputs. Recent progress with dynamic graph data structures suggests that HashGraph might be extendable to dynamic inputs as well. We show that HashGraph can deal with a large number of hash values per entry without loss of performance. Last, we show a new querying algorithm for value lookups. We experimentally compare HashGraph to several state-of-the-art implementations and find that it outperforms them on average 2× when the inputs are unique and by as much as 40× when the input contains duplicates. The implementation of HashGraph in this article is for NVIDIA GPUs. HashGraph can build a hash table at a rate of 2.5 billion keys per second on a NVIDIA GV100 GPU and can query at nearly the same rate.