ホームリレーショナル・データベースの世界


「SQLアタマアカデミー」サポートページ


 『Web+DB Press』(技術評論社)から引き合いをいただいて、2008年4月号より SQL についての「SQLアタマアカデミー」という連載講座を持たせてもらっています。初回の4月号だけ特集の形で、6月号からは連載の形式となっています。この講座では、サンプルコードと解説だけでなく、毎回ちょっとした演習問題を載せているので、本サイトではその解答・解説を中心に補足情報を提供することを目的としています。

 また、疑問、間違いの指摘、新たな解法のアイデアなども随時受け付けております。メールゲストブックブログのいずれからでもどうぞ。

2008年 4月(Vol.44):特集「SQLアタマ養成講座」
2008年 6月(Vol.45):第1回「SQLで連番を扱う」
2008年 8月(Vol.46):第2回「更新なんてこわくない!」
2008年10月(Vol.47):第3回「テーブル設計のグレーゾーン」
2008年12月(Vol.48):第4回「行か列か、それが問題だ」
2009年 2月(Vol.49):第5回「SQLで木構造を扱う (1) 入れ子集合モデル」
2009年 4月(Vol.50):第6回「SQLで木構造を扱う (2) 入れ子区間モデル」
2009年 6月(Vol.51):第7回「性能改善の鍵、インデックスの特性を知る」


2008年4月(Vol.44):特集「SQLアタマ養成講座」

・初出は『WEB+DB PRESS Vol.44』
・サンプルコードのダウンロードは『WEB+DB PRESS』Vol.44 サポートページより。

 演習問題のサンプルデータは、本文の第3章に掲載の HotelRooms を使います。データ作成の SQL は以下のとおり。

サンプルデータ
CREATE TABLE HotelRooms
(room_nbr   INTEGER NOT NULL,
 start_date DATE NOT NULL,
 end_date   DATE NOT NULL,
   PRIMARY KEY(room_nbr, start_date));

INSERT INTO HotelRooms VALUES (101, '2008-02-01', '2008-02-06');
INSERT INTO HotelRooms VALUES (101, '2008-02-06', '2008-02-08');
INSERT INTO HotelRooms VALUES (101, '2008-02-10', '2008-02-12');
INSERT INTO HotelRooms VALUES (202, '2008-02-05', '2008-02-06');
INSERT INTO HotelRooms VALUES (202, '2008-02-08', '2008-02-09');
INSERT INTO HotelRooms VALUES (202, '2008-02-09', '2008-02-10');
INSERT INTO HotelRooms VALUES (303, '2008-02-03', '2008-02-17');

 問題は、このテーブルから、各部屋の稼働日数の合計を調べ、それが10日を超える部屋を求める、というものでした。部屋ごとに集計するのだから、集約キーが room_nbr であることは明らかです。後は、日付型の投宿日と出発日の列から、日数を求める方法、ということになりますが、実はここが、現時点では実装によって結構マチマチで悩ましいところです。

 まず、Oracle、DB2、 PostgreSQL ならば、そのまま日付の引き算をしましょう。

SELECT room_nbr,
       SUM(end_date - start_date) AS stay_days
  FROM HotelRooms
 GROUP BY room_nbr
HAVING SUM(end_date - start_date) >= 10;

room_nbr  stay_days
-------- ----------
     303         14

 SQLServer、MS-Access の場合は、DATEDIFF 関数を使います。

SELECT room_nbr,
       SUM(DATEDIFF(end_date, start_date)) AS stay_days
  FROM HotelRooms
 GROUP BY room_nbr
HAVING SUM(DAYS(end_date, start_date)) >= 10;




2008年6月(Vol.45):第1回「SQLで連番を扱う」

・初出は『WEB+DB PRESS』Vol.45
・サンプルコードのダウンロードは『WEB+DB PRESS』Vol.45 サポートページより。

 SQL とリレーショナル・データベースは「連番」を生成したり扱うための機能を非常に軽視してきました(なかば敵視してきた、と言ったらいいすぎか)。その最大の理由は、本文の導入部でも軽く説明しているとおり、連番がこの世界に存在するエンティティの属性とは考えられていないからです。要するに、システム側の都合で割り振られる管理用の識別子という点で、アドレスに連なる存在として考えられてきたわけです(リレーショナル・データベースがアドレスに対して抱く反感については、「アドレス、この巨大な怪物」を参照)。この論点は、不定期に繰り返される「ナチュラルキー VS サロゲートキー」論争にも共通のものです。実際、連番はサロゲートキーとして使われることも多い。

 しかしま、理論家や原理主義者のとうとうたる演説を聞いていても、現場の世界で連番を使うことを要請される私たち末端エンジニアには、腹の足しになりません。それに、さすがの連番嫌いの RDB も、最近では現場からの「不本意な」圧力に屈して ROW_NUMBER や ID 列といった機能を追加するようになっています。そのことの良し悪しについての評価は分かれるけど、私はこれぐらいは歓迎してもいい拡張だと思っています。

 さて、前置きはこれぐらいにして、本題に入りましょう。まずは演習問題1の解答・解説です。

解答1
/* MySQL 以外 */
SELECT AVG(weight) AS median
  FROM (SELECT
            weight,
            (SELECT COUNT(W1.Weight)
               FROM Weights W1
              WHERE CAST(W1.Weight AS CHAR(4))  || W1.student_id 
                     < CAST(Weights.weight AS CHAR(4)) || Weights.student_id) AS hi,
            (SELECT COUNT(W2.Weight)
               FROM Weights W2
              WHERE CAST(W2.Weight AS CHAR(4))  || W2.student_id
                     > CAST(Weights.weight AS CHAR(4)) || Weights.student_id ) AS lo
          FROM Weights ) TMP
 WHERE hi IN ( lo, lo+1, lo-1 );

/* MySQL版 */
SELECT AVG(weight) AS median
  FROM (SELECT
            weight,
            (SELECT COUNT(W1.Weight)
               FROM Weights W1
              WHERE CONCAT(CAST(W1.Weight AS CHAR(4)) , W1.student_id)
                     < CONCAT(CAST(Weights.weight AS CHAR(4)) , Weights.student_id)) AS hi,
            (SELECT COUNT(W2.Weight)
               FROM Weights W2
              WHERE CONCAT(CAST(W2.Weight AS CHAR(4)), W2.student_id)
                     > CONCAT(CAST(Weights.weight AS CHAR(4)), Weights.student_id)) AS lo
          FROM Weights ) TMP
 WHERE hi IN ( lo, lo+1, lo-1 );

 要点は、連番を振るために使っていた二つの ROW_NUMBER 関数を相関サブクエリで代用することです。昇順ソートと降順ソートを表現する不等号の向きを逆にすることだけ忘れないように。

 CAST関数で4桁の文字型へキャストしていますが、この桁数は、データの最大値を考慮して適宜変更すること(誌面上のサンプルデータならば、2桁でも可)。ゼロ埋めまでしてやるとなお分かりやすくて親切かもしれません。また、MySQLの場合は文字列の連結に「||」ではなく CONCAT 関数を使う必要があります(昔から疑問なのだけど、この MySQL の独自仕様は何なのでしょうね? 普通に「||」演算子を持てばいいのに)。

 それではお次。

解答2
ソートキーを体重(weight)列のみとすると、hiとloを算出する際に、
同じ体重の生徒が同じ順序でソートされる保証がないため。

 例えば 72kg という生徒が A、B、C の3人いた場合、体重だけをキーにソートしたら、この3人の間でどういう基準に従って順序付けすればいいのか分かりません。あるときは(A, B, C)、違うときは(B, C, A)となってしまいます。おそらくデータベースは何らかの基準(きっとアドレスなど物理的なロケータ)に従って場当たり的な順序付けをするのでしょうが、hi と lo は同一の基準に従った昇順と降順でなければなりません。従って、SQL で連番を振るときは、必ず一意キーを使うことが鉄則なのです。  それでは最後。これも解答1、2を理解した皆さんには、難しくないでしょう。

解答3
/* 手続き型:ROW_NUMBERを使用 */
SELECT class, AVG(weight) AS median
  FROM (SELECT class, weight,
               ROW_NUMBER() OVER (PARTITION BY class ORDER BY weight ASC, student_id ASC) AS hi,
               ROW_NUMBER() OVER (PARTITION BY class ORDER BY weight DESC, student_id DESC) AS lo
          FROM Weights2 ) TMP
 WHERE hi IN ( lo, lo+1, lo-1 )
GROUP BY class;

/* 集合志向型:相関サブクエリを使用 */
SELECT class, AVG(weight) AS median
  FROM (SELECT class, weight,
            (SELECT COUNT(W1.Weight)
               FROM Weights2 W1
              WHERE W1.class = Weights2.class
                AND CAST(W1.Weight AS CHAR(4))  || W1.student_id 
                     < CAST(Weights2.weight AS CHAR(4)) || Weights2.student_id) AS hi,
            (SELECT COUNT(W2.Weight)
               FROM Weights2 W2
              WHERE W2.class = Weights2.class
                AND CAST(W2.Weight AS CHAR(4))  || W2.student_id
                     > CAST(Weights2.weight AS CHAR(4)) || Weights2.student_id ) AS lo
          FROM Weights2 ) TMP
 WHERE hi IN ( lo, lo+1, lo-1 )
GROUP BY class;

 クラスごとに母集合をカットするということなので、ROW_NUMBER の場合は PARTITION BY 句を使いましょう。相関サブクエリの場合は、「同じクラス内で連番を振る」という条件を追加してやれば OK。

 いかがでしたか? 簡単だったでしょうか?

 さて、ついでに、p.143 で利用した任意の大きさの連番の生成方法を、二つほど紹介しましょう。「:n」が生成したい連番の上限を表すパラメータです。

/* 階層問い合わせ(Oracle) */
SELECT rownum
  FROM dual
CONNECT BY LEVEL <= :n;


/* 再帰共通表式(DB2、SQLServer) */
CREATE TABLE OneRow 
(seq INTEGER NOT NULL);
INSERT INTO OneRow VALUES(1);

WITH Sequence (seq)
AS
(SELECT seq FROM onerow
 UNION ALL
 SELECT seq + 1
   FROM Sequence
  WHERE (seq + 1) <= :n)
SELECT seq FROM Sequence;

 方法としては、紙面でも取り上げた連番ビューとあわせてこの三つが代表的なものでしょう。CONNECT BY を使う方法は、非常にコードが簡潔に書けるのがメリットです。テーブルも最初から用意されているdualテーブルを使えばいい。ただし、Oracleのみでしか通用しないのが難点。一方、再帰共通表式は、実装非依存でどんな DB でも使えます。しかも連番に上限もないというすぐれもの(現実には実装が許す再帰の回数に依存しますが)。ただし、再帰的に何度もクエリを発行するので、多きな連番を生成しようとするとパフォーマンスが悪くなります。そして今のところ、現実問題として DB2 と SQLServer でしか使えないのも残念。でも将来的にはこの方法が一番有望な気はします。セルコも『Thinking in Sets』の「5.1.1 Creating Sequence Table」で紹介しています。

 それじゃ、今月はここまで。8月までご機嫌よう。


2008年8月(Vol.46):第2回「更新なんてこわくない!」

・初出は『WEB+DB PRESS』Vol.46
・サンプルコードのダウンロードは『WEB+DB PRESS』Vol.46 サポートページより。

 やあ皆さん、ご無沙汰。どうもどうも、お元気でしたか。夏休みはちゃんととりましたか? まだ休暇を取っていない人は上司と喧嘩してでもとりましょう。人生にはリフレッシュが必要です。仕事の能率もバカンスがあってこそ上がるものでございますゆえ。

 さて、それでは夏休みボケを振り払って、演習の答え合わせといきましょう。今号の演習問題に必要なデータ作成 SQL は以下のとおりです。

/* 演習問題用サンプルデータ */
CREATE TABLE ScoreRowsNN
(student_id CHAR(4)    NOT NULL,
 subject    VARCHAR(8) NOT NULL,
 score      INTEGER    NOT NULL,
  PRIMARY KEY (student_id, subject));

CREATE TABLE ScoreCols
(student_id CHAR(4)    NOT NULL,
 score_en      INTEGER ,
 score_nl      INTEGER ,
 score_mt      INTEGER ,
  PRIMARY KEY (student_id));

DELETE FROM ScoreRowsNN;
INSERT INTO ScoreRowsNN VALUES ('A001',	'英語',	0);
INSERT INTO ScoreRowsNN VALUES ('A001',	'国語',	0);
INSERT INTO ScoreRowsNN VALUES ('A001',	'数学',	0);
INSERT INTO ScoreRowsNN VALUES ('B002',	'英語',	0);
INSERT INTO ScoreRowsNN VALUES ('B002',	'国語',	0);
INSERT INTO ScoreRowsNN VALUES ('C003',	'英語',	0);
INSERT INTO ScoreRowsNN VALUES ('C003',	'国語',	0);
INSERT INTO ScoreRowsNN VALUES ('C003',	'社会',	0);

DELETE FROM ScoreCols;
INSERT INTO ScoreCols VALUES ('A001',	100,  58,   90);
INSERT INTO ScoreCols VALUES ('B002',	 77,  60,   NULL);
INSERT INTO ScoreCols VALUES ('C003',	 52,  49,   NULL);
INSERT INTO ScoreCols VALUES ('D004',	 50,  100,  150);

 それでは、問題1から始めましょう。ScoreRowsNN テーブルの NOT NULL制約対応ですね。基本的には、NULL を値に変換するという、誌面で紹介した リスト5, 6 の解答と同じ考え方で OK です。変換後の値は、やはりゼロでよいでしょう。ただし、「どこで」変換するかによって、答えも二通りに分かれます。

/* 演習1の解答 その1
   サブクエリの内部でNULLを0に変換する
*/
UPDATE ScoreRowsNN
   SET score = (SELECT COALESCE(CASE ScoreRowsNN.subject 
                                     WHEN '英語' THEN score_en
                                     WHEN '国語' THEN score_nl
                                     WHEN '数学' THEN score_mt
                                     ELSE NULL
                                 END, 0)
                  FROM ScoreCols
                 WHERE student_id = ScoreRowsNN.student_id);

/* 演習1の解答 その2
   サブクエリの外部でNULLを0に変換する
*/
UPDATE ScoreRowsNN
   SET score = COALESCE((SELECT CASE ScoreRowsNN.subject 
                                     WHEN '英語' THEN score_en
                                     WHEN '国語' THEN score_nl
                                     WHEN '数学' THEN score_mt
                                     ELSE NULL
                                 END
                  FROM ScoreCols
                 WHERE student_id = ScoreRowsNN.student_id), 0);

 その1の方は、素直なものです。CASE式の戻り値が NULL だった場合にゼロへ変換しています。一方、その2は、サブクエリ全体をCOALESCE関数の引数としています。こちらは、厳密に考えると、少し構文的におかしいのです。というのも、サブクエリもクエリである以上、条件に一行もヒットしなかったときの戻り値は空集合になります。そして、スカラ関数であるCOALESCEの引数に空集合を取ることなど不可能なはずです。それなのに現実にこの解が通る理由は、SQL が空集合を NULL で代用するという摩訶不思議な仕様を持っていることによります。いわば、SQL の言語としてのいい加減さに付け込んだ解、ということです。「NULL と空集合の違い」というテーマについてもう少し詳しく知りたい方は、「存在と無」を参照。

 それでは次は問題2です。こちらの題意を一言でいえば、「MERGE文を書いてくれ」ということです。もちろん、MERGE文のない実装ならば、それと同等のものを、ね。この問題のサンプルデータは技術評論社のサポートページからダウンロードできるファイルに含まれています。解答は、以下の二通りです。

/* 演習2の解答 その1
   演習1の解答を使ってUPDATEを行った後に、足りない生徒の情報をINSERTする。
   WHERE句の条件に注目
*/
INSERT INTO ScoreRows
SELECT student_id,
       '英語',
       score_en
  FROM ScoreCols SC
 WHERE NOT EXISTS
         (SELECT *
            FROM ScoreRows SR
           WHERE SC.student_id = SR.student_id)
UNION ALL
SELECT student_id,
       '国語',
       score_nl
  FROM ScoreCols SC
 WHERE NOT EXISTS
         (SELECT *
            FROM ScoreRows SR
           WHERE SC.student_id = SR.student_id)
UNION ALL
SELECT student_id,
       '数学',
       score_mt
  FROM ScoreCols SC
 WHERE NOT EXISTS
         (SELECT *
            FROM ScoreRows SR
           WHERE SC.student_id = SR.student_id);


/* 演習2の解答 その2:MERGE文を利用して一回で更新 */
MERGE INTO ScoreRows
   USING (SELECT student_id,
                 '英語'   AS subject,
                 score_en AS score
            FROM ScoreCols SC
          UNION ALL
          SELECT student_id,
                 '国語'   AS subject,
                 score_nl AS score
            FROM ScoreCols SC
          UNION ALL
          SELECT student_id,
                 '数学'   AS subject,
                 score_mt AS score
            FROM ScoreCols) SC
      ON (    ScoreRows.student_id = SC.student_id 
          AND ScoreRows.subject    = SC.subject)
   WHEN MATCHED THEN
        UPDATE SET ScoreRows.score = SC.score
   WHEN NOT MATCHED THEN
        INSERT (student_id, subject, score)
        VALUES (SC.student_id, SC.subject, SC.score);

 答え1の方は、UPDATE + INSERT という二つの SQL を発行する手間がかかります。答え2の MERGE文であれば、一つの SQL で可能です。コードの簡潔さという点でも、実行速度という点でも、MERGE文の方がよいでしょう。2008年現在では Oracle と DB2 だけしかサポートしていませんが、いずれは全ての DB が実装するでしょうし、今後主流になるのはこちらのやり方だと思います。

 さて、今月はここまでです。まだまだ残暑厳しい日々が続きますが、次号までお元気で。


2008年10月(Vol.47):第3回「テーブル設計のグレーゾーン」

・初出は『WEB+DB PRESS』Vol.47
・サンプルコードのダウンロードは『WEB+DB PRESS』Vol.47 サポートページより。

 まず最初に、本稿のコードの間違いについて訂正させていただきます。上記の技術評論社のサポートページをご参照ください。私の不手際で読者の方々にご迷惑をおかけして申し訳ありません。

 さて、それでは演習問題の解答・解説です。演習問題1は、CHECK 制約によってコードの取りうる値の範囲を制限することが方針となります。ただし、当然ながら、コードの種類に応じて値の範囲(ドメインまたは定義域とも呼ぶ)が異なる点に注意が必要です。

/* 演習1の解答
   コード体系に応じてドメインを設定する
*/

ALTER TABLE OTLT ADD CONSTRAINT check_OTLT CHECK
( CASE WHEN code_type = 'pref_cd'
            THEN code_value BETWEEN '01' AND '47'
       WHEN code_type = 'sex_cd'
            THEN code_value IN ('0', '1', '2', '9')
       ELSE NULL END);

/* エラーデータ */
INSERT INTO OTLT VALUES('pref_cd',   '00',   '全国');
INSERT INTO OTLT VALUES('pref_cd',   '48',   '????');
INSERT INTO OTLT VALUES('sex_cd',    '3',    '????');
INSERT INTO OTLT VALUES('sex_cd',    '99',   '????');

 上の解答のように、ドメインの設定には、BETWEEN か IN を使うのが一般的です。ほぼこれでカバーできるでしょう。

 それでは演習問題2、オートナンバリングの方法です。これは現在、実装ごとに方法がバラバラで、DB エンジニアにとって頭痛の種になっているテーマです。なんでこんな、ある意味「基本的」と言えるような機能が標準化されていないかというと、本文でも書いたように、SQL と関係モデルがその教義上、連番という概念を認めたがらなかったからです。教義なんて言うと宗教的な響きがありますが、実際ここはちょっと宗教論争じみたところもあるのです・・・・・・。

 しかし、ようやく SQL:2003 において、シーケンス・オブジェクトと、オートナンバリング機能が標準に入ったので、いずれこの問題は解消されるでしょう。兄弟よ、未来は明るいぞ(と信じよう)。

/* 演習2の解答
  実装ごとのオートナンバリング
   1. Oracle と PostgreSQL の場合:シーケンス・オブジェクトを使う
*/

/* サンプルテーブル */
CREATE TABLE Nums 
(num INTEGER NOT NULL PRIMARY KEY);

/* シーケンス・オブジェクトの作成 */
CREATE SEQUENCE seq;

/* Oracle の場合 */
INSERT INTO Nums (num) VALUES (seq.nextval);

/* PostgreSQL の場合 */
INSERT INTO Nums (num) VALUES (NEXTVAL('seq'));


 Oracle と PostgreSQL のシーケンス・オブジェクトは、複数ユーザから同時にアクセスが発生しても、ユニークな連番を保証してくれます。増分や最大値、開始値等をオプションで指定できますが、今回はデフォルトを使いました。

 それぞれのシーケンス機能の詳細は以下のマニュアルを参照。

/* 2. SQLServer と MySQL の場合:連番用のデータ型を使う
  2-1. MySQLの場合
*/

/* サンプルテーブル */
CREATE TABLE Nums2
(num  INTEGER AUTO_INCREMENT PRIMARY KEY);

INSERT INTO Nums2 () VALUES();


/* 2-2. SQL Server の場合 */

/* サンプルテーブル */
CREATE TABLE Nums2
(num  INTEGER IDENTITY PRIMARY KEY,
 text CHAR(10));

INSERT INTO Nums2 (text) VALUES ('test');

 SQL Serverの場合、連番列の他に列が存在しないと、INSERT文が実行できないようです。MySQL にはこういう制限はありません。連番列だけのテーブルなんて、実際に作ることはないでしょうから、そんなに気にする必要のある制限ではないでしょうけど。
 最後に、DB2 の場合ですが、DB2 においては、シーケンス・オブジェクトも オートナンバー列も使用可能です。詳しくは、以下の IBM 社の技術情報を参照。
 なお、記事で紹介した単一参照テーブル(OTLT)の元ネタは以下のセルコの記事から。


2008年12月(Vol.48):第4回「行か列か、それが問題だ」

・初出は『WEB+DB PRESS Vol.48』
・サンプルコードのダウンロードは『WEB+DB PRESS』Vol.48 サポートページより。

 年末も押し迫ってきましたね。皆さん、無事に新年は越せそうですか? 越せる方も越せない方も、新年には新年の風が吹く。ジタバタしても始まりませんや。どっしり構えていきましょう。

 今回のお題は、スカラ・サブクエリ。知っているようで意外に知らない技術です。これも、簡単に使う分には簡単に使えるのだけど、本当に使いこなそうとすると SQL 特有のロジックを理解する必要があるのです。


2009年 2月(Vol.49):第5回「SQLで木構造を扱う (1) 入れ子集合モデル」

・初出は『WEB+DB PRESS Vol.49』

 今回から二回続きの大ネタ。実用性はとりあえず二の次で、SQL の可能性について語った回。

 詳細は以下のサイトを参照。


2009年 4月(Vol.50):第6回「SQLで木構造を扱う (2) 入れ子区間モデル」

・初出は『WEB+DB PRESS Vol.50』

 入れ子集合モデルには、挿入時に影響を受けるレコードが多くて、パフォーマンスが悪いという欠点がありました。その点を改良した進化版のモデルが、本稿で紹介した「入れ子区間モデル」です。前回に引き続き夢みたいな話をしているのですが、記念すべき連載一周年ということで大目に見てください。それに結構実用的でもあるんだから。このモデルを日本語で紹介したのは、私が初めてだと思う。




2009年 6月(Vol.51):第7回「性能改善の鍵、インデックスの特性を知る」

・初出は『WEB+DB PRESS Vol.51』

 当初一年間ということで引き受けた連載で、前号はその締めくくりにふさわしく大ネタを持ってきたのですが、何だかそのまま第2学年も続けることになりました。自分でも地味なコーナーであることは自覚していたのでそんなに読者からの人気があるとは思っていなかったのですが、望外の支持をいただいたというのは大変ありがたいことです。さて、それでは諸君、授業を始めようか。

 第2学年最初のテーマは、インデックス、とくに B-tree とハッシュのアルゴリズムについてです。「インデックスなんてとっくに使ってらあ」という声もあるでしょうが、でも本当に内部ロジックまで分かって使っていると言い切れる人は、それほど多くないでしょう。実際、インデックスの内部アルゴリズムの実装は、企業秘密に属するという理由もあって、あまり情報も公開されていないのです。そんなわけで、本誌でもあくまで一般的な観点からの話をしているのですが、それでも、これだけ知っていれば十分でしょう。

 演習問題の解答は、それぞれ以下のとおりです。

 問1:多くの DB では、主キーや一意キー制約を作成すると、対象の列に B-tree インデックスが暗黙に作成されます。これはなぜでしょう。

 解答:列の一意性についてチェックするためには、対象の列の値をソートする必要があります。B-tree インデックスはソートされた配列のため、これを作っておけば、一意性チェックを更新のたびにソートしなくても可能になるという性能上のメリットがあるからです。


 問2:もしハッシュ関数が不運にも全てのキーについて衝突を起こした最悪の場合、検索にかかる計算量はどうなるでしょう。

 解答:全てのキーについて衝突を起こしたということは、全てのキーに紐づくデータの格納先が全て同じになるということです。すると、結局ハッシュによるアクセスはただのシーケンシャルアクセスとなるため、計算量はデータ量に比例する O(n)となります。要するにそれは、ハッシュが何の役にも立たないケースということです。


作成者:ミック
作成日:2008/07/03
最終更新日:2009/07/05

Creative Commons License
この作品は、クリエイティブ・コモンズ・ライセンスの下でライセンスされています。
戻る
b_entry.gif b_entry.gif