nati_uenoのブックマーク / 2018年8月29日

GolangでBloomFilterを実装してみた - 逆さまにした

2018/02/17追記 Goらしくレシーバを使うようリファクタリングしました。実装が少し変わっていますが、考え方自体は本記事から変わりありません。リファクタリング後の実装は以下のGithubのとおりです。 github.com 前回調べたBloomFilterをGolangで実装してみました。要素を蓄えるBloomFilterの用意 BloomFilterをサイズm[bit]のboolean配列として用意します。実装中ではmをsizeという変数にしているので、適宜読み替えてください。今回はBloomFilter型を用意します。 gistf2f5c87d2ca403d6f1b3deacb4d52ab4 使用するハッシュ関数要素の追加および要素の有無を検証するときに、k個のハッシュ関数を用意する必要があります。今回はハッシュ関数としてMD5を用いることにします。 gist4c6

nati_ueno 2018/08/29

リンク

Try Golang! 効率的なHashmapを実装するためにGoがしたこと

先日、Go Conference 2018 Springに参加してきました。キーノートはDave Cheney氏による、GoのHashmapはどのようにして効率的な実装を達成したのか、について（本記事のサブタイトルに、キーノートのタイトルを借用させていただきました）。復習も兼ねてHashmapの実装を覗いてみたので、簡単にまとめようと思います。なお、英語のセッションだったので、正しく理解できていない部分があるかもしれません。お気付きの方は、ぜひご指摘ください。 Hashmapに関する他言語の問題点Dave Cheney氏によると、C++とJavaのHashmapには、それぞれ以下のような問題点があるとのことです。 C++: キーと値の組合せが異なるHashmapは、型としても全く別物となる。結果、コンパイル後のプログラムには、それぞれのHashmap実装が別物として含まれることになる。J