CS 6.006 Lecture 8 Hashing with Chaining を見る

わかったこと

ディクショナリはハッシュ表、Binary Search Treeの上位概念

Pythonでお馴染みのディクショナリ。 ディクショナリは

• insert
• delete
• search

を行うもので、具体的な実装方法としてハッシュ表、Binary Search Treeがある。 ディクショナリとハッシュ表を同じレイヤのものだと思っていたが、あくまでディクショナリが上位の概念。

ディクショナリの利用例

• 文字頻度のカウント
• コンパイラにグローバル変数を保存する (Pythonの古い実装)
• ネットワークのルータ (IPアドレスとホストの対応づけ?)

PrehashとHashの違い

Pythonでimmutable(値を後から変更できない)な任意のオブジェクトをディクショナリのキーに突っ込めるのは、Prehashのおかげ。 Prehashはオブジェクトから適切なintegerを返す関数で、Hashとは違う位置付け。 オブジェクトのidが使われる(?)が、クラス内のhashメソッドを自分で実装することもできる。 が、自前で実装することはあまりお勧めされていない。講義中でもDon't mess with itと言われている。 これは、オブジェクトの内部の値などが変わってしまった時にhashの計算結果が変わってしまうことで、 オブジェクトから計算されるキーの値が変わってしまうから。 mutableなオブジェクト(値をあとから変更できるオブジェクト)をキーにすることができないのはこのためで、値が変わってしまい、キーが変わってしまう恐れがあるから。 Pythonだと、set, list, dictがimmutableなオブジェクトとしてあげられる。

参考： medium.com