ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)

btk @btk15049

ところで64bitのハッシュキラー対策の記事の修正をまだしていませんね

btk @btk15049

バケツ数の倍数で殴る攻撃 ->rehashでバケツの数を乱数に変えて対処 キーが64bitのとき下位32bitが同じ数で殴る攻撃 ->上位と下位をxorとシフトでうまく組み合わせて32bit生成or32bit以内の乱数でmod ->安全性高めるため異なる32bit乱数でxor

btk @btk15049

modとるのは遅いからあんまりやりたくないんだけどうーむ

btk @btk15049

上位32bitだけxorshift32にかけてそれと下位32bitのxor使うとか良さそう

btk @btk15049

@btk15049 これはダメで、f=xorshift32の逆関数とするとf(x)<<32 +xを与えられ続けると永遠にハッシュ値が0になって死ぬ

btk @btk15049

上位64bitだけxorshift64にかけたらいい気がしてきたんだけど実質40bitぐらいしか使わないことになりそうでダメそう

btk @btk15049

5回ぐらいぐりぐりしてもいいけど速度的な問題は知らん

いしかど @ISIKADO

ふと前話題になってたunorderd_map殺しの話がきになって、まとめさがしてる

agw @masashinakata

@isikado つ togetter.com/li/1084273

agw @masashinakata

(合ってるかしら)