この手の話は一から説明を書くよりも､解説されたﾍﾟｰｼﾞを探した方が体系だった説明があると思いますが､
ﾊｯｼｭ関数
ﾊｯｼｭ法

概要を書けば､
単純に配列を考えた場合､そこに任意に登録した単語を検索するには平均 単語数/2 の検索処理が発生します(数に比例)｡

ﾊｯｼｭではﾊｯｼｭ関数(ﾃﾞｰﾀからｲﾝﾃﾞｯｸｽを計算する関数)によって格納位置を配列内になるべく均等になるようにして､そこにたどり着くまでの回数をなるべく少なくなるように設計します(されているはず)｡
ﾊｯｼｭ関数の結果が同じになれば､そこからは逐次検索ですが､それでも全体に対する検索に比べれば､はるかに少ない検索ｺｽﾄで済みます｡
極端な例として､完全ﾊｯｼｭ関数が実装できるｹｰｽでは一回の検索で済むわけです｡

連想配列では､ﾊｯｼｭ以外にも平衡2分探索木などによる実装もあるようです｡
いずれも､目的の値までにいかに少ない検索回数で到達するかという工夫です｡

ﾃﾞｰﾀﾍﾞｰｽも基本的には同じ話ですが､興味があればこのあたりを読んでみてはどうでしょうか｡
基礎から理解するﾃﾞｰﾀﾍﾞｰｽのしくみ(7) ﾃﾞｰﾀの格納方法を知ろう(2)

(1)ﾊｯｼｭは言うなれば背番号制｡
ﾃﾞｰﾀを保存する時に､
ﾊｯｼｭ関数で背番号を生成して保存しておく｡
(当然ながら保存処理は平文よりも長くなる)

(2)早い理由はﾌﾙﾈｰﾑではなく背番号による検索だから｡
ﾃﾞｰﾀを検索する時には､
まず検索対象をﾊｯｼｭ関数で背番号にして､
その背番号でﾃﾞｰﾀの存在を探す｡
(元が大きなﾃﾞｰﾀでも､背番号の比較で済むため､
検索時間は短くて済む)

(3)氏名､年齢､身長､体重･･･項目が増えても背番号は1つ｡
1件ごとに番号を生成して付けるため､
文字数や項目の数が増えても検索速度は変わらない｡
(もちろん､ﾊｯｼｭを計算する時間は長くなるけれど､
それは登録時の1回と､検索開始時点の1回だけで､
検索作業は背番号で済むので早い)

(4)複雑な条件付き検索は苦手です｡
背番号51を探せと命じてｲﾁﾛｰと答えさせるのは非常に早い｡
だがしかし､背番号51から61までを出力しろと命じると非常に遅い｡
(背番号をつけただけで､並び順までは管理していないため､
ﾃﾞｰﾀの末尾に達するまで比較検討することになったりするのです)

(5)すなわち､
単一の値を探し出すことを優先する連想配列などであれば､
ﾊｯｼｭは非常に有効な手段となるけれど､
複雑な条件設定になるﾃﾞｰﾀﾍﾞｰｽのﾃｰﾌﾞﾙでは､
B-treeが多様されるというようなことになります｡
(ﾃﾞｰﾀﾍﾞｰｽのﾃｰﾌﾞﾙでも単一の値を探すことに特化できる場合は､
ﾊｯｼｭを選ぶ場合もあります)

(その他)MySQL5.xのmemoryｽﾄﾚｰｼﾞｴﾝｼﾞﾝはﾒﾓﾘ上にあるから早いのです｡
4.x時代はﾋｰﾌﾟでしたが､
現在はﾃﾞｨｽｸに保管するﾃｰﾌﾞﾙに近い機能を持っていて､
ﾊｯｼｭとB-treeを必要に応じて使い分けてくれます｡