散列表

Posted on | In

散列函数

散列函数总是将相同的输入映射到相同的索引
散列函数将不同的输入映射到不同的索引
散列函数知道数组有多大，只返回有效的索引
利用散列函数和数组创建一种数据结构：散列表。散列表由键和值组成（dict字典是散列表在python中的体现）

散列表用于缓存

  1. 你向facebook的服务器发出请求
  2. 服务器做处理，生成一个网页并将其发送给你
  3. 你获得一个网页
    网站将数据记住，而不再重新计算。
    这就是缓存，具有以下两个有点：
  4. 用户能更快的看到网页
  5. 需要做的工作更少

当你访问页面的时候，网站首先会检查散列表中是否存储了该页面，如果有，就会发送给你缓存的页面；如果没有，就将请求发送给服务器做处理。并且将服务器处理生成的数据保存在缓存中，下次请求相同数据的时候，可以直接从缓存中读取并发送。

1
2
3
4
5
6
7
8
cache = {}
def get_web(url):
  if catch.get(url)：
    return cache[url]
  else:
    data = get_data_from_server(url)
    cache[url] = data
    return data

小结

  • 模拟映射关系
  • 防止重复
  • 缓存/记住数据，以免服务器再通过处理来生成它们

冲突

假如有一个数组，包含了26个位置。使用的散列函数根据字母表分配位置，如果第一个键为apple那么分配到第一个位置，第二个键位banana就分配到第二个位置，但是如果三个键是aid，那么也会分到第一个位置，这个时候就产生了 冲突。此时可以在第一个位置，将两个键存到一个链表，在将链表存储在第一个位置。但是最坏情况下所有的键值都是a字母开头的，那么相当于第一个位置存储了一个很长的链表，但是其他25个位置都没有存储数据造成了浪费。这个时候用散列表存储和用链表存储是一样的。

  • 散列函数很重要，最理想情况下，所有的键均匀地映射到散列表不同的位置。
  • 如果使用的散列函数好，链表就不会很长。

性能

散列表的装填因子 = 散列表包含的元素数 / 位置总数
装填因子越小，散列表分布的越均匀，发生冲突的可能性越小；如果装填因子过大，则需要调整位置长度，在散列表中添加长度。
SHA函数（可以用作散列函数）

小结

编程语言都提供的散列表的实现，不用自己去实现。

  • 可以结合散列函数和数组来创建散列表
  • 使用可以最大限度减少冲突的散列函数
  • 散列表的查找、插入和删除速度都很快
  • 散列表适用于模拟映射关系
  • 一旦装填因子超过0.7， 就该调整散列表的长度
  • 散列表可以用于缓存数据
  • 散列表适用于防止重复