1

私は 1 年生のコンピューター サイエンスの学生です。インタビューのためにハッシュテーブルを独学しようとしています。それらについてのいくつかの記事を読んだ後、私はそれを理解したかどうかを確認する最良の方法は、Python で独自のハッシュ テーブルを実装することだと思いました。それが私がやったことです。誰かがそれを見て、あなたの考えを教えてくれませんか？ハッシュテーブルで何をしようとしているのかを正しく理解できましたか?

storage_array = []

def show_menu():
    menu_option = int(raw_input("Enter 1 to store data, Enter 2 to retrieve data: "))
    if (menu_option == 1):
        store_data()
    elif (menu_option == 2):
        retrieve_data()

def store_data():
    key_for_data = raw_input("Please enter the key for the data you want to store: ")
    actual_data = raw_input("Please enter the data you want to store: ")
    ascii_count = generate_hash(key_for_data)
    print ascii_count
    storage_array[ascii_count] = actual_data
    print "The data:'", actual_data, "'has been stored at index:'", ascii_count, "' which is the ascii count of:'", key_for_data, "'"
    show_menu()

def retrieve_data():
    key_for_data = raw_input("Enter the key for the data you want to retrieve: ")
    ascii_count = generate_hash(key_for_data)
    if (storage_array[ascii_count] == None):
        print "No data was stored under this key"
    else:
        print "The data you requested for key:'", key_for_data, "'with ASCII count:'", ascii_count, "' is:'", storage_array[ascii_count], "'"
    show_menu()

def generate_hash(input):
    character_list = list(input)
    ascii_count = 0
    for character_index in range(0,len(character_list)):
        ascii_count += ord(character_list[character_index])
    return ascii_count

def initiate_list():
    for repeat_index in range(0,1000):
        storage_array.append(None)
    print "List initiated with index's to 1000"

initiate_list()
show_menu()


##Or is it meant to hash the key like a dictionary and then store
##the value for that key in the hashed value in the hash table?
4

3 に答える 3

2

一般的な概念が正しいようです。ハッシュ テーブルは任意のキーを受け取り、特別なメソッドを介して配列のインデックスに変換します。

いくつかのポイント：

最初に、そして最も重要なこと: キーの ord() の合計が 1000 より大きい場合、generate_hash 関数は無効なインデックスを返す可能性があります。

これを修正するには、generate_hash を return にしascii_count % 1000ます。意味がわからない場合は%、モジュラス演算子を読んでください (心配しないでください。それほど複雑ではありません)。

次に、これも重要です。次の 2 つのキーを使用するとどうなるか考えてみてください:abとba. あなたがしていることは必ずしも間違っているわけではありませんが、異なるキーが衝突したときのハッシュ テーブルの動作を理解することは重要です。

第三に、それほど重要ではありません: for ループは、C/C++ のように機能する必要はありません。あなたは変えることができます

for character_index in range(0,len(character_list)):
        ascii_count += ord(character_list[character_index])

に

for character in character_list:
        ascii_count += ord(character)

Python の for ループはかなり凝っています :)

全体として、それは素晴らしいです！

于 2012-11-25T23:52:52.460 に答える
0

ハッシュ関数（同じ入力に対して同じハッシュを生成すると仮定）があり、キーのハッシュ関数から生成されたハッシュを配列へのインデックスとして使用して、キーに関連付けられたデータにアクセスするため、はい、表示されますハッシュテーブルの要点があります。

心に留めておくべき良いことは、入力に対して高速に動作し、衝突 (2 つのキーが同じハッシュを生成する場合) を合理的に回避するのに十分に適切に記述されたハッシュ関数を選択する必要があるということです。

于 2012-11-25T23:46:35.470 に答える
0

関数generate_hash()は、テーブル外のハッシュ値を返す可能性があります。

また、衝突に対処するための戦略も必要です。最終的にハッシュテーブルとの衝突は常に発生します。

generate_hash 関数はもっと簡単に書くことができます

def generate_hash(s):
    return sum(ord(c) for c in s)

モジュラス 1000 を使用すると、ハッシュ値が表から外れる問題を回避できます

def generate_hash(s):
    return sum(ord(c) for c in s)%1000

retrieve_data()バグがあります。衝突について考えたことがないので、キー「ad」で何かを保存すると、キー「cb」を使用してそれを取得できます

于 2012-11-25T23:46:40.680 に答える