Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found

2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構

[nyomonyomo]

記事の内容自体も興味深かったけどソレよりも弾氏にまどマギが与えた影響の大きさの方が印象深い記事だった

[udzura]

真面目だし有益な内容だとおもうので、まどマギネタ止めればいいと思うんですけれど

[s-tomo]

円環の理に導かれすぎて読めない

[K-Ono]

放送1年記念エントリとしてブクマする。

[todesking]

あっ有益なブログだ

[youhey]

なるほど。でも、そんな長いキーを使うケースがない。

[boxphere]

キー長による性能劣化

[katryo]

ためになった

[arakik10]

ハッシュテーブルという連想配列の実装方法はキーが長いと探索に時間がかかるので、トライ木(Trie)による実装も考えるべきだという話、でいいのかな？

[heiwaboke]

後で実装してみる

[naga_sawa]

キーが長いとハッシュ表はパフォーマンス出ないからtrie木系を使えばいいんじゃない。というお話/適所適材

[side_tana]

読んだ

[vvakame]

trie木というのがあるらし

[mikage014]

「予想どおり、キーが長くなるにつれ性能はどんどん劣化していきます。一行の長さとしてよく出てきそうな二桁台の後半は、単語の長さとして適当な一桁台-二桁前半の半分まで落ちています。」

[new3]

　Tie

[warriorking]

404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン?

[John_Kawanishi]

より早い連想配列のアルゴリズムだかデーター構造なんかがあるんだぁ

[tmatsuu]

適材適所だけど、こういう選択肢があることを知ってることは大事。

[ang65]

状況しだいでどのデータ構造が最適化は変わってくるので使う時気をつけていかないと・・・・　[データ構造][algorithm][アルゴリズム][perl]

[atsukanrock]

キーが長大だとハッシュテーブルも遅くなっちゃうYO、という話。うんうん、たしかに以前から気になってたそこ。そこでTrieを使うあたり、さすが dankogai さん。しかしハッシュ＜Trieになるのは2048 bytesあたりというw

[twodollarz]

連想配列の実装の一種がハッシュテーブルによるというものであって、連想配列＝ハッシュと考えてはいけない。

[al001]

> 今回のhashdosの教訓ではありますが、Perlはもう9年も前にVersion 5.8.1でハッシュシードの乱択化により解決していました。

[masato-ka]

そのデータ構造は、君の魂を差し出すに足るものかい?

[takfjt]

死ぬ思い出パトリシアトライを書いたのももう１０年前か・・・

[zetamatta]

2048bytes 以上のキーでは、ネイティブの Hash より、Tie::Judy の方が高速

[monjudoh]

トライ木について

[escape_artist]

まどマギはもういいよ…

[nanakoso]

Try木

[Nyoho]

ちょうどハッシュではない連想配列の実装ってどんなのがあるのか知りたいと思っていた矢先にこの記事だ。dankogai先生は超能力者なのか

[ume-y]

ハッシュはキーが長くなるとO(k)になる。トライ木が有望とのこと。/ キー長でなくて共通接頭辞長でした。