哈希(hashing)、哈希函数(Hash Function)、哈希表(Hash Table)、哈希冲突(Hash Collision)

现有长度为7、初始为空的散列表HT，散列函数H(k)=k % 7，用线性探测再散列法解决冲突。将关键字22，43，15依次插入到HT后，查找成功的平均查找长度是( )

A.1.5 B.1.6 C.2 D.3

首先，我们需要了解，什么是哈希？什么是哈希函数？什么是哈希表？什么是哈希冲突？什么是平均查找长度ASL？

哈希(hashing)

即一种方法，通过合理选择哈希函数将关键字(Key)映射到表中一个位置，直接定位数据位置，无需进行比较，避免了逐一遍历，从而加快查找、插入和删除的速度，用时为常数平均时间。这里讲到的表即为哈希表。
1. 哈希函数(Hash Function)
  1. 也称为散列函数，是一种能把输入值影射为输出字符串的算法。哈希函数产生的哈希值具有唯一性，罕见情况下会产生碰撞问题。
2. 关键字(key)
  1. 也就是项的某个部分
  2. 关键字对应的记录存储位置称为哈希地址(Hash Address
  3. 若对于关键字集合中的任一个关键字，经哈希函数映象到地址集合中任何一个地址的概率是相等的，则称此类哈希函数为均匀哈希函数。
    1. 均匀哈希函数(Uniform Hash function)
      1. 使关键字经过哈希函数得到一个“随机的地址”，从而减少冲突。
3. 哈希表(Hash Table)
  1. 也被称为散列表。是一种使用哈希将记录存储在一块连续的存储空间中的表，它是通过关键字值(Key value)直接进行访问的数据结构，底层数据结构是包含一些项的数组。
    1. 根据给定的关键字key，用该表对应的哈希函数求得哈希地址，判断该地址的记录与key是否相同。
      1. 相同
        
        结构为Set(集合)。
      2. 不相同
        
        结构为Map(键值对集合)。
        
        用此哈希表处理冲突的方法来找到下一个哈希地址，直到哈希地址的记录为空或者找到与key值相同的记录为止。
  2. 时间复杂度
    1. 时间复杂度为O(1)。
    2. 通过牺牲一定的存储空间来换取时间上的优势【算法上称为“空间换时间”】。
    3. 查找过程和造表过程基本一致。
      1. 能够在数据库索引‌、缓存‌、词频统计‌中保持高效的性能，极大地提高了数据高效访问、处理的效率。
      2. 但对于有序访问却没有办法应对。
4. 哈希冲突(Hash Collision)
  1. 由于关键码集合通常比地址集合大，有时候会出现不同的键映射到同一个位置的情况，这种情况叫哈希冲突，需要进行处理，均匀地将数据分布到整个哈希表中，有两种处理方法：
    1. ‌开放地址法(Open Addressing)：
      1. 这种方法会在遇到冲突时尝试寻找其他空闲位置存储元素，空间利用率较高，但实现复杂度较大。
        线性探测法
        Hᵢ(key) = ( key + dᵢ ) % p (p≤m) m为哈希表表长
        dᵢ=0，1，2，3，......，m-1
        
        线性探测再散列法
        再散列法
        这种方法会在遇到冲突时尝试更换以下提到的不同的哈希方法计算哈希地址从而解决冲突。
        
        除留余数法【最常用】
        
        H(key) = key % p (p≤m) m为哈希表表长。
        
        如果p选得不好，就很容易出现同义冲突的情况。
        
        同义词(Synonym)
        
        两个标识符经过哈希函数运算后所得的数值相同，即称这两个标识符为该哈希函数的同义词。
        
        随机数法
        
        折叠法
        
        平方取中法
        
        数字分析法
        
        直接寻址法
        
        二次探测法
        Hᵢ(key) = ( key + dᵢ ) % p (p≤m) m为哈希表表长
        dᵢ=1²，-1²，2²，-2²，......，q²，-q²，q≤m/2
        即变成平方的这种，减少冲突的可能性
    2. 链地址法(Separate Chaining)【别名：链式法、分离链接法】：
      1. 每个哈希桶存储一个链表，所有映射到相同位置的键值对都存储在这个链表中。即使多个键映射到同一个桶，它们也可以通过链表组织在一起，避免了哈希表的性能下降‌。
        桶(Bucket)
        也就是哈希表中多个存储记录的位置
        槽(Slot)
        也就是每一个记录包含的多个字段
        
        桶中元素过少
        也就是负载因子过小，会造成空间浪费。
        负载因子【也称为加载密度(Loading Factor)，一般用α表示】
        α=标识符使用数目/(每一个桶里面的槽数×桶的个数)
        
        桶中元素较多
        也就是负载因子过大，容易导致冲突。
        桶溢出
        经过哈希函数运算后桶满了，就会发生桶溢出。
        
        链表
        可以动态调整指针进行扩展，无需预先确定大小，当发生冲突时，直接在链表中高效地添加和删除元素，即可以容纳多个发生冲突的键值对‌。
        但链表长度过长，时间复杂度可能退化为O(n)‌1。
        链表中的每个节点需要额外的指针来连接，空间利用率较低。
        需要额外的空间去存储，甚至需要使用其他数据结构。

回到题目，

A.1.5 B.1.6 C.2 D.3

由上可知：

再散列法这种方法会在遇到冲突时尝试更换不同的哈希方法计算哈希地址从而解决冲突。
1. 最常用的莫过于除留余数法
  1. H(key) = key % p (p≤m) m为哈希表表长。
线性探测法的方法如下：
1. Hᵢ(key) = ( key + dᵢ ) % p (p≤m) m为哈希表表长(p≤m) m为哈希表表长
  1. dᵢ=0，1，2，3，......，m-1
2. 其实可以看出用的方法就是除留余数法
故而，线性探测再散列法可以理解为我第一次用了除留余数法，那么遇到冲突了，那我就再散列，也就是再次使用除留余数法，只不过其中的Hᵢ(key) = ( key + dᵢ ) % p 的dᵢ发生了变化，如下：
1. 已知散列函数H(k)=k % 7，
  1. 第1个关键字是22，那么第1次算时dᵢ=0，(22+0)%7=22%7=1
    1. 因为余数=1，所以在下表序号1这里写关键字22
    2. 余数【也就是哈希地址的索引下标】 0 1 2 3 4 5 6
      关键字 22
  2. 第2个关键字是43，又dᵢ=0，1，2，3，......，m-1，那么dᵢ=0时，(43+0)%7=1
    1. 又是余1，结果就冲突了，那么我们就再散列，即后退1位【即右移1位】，即dᵢ=1，故(43+1)%7=2，余数是2，这下不冲突，因为余数=2，所以在下表序号2这里写关键字43
    2. 余数【也就是哈希地址的索引下标】 0 1 2 3 4 5 6
      关键字 22 43
  3. 第2个关键字是15，又dᵢ=0，1，2，3，......，m-1，那么dᵢ=1时，(15+1)%7=2
    1. 又是余2，结果就冲突了，那么我们就再散列，即后退1位【即右移1位】，即dᵢ=2，故(15+2)%7=3，余数是3，这下不冲突，因为余数=3，所以在下表序号3这里写关键字15
    2. 余数【也就是哈希地址的索引下标】 0 1 2 3 4 5 6
      关键字 22 43 15