初学算法（一）：哈希算法

一、什么是哈希

哈希算法也被称作散列函数算法，在其核心机制中是一种查找算法。它的基本原理是通过预先定义的方式来实现数据存储与检索过程。它的工作方式通常是将大量数据按照一定的规则转化为另一种形式的数据，并以更便于后续查找的目的将其存储起来。然而，在这种转换过程中可能会导致多个不同的数据被分配到同一个存储位置上——这被称为‘哈希碰撞’现象——从而影响后续的操作效率。为了应对这种情况，在实际应用中通常会采取一些补救措施或优化策略。

1、常见的数据查找算法

（1）线性搜索：最简单的数据检索方法，在一个无序的数据集合中逐项比对目标值直至找到匹配项或遍历完整个集合。由于每次都需要与所有元素进行比较，在处理大规模数据时计算复杂度较高。
（2）折半搜索：通过不断缩小搜索范围来提高效率的方法，在有序序列中找到目标值的位置较为快捷。但该算法仅适用于有序序列，在实际应用中若遇到无序序列还需先对其进行排序处理。
（3）深度优先遍历难以应对规模庞大的数据存储问题。
（4）哈希表查询：该方法凭借其快速的访问速度在现代数据库设计中得到广泛应用。相比其他查询方式，在解决大量散列问题上表现出显著优势。

2、哈希算法基本原理

基于数据量预先配置一个长度为M的数组，并通过一个哈希函数F将输入的数据作为其输入变量来计算出唯一的结果值。这些结果值的范围限定在0至M-1之间。通过函数F即可实现数据对应到数组中的某个索引位置上，并将其存放在该位置上。当查询时同样应用函数F来确定所需数据的位置，并直接访问对应的下标位置获取所需的数据即可完成整个操作流程。

3、举个栗子（此处有图，自行想象）

举个例子来说吧！假设有这么一组数据：4、12、6、10和8都需要存档。我们可以设计一个哈希函数为F(x) = x \mod 7的形式，在这种情况下运用该哈希函数对这些数值进行处理后就得到了如下的哈希表

通过分析得到的数组可以看出，在处理过程中我们将数据除以7取余，并将余数值作为索引将其存入该索引位置。

4、哈希冲突

（1）采用统一设定下的哈希函数进行数据存储和查找操作，在理论上讲这种做法能够实现常数级别的查找效率。
（2）在实际应用场景中通常会遇到大量不同数值的数据存在的情况，在设计哈希函数时很难确保所有输入都能产生唯一的映射结果。
（3）例如当处理的数据量超过一定范围后就会出现多个元素被映射到同一位置的情形这就是所谓的哈希冲突现象。
（4）针对这一问题已经开发出了多种解决方案如链地址法、二次再散列法等包括线性探测再散列和建立公共溢出区等多种方法可供选择。

5、链地址法

（1）链地址法的本质是使用数组加链表的形式，如果每一数据对应的哈希值都是唯一的那么会形成一个数组，但是冲突发生了会形成另一种情况，有多个数据对应一个哈希值，我们把这些相同哈希值的数据放在一个链表中，该链表称作同义词链表，这个链表也称作桶。
链地址法的本质是数组+链表的数据结构
（2）链地址法存储数据的具体过程，先建立一个数组Hash存储所有链表的头指针，由数据通过对应的哈希函数计算出哈希地址，找到对应的链表，建立新的节点存储该数据，并把节点加到链表的最后面或者最前面。

二、哈希算法的实际应用

在给定的一些无序数字中找到两个数让他们的和为N。

1、普通指针解法

我们采用常规的指针逻辑来解决这个问题。
解析 ：在这个例子中第一步我们将数据放到一个数组中 并设定一个目标值target 此时 我们只需在该数组中找出两个数 其和等于目标值 并输出这两个数对应的索引位置。
特别说明：输出索引位置而非索引值 即该数值在数组中的具体位置 可以通过"索引+1"的方式来表示 例如数组第一个元素的位置"索引+1"即为0+1=1的位置。
（1）第一步 在指针算法中由于需要对数组进行排序 所以我们需要先复制一份原始数据 然后再对其进行排序处理。

    def twosum(nums,target):
    res = []                         #存放结果集
    nums2 = nums[:]                  #深拷贝
    nums2.sort()
    #查询两个数使他们和等于target
    return (res[0]+1,res[1]+1)

在第二步骤中，我们已经获得了按顺序排列的一组数值，并初始化了两个指针变量分别为left和right。当这两个指针指向的数值之和正好等于目标值时，则查找过程完成；若两者的总和低于目标值，则说明左侧数据可能偏小，请将左指针向右移动一位；若两者的总和高于目标值，则表明右侧数据可能偏大，请将右指针向左调整一位。

    def twosum(nums,target):
    res = []   
    nums2 = nums[:]   
    nums2.sort()
    left = 0
    right = len(nums2)-1
    while left<right:
        if nums2[left]+nums2[right]==target:
            #通过这两个新数组的下标，找到原数组下标并存到结果集       
        elif nums2[left]+nums2[right] < target:
            left = left+1
        elif nums2[left]+nums2[right] > target:
            right = right-1
     return res[0]+1,res[1]+1

（3）此时我们在新数组中成功找到了两个与目标值相等的元素的索引位置。为了最终确定结果我们需要在原始数组中定位这两个元素的具体位置，并将它们的信息存储到res数组里。下面是最终的代码

    def twosum(nums,target):
    res = []   
    nums2 = nums[:]   
    nums2.sort()
    left = 0
    right = len(nums2)-1
    while left<right:
        if nums2[left]+nums2[right] == target:
            for i in range(0,len(nums)):
                if nums2[left] == nums[i]:    #遍历原数组后，找到下标对应的值等于新数组下标对应的值
                    res.append(i)             #放到结果集中
                    break
            for i in range(len(nums)-1,-1,-1):
                if nums2[right] == nums[i]:
                    res.append(i)
                    break
            res.sort()             #因为原数组中无序，所以结果集中也无序，我们为了方便排序一下
            break
        elif nums2[left]+nums2[right] < target:          
            left = left+1          #指针向右移动
        elif nums2[left]+nums2[right] > target:
            right = right-1        #指针左移
    return res[0]+1,res[1]+1

总结部分

2、哈希解法

分析：我们的目标是找到两个数，并使它们的和等于目标数值。对于每一个给定的数值m来说，在数据集中是否存在另一个数值n= target - m呢？我们可以使用哈希表来记录已经出现过的数值，在处理新的数值时就可以快速查找是否有对应的配对值存在。每当遇到一个新的数值时，则将它加入到哈希表中备用。

    def twonums2(nums,target):
    dict = {}
    for i in range(len(nums)):
        m = nums[i]
        if target-m in dict:          #判定target-m是不是在字典中
            return (dict[target-m]+1,i+1)
        dict[m] = i                   #记录这对键值

（2）总结：可以看出采用哈希方法不仅可以省略排序步骤，并且也不必在原始数组中寻找元素的位置信息。这种方法不仅提升了算法的时间效率，并且使得代码规模得到了显著缩减。因此，在处理类似查询问题时应当优先考虑哈希算法的应用。