hashtableのn * 2 + 1の意義

くまぎ @kumagi

【教えて】Javaのハッシュテーブルについて「新しいテーブルサイズは (古いサイズ * 2 + 1) になる。これは検索効率を低下させないための工夫である」という記述を見かけましたが、(古いサイズ * 2)ではなくそこに1足す事で具体的にどんな利益があるんですか？

mzp @mzp

@kumagi 古いサイズが0になるときとか？ 今思いついただけですけど

くまぎ @kumagi

@mzp サイズ0のハッシュテーブルは作らないと思いますし、2のべき乗以外のサイズのテーブルになると&じゃなくて%で目的に至る必要があるので計算負荷がかかります。悪いこと尽くめだと思うのですが。

tomo🐧@learning @cocoatomo

@kumagi @finalfusion サイズが 0 だったときのための安全策です.

くまぎ @kumagi

@cocoatomo @finalfusion JavaのHashtableは初期サイズ0なのでしょうか。

tomo🐧@learning @cocoatomo

@kumagi @finalfusion いいえ, 違います. 初期容量は 11 らしいです. しかし, 初期容量を指定できるコンストラクタがあるのでサイズ 0 のものを作ることは可能です. http://t.co/W8P5D9x

くまぎ @kumagi

@cocoatomo @finalfusion サイズ0のテーブルに要素つっこんだら例外投げるか、強制的にサイズ1にするかぐらいしてもいいんじゃないかと思います。初期容量11は真剣に謎ですね…。

tomo🐧@learning @cocoatomo

@kumagi @finalfusion (oldSize * 2 + 1) という式で, サイズが 0 だったら 1 にしてますが. そういうことではなく? 初期サイズは謎です. ちなみに ArrayList の初期サイズは 10 です. 謎です.

くまぎ @kumagi

@cocoatomo @finalfusion サイズが0の時だけifで切って1にする、もしくはテーブルサイズが0なんて例外中の例外は特別扱いしていいんじゃないか、ってことです。

tomo🐧@learning @cocoatomo

@kumagi @finalfusion う〜ん, 理由は分からないですねぇ. JVM 上では if のコストってそんなに高いんでしょうかねぇ……

_sss_ @_sss_

@kumagi 少しだけ java.uti.Hashtable のソースを見てみたのですが "newCapacity the new capacity, MUST be a power of two" と書いてあるくらいなので、その +1 というのが間違ってるのかな、と。

くまぎ @kumagi

@_sss_ ですよね。わざわざ足す意義が見つからないです。

oza @oza_x86

@kumagi ほえー，ちなみにソースは？

くまぎ @kumagi

@oza_x86 http://www.nurs.or.jp/~sug/soft/super/hash.htm の一番下です。dankogaiさんのブログでは「ここでは新しいハッシュテーブルの大きさは2倍+1要素としています。多くのハッシュテーブルの実装ではそうなっています」と。

くまぎ @kumagi

@oza_x86 そちらのブログは http://blog.livedoor.jp/dankogai/archives/50961440.html ここです。+1謎い…。

アノヒト（スマホ大破：連絡先ゼロ） @mindstack

@kumagi 初期サイズ0が許される。でも、デフォルトサイズも11というキリの悪い数字にされてるね。デフォルト負荷率75％も、どうしてそうなってるのかは知らない。

くまぎ @kumagi

@mindstack 11という数字が謎過ぎる。 load factor 75%はopen addressingを意識してでしょうか… http://en.wikipedia.org/wiki/File:Hash_table_average_insertion_time.png

アノヒト（スマホ大破：連絡先ゼロ） @mindstack

@kumagi loadfactorに100%も指定できるようだし、そこら辺の処理用に+1配列の冗長性使ってるんじゃないかと推測。

くまぎ @kumagi

@mindstack なるほど、open addressingに対して100%使用は無限ループになりかねませんし。でもそれを「検索効率を低下させないための工夫」と呼ぶのかは疑わしいです。

アノヒト（スマホ大破：連絡先ゼロ） @mindstack

@kumagi なんか見っけてきたよ。http://bit.ly/eKQwUb

くまぎ @kumagi

@mindstack ﾜｫ!

くまぎ @kumagi

そうか、ハッシュ関数が偏ったときにも性能がガタ落ちしないための工夫か。table[0]の物が3箇所にバランスされる。

勇士Ｑ @ucq

ハッシュテーブルのサイズの件はは以前どっかでみたような

勇士Ｑ @ucq

+1するのはなるべく素数にしたいから？ Rubyのハッシュテーブルのサイズは素数になるように実装されてるっけ。

Tsukasa #01 @a4lg

@ucq たしかにメルセンヌ数 (メルセンヌ素数ではない!) を 2n+1 すれば次のメルセンス数になるねぇ。それが素数になるかは別として。