paiza 問題集ハッシュテーブルを使おう JavaScript 解答

ハッシュメニュー【オープンアドレス法・チェイン法・ハッシュテーブルを使おう】

Task

【オープンアドレス法】コード

reader.on('close', () => {
   const H = new Array(10).fill(-1);  // 要素数 10 の配列,初期値は全て -1
   const N = Number(lines[0]);
   for (let i = 1; i <= N; i++) {
      const x = Number(lines[i]);  // 格納するデータ
    // console.log(x);
      let h = x;  // h を x で初期化 
      while (H[h % 10] !== -1) {  // H[h % 10] が -1 でない間
         h++;  // h をh + 1 で上書き
      }
      h %= 10;  // h をh mod 10 で上書き
      H[h] = x;  // H[h] に x を保存
   }
   H.forEach(h => {
      console.log(h);  // H の各値を出力
   });
});

while文で値 (添字) の計算を行っています。

top

問題【STEP: 2】チェイン法

Task

全データを格納したあとのハッシュテーブルの状態を10行出力してね。

【チェイン法】コード

reader.on('close', () => {
   const H = [];
   for (let i = 0; i < 10; i++) {
      H.push([]);  // H に 空の配列を 10個 保存→二次元配列
   }
   const N = Number(lines[0]);
   for (let i = 1; i <= N; i++) {
      const x = Number(lines[i]);  // 格納するデータ
      // console.log(x);
      const h = x % 10;  // h = x のハッシュ値
      H[h].push(x);  // H[h] に x を保存
   }
   H.forEach(h => {
      console.log(...h);
   });
});

ハッシュ値が重複した場合は同じ場所に複数のデータを保存。

top

問題【FINAL】ハッシュテーブルを使おう

Task

全クエリを処理した後ハッシュテーブルの状態を 100 行で出力してね。

【ハッシュテーブルを使おう】コード

reader.on('close', () => {
   const H = [];
   for (let i = 0; i < 100; i++) {
      H.push([]);
   }
   const [a, b] = lines[0].split(' ').map(Number);
   const q = Number(lines[1]);
   for (let i = 2; i < q + 2; i++) {
      const [Q, x] = lines[i].split(' ').map(Number);  // x = 格納するデータ
      const h =  (a * x + b) % 100;  // h = ハッシュ値
      switch (Q) {  // Q が…
      case 1:  // 1 なら…
         H[h].push(x);  // H[h]. に x を保存
         break;
      case 2:  // 2 なら…
         console.log(H[h].includes(x) ? 'Yes' : 'No');  // H[h] に x が含まれるかどうか判定
         break;
      }
   }
   H.forEach(h => {
      console.log(...h);
   });
});

青字の部分をconst H =new Array(100).fill([]);に書き換えるとなぜかエラーになりました何故？？(´·ω·`)。

top