要素の挿入と削除による性能低下を抑えた高速ハッシュテーブルアルゴリズムの提案

A proposal and implementation of a fast hash table algorithm which suppresses decrease in search performance that is caused by repeating addition and deletion of elements (C/C++) August 2015 - January 2017

Abstract

  Although the hash table of the Open Addressing method shows high search performance, the search performance is decreased by repeating addition and deletion of elements. And the hash table of the Closed Addressing method doesn't change search performance, although search performance is low because of its pointer connections make cache miss. Therefore, I developed an algorithm that embeds a doubly linked list in the Open Addressing hash table. When a load factor is 50%, this algorithm is 2.18 times for insertion, 1.23 to 1.44 times for search and 1.80 times for deletion faster than std::unordered_map in Microsoft Visual C++ 2015 respectively. Moreover, by adopting the doubly linked list, Unlike the conventional Open Addressing type hash table, decreases of search performance due to addition and deletion of elements is suppressed under 6%. The suppression of decrease in search performance is due to the ability to insert elements in the place where is little need to seek by adopting the doubly linked list. (Added on March 10, 2017)

  従来の Open Addressing 方式のハッシュテーブルは， 検索性能は高いものの，要素の追加と削除を繰り返すことで， 検索性能が低下することが知られています． また， 要素の追加と削除により，検索性能が変化しない， Closed Addressing 方式のハッシュテーブルは， 検索性能が低いことが知られています． この投稿では，高速な Open Addressing 方式のハッシュテーブルに， 双方向リスト構造 (鎖型構造) を埋め込むアルゴリズムを開発し， key: UINT64，value: UINT64 のペアについて， Microsoft Visual C++ 2015 に実装されている std::unorderd_map ※1 と比較して， 挿入 2.18 倍，検索 1.23~1.44 倍，削除 1.80 倍の性能を達成しました． また， 双方向リスト構造の採用により， 従来の Open Addressing 型のハッシュテーブルと異なり， 要素の追加と削除による検索性能の低下を 6% 以内に抑えました ※2．