本文共 3298 字，大约阅读时间需要 10 分钟。

一.字典

• 字典的主要特点是一一对应的关系，即存储的是键值对
• 使用数组的方式：[18,‘coderwhy’,1.88],可以通过下标值取出信息
• 使用字典的方式：{‘age’:18,‘name’:‘coderwhy’,‘height’:1.88},可以通过key取出value
• 另外字典中的key是不可以重复的，但是value可以重复，并且字典中的key是无序的
• 有些编程语言将这种映射关系称为字典，而有些编程语言将其称为Map

二.哈希表

1. 哈希表通常是基于数组进行实现的，但是相对于数组，它也有很多优势
   数组目前存在的缺陷如下：
   ~数组进行插入操作时，效率比较低（即后面的数据均需要移位）
   ~数组进行查找操作的效率：
   1)如果是基于索引进行查找操作效率非常高
   2)基于内容查找，效率较低
   ~数组进行删除操作，效率比较低
2. 哈希表可以提供非常快速的插入——删除——查找操作
3. 无论多少数据，插入和删除值需要接近常量的时间，即O(1)的时间级
4. 哈希表的速度比树还要快，基本可以瞬间查找到想要的元素
5. 哈希表相对于数组的不足：
   哈希表中是数据是没有顺序的，所以不能以一种固定的方式（比如从小到大）来遍历其中的元素
   通常情况下，哈希表中的key是不允许重复的，不能放置相同的key，用于保存不同的元素

三.哈希化

哈希化：将大数字转化成数组范围内下标的过程，称之为哈希化

哈希函数：通常我们会将单词转成大数字，大数字在进行哈希化的代码实现放在一个函数中，这个函数称为哈希函数 哈希表：最终将数据插入到的这个数组，对整个结构的封装，称之为哈希表

四.冲突

下面举一个例子说明冲突产生的情况：

现在有50000个单词，我们使用了100000个位置来存储它们，并且通过一种相对比较好的哈希函数来完成，但是依然可能会出现两个单词通过哈希函数得到的数组下标值相同的情况，这种情况我们称其为冲突。

• 冲突不可避免，我们只能解决冲突
• 常见的解决方法有两种：链地址法和开放地址法

五.链地址法

• 链地址法是一种比较常见的解决冲突的方法（也称为拉链法）
• 链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据，而是一个链条
• 这个链条通常使用数组或链表的数据结构
• 若为链表，也就是每个数组单元中存储着一个链表，一旦发现重复，将重复的元素插入到链表的首端或者末端即可
• 当查询时，先根据哈希化后的下标值找到对应的位置，再取出链表，依次查询寻找的数据

那么链条中何时存储数组，何时存储链表呢？

• 数组或链表在链地址中的效率其实差不多
• 因为根据哈希化的index找出这个数组或链表时，通常就会使用线性查找，这个时候数组和链表的效率差不多
• 应对一些需要将新数据放在链条最前面的要求时，最好采用链表，因为数组在首位插入数据是需要所有其他项后移的，链表就没有这样的问题

六.开放地址法

• 开放地址法的主要工作方式是寻找空白的单元格来添加重复的数据
• 比如数字32应该放入下标值为2的位置，但是当前2位置被占领了，按照开放地址法即会把数字32放在数组中的其他空白位置处。探索这个位置有三种方法：①线性探测 ②二次探测 ③再哈希法

1.线性探测

插入数字32：

• 首先32经过哈希化得到index=2，但是在插入时，发现该位置上已经存在数据了
• 那么线性探测就是从index位置+1开始一点点查找合适的位置来放置32
• 空的位置就是合适的位置，倘若index=3为空位置，那么这个时候32就会放在该位置

查询32：

• 首先经过哈希化得到index=2，比较2的位置存放的数据和查询的数值是否相同，相同那么直接返回
• 若不同，则线性查询，从index位置+1开始查找数字32
• 这里需要特别注意，如果数字32之前从未插入，则在查询过程中，当查询到空位置时，就停止
• 因为数字32不可能跳过空位置去其他位置

删除32：

• 在删除操作一个数据项时，不可以将这个位置下标内容设置为null
• 因为将它设置为null可能会影响之后的其他查询操作，所以通常删除一个位置的数据项时，可以将它设置为-1
• 当我们之后看到-1位置的数据项时，就知道要继续查询，但是插入时这个位置可以放置数据

线性探测存在的问题：

• 线性探测的一个比较严重的问题就是聚集
• 比如在没有任何数据的时候，插入的是22-23-24-25-26，那么就意味着下标值2-3-4-5-6的位置都有元素
• 这一连串填充单元就叫聚集
• 聚集会影响哈希表的性能，无论是插入/删除/查询都会有影响
• 比如插入一个32，会发现连续的单元都不允许我们放置数据，并且这个过程中我们需要探索很多次

2.二次探测

• 如果之前的数据是连续插入的，那么新插入的一个数据可能需要探测很长的距离
• 二次探测主要优化的是探测时的步长
• 线性探测，可以看成是步长为1的探测，比如从下标值x开始，那么线性测试就是x+1,x+2,x+3依次探测
• 二次探测，对步长做了优化，比如下标值x开始，x+1^2, x+2^2 , x+3^2
• 这样就可以一次性探测比较长的距离，避免聚集带来的影响

二次探测存在的问题：

• 比如连续插入的是32-112-82-2-192，那么它们依次累加的时候步长是相同的
• 这种情况会导致步长不一的一种聚集

3.再哈希法

• 为了消除线性探测和二次探测中无论步长+1还是步长+平方的问题，还有一种解决方法：再哈希法
• 二次探测算法产生的探测序列步长是固定的：1,4,9,16，依次类推
• 现在需要一种方法：产生一种依赖关键字的探测序列，而不是每个关键字都一样
• 那么，不同的关键字即使映射到相同的数组下标，也可以使用不同的探测序列
• 再哈希法的做法就是：把关键字用另外一个哈希函数，再做一次哈希化，用这次哈希化的结果作为步长
• 对于指定的关键字，步长在整个探测中是不变的，不同的关键字使用不同的步长

第二次哈希化需要具备如下特点：

• 和第一个哈希函数不同（不然还是原来的结果）
• 不能输出为0（否则将没有步长，每次探测都是原地踏步，算法进入死循环）
• 目前已经设计好一种哈希函数
• stepSize = constant - (key % constant)
• 其中constant是质数，且小于数组的容量
• 例如：stepSize = 5 - (key % 5)，其中key为关键字

七.哈希化的效率

• 哈希表中执行插入和搜索操作效率是非常高的
• 如果没有产生冲突，那么效率就会更高
• 如果发生冲突，存储时间就会依赖后面的探测长度
• 平均探测长度以及平均存取时间，取决于填装因子，随着填装因子变大，探测长度也越来越长
• 装填因子 = 总数据项 / 哈希表长度
• 开放地址法的装填因子最大是多少呢？1，因为它必须寻找到空白的单元才能将元素放入
• 链地址法的装填因子呢？可以大于1，因为拉链法可以无限的延伸下去
• 在实际开发中，链地址法相对来说效率是好于开放地址的，所以使用链地址法的情况较多
  因为它不会因添加了某些元素后性能急剧下降，比如在java的HashMap中使用的就是链地址法

八.哈希函数应具备的优点

• 快速的计算
  哈希表的优势在于效率，提高速度的一个办法是让哈希函数中尽量少的出现乘法和除法，因为它们的性能比较低
• 均匀的分布
  无论是链地址法还是开放地址法，当多个元素映射到同一位置的时候，都会影响效率。所以优秀的哈希函数应该尽可能的将元素映射到不同的位置，让元素在表中均匀分布。

九.设计哈希函数

// 1.将字符串转成比较大的数字hashCode// 2.将大的数字hashCode压缩到数组范围之内function hashFunc(str,size){   	// 定义hashCode变量	var hashCode = 0	// 霍纳算法，来计算hashCode的值	for(var i = 0; i < str.length; i++){   		hashCode = 37 * hashCode + str.charCodeAt(i) // 将字母转换成Unicode编码	}	// 取余操作	var index = hashCode % size	return index}

转载地址：http://hhze.baihongyu.com/