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。如果您不知道是什么%意思，请阅读模数运算符（别担心，它并不太复杂）。

其次，同样重要的是：想想如果你使用以下两个键会发生什么：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

你有一个散列函数（我假设它为相同的输入产生相同的散列）并且你使用你的键上的散列函数产生的散列作为你的数组的索引来访问与键关联的数据，所以是的你有哈希表的要点。

要记住的一件好事是，您应该选择一个在输入上快速运行并且编写得足够好以合理避免冲突的散列函数（两个键产生相同散列的情况）。

于 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 回答