【Python】【アルゴリズム】ハッシュ探索法

スカヨハ攻殻こと実写版Ghost In The Shellを観てきました。 士郎正宗先生の原作マンガ、押井守監督の映画版、神山健治監督のSACのどれも好きなのですが、 今回の実写版は正直微妙でした…。 攻殻ファンならニヤリとできるシーンが随所に散りばめられていたので、そこは楽しめましたが。 字幕版より吹き替え版を観るべきだったかもしれません。

ハッシュ探索法

アルゴリズムを、はじめよう

「アルゴリズムを、はじめよう」を読んで、本日はハッシュ探索をPythonで実装してみました。

• hash_store()

  • リストarrayDの各要素をhash_keyで除算した余りをインデックスとしてarrayH(0で初期化)に挿入します。
  • 挿入先にすでにデータが存在する(要素が0)の場合は、インデックスをインクリメントし空いている挿入先を探し続けます。

• hash_search()

  • xをhash_keyで除算した余りをインデックスとして、リストの探索をスタートします。
  • インデックスをインクリメントしていって、対象が見つかるか、要素0が現れるまで探索を続けます。
  • 対象が見つかった場合はインデックスを返し、要素0が現れた場合はNoneを返します。

hash.py

import sys

def hash_store(arrayD, hash_key):
    arrayH = [0 for x in range(0,11)]

    for x in arrayD:
        k = x % hash_key
        while(arrayH[k] != 0):
            k = (k + 1) % hash_key
        arrayH[k] = x

    return(arrayH)

def hash_search(ls, x, hash_key):
    k = x % hash_key
    while(ls[k] != 0):
        if(ls[k] == x):
            return(k)
        else:
            k = (k + 1) % hash_key
    return(None)
        
def main():
    target = int(sys.argv[1])
    hash_key = int(sys.argv[2])
    
    arrayD = [12, 25, 36, 20, 30, 8, 42]

    hash_array = hash_store(arrayD, hash_key)
    print("hash_array:", hash_array)

    print(hash_search(hash_array, target, hash_key))
    
if __name__ == '__main__':
    main()

>python hash.py 42 11
hash_array: [42, 12, 0, 25, 36, 0, 0, 0, 30, 20, 8]
0
>python hash.py 36 11
hash_array: [42, 12, 0, 25, 36, 0, 0, 0, 30, 20, 8]
4
>python hash.py 30 11
hash_array: [42, 12, 0, 25, 36, 0, 0, 0, 30, 20, 8]
8
>python hash.py 19 11
hash_array: [42, 12, 0, 25, 36, 0, 0, 0, 30, 20, 8]
None