《算法图解》之散列表

原创
2018/08/31 09:46
阅读数 360

第五章讲述散列表,在Python中实现为字典,以散列函数与数组等构成,优点兼具数组与链表,防止重复,可以模拟映射关系。

散列表实现

散列函数 + 数组 实现散列表

散列函数

散列函数是这样的函数,即无论给它什么数据,它都还你一个数字。专业术语来说就是,散列函数“将输入映射到数字”。散列函数有两个特点,一是它必须是一致的,即将同样的输入映射到相同的索引;二是它应将不同的输入映射到不同的索引

冲突

不同输入映射到相同的输出上,这就是冲突。如何处理冲突呢,在相同输出上创建一个链表。

填装因子

散列表包含的元素数/位置总数,填装因子度量的是散列表中有多少位置是空的。一旦填装因子大于0.7,就调整散列表的长度。

散列表用途

查找

创建一个电话簿

phone_book = dict()                                                                
phone_book = {}                                                                    
phone_book['jenny'] = 8675309                                                      
phone_book['emergency'] = 911                                                      
print(phone_book['jenny'])

防止重复

管理一个投票站

voted = {}

def check_voter(name):
    if voted.get(name):
        print('kick them out!')
    else:
        voted[name] = True
        print('let them vote!')

check_voter('tom')
check_voter('mike')
check_voter('mike')

缓存

用作网页缓存

cache = {}
def get_page(url):
    if cache.get(url):
        return cache[url]
    else:
        data = get_data_from_server(url)
        cache[url] = data
        return data

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部