ここでBig Oはハッシュテーブルに対して定義されていませんか？

Question

このチートシートでは、ハッシュテーブルにアクセスするための平均時間複雑度はN/Aとしてリストされています。

私はなぜ興味があるのですか？ハッシュテーブルは主に数学的なものであり、他の演算と同様にO（1）であると仮定します...検索、挿入、削除。そのテーブルの

http://bigocheatsheet.com/

Answer 1

、「アクセス」列がインデックスによって、指定された要素にアクセスするための時間を指します。そのため、配列内のアクセスはO（1）と記述されます。配列のi番目の要素を返すことは、一定の時間の操作です。同様に、リンクされたリストの場合は、O（n）の操作です。リンクされたリストがあり、そのアイテムをインデックスiにしたい場合は、リンクからリンクへジャンプする必要があります。

ハッシュテーブル（辞書、ハッシュマップなど）では、「インデックスiの要素」については話しません。インデックスについては一切言及しません。これは、ハッシュテーブルの 'アクセス'の値としてNAを持つことによって、このテーブルが意味するものです。ハッシュマップ上で（ここで使用されている意味で）「アクセス」操作を行うだけではありません。

おそらく明示的な例が役立つかもしれません。最初の2つの例では

myLinkedList = ['red','blue','orange']

myArray = ['black','white','green','yellow']

myHashMap = {'address':'10 wall st', 'gender':'male'}'

、我々は、アクセスは、指定されたインデックスの要素缶。

すなわち：

myLinkedList[1] == 'blue'と

しかし、我々はできませんアクセスハッシュマップインデックスによります。

myHashMap[0]はこの例では定義されていません。したがって、 'アクセス'はハッシュマップに対してNAです。

ただし、このコンテキストでは、操作：キーによる検索と同等です。

例：

myHashMap['address'] == '10 wall st'

アンO（1）操作。

データ構造の内部構造がわからないために質問しても（その場合は、それを学ぶ価値があります）、単にそのチートシートの用語で混乱しただけの場合は、 。