[C5][哈希] 散列表（hashtable）

hash -> 散列，排列
(a dish of cooked meat cut into small pieces and cooked again, usually with potatoes)

使用场景：超市商品价格的查找，实现给定一个商品，立刻返回商品价格，这是需要使用散列函数，得到散列表

由此，每次查找商品价格的时间复杂度为O(1)，即查找时间为常数（线性时间），与商品数量无关

1. 散列函数

给定输入 -> 散列函数 -> 给出输出
（商品 -> 函数 -> 价格）

散列函数将输入映射到数字

• 输出必须一致（一对一关系，理想情况）

举例：商品与价格

• 首先，创建一个空数组
• 构建散列函数，将所有商品输入到散列函数，并得到返回值，作为数组的索引
• 在索引处存储物品的价格
• 价格查找时：再次将商品输入散列函数，可直接得到商品价格 O(1)

2. 应用

• 模拟映射关系
• 防止重复
• 缓存/记录数据，以免服务器再加工生成数据

2.1 查找

• 电话薄查找（联系人：联系方式）
• IP地址查找（域名：IP address）这个过程被称为DNS resolution

2.2 防止重复

• 投票记录，当来一个用户名时，判断此人是否已投票

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

  相比于存储于列表，散列表的查找的速度会非常快

2.3 用作缓存

网站缓存：访问facebook

• 向facebook服务器发出请求
• 服务器做一些处理（例如：facebook服务器搜集你朋友最近的活动信息，需要等待几秒），生成一个网页并发送给你
• 你获得一个网页

缓存信息：

• 登录状态时，你可以获得之前访问所保存的页面信息（已缓存信息）
• 未登录时，服务器做一些处理，生成新的页面（无缓存）

缓存的优势：

• 用户可以更快速的浏览网站
• facebook服务器可以减少工作量

缓存是一种常用的加速方式，大型网站都在使用，其数据存储在散列表中

facebook存储缓存信息 {域名：页面数据}

• 请求facebook一个URL
• 检测URL是否在散列表中
• 如果在，返回存储数据（缓存）；否则，服务器处理生成页面

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

3. 冲突 collision

散列表大多数语言都提供实现方式，为了更好的应用，我们需要了解散列表的性能

理想的散列函数，可以将不同的输入映射到数组的不同位置，但实际上，几乎不可能编写出这样的散列函数

冲突

• 即多个输入经过散列函数所得的输出指向同一块内存空间（数组地址）

解决方法

1. 可以在存储位置存储一个链表，存储速度下降，因为查找时需要查找链表，速度随着链表长度的增加而降低（如果散列函数较好，冲突少，长度短）；此外，开始分配的数组空间也可能被浪费

4. 性能

由于哈希冲突的存在，散列表的查找、插入、删除的最糟糕时间均是O(n)线性时间，速度大大降低，因此尽可能的避免冲突至关重要

方法：

• 较低填装因子
• 良好的散列函数

4.1 填装因子

散列表使用数组存储数据，因此你需要计算数组中被占用的位置数

例如初始化5个位置的数组，只有两个位置被元素占用，填装因子为0.4；如果有100个元素，但仅有50个位置，那么填装因子为2，这时需要调整数组长度

Tips：

• 填装因子越小，发生冲突可能性越小，散列表的性能越高；因此，如果大于0.7，建议调整散列表长度
• 但我们尽量不要频繁调整散列表长度，因为也需要时间开销

4.2 良好的散列函数

好的散列函数可以使数组中的值呈均匀分布；而糟糕的散列函数让值扎堆，产生大量冲突

举例：SHA函数