散列表

必看：来吧！一文彻底搞定哈希表！

进阶：哈希表_百度百科 (baidu.com)

简介

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

概念：

• 一种功能强大的数据结构，其操作速度快，还能以不同的方式建立数据模型
• 一种包含额外逻辑的数据结构
• 也被称为散列映射、映射、字典和
  关联数组
• 散列表的查找、插入和删除速度都非常快

应用：

• 查找（模拟映射关系）
• 防止重复
• 用作缓存

冲突

什么是冲突

冲突很糟糕，应使用可以最大限度减少冲突的散列函数

避免方法：

1. 较低的填装因子
   • 填装因子越低，发生冲突的可能性越小，
     散列表的性能越高
   • 经验：一旦填装因子大于0.7，就调整散列表的长度
   • 虑到调整长度所需的时间，散列表操作所需的时间也为O(1)
2. 良好的散列函数
   • 良好的散列函数让数组中的值呈均匀分布
   • 糟糕的散列函数让值扎堆，导致大量的冲突
   • 散列函数的结果必须是均匀分布的，这很重要。它们的映射范围必须尽可能大。最糟糕的散列函数莫过于将所有输入都映射到散列表的同一个位置

散列函数

1. 散列函数总是将同样的输入映射到相同的索引。
2. 散列函数将不同的输入映射到不同的索引。
3. 散列函数知道数组有多大，只返回有效的索引。如果数组包含5个元素，散列函数就不会返回无效索引100

实操

伪散列函数查找商品价格

功能：

1. 添加商品及其价格
2. 输入商品，得到其价格

思路：

1. 使用类存储
2. 获取商品价格方法
   • 通过遍历已有商品得到其价格并返回出去
3. 添加商品方法
   • 通过添加商品将该数据添加到对象中

模拟散列表

该散列表默认按照最高长度为24来进行字符串存储

slots用于初始化散列表时的数据存储

• add方法
  • 得到当前传入值的字符串长度
  • 判断当前长度对应的数组位置是否还未开辟出新的数组，是则开辟出新的内存地址
  • 将当前字符串添加到散列表（slots）中去
• delete方法
  • 从散列表中查找该字符串长度对应的数组位置
  • 获得该元素在该数组（对应字符串长度的数组）中的位置
  • 将该数据从散列表中数组对应的位置删除
• get方法
  • 通过过滤函数（filter）将数据从散列表中取出来，并返回该值