O(1)查找的类型

O(1)查找的类型主要包括哈希表（Hash Table）和数组（Array）。

1. 哈希表（Hash Table）： 哈希表是一种使用哈希函数将键映射到唯一的索引位置的数据结构。通过计算键的哈希值，可以直接定位到存储该键值对的位置，从而实现O(1)的查找操作。

示例代码：

class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [None] * self.size

    def hash_function(self, key):
        return key % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        self.table[index] = value

    def get(self, key):
        index = self.hash_function(key)
        return self.table[index]

# 创建哈希表对象
hash_table = HashTable()

# 插入键值对
hash_table.insert(1, "apple")
hash_table.insert(2, "banana")
hash_table.insert(3, "orange")

# 查找键对应的值
print(hash_table.get(2))  # 输出：banana

2. 数组（Array）： 数组是一种连续存储相同类型元素的数据结构。通过索引的方式，可以直接访问数组中的元素，因此可以实现O(1)的查找操作。

示例代码：

# 创建数组
arr = [None] * 10

# 插入元素
arr[0] = "apple"
arr[1] = "banana"
arr[2] = "orange"

# 查找元素
print(arr[1])  # 输出：banana

需要注意的是，数组的O(1)查找是基于已知索引的情况下，如果需要根据元素的值进行查找，时间复杂度就会变为O(n)。