题目链接1、二和难度：$\color{#00965e}{easy}$知识点1、散列（Hash）函数经典散列函数Times33应用广泛，其核心算法如下：hash(i)=hash(i-1)*33+str[i]Laruence有一篇文章：PHP中的Hash算法-风雪角2.HashCollision处理方法2.1链地址法（拉链法）（广泛使用）使用单向链表来处理散列冲突键；php和java都使用这种方法。优点：处理冲突简单，没有积累；平均搜索长度短；链表中的节点是动态申请的，适用于无法确定构造表长度的情况；节省空间，相对来说zipper方式的指针字段可以忽略，所以比open地址方式更节省空间。方便插入和删除。插入节点应该在链的头部。删除节点更方便。您只需要调整指针，无需调整其他冲突元素。Tips：如果链表过长，查询效率会从O(1)变为遍历链表，效率会降低。这时候可以用树结构代替链表来提高查询效率。（这就引出了另一个知识点：二叉树和二叉查找树），这里就不赘述了。2.2开放寻址法Hi=(H(key)+di)MODmi=1,2,...,k(k<=m-1)其中m为哈希表的长度。di是发生冲突时的增量序列。如果di的值可能是1,2,3,...m-1，则称为线性检测和哈希。如果di为1，则每次碰撞后，向后移动1个位置，称为线性检测和哈希；如果di值可能是1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2),称为二次检测和散列；如果di的值可能是一个伪随机序列。它被称为伪随机检测和重新散列。缺点：容易处理冲突，没有堆积现象；平均搜索长度较短；2.3re-hash方法Rehash当发生冲突时，使用second、third、hash函数计算地址，直到没有冲突为止。缺点：增加计算时间。比如上面的第一个hash就是根据姓氏的首字母进行的。如果有冲突，可以按照姓氏的第二个首字母进行hash，然后是冲突的，第三个，直到没有冲突为止。这种方法不容易产生聚合，但增加了计算时间。2.4建立普通溢出区假设哈希函数取值范围为[0,m-1]，设置向量HashTable[0..m-1]为基础表，设置存储空间向量OverTable[0..v]用于存储冲突记录。解决方法1.跳过暴力双循环；2.哈希表（桶）；对于数组A，构造一个hash，记录第一次遍历时的值和数组下标，遍历过程中先判断hash表中是否已经存在target-A[i]，如果存在则返回直接地;复杂度分析时间复杂度：O(N)，其中N为数组元素个数。对于每个元素x，我们可以在O(1)时间内找到目标-x。空间复杂度：O(N)，其中N是数组中元素的数量。主要是哈希表的开销。C语言没有hashTable结构，所以需要自己实现hashTable（知识点：如何实现hashTable的插入/删除）这里是用PHP的demo代码实现的，其他语言类似，就不赘述了详情在这里；classSolution{/***@paramInteger[]$nums*@paramInteger$target*@returnInteger[]*/functiontwoSum($nums,$target){$len=count($nums);$表=[];$结果=[]；//phparray底层实现是哈希表，这里不像c那样计算最小值的步骤，只是穿梭for($i=0;$i<$len;$i++){//首先判断是否有，是if(isset($table[$target-$nums[$i]])){return[$table[$target-$nums[$i]],$i];}else{//否则hash中的数=>下标$table[$nums[$i]]=$i;}}}}
