検索と挿入がともにO(1)であるようなHashを作るにはコツがいる

このところ立て続けに表記の事実を理解していない俺実装のHash(しかもCで!)を見かけたので、おそらく知られていないんだと思う。以降、同じ轍を踏む人が少なくなればと思い、啓蒙のために公開しておく。 先に言っておくがおまえらはHashを再発明するんじゃねよボケが。おとなしくありもののライブラリ使えよ。つうかHashのある言語使えよ。Cとかマゾかよ。 言葉と前提とりあえずHashが何であるかとか、どういう作りになっているかとか、そういうことは既知とする。リストの配列ってことね。←これで何言ってるか分からないおまえらにはこの文章はちょっとはやい。先にデータ構造の教科書を読むことをおすすめ。以下ではHashに登録されるキーとデータのペアのことをentryと呼び、リストの配列と言ったときのリストのほうをbin、配列のほうをbucketと呼ぶ。つまり、 class Hash { typedef lis

[kabiy]

“卜部昌平のあまりreblogしないtumblr - 検索と挿入がともにO(1)であるようなHashを作るにはコツがいる”

[mooz]

ハッシュの実装. チェイン法. 検索を O(1) で行いたければ, 一つのハッシュ値に繋がれたリストが長くならないよう, ハッシュ表のサイズを動的に変更する必要が出てくる. => 適切なタイミングでリハッシュする.

[tagomoris]

ブクマしてなかった／今後万が一Hashを作りたくなったときのために。ないだろうけどｗ

[sigh1175]

ブクマしてなかった／今後万が一Hashを作りたくなったときのために。ないだろうけどｗ

[mamoruk]

ちゃんと書いてくれる人がいるというのは大事ですね

[pi8027]

マゾです。ごめんなさい。http://stricter.org/software/libdatastruct/

[rin51]

>つうかHashのある言語使えよ。Cとかマゾかよ。

[joan9]

> つまり、rehashしないhashはhashじゃねえという事実を知っておかないと、予想外の振る舞いに戸惑うことになる。どうもhashの振る舞いが定数時間じゃなくてソース読んでみた俺がびっくり仰天とかいう話になる。おまえらも

[gamella]

shyouhei: このところ立て続けに表記の事実を理解していない俺実装のHash(しかもCで!)を見かけたので、おそらく知られていないんだと思う。以降、同じ轍を踏む人が少なくなればと思い、啓蒙のために公開しておく。 先に言