小白学算法: 哈希 - 数据结构和算法教程

散列是指使用称为散列函数的数学公式从可变大小的输入生成固定大小的输出的过程。该技术确定数据结构中项目存储的索引或位置。

小白学算法: 哈希 - 数据结构和算法教程_字符串

需要Hash数据结构

互联网上的数据每天都在成倍增加，有效存储这些数据始终是一个难题。在日常编程中，这些数据量可能不是那么大，但仍然需要轻松高效地存储、访问和处理。用于此目的的一种非常常见的数据结构是数组数据结构。

现在问题来了，如果数组已经存在，还需要一个新的数据结构吗！答案就在“效率”二字。虽然存储在数组中需要 O(1) 时间，但搜索至少需要 O(log n) 时间。这个时间看起来很小，但是对于大型数据集来说，它可能会导致很多问题，进而使数组数据结构效率低下。 所以现在我们正在寻找一种可以在恒定时间内（即 O(1) 时间）存储数据并在其中进行搜索的数据结构。这就是哈希数据结构发挥作用的方式。随着哈希数据结构的引入，现在可以轻松地在恒定时间内存储数据并在恒定时间内检索数据。

散列的组成部分

哈希主要包含三个组成部分：

1. 键：键可以是任何字符串或整数，作为哈希函数的输入，该技术确定数据结构中项目存储的索引或位置。 
2. 哈希函数：哈希函数接收输入键并返回称为哈希表的数组中元素的索引。该索引称为哈希索引。
3. 哈希表：哈希表是一种使用称为哈希函数的特殊函数将键映射到值的数据结构。哈希以关联方式将数据存储在数组中，其中每个数据值都有自己的唯一索引。

小白学算法: 哈希 - 数据结构和算法教程_数据结构_02

散列的组成部分

哈希是如何工作的？

假设我们有一组字符串 {“ab”, “cd”, “efg”} 并且我们希望将其存储在表中。 

我们这里的主要目标是在 O(1) 时间内快速搜索或更新表中存储的值，并且我们不关心表中字符串的顺序。因此给定的一组字符串可以充当键，而字符串本身将充当字符串的值，但是如何存储与键对应的值呢？ 

• 步骤1：我们知道哈希函数（这是一些数学公式）用于计算哈希值，该哈希值充当存储该值的数据结构的索引。 
• 第 2 步：那么，让我们分配 
• “a”=1，
• “b”=2，.. 等等，适用于所有字母字符。 
• 步骤3：因此，字符串中所有字符相加得到的数值为： 

• “ab” = 1 + 2 = 3， 
• “CD” = 3 + 4 = 7 ， 
• “efg” = 5 + 6 + 7 = 18  
• 步骤 4：现在，假设我们有一个大小为 7 的表来存储这些字符串。这里使用的哈希函数是key mod Table size中的字符之和。我们可以通过sum(string) mod 7来计算字符串在数组中的位置。
• 第5步：所以我们将存储 
• 3 mod 7 = 3 中的“ab”， 
• 7 mod 7 = 0 中的“cd”，以及 
• 18 mod 7 = 4 中的“efg”。

小白学算法: 哈希 - 数据结构和算法教程_数据结构_03

将键映射到数组的索引

上述技术使我们能够使用简单的哈希函数计算给定字符串的位置，并快速找到存储在该位置的值。因此，散列的想法似乎是在表中存储数据（键，值）对的好方法。

什么是哈希函数？

哈希函数创建键和值之间的映射，这是通过使用称为哈希函数的数学公式来完成的。散列函数的结果称为散列值或散列。哈希值是原始字符串的表示，但通常小于原始字符串。

例如：将数组视为 Map，其中键是索引，值是该索引处的值。因此，对于数组 A，如果我们有索引i，它将被视为键，那么我们只需查看 A[i] 处的值即可找到该值。 只需查找 A[i]。 

哈希函数的应用：

判断一个数组是否是另一个数组的子集

给定两个数组：arr1[0..m-1] 和 arr2[0..n-1]。判断 arr2[] 是否是arr1[] 的子集。两个数组都没有按顺序排列。可以假设两个数组中的元素是不同的。

例子：

输入：arr1[] = {11, 1, 13, 21, 3, 7}, arr2[] = {11, 3, 7, 1}  输出：arr2[] 是 arr1[] 的子集 输入：arr1[] = {1, 2, 3, 4, 5, 6}, arr2[] = {1, 2, 4}  输出：arr2[] 是 arr1[] 的子集 输入：arr1[] = {10, 5, 2, 23, 19}, arr2[] = {19, 5, 3}  输出：arr2[] 不是 arr1[] 的子集 

解法：暴力解法

使用两个循环：外层循环一一选取 arr2[] 的所有元素。内循环线性搜索外循环选取的元素。如果找到所有元素则返回 1，否则返回 0。

下面是上述方法的实现：

＃Python 3程序，用于查找一个数组是否是另一个数组的子集

＃如果arr2 []是arr1 []的子集，则返回1

def isSubset(arr1, arr2, m, n):
	i = 0
	j = 0
	for i in range(n):
		for j in range(m):
			if(arr2[i] == arr1[j]):
				break

		# 如果上面的内部循环根本没有被中断，那么arr2[i]在arr1[]中不存在。
		if (j == m):
			return 0

	# 如果我们到达这里，那么所有 arr2[] 中的元素都存在 在 arr1[] 中
	return 1


if __name__ == "__main__":

	arr1 = [11, 1, 13, 21, 3, 7]
	arr2 = [11, 3, 7, 1]

	m = len(arr1)
	n = len(arr2)

	if(isSubset(arr1, arr2, m, n)):
		print("arr2[] is subset of arr1[] ")
	else:
		print("arr2[] is not a subset of arr1[]")

输出

arr2[] 是 arr1[] 的子集

复杂度分析

时间复杂度： O(m*n) 辅助空间： O(1)

使用排序和二分查找

这个想法是对给定的数组 arr1[] 进行排序，然后对 arr2[] 中的每个元素在排序的 arr1[] 中进行二分搜索。如果未找到该元素则返回 0。如果所有元素都存在则返回 1。

步骤：

给定数组arr1[] = { 11, 1, 13, 21, 3, 7 }和arr2[] = { 11, 3, 7, 1 }。 步骤 1：我们对数组 arr1[] 进行排序，得到 arr1[] = { 1, 3, 7, 11, 13, 21}。 步骤 2：我们将使用二分查找在 arr1[] 中查找 arr2[] 中的每个元素。

• arr2[] = { 11 , 3, 7, 1 }, 11 出现在 arr1[] = { 1, 3, 7, 11 , 13, 21}中
• arr2[] = { 11, 3 , 7, 1 }, 3 出现在 arr1[] = { 1, 3 , 7, 11, 13, 21}中
• arr2[] = { 11, 3, 7 , 1 }, 7 出现在 arr1[] = { 1, 3, 7 , 11, 13, 21}中
• arr2[] = { 11, 3, 7, 1 }, 1 出现在 arr1[] = { 1 , 3, 7, 11, 13, 21}中

当找到所有元素后，我们可以得出 arr2[] 是 arr1[] 的子集。

算法：

该算法非常简单。 

• 对第一个数组 arr1[] 进行排序。
• 在已排序的 arr1[] 中查找 arr2[] 的元素。
• 如果我们遇到 arr2[] 中存在但 arr1[] 中不存在的特定值，则代码将终止，arr2[] 永远不可能是 arr1[] 的子集。
• 否则 arr2[] 是 arr1[] 的子集。

下面是上述方法的代码实现：

def isSubset(arr1, arr2, m, n):
	i = 0

	quickSort(arr1, 0, m-1)
	for i in range(n):
		if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1):
			return 0

	# 如果我们到达这里，那么所有元素
	# arr2[] 中的所有元素都存在于 arr1[] 中
	return 1


def binarySearch(arr, low, high, x):
	if(high >= low):
		mid = (low + high)//2

		if((mid == 0 or x > arr[mid-1]) and (arr[mid] == x)):
			return mid
		elif(x > arr[mid]):
			return binarySearch(arr, (mid + 1), high, x)
		else:
			return binarySearch(arr, low, (mid - 1), x)

	return -1


def partition(A, si, ei):
	x = A[ei]
	i = (si - 1)

	for j in range(si, ei):
		if(A[j] <= x):
			i += 1
			A[i], A[j] = A[j], A[i]
	A[i + 1], A[ei] = A[ei], A[i + 1]
	return (i + 1)

# 实现快速排序
# A[] --> 待排序数组
# si --> 起始索引
# ei --> 结束索引

def quickSort(A, si, ei):
	# 分区索引
	if(si < ei):
		pi = partition(A, si, ei)
		quickSort(A, si, pi - 1)
		quickSort(A, pi + 1, ei)


arr1 = [11, 1, 13, 21, 3, 7]
arr2 = [11, 3, 7, 1]

m = len(arr1)
n = len(arr2)

if(isSubset(arr1, arr2, m, n)):
	print("arr2[] is subset of arr1[] ")
else:
	print("arr2[] is not a subset of arr1[] ")