Pythonのハッシュ衝突攻撃の考察3: setの理解と効率的な衝突の実践(anti-setの実践) - Qiita振り返り1: C++のハッシュ法 C++のunordered_set/unordered_mapでは現在のデータ構造のサイズを基にしたlinked-listを指すテーブルを持ちます。まず、入力値(key)のハッシュを得て、modを取りindexを定めます。各indexに対応するlinked-listの各要素はkeyを持ち、存在を管理・値を格納します。これがハッシュ法です。 入力がランダムの場合、indexはうまくばらけて各linked-listは浅い状態になります。テーブルのサイズを動的に変化させることで、平均計算量$O(1)$でのアクセスが可能です。しかし、毎回同じindexとなるような値(key)をN個入力すると特定のlinked-listの深さをNとすることが可能です。C++20であれば85229ul * iという値を$2e5$個入るようにすればanti-unordered_set/
オイラーツアーした木に対するクエリ - Qiita
