配列と、ハッシュでは計算量に差が出る。

投稿日: 2021年 2月 9日

配列と、ハッシュとでは、配列にたいする計算量が圧倒的に大きくなる場合があるので、なるべくハッシュで対応できない考えるようにしたい

配列

ある要素が配列に含まれるかどうかを確認するとき、配列の先頭の要素から順番に見ていくので、時間がかかる。
しかも、

1, 1/2, 1/2/3, 1/2/3/4 ...

というような感じで、要素が増えるたびに冗長なチェックが増えていく

ハッシュ

配列とは違って、一発で目的の要素を取得することができる
なぜなら、キーに紐づく値を元にハッシュを生成してそれをキーにするから。
目的の値が手元にあれば、それを元にハッシュを生成すると、そのハッシュをキーに目的の値を探しに行けばいい。
問題は、ハッシュを生成するアルゴリズムによっては、キーの重複がありえる。キーの重複が発生した場合はリストを使うようにすれば、一つのハッシュキーに対して複数の値を管理することができる。
ハッシュのキー重複が多発すると、今度はリストから目的の値を探すコストが増えていって、一発で目的の要素を取得することができるというハッシュのメリットがなくなる点に注意が必要。

https://programming-place.net/ppp/contents/algorithm/search/006.html

プログラミングに関するオススメ書籍