1. 散列表是用数组支持按照下表随机访问数据的特性,源于数组,借助散列函数扩展数组的属性.

2. 散列函数的基本要求

   • 散列函数计算得到的散列值是一个非负整数；
   • 如果 key1 = key2，那 hash(key1) == hash(key2)；
   • 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

3. 散列冲突的解决

   • 开放寻址法

     1. 线性探测:
        插入:经散列函数计算后的得到储存位置被占用,从当前位置依次往后查找,找到空位插入
        查找:散列后得到的位置,对比该位置的元素和要查找的元素是否相等,否则依次往后查找,查找到空位,则不在散列表中. 问题:散列表如何查找,给定key还要给定value?
        删除:不能直接置空,查找的时候遇到空位就说明不在散列中,会有问题.而是标记为deleted,查找时候遇到deleted继续查找.

        缺点:空闲位置少时,探测时间久,最坏情况的时间复杂度为O(n)

     2. 二次探测 探测的步长是原来的平方

     3. 双重散列 使用一组散列函数,用第一个散列函数计算得出的位置被占用,就用第二个散列函数计算,以此类推,直到找到空闲位置.

   • 链表法
     在对应的散列槽位后是一个链表,相同的位置元素在一个链表中.
     插入是O(1),查找和删除是O(k),k为拉表的长度,理想情况k=n/m,n是槽位的个数,m是数据的个数

4. 装填因子

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

装填因子越大,空闲位置越少,冲突越多

---

散列碰撞攻击原理:
基于链表的冲突解决方法,使所有数据散列后都在一个槽里,查询时间复杂度由O(1)退化到O(n)

散列函数设计要求:

1. 设计不能太复杂,减少计算时间
2. 散列函数生成的值要均匀分布且随机

动态扩容:
装载因子超过阈值时,动态扩容.

避免低效的扩容:
问题: 在达到阈值后,插入数据,需要扩容,时间复杂度是O(n),即一次性扩容.
解决: 到达阈值后,只申请空间,不搬移数据.插入时,将新数据插入新散列表,再搬移一个数据到新表.查询,先在新表中查,再在老表中查

开放寻址和链表法的优缺点对比:

• 开放寻址优点:序列化容易,数据都储存在数组中,可以利用cpu缓存加快查询速度.

• 缺点:都在数组中,冲突的代价太大,因此装填因子不能大,浪费内存.删除的操作麻烦.

总结: 适用数据量和装填因子小的情况

• 链表法优点: 可以容忍大装填因子,因为冲突也就是链表变长而已.可以将链表改为其他高效的数据接口,如:跳表,红黑树.

• 缺点: 储存指针,对于小数据,内存消耗翻倍.另外,不连续储存,对CPU缓存不友好. 而对于储存的对象大小远大于指针大小,指针的内存消耗可忽略不计.

总结: 适合储存大对象,大数据量的散列表

---

实现工业级散列表的思路:

1. 散列函数要合适
2. 定义装填因子,要设计动态扩容
3. 要有合适的冲突解决方法. 例如:链表法,拉链过长时,采用红黑树,缩短时,再从红黑树变回链表.

散列表的几种应用:

1. 查找 例如人名是key,电话号是value,例如DNS解析,网址转IP地址
2. 防止重复
3. 缓存 eg:URL和对应的网页

散列表 插入,查找,删除,平均时间复杂度都是O(1)

安全散列函数(SHA)特点:

1. 无法倒推 知道value,推导不出key 应用:储存密码
2. 局部不敏感