- 847 名前：デフォルトの名無しさん mailto:sage [2015/10/07(水) 09:44:01.58 ID:0iwSPjqO.net]
- Rubyでは、Hashの要素数が増えていくと、再編成される
バケット数は、2の累乗付近の素数を使う。
つまり、倍々に増やしていく
8+3, 16+3, 32+5, 64+3, 128+3, 256+27, 512+9...
1つのバケットには、平均して5つの要素を入れる(衝突)。
11*5=55, 19*5=95, 37*5=185...
つまり要素数が、56, 96, 186...個になると、
バケット数を増やして、再編成する
普段、1万個の要素を追加するのに、8msかかるが、
再編成するタイミングでは、20msかかる。
要素数が増えていけば、もっとかかるだろう
