Help us understand the problem. What is going on with this article?

[Ruby]ハッシュ探索

More than 1 year has passed since last update.

ハッシュ探索とは?

データの「中身」と格納先の「要素」をあらかじめひもづけしておくことで、ごく短時間で探索できるように工夫したアルゴリズム

・探索しやすいように、あらかじめ関数を使ってデータを格納
・格納するのに使った関数を使い、一発でデータを探索

引用: 「アルゴリズムを、はじめよう」 p118

ポイント

格納先の配列は0で初期化。長さは格納前の1.5〜2倍に設定。

探索処理の速さを維持しつつ、メモリ使用量をできるだけすくなくする。このバランスがとれているのが格納データ数の1.5〜2倍とされている。

引用: 「アルゴリズムを、はじめよう」 p127

コード例

hash_search.rb
## 乱数を利用して数列を準備
def prepare_arrayD(length)
    arrayD = []

    length.times do
        arrayD.push(rand(length))
    end

    return arrayD
end

## 格納先の配列(0で初期化)
def prepare_arrayH(length)
    arrayH = Array.new(length*1.5,0)

    return arrayH
end


## ハッシュ探索の実装
def hash_search(length)

    arrayD = prepare_arrayD(length)
    arrayH = prepare_arrayH(length)

    target = rand(length)

    puts "--------------"
    puts "探したい数字:#{target}"

    ## arrayDの各値を関数を利用してarrayHに格納
    arrayD.each do |array|
        i = array % arrayH.size
        arrayH[i] = array
    end

    puts
    puts "arrayD: #{arrayD}"
    puts "arrayH: #{arrayH}"
    puts

    ## arrayHからtargetを探索
    count = 0

    arrayH.each do |array|
        if(array==target)
            puts "#{target}はarrayH[#{array}]にあります"
            break
        else
            if count < arrayD.size
                count += 1
            else
                puts "#{target}はありません"
                break
            end
        end
    end

    puts "--------------"
end

length = 10
hash_search(length)

出力結果

--------------
探したい数字:9

arrayD: [2, 5, 3, 5, 7, 7, 9, 1, 4, 4]
arrayH: [0, 1, 2, 3, 4, 5, 0, 7, 0, 9, 0, 0, 0, 0, 0]

9はarrayH[9]にあります
--------------

編集履歴

2018/12/02 初稿投稿
2018/12/03 一部改行修正

参考資料

伊藤静香 「アルゴリズムを、はじめよう」(インプレスジャパン,2012)

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away