[数据结构与算法]数据结构之散列表

散列表：

1.散列函数：

1. 将输入映射到数字 ；
2. 它必须是一致的；
3. 它应将不同的输入映射到不同的数字；
4. 将变量作为输入交给散列函数，根据相应的索引，将值存储到数组中。

2.散列函数的特点：

1. 散列函数总是将同样的输入映射到相同的索引；
2. 散列函数将不同的输入映射到不同的索引；
3. 散列函数知道数组有多大，之返回有效的索引。

3.散列表的应用：

1. 创建电话薄获得电话

phone_book = dict{}
phone_book["jack"] = 878789
phone_book["Tom"] = 678999
print(phone_book["Tom"])

2. DNS解析
3. 做一个投票的小程序。防止重复
4. 用作缓存；网站将数据记住，而不再重新计算。比如你登陆facebook的主页，服务器就会存储起来，不会每次重新生成，并在需要的时候发送给用户。需要把页面URL映射到页面数据

4.冲突
即给两个键分配相同的位置，最简单办法是，在冲突的位置存储一个链表；但是如果链表很长，查询会相当的慢；
所以，散列函数很重要。

5.填装因子
散列表包含的元素数除以位置总数，不大于0.7时，性能较好。良好的散列函数让数组中的值均匀分布