哈希表平均查找长度，查找失败情况下的计算方式及代码示例

哈希表（也称为散列表）的平均查找长度通常取决于哈希函数的质量以及装载因子（元素数量除以桶的数量）。理想情况下，如果哈希函数均匀分布元素，平均查找长度接近于常数O(1)，表示无论表有多大，查找操作都可以非常快。

当查找失败（即发生冲突，因为两个不同的键映射到同一个哈希地址），常见的处理方式有以下几种：
1. 开放寻址法（Open Addressing）：通过一定的探测序列，如线性探测、二次探测等，在哈希表内找到下一个空位置存储数据，查找时同样按照探测序列查找目标值。
2. 链地址法（Chaining）：每个桶不是一个直接存储元素的位置，而是一个链表，所有哈希到该桶的数据都存储在链表上，查找时沿着链表逐个比较。

以下是使用链地址法的一个简单Python代码示例：

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]  # 初始化一个大小为size的列表列表

    def hash_function(self, key):
        return len(key) % self.size  # 假设key的长度作为哈希值

    def insert(self, key, value):
        index = self.hash_function(key)
        for pair in self.table[index]:  # 如果键已存在，更新值；否则添加新键值对
            if pair[0] == key:
                pair[1] = value
                break
        else:
            self.table[index].append([key, value])  # 插入新节点

    def search(self, key):
        index = self.hash_function(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        return None  # 查找失败返回None

# 示例
ht = HashTable(5)
ht.insert("apple", 1)
print(ht.search("apple"))  # 输出：1

在这个例子中，`search`方法会先计算哈希值，然后检查对应桶的链表是否包含目标键，如果存在则返回对应的值，否则返回`None`。