檢查我的哈希表

我是一年級計算機專業的學生的理解。我正試着自己教一個散列表來面試。在閱讀了關於它們的幾篇文章之後，我認爲看看我是否能夠實現它的最好方法是在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?

來源

2012-11-25 Sam Heather

請發佈代碼，不要發佈屏幕截圖。 – alex

爲什麼？屏幕截圖不僅僅可以用來檢查對概念的理解嗎？ –

您發佈了一張文字圖片。改爲發佈文字。 – vicvicvic

看起來你有一般概念正確的檢索。哈希表採用任意鍵，並通過一些特殊的方法將其轉換爲數組的索引。

有幾點：

首先，也是最重要的：你的generate_hash函數可以返回的索引是無效的，如果在ord（關鍵的總和）s大於1000

要解決此問題，請使用generate_hash返回ascii_count % 1000。如果你不知道什麼%手段，去模運算符讀了（別擔心，這不是太複雜）。

第二個，也很重要：考慮如果您使用以下兩個鍵會發生什麼：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-25 23:52:52

非常感謝！ –

你有一個散列函數（我假設產生了相同的輸入相同的哈希），並使用從您的關鍵字作爲索引散列函數產生的散列到您的數組訪問與相關的數據關鍵，所以是的，看起來你有散列表的要點。

好事要記住的是，你應該選擇在輸入快速運行，並寫入不夠好，合理的避免碰撞（情況兩個鍵產生相同的散列）散列函數。

來源

2012-11-25 23:46:35 BoredBlazer

與下面相同：碰撞，謝謝。 RE：'快速運作'，我有什麼快速運作的？我該如何解決某些在這種情況下不會出現的問題？ –

散列函數的「最終特徵」是它們具有（大部分）O（1）查找時間，這意味着獲取值所需的時間不取決於散列表中的事物數量。「快速運營」主要是其延伸。人們使用哈希表是因爲它們*快*，並且大量時間用於優化創建索引的哈希函數。在這種情況下，我不會過分擔心你的散列函數的速度。 –

你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()有一個bug之外的問題。因爲你有沒有想過碰撞，如果我存儲與鍵「廣告」的東西，我可以使用鍵「CB」

來源

2012-11-25 23:46:40

嗨。感謝你的回答。試圖首先得到一個真正的基本理解，但是 - 謝謝。 –

它可能更糟糕的提到散列會有很多衝突。例如，'generate_hash（「ab」）'將與'generate_hash（「ba」）'相同。 – Blckknght

@Blckknght，只是因爲密鑰空間非常小，它會有很多衝突。碰巧有意識地發現與這裏使用的特定散列衝突。 –

檢查我的哈希表

回答

相關問題