某誌の連載は「とりあえず様子見で3回くらいやってみましょうか」で始めて，今月発売の号で3回掲載になりましたので，終わりました．
担当編集の方々や読者からの反応は悪くは無かったと自負はしているのですが，もっと大枠のところで色々と思うところありまして．主に私の側の問題です．
計算機科学(工学)周りでは，高校生/高専生/(情報工学専攻以外の)大学生には触れる機会がないけれども，プログラミングするなら知らないと辛い概念が結構あります． 私自身も専攻は物理で，計算機科学の高等教育を受けておらず，しんどい思いをしてきました．身に沁みています． 計算機科学の触りを，初学者向けに軽め/短めに解説するという連載の趣旨そのものは，提案した私が言うのもナンですが，良いと思っています． どなたかパクっていただけないかなとも思うのですが…止めた私が言うのもナンですが．
ともあれ，期待して頂いた読者がいらっしゃったかもと思うと，申し訳ない気持ちはあります． エアお詫びを兼ね，「4回目があったとしたら，何を扱うかな」というお題で，小一時間で書いてみました． 編集/校正を通しておらず，イラストもありません． よって，読みづらいかもしれませんが，どうぞ．
ハッシュ関数 〜 ビッグデータの根本を支える数学
ビックデータ時代の到来
ビッグデータという言葉は，業界用語を超えて，一般のメディア媒体にも登場するようになりました． 広く知られるようになると，意味が曖昧になるのが世の常です． 本題に入る前に，軽く整理しておきましょう．
近年，計算機の処理能力が上がり，それらがつながるネットワークが高速化しました． 結果として，大規模な並列処理が可能になりました． 同時並行で処理できるようなデータについては，その総量が膨大であっても，実用的な時間で分析が可能となりました． このような背景をもってして，初めて分析が可能になるような膨大な量のデータを「ビッグデータ」と呼びます．
一般に，データの量とノイズの少なさには，概ね正の相関関係があります． 今までは，大量のデータをそのまま処理したいと思いつつも，計算機の能力の限界ゆえに，多くのデータは捨てられていたのです．
ビッグデータが抱える技術的課題
上記のように，ネットワークで繋がれた並列計算機による処理分散が，ビックデータ分析の肝です． 確かにネットワークは以前よりは高速化しましたが，CPUの中に比べると桁違いに時間がかかります．同時並行で処理できるようなデータを扱うとはいえ，ディスクやデータベースといったストレージへのアクセスは起きます． 隣の計算機で処理しているデータとの比較も行いたくなります． 現実には，システム全体で見た時，ネットワークの遅さは，大きなボトルネックになります． いかにデータ本体をネットワーク転送させないか，というのは分散コンピューティングにおける最大の課題なのです．
ハッシュ関数 = データの要約を求める関数
データ転送量の抑制方法は，いくつか存在します． それらのうち，仕組みが分かりやすく実効性も高いものに，データの本体ではなく，特徴を転送するというものがあります．
たとえば，つぎのような”ビッグデータ(笑)“の各行が複数の計算機上に分散して置かれているとします． そして，辞書順に並べる処理をしたいとしましょう． この場合，全部のデータを送りあうのは得策ではありません． たとえば，一文字目の「か・の・む・や」だけをネットワークに流して比較するのはどうでしょうか．総文字数16文字に対して4文字で済みます．
しかし残念ながら，この例の場合，「むらなか」と「むろた」は，一文字目だけでは辞書順に並び買えられません． この場合は「むらなか」のデータを持っている計算機と「むろた」を持っている計算機との間で2文字目の「ら・ろ」を比べる処理が必要になります．手間はかかりますが，16文字を送りあうよりは転送量は少ないでしょう． また，「かとう」「のむら」「やすだ」のデータを持っている計算機は，その間に別の処理を行えます．
1
| |
1
| |
1
| |
1
| |
1
| |
これは初歩的な一例でしかありませんが，「かとう」 → 「か」といったような処理を，計算機科学では関数であると見做して， ハッシュ関数 (和訳は 要約関数 )と呼びます． ハッシュ関数は，計算機科学における極めて重要な概念であり，またプログラミングの現場でも欠かすことのできない知識です．
ハッシュ関数をどのように選ぶかで，システムの性能は大きく影響されます． 例えば上記の例でのハッシュ関数では「むらなか」と「むろた」の順序を決定できませんでした．これは， 衝突 と呼ばれる状態です．衝突が起きると，それを回避する処理が必要になり，性能が落ちるので好ましくありません． ハッシュ関数の結果は，元のデータより情報量が落ちますので，衝突は避けられないものではあります．しかし，より衝突が少なくなるよう関数の中身を考えるのが，技術者・研究者の腕の見せ所でもあるのです．
備考: プログラミング言語とハッシュ
Perl, Ruby, JavaScript など，一部の言語では，連想配列に相当する機能をハッシュと呼ぶことがあります．これらの言語の内部で，連想記憶の管理にハッシュ関数を使っていることに起因します．全く無関係でもないのですが，概念としては別物として考えておくほうが良いでしょう．