第五章 散列表
本章开头作者用一个雇员的例子, 引出了散列表的好处. 字典就是散列表
- 散列函数总是将同样的输入映射到相同的索引
- 散列函数将不同的输入映射到不同的索引
- 散列函数知道数组有多大，只返回有效的索引
总结一下就是跟字典的键值对形式一样, 键是唯一的, 值是键对应的值。
这章中还提到了缓存的概念, 让我想到了之前看的慕课网视频里面讲到的装饰器缓存的例子, 觉得太神奇了, 还能这么玩!
# coding: utf-8
"""
斐波那契数列: 又称黄金分割数列,
指得是这样一个数列, 1, 1, 2, 3, 5, 8...,
这个数列从第三项开始, 每一项都等于前两项之和。 求数列第n项
"""
# 我们很容易就可以写出这么一个递归函数
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
li = fibonacci(5)
print(li)
# 改进一
def fibonacci(n, cache=None):
if cache is None:
cache = {}
if n in cache:
return cache[n]
if n <= 1:
return n
cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache)
return cache[n]
print(fibonacci(100))
# 改进二
def memo(func):
cache = {}
def wrap(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
return wrap
@memo
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(60))
小结
- 散列表的查找 O(n)、插入 O(1) 和删除 O(1) 速度都很快
- 散列表可用于缓存数据
- 散列表非常适用于防止重复
