向量化的散列表

摘要

本文描述了用于使用非常高效的增长和插入技术的向量化的散列表的技术。单探测散列表是经由向量化的指令增长的，这些指令将散列表的每个桶拆分为经扩展的散列表的相应上桶和下桶。另外，使用空槽指示符值(例如，“0”)指示空槽，并且所有空槽都紧跟在桶中所有被占用的槽的右侧。向量化的比较指令确定值是否已经在桶中。如果没有，那么向量化的比较指令也被用于基于桶是否包含空槽指示符值来确定桶是否有空槽。为了将值插入到桶中，使用向量化的指令将桶中的值向右移动一个槽并将新值插入到最左边的槽中。