3.5 まとめ¶
1. 重要ポイントの振り返り¶
- データ構造は、論理構造と物理構造という 2 つの観点から分類できます。論理構造はデータ要素間の論理的関係を記述し、物理構造はデータのコンピュータメモリ上での格納方法を記述します。
- 代表的な論理構造には、線形、木構造、網状構造などがあります。通常、論理構造に基づいてデータ構造を線形（配列、連結リスト、スタック、キュー）と非線形（木、グラフ、ヒープ）の 2 種類に分類します。ハッシュテーブルの実装には、線形データ構造と非線形データ構造が同時に含まれる場合があります。
- プログラムの実行時、データはコンピュータメモリに格納されます。各メモリ空間には対応するメモリアドレスがあり、プログラムはそれらのメモリアドレスを通じてデータにアクセスします。
- 物理構造は主に連続領域への格納（配列）と分散領域への格納（連結リスト）に分けられます。すべてのデータ構造は、配列、連結リスト、またはその両方の組み合わせによって実装されます。
- コンピュータにおける基本データ型には、整数
byte、short、int、long、浮動小数点数float、double、文字char、真偽値boolがあります。これらの値域は、使用する記憶領域の大きさと表現方式によって決まります。 - 符号付き絶対値表現、1 の補数、2 の補数は、コンピュータで数値を符号化する 3 つの方法であり、相互に変換できます。整数の符号付き絶対値表現では最上位ビットが符号ビットで、残りのビットが数値の値です。
- 整数はコンピュータ内では 2 の補数の形式で格納されます。2 の補数表現では、コンピュータは正数と負数の加算を同じように扱うことができ、減算のために特別なハードウェア回路を別途設計する必要がなく、さらに正負のゼロが重複する問題もありません。
- 浮動小数点数の符号化は、1 ビットの符号部、8 ビットの指数部、23 ビットの仮数部で構成されます。指数部があるため、浮動小数点数の値域は整数よりはるかに広くなりますが、その代償として精度が犠牲になります。
- ASCII コードは最も早く登場した英字文字集合で、長さは 1 バイト、収録文字数は 127 です。GBK 文字集合はよく使われる中国語文字集合で、2 万字以上の漢字を収録しています。Unicode は完全な文字集合標準を提供することを目指しており、世界中のさまざまな言語の文字を収録することで、文字コード方式の不一致によって生じる文字化けの問題を解決します。
- UTF-8 は最も広く使われている Unicode の符号化方式で、汎用性が非常に高いです。可変長の符号化方式であり、拡張性に優れ、記憶領域の利用効率を効果的に高めます。UTF-16 と UTF-32 は固定長の符号化方式です。中国語を符号化する場合、UTF-16 は UTF-8 よりも使用領域が小さくなります。Java や C# などのプログラミング言語は、デフォルトで UTF-16 を使用します。
2. Q & A¶
Q：なぜハッシュテーブルには線形データ構造と非線形データ構造が同時に含まれるのですか？
ハッシュテーブルの基盤は配列であり、ハッシュ衝突を解決するために「チェイン法」（後続の「ハッシュ衝突」の章で説明します）を使うことがあります。配列内の各バケットは 1 つの連結リストを指し、その連結リストの長さがある閾値を超えると、木（通常は赤黒木）に変換されることもあります。
格納の観点から見ると、ハッシュテーブルの基盤は配列であり、各バケットスロットには値が入ることもあれば、連結リストや木が入ることもあります。したがって、ハッシュテーブルには線形データ構造（配列、連結リスト）と非線形データ構造（木）が同時に含まれる場合があります。
Q：char 型の長さは 1 バイトですか？
char 型の長さは、プログラミング言語が採用する符号化方式によって決まります。たとえば、Java、JavaScript、TypeScript、C# はいずれも UTF-16 符号化（Unicode コードポイントを保持）を採用しているため、char 型の長さは 2 バイトです。
Q：配列ベースで実装されたデータ構造を「静的データ構造」と呼ぶのは曖昧ではありませんか？ スタックも push や pop などの操作ができ、これらの操作はどれも「動的」です。
スタックは確かに動的なデータ操作を実現できますが、データ構造自体は依然として「静的」（長さが不変）です。配列ベースのデータ構造でも要素を動的に追加または削除できますが、その容量は固定です。データ量が事前に確保した大きさを超えた場合は、より大きな新しい配列を作成し、古い配列の内容を新しい配列にコピーする必要があります。
Q：スタック（キュー）を構築するときにサイズを指定していないのに、なぜそれらは「静的データ構造」なのですか？
高水準プログラミング言語では、スタック（キュー）の初期容量を人手で指定する必要はなく、この作業はクラス内部で自動的に行われます。たとえば、Java の ArrayList の初期容量は通常 10 です。また、容量拡張も自動的に実装されています。詳しくは後続の「リスト」の章を参照してください。
Q：符号付き絶対値表現から 2 の補数への変換方法は「先にビット反転してから 1 を加える」ですが、2 の補数から符号付き絶対値表現への変換は逆演算である「先に 1 を引いてからビット反転する」べきなのに、同じく「先にビット反転してから 1 を加える」でも求められます。これはなぜですか？
これは、符号付き絶対値表現と 2 の補数の相互変換が、実際には「補数」を計算する過程だからです。まず補数の定義を示します。\(a + b = c\) とすると、\(a\) を \(b\) から \(c\) への補数と呼び、逆に \(b\) も \(a\) から \(c\) への補数と呼びます。
長さ \(n = 4\) ビットの 2 進数 \(0010\) が与えられたとします。この数を符号付き絶対値表現（符号ビットは考慮しない）とみなすと、その 2 の補数は「先にビット反転してから 1 を加える」ことで得られます。
ここで、符号付き絶対値表現と 2 の補数の和は \(0010 + 1110 = 10000\) となります。つまり、2 の補数 \(1110\) は符号付き絶対値表現 \(0010\) から \(10000\) への「補数」です。これは、上記の「先にビット反転してから 1 を加える」が、実際には \(10000\) への補数を計算する過程であることを意味します。
では、2 の補数 \(1110\) から \(10000\) への「補数」はいくつでしょうか。これもやはり「先にビット反転してから 1 を加える」ことで求められます。
言い換えると、符号付き絶対値表現と 2 の補数は互いに相手から \(10000\) への「補数」なので、「符号付き絶対値表現から 2 の補数への変換」と「2 の補数から符号付き絶対値表現への変換」は同じ操作（先にビット反転してから 1 を加える）で実現できます。
もちろん、逆演算を用いて 2 の補数 \(1110\) の符号付き絶対値表現を求めることもでき、その場合は「先に 1 を引いてからビット反転する」ことになります。
まとめると、「先にビット反転してから 1 を加える」と「先に 1 を引いてからビット反転する」の 2 つの演算は、どちらも \(10000\) への補数を計算しており、等価です。
本質的には、「ビット反転」という操作は実際には \(1111\) への補数を求めています（常に 符号付き絶対値表現 + 1 の補数 = 1111 が成り立つため）。そして、1 の補数にさらに 1 を加えて得られる 2 の補数が、\(10000\) への補数です。
上記では \(n = 4\) を例にしましたが、この考え方は任意のビット長の 2 進数に一般化できます。