名古屋工業大学 工学研究科 工学専攻 情報工学系 2023年度 計算機ソフトウェア（データ構造とアルゴリズム）

标签：

• Nagoya-Institute-of-Technology
• Hash-Table
• Linear-Probing-Hashing
• Algorithm-Complexity
• Combinatorial-Probability
• Greatest-Common-Divisor

Author

GPT-5.6 Sol, 祭音Myyura

Description

問題27「計算機ソフトウェア」の設問 I について答えよ。

(1)

ハッシュ法による配列へのデータ格納と探索に関する次の記述の正誤を答えよ。ハッシュ関数の評価は $O(1)$ とし、オープンアドレス法と線形探査を用いる。

1. (ア) ハッシュ法では常に配列中の連続した領域にデータが格納される。
2. (イ) ハッシュ法ではデータの格納と探索にかかる計算量が、配列内の空要素数に依存する。
3. (ウ) 格納され得るすべてのデータについてハッシュ値が重複せず、同一データを複数回格納しないとする。このとき、十分な配列サイズがあれば、格納と探索をともに $O(1)$ で実行できる。
4. (エ) 異なるデータに対してハッシュ値が重複すると、ハッシュ法を利用できない。
5. (オ) データ探索は最悪の場合でも $O(\log_2 n)$ となる。ただし、$n$ は格納する配列のサイズである。

(2)

要素数 6 の配列 $H$ に対し、線形探査を用いるオープンアドレス法を考える。格納するデータは正の整数であり、$\emptyset$ は空要素を表す。

Insert(x)
    i <- 0
    while (true) {
        j <- Hash(x,i)
        if ([a]) {
            [b]
            return [c]
        }
        i <- i + 1
        if ([d]) return -1
    }

Search(x)
    i <- 0
    while (true) {
        j <- Hash(x,i)
        if (i = 6 or H[j] = ∅) return -1
        if (H[j] = x) return j
        i <- i + 1
    }

Hash(x,i)
    return (x + i) mod 6

(ア)

$$H=[8,\emptyset,2,3,10,9]$$

とする。Search(x) を $x=3,9,4,8$ に対して実行したときの返り値と、return 実行時の $i$ をそれぞれ答えよ。

(イ)

Insert(x) が、格納成功時には格納した添字を、失敗時には $-1$ を返すように、空欄 (a)--(d) を次から選べ。

選択肢	処理	選択肢	処理
(A)	i	(B)	j
(C)	i = 6	(D)	j = 6
(E)	H[i] = ∅	(F)	H[j] = ∅
(G)	H[i] <- x	(H)	H[j] <- x
(I)	j <- j + 1	(J)	-1

(ウ)

配列 $H$ のちょうど 3 要素に値が格納され、残り 3 要素が空であるとする。値の入る 3 要素の選び方はすべて等確率である。$H$ に格納されていない任意の正整数 $x$ に対して、Search(x) 内で return が実行される瞬間に $i=2$ となる確率を求めよ。

(エ)

Hash(x,i) を次のように変更する。ただし、$a$ は 1 以上の整数である。

$$\operatorname{Hash}(x,i)=\bigl(x+i(1+a(x\bmod 2))\bigr)\bmod 6.$$

1. $a=1$ のとき、$\operatorname{Hash}(3,0),\ldots,\operatorname{Hash}(3,5)$ の値を答えよ。
2. 任意の正整数 $x$ について、$i=0,1,\ldots,5$ の探査で配列 $H$ の全要素を調べられる最小の $a$ を求めよ。なお、$y$ と $z$ が互いに素であるとき、$(x+iy)\bmod z$ は $i=0,\ldots,z-1$ に対して $0,\ldots,z-1$ の並べ替えとなることを用いてよい。

Kai

(1)

• (ア) 誤。ハッシュ値に応じて格納位置が決まるため、全データが一つの連続領域に入るとは限らない。
• (イ) 正。空要素が少なく、すなわち負荷率が高くなるほど、衝突後に必要な探査回数が増えやすい。厳密な回数はデータの配置にも依存する。
• (ウ) 正。衝突がなければ、ハッシュ値の計算と 1 回の配列アクセスで格納・探索できる。
• (エ) 誤。線形探査などの衝突解決法を用いれば格納できる。
• (オ) 誤。最悪の場合は配列の全要素を調べるため、時間計算量は $\Theta(n)$ となる。

したがって、

$$\boxed{\text{(ア) 誤、(イ) 正、(ウ) 正、(エ) 誤、(オ) 誤}}$$

である。

(2)

(ア)

線形探査で調べる添字を順に追う。

$x$	調べる添字	返り値	return 時の $i$
3	$3$	$3$	$0$
9	$3,4,5$	$5$	$2$
4	$4,5,0,1$	$-1$	$3$
8	$2,3,4,5,0$	$0$	$4$

よって、

$$\boxed{(3,0),\ (5,2),\ (-1,3),\ (0,4)}$$

である。各組は「返り値、$i$」の順である。

(イ)

空要素を発見したとき、その添字 $j$ に $x$ を格納して $j$ を返す。6 箇所を探査しても空きがなければ失敗とする。したがって、

(a) H[j] = ∅        : (F)
(b) H[j] <- x       : (H)
(c) j               : (B)
(d) i = 6           : (C)

となる。

(ウ)

最初の二つの探査位置が使用中で、三つ目が空のときに限り、$i=2$ で return が実行される。使用中の 3 要素の選び方は全部で

$$\binom{6}{3}=20$$

通りである。最初の二位置を使用中、三位置目を空と固定すると、残りの使用中 1 要素は他の 3 位置から選べるので 3 通りである。よって、求める確率は

$$\boxed{\frac{3}{\binom{6}{3}}=\frac{3}{20}}$$

となる。

(エ)

1.

$a=1$、$x=3$ では $x\bmod2=1$ なので、探査幅は $1+a=2$ である。したがって、

$$\operatorname{Hash}(3,i)=(3+2i)\bmod6$$

より、

$$\boxed{3,5,1,3,5,1}$$

となる。

2.

$x$ が偶数なら探査幅は常に 1 であり、6 要素すべてを探査できる。$x$ が奇数なら探査幅は $1+a$ であるため、全要素を探査する必要十分条件は

$$\gcd(1+a,6)=1$$

である。$a=1,2,3$ では探査幅がそれぞれ $2,3,4$ となり 6 と互いに素ではない。$a=4$ では探査幅が 5 となり、$\gcd(5,6)=1$ である。したがって、

$$\boxed{a=4}$$

が最小である。

検算

プログラムで Search をそのまま実行し、$(3,0),(5,2),(-1,3),(0,4)$ を確認した。また、使用中位置の $\binom{6}{3}=20$ 通りを全列挙すると、$i=2$ で失敗する配置は 3 通りであった。さらに $a\ge1$ を順に調べると、すべての偶数・奇数 $x$ について 6 添字を一度ずつ探査できる最小値は $a=4$ となった。

Reference

• 2023年度 専門試験問題公開のお知らせ