連想配列

PHP

連想配列のキーは常に文字列として扱われるため、ダブルクォーテーションで囲む必要がある。

JavaScript

文字列リテラルまたは識別子を使用できる。
そのため、ダブルクォーテーションで囲む必要がない。

ハッシュマップ

キーと値のペアを格納するデータ構造
for ループでリストを全てループするよりも、過去のデータをキャッシュできるため、効率的に処理できる。
ルックアップテーブルによって保存されたデータへのアクセスは平均的に O(1) の速度で行なうことができる。

特徴
①キーは一意
同じキーを複数回使うと、後から追加された値で上書きされる。
②高速な検索
キーを使って値を取得する操作が非常に高速。
③順序保証なし
キーと値のペアは順序を保証しない
※挿入順とは異なる順序で格納されることがある。

ハッシュマップの仕組み

ハッシュテーブルというデータ構造を使って実装されている。

ハッシュ関数
キーをハッシュ値（整数）に変換。
（例）"apple" → 12345、"banana" → 67890

バケット
ハッシュ値に基づいて、キーと値のペアを格納する場所（バケット）を決定する。
（例）ハッシュ値 12345 → バケット 1、ハッシュ値 67890 → バケット 2

衝突処理
異なるキーが同じハッシュ値を持つ場合（衝突）、リンクリストやツリー構造を使って複数のペアを管理する。

応用例

データのキャッシュ
頻繁にアクセスするデータをハッシュマップに保存し、高速に取得する。

設定の管理
キーを設定名、値を設定値として管理する。

カウンタ
キーをアイテム名、値を出現回数としてカウントする。

※キーは順番のないリストのようなものであるため、どのような順番で取得されるか予測することはできない。そのため、キーの順番に依存する処理を行う場合は、注意が必要。

リスト（list）

データを順番に並べて保管するための仕組み
その中に入っている値には番号（インデックス）が割り当てられている。

リストのデータ構造

①配列
②連結リスト

配列（array）

連続したメモリにそれぞれの要素を格納するデータ構造

コンピュータのメモリでは、一つ一つのメモリアドレスがメモリ上の 1 バイトを指している。
例えば、0x7FFE23B3E88C というメモリアドレスは、コンピュータのメモリ上の 1 バイトを直接指すことになる。

データが「連続して」格納されているということは、例えば 0x034FD32 のメモリアドレスが指すところにデータ値が格納されている場合、次のデータ値は 0x034FD33 のメモリアドレスに格納され、その次の値はメモリアドレス 0x034FD34 に格納されます。
ただし、データ型によって必要とするバイト数は仕様によって異なる。
例えば、32 ビットの int データ型であれば、格納される値ごとに 4 バイトが必要になる。
したがって、最初の int データがメモリアドレス 0x63FE44 に格納されると、次の int データがメモリアドレス 0x63FE48 に格納される。

配列にはインデックスでアクセスできる

配列では、各要素が連続してメモリに格納され、各要素の大きさによって各要素間の距離が決まる。
つまり、要素のサイズとアクセスしたい要素のインデックスから、簡単な計算式でそのメモリアドレスを算出すれば、配列内のどの要素にもアクセスできる。

※配列のサイズは慎重に
プログラムで配列を作成する際には、配列のサイズを指定する必要があり、それによって配列が占有するメモリ量が決まる。
したがって、プログラムで使用する配列のサイズは慎重に検討し、プログラムの必要性と利用可能なメモリ量に基づいて適切なサイズを選択することが重要。

※配列サイズは一度決定すると後から変更することができない。
※値を置き換えることは可能

配列の注意点

・配列は固定されているため、一度宣言された項目を削除することはできない。
要素内のデータを置き換えることのみ許されている。
例えば、4 番目の要素の値を 3 から 20 に変更するような操作は可能。
配列は可変オブジェクトのため、これらの操作が可能。
・配列のサイズ以上に要素を追加するには、より大きなサイズの新しい配列を作成して、すべての項目を新しい配列にコピーする必要がある。コピーする要素が n 個あるので、これには O(n) の時間計算量がかかる。
・配列の値の取得には、O(1) の時間がかかる。
それは連続したメモリ構造を持っているから。
ベースアドレス +（インデックス × データサイズ）の式を使うことによって、インデックスはメモリから直接値を取得することができる。
このように、任意の要素に同じ時間でアクセスできることを、ランダムアクセス、またはダイレクトアクセスと呼ぶ。
・配列内では原則 1 種類のデータ型しか使用することができない。
それはコンパイラがデータをメモリに格納するためには、同じサイズのデータである必要があるから。
中には JavaScript や PHP のように、str 型、double 型、int 型などの混在したデータ型を一緒に格納できる言語も存在するが、配列を使用する際には、同じデータ型を使うのがベストプラクティスと言われている。

動的配列（dynamic array）

格納されている要素数に応じて、必要に応じて自動的に大きくしたり小さくしたりできるデータ構造
動的配列は配列データにアクセスしてくれるメソッドや演算子を提供し、中に含まれる配列を自動的に管理するデータ構造。
配列のサイズや占有するメモリの量を気にすることなく、要素の保存やアクセスを効率的に行うことができる。

動的配列は、新しい要素を追加するときに既存のメモリスペースが不足している場合、自動的により大きなメモリブロックを確保する。そして、既存の要素を新しいメモリブロックにコピーする。この機能により、配列は効率的に大量の要素を取り扱うことが可能になる。

動的配列において要素が削除されるとき、実際には要素がメモリから物理的に削除されるわけではないことが一般的。
代わりに、配列の論理サイズ（要素数）がデクリメント（減少）され、要素が削除された場所は空きスペースとなる。この空きスペースは、新たに要素が追加される際に再利用される。

固定長配列：固定サイズ配列は、作成時に長さが決まっており、後から変更することができない

動的配列：サイズ変更が可能。配列データを操作するためのさまざまなメソッドが用意されており、配列に対する操作を行なうことができる

※JavaScriptやPythonでは、動的配列はオブジェクト

動的配列の仕組み

動的配列では、配列の論理サイズ（logical size）と容量（capacity）というものが常にメモリ内で把握されている。

論理サイズ：現在配列に格納されている要素数を表す

容量：サイズを変更する前に配列が保持できる最大要素数を表す

動的配列に要素を追加し、要素数が容量を超えると、新しい要素を収容するために配列は自動的に大きなサイズにリサイズされる。

論理サイズが要素で満たされたとき
①新しい容量 = 論理サイズ × d となるように、より大きな容量の新しい配列を作成する。
・自動的（動的）にさらに大きな容量の配列を作成し、拡張する。
・この d は成長係数と呼ばれ、1.5 や 2 がよく使われる。
・つまり、現在の論理サイズの1.5 倍または 2 倍の論理サイズに拡張される。
②新たな配列が作成されると、古い配列に入っていた要素が新しい配列へコピーされる。

※メモリ上のスペースに無駄ができる可能性がある。最悪の場合、O(n) 分のメモリが無駄になることもある。

動的配列における計算量

①先頭への挿入: O(n)

動的配列の先頭に要素を挿入するには、通常、既存のすべての要素を 1 つずつずらして、新しい要素のためのスペースを確保する必要がある。
これは特に配列が大きい場合には、時間のかかる操作となる。n 個の要素がある場合、n 個の要素を移動させる必要があるため、結果として O(n) の計算コストが必要になる。動的配列の一番最初の要素にいきなり値を追加できないのは、すでにセルの中に値が存在していており、値を上書きしてしまうためである。

②先頭の削除: O(n)

先頭の要素を削除する場合は、n-1 個の要素を 1 スロット後ろ方向に移動させる必要があるため、O(n) の計算コストが必要になる。

③途中への挿入: O(n)

④途中の削除: O(n)

⑤末尾への挿入: O(1)

⑥末尾の削除: O(1)

二次元配列

データの表を表現することができる。

キャッシュ（cache）

データを保存し、そのデータに対する将来の要求をより速く処理できるようにするハードウェアまたはソフトウェアコンポーネントのこと
頻繁に使用またはアクセスされるデータへのアクセス時間を短縮することによって、システムのパフォーマンスを向上させるために使用される。

キャッシュは、コンピュータの中にある一種の保存場所で、CPU や Web ブラウザ、データベースなど、いろいろな場所で使用される。
キャッシュは、以前にアクセスされたデータのコピーを保存することで、同じデータがもう一度要求された場合に、元の場所から取得するのではなく、素早くキャッシュから取得できるようにする仕組み。

実装例：エラトステネスの篩