1. hash，一般翻译为散列，是把任意长度的输入通过散列算法变换成固定长度的输出，该输出的值就是散列值。这种转换是一种压缩映射，隐射表达是一种是一一对应的关系，也就是说，散列值的空间通常会小于输入的空间。
  2. 哈希算法不能从结果中去推算出输入，也就是说哈希算法是不可逆的。
  3. 哈希特性：
  4. 1、不可逆，哈希算法可以当作一种加密算法存在。
  5.      MD5就是不可逆的，对比的方式进行校验
  6. 2、计算极快
  7.         20G高清电影，5k文本文件
  9.  哈希的用途：
  10.  1、密码
  11.  2、文件完整的校验
  1. 数组存在不足
  2. 1、数组存在的不足
  3. 插入删除：链表的性能好，查询修改：数组的性能好（如果是基于索引查找效率很高，如果是基于内容查找，效率很低，需要遍历）
  1. 哈希表通常是基于数组实现的，但是相对于数组，他有很多的优势：
  2. 1、它可以提供非常快速的插入-删除-查找操作
  3. 哈希表的结构：就是数组，但是它和数组的不一样的地方是：哈希表对于索引的一种转换，这种转换我们称之为哈希函数。
  4. 重点：有一个哈希函数，通过哈希函数就会把要存储的值能够映射到一个位置，这个位置就是它的下标或者是索引，传一个字符串进来，就会把它映射成为数字
  5. 哈希表是以键值对的形式存储的数据结构，不同点是哈希表的键：是经过散列函数计算得出来的，关键码，每一个关键码对应一个值，我们把这种以 关键字->值 的形式存储数据的数组我们成为哈希表（散列表）
  6. 最简单的哈希函数：取每一个字符的ascii码值相加再模一个数字（取余）

哈希表图示

image.png

  1. 数组里边：如果数组的下标相同，后边添加的就会覆盖前面的，这个叫覆盖
  2. 哈希表：冲突，碰撞，对于不同的要存储的数据经过哈希函数得到的索引有可能相同，这时后面的值也会覆盖掉前面的值
  1. 链地址法：
  2. 开放地址法：寻找空白的位置来放置冲突的数据项
  3. 经过哈希化得到的是index=5，但是在插入的时候，发现这个位置已经有了10，怎么办
  4. index+1的位置，一点点的查找合适的位置来放置35
  1. 线性探测法的缺点
  2. 10,11,12,13,14,15
  3. 下标：0,1,2,3,4,5
  4. 这种一连串的填充单元叫聚集，无论是插入/删除/查询聚集都会影响到性能。

image.png

总结

  1. 哈希类似于数组，以key-value的存储的数据结构，不同点在于哈希表它的key是经过一个哈希函数计算出来的，这个key成为关键码
  3. 哈希表的神奇之处：对于下标的一种变换，这种变换我们称之为哈希函数
  4. 重点：通过一个哈希函数，把要存储的值能够 映射到一个位置，这个位置就是它的下标或者是索引，传一个字符串=>数组的下标
  6. 冲突的问题：索引相同，后添加的会覆盖前面的，这个叫做哈希覆盖
  7. 解决冲突：
  8.     链地址法：数组存储的不是实际的值，存储一个链表用来存储实际数据
  9.   开放地址法：1、线性探测法 2、二次探测（平方探测法）3、再哈希法