(訳注:2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら(どのプログラミング言語かに関わらず)、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の
![高速なハッシュテーブルを設計する | POSTD](https://cdn-ak-scissors.b.st-hatena.com/image/square/a648c946e6eeb30b05d538d7c6ad3daa5068a53a/height=288;version=1;width=512/https%3A%2F%2Fpostd.cc%2Fwp%2Fwp-content%2Fuploads%2F2016%2F01%2Fhome-office-336377_1920-500x333.jpg)