Python一日一練17----ハッシュ検索

紹介する
ハッシュ検索は、データ要素の記憶アドレスを計算することによって検索する方法である.
例えば、「5」は保存する数であり、ハッシュ関数に捨てられ、ハッシュ関数は「2」を返してくれる.このときの「5」と「2」は対応関係を確立し、この関係はいわゆる「ハッシュ関係」であり、実際の応用では「2」はkeyであり、「5」はvalueである.
ハッシュは2つの原則を守らなければなりません:①:keyはできるだけ分散して、つまり私は1つの“6”と“5”をなくしてあなたにあげて、あなたはすべて1つの“2”を返して、それではこのようなハッシュ関数は完璧ではありません.②:ハッシュ関数はできるだけ簡単です.つまり、「6」をなくしてあげます.ハッシュ関数は1時間やってからくれません.これもよくありません.
一般的なハッシュ関数の構築方法:

直接アドレス法:分かりやすく、key=Value+C;この「C」は定数です.Value+Cは実は簡単なハッシュ関数です.

除算余剰法:分かりやすく、key=value%C;説明は同じです.

デジタル分析法:これは面白いですね.例えば、value 1=112233、value 2=112633、value 3=119033のグループがあります.このような数について、分析数の間に2つの数が変動しています.他の数は変わりません.では、keyの値をとるとkey 1=22、key 2=26、key 3=90になります.

平方取中法.ここでは無視し,名を見て意を知る.

折り畳み法:value=135790のように興味深い.keyは2桁のハッシュ値であることが要求される.では、valueを13+57+90=160に変更し、高位「1」を削除します.このときkey=60、ははは、これが彼らのハッシュ関係です.このような目的は、keyが各valueに関連して、「ハッシュアドレス」ができるだけ分散する目的を達成することです.・

2つの異なるデータ要素のハッシュ値が同時になると、競合が発生します.衝突を解決するためによく使われる手法は2つあります.

オープン・アドレス・メソッド:2つのデータ要素のハッシュ値が同じ場合、ハッシュ・テーブルで後に挿入されたデータ要素の別のテーブル・アイテムが選択されます.プログラムがハッシュ・テーブルを検索すると、最初の対応するハッシュ・テーブル・アイテムに検索要件に合致するデータ要素が見つからない場合、プログラムは検索要件に合致するデータ要素が見つかるか、空のテーブル・アイテムに遭遇するまで検索を続行します.

リンク法:ハッシュ値が同じデータ要素をチェーンテーブルに格納し、ハッシュテーブルを検索する過程で、このチェーンテーブルを検索するときは、線形検索方法を採用する必要があります.

コード#コード#

#coding=utf-8
__author__ = 'a359680405'

#            
def myHash(data,hashLength,):
    return data % hashLength
#       
def searchHash(hash,hashLength,data):
    hashAddress=myHash(data,hashLength)
   #  hashAddress  ，      ，         
    while hash.get(hashAddress) and hash[hashAddress]!=data:
        hashAddress+=1
        hashAddress=hashAddress%hashLength
    if hash.get(hashAddress)==None:
        return None
    return hashAddress

#       
def insertHash(hash,hashLength,data):
    hashAddress=myHash(data,hashLength)
    #  key           ，       
    while(hash.get(hashAddress)):
        #      
        hashAddress+=1
        hashAddress=myHash(data,hashLength)
    hash[hashAddress]=data

if __name__ == '__main__':
    hashLength=20
    L=[13, 29, 27, 28, 26, 30, 38 ]
    hash={}
    for i in L:
        insertHash(hash,hashLength,i)
    result=searchHash(hash,hashLength,38)
    if result:
        print("     ，     ",result)
        print(hash[result])
    else:
        print("      ")

時間複雑度O(1)
本文の住所http://blog.csdn.net/a359680405/article/details/51152084