阐述以下概念 1、顺序查找： 2、折半查找： 3、哈希函数： 4、冲突及处理：

1、顺序查找：也称线性查找，是一种基础的查找算法。它从数据结构的起始位置开始，依次遍历每一个元素，直到找到目标元素或者遍历完整个数据结构为止。

2、折半查找：也称二分查找，是一种高效的查找算法。它要求数据结构中的元素已经按照一定的顺序排列，然后每次将查找区间缩小一半，直到找到目标元素或者确定目标元素不存在为止。

3、哈希函数：是一种将任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出（又叫做哈希值， hash值），该输出值具有不可逆性、唯一性和固定性。

4、冲突及处理：哈希函数可能会出现不同的输入得到相同的输出，这种情况称为哈希冲突。哈希冲突会影响哈希表的查找效率，因此需要采取一些方法来处理冲突，如开放地址法、链地址法等。其中，开放地址法是指当哈希冲突发生时，继续探测哈希表中的下一个空闲位置，直到找到一个空闲位置为止；链地址法是指将哈希表中的每个位置都设置为一个链表，当哈希冲突发生时，将元素插入到对应位置的链表中。

相关问题

1010: 折半查找的实现

折半查找（Binary Search）是一种在有序数组中查找特定元素的算法，其基本思想是将查找区间不断折半缩小，直到找到目标元素或者查找区间为空为止。

以下是折半查找的实现代码：

// 在有序数组 arr 中查找元素 x，返回元素所在下标（从 0 开始计数），若不存在返回 -1
int binarySearch(int arr[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) {
            return mid;
        } else if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

其中，变量 `left` 和 `right` 分别表示查找区间的左右边界，初始时左边界为 0，右边界为数组长度减一。在每一轮循环中，首先计算中间位置 `mid`，然后将目标值 `x` 与 `arr[mid]` 进行比较，若相等则直接返回下标 `mid`，否则根据大小关系更新左右边界，继续缩小查找区间。如果最终查找区间变为空，则说明目标值不存在于数组中，返回 -1。

编写具体函数实现查找表的顺序查找与折半查找

顺序查找函数实现：

def sequential_search(arr, target):
    """
    顺序查找
    :param arr: 待查找的数组
    :param target: 目标值
    :return: 目标值在数组中的下标，若不存在则返回-1
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

折半查找函数实现：

def binary_search(arr, target):
    """
    折半查找
    :param arr: 待查找的数组（已有序）
    :param target: 目标值
    :return: 目标值在数组中的下标，若不存在则返回-1
    """
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return -1

以上是 Python 语言的实现，其他编程语言的实现也是类似的。