 增删查改与扩容冲突实战)
Hello 算法精讲哈希表原理、O(1) 增删查改与扩容冲突实战【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇技术指南以《Hello 算法》哈希表章节为骨架讲解哈希表如何通过键key到值value的映射实现 $O(1)$ 级元素查询并沿仓库中的真实源码逐层剖析从语言内置容器的增删查操作、三种遍历方式到手写数组 哈希函数的最小实现最后说清哈希冲突为何必然发生、负载因子与扩容机制如何生效。读完你将能对照 12 种主流语言完成哈希表的初始化、写入、查询、删除与遍历并能动手运行仓库自带的示例代码验证每一个结论。什么是哈希表用映射换取常数级查询哈希表hash table又称散列表。它不再依赖遍历后比较来查找元素而是直接通过键key与值value之间预先建立的映射关系定位数据。具体而言只要向哈希表中输入一个键key就能在 $O(1)$ 时间内取回对应的值value。教材用一个非常直观的例子引入给定 $n$ 个学生每人拥有姓名和学号两项数据。如果希望实现输入学号 → 返回姓名的查询功能只需要把学号作为key、姓名作为value存入哈希表即可。同样的功能用数组或链表也能实现但代价完全不同添加元素仅需将元素追加到数组链表尾部消耗 $O(1)$ 时间查询元素数组链表中数据是乱序的只能遍历所有元素逐个比对消耗 $O(n)$ 时间删除元素需要先线性查询到目标元素再执行删除同样是 $O(n)$ 时间。三种数据结构的效率对比如下操作数组链表哈希表查找元素$O(n)$$O(n)$$O(1)$添加元素$O(1)$$O(1)$$O(1)$删除元素$O(n)$$O(n)$$O(1)$对比可知哈希表把增、删、查、改的时间复杂度全部压到了 $O(1)$这正是它在缓存、索引、去重等高频场景中成为核心数据结构的原因。需要注意的是这个 $O(1)$ 是建立在良好散列与合理扩容策略之上的平均复杂度其前提与边界正是后文哈希冲突与扩容要回答的问题。哈希表常用操作初始化、添加、查询与删除哈希表的常见操作包括初始化、添加键值对、查询键值对和删除键值对。仓库中每个语言目录都提供了对应的可运行示例如 Python 版 hash_map.py、Java 版 hash_map.java、C 版 hash_map.cpp。下面以 Python 为例给出完整可执行代码Driver Code if __name__ __main__: # 初始化哈希表 hmap dict[int, str]() # 添加操作在哈希表中添加键值对 (key, value) hmap[12836] 小哈 hmap[15937] 小啰 hmap[16750] 小算 hmap[13276] 小法 hmap[10583] 小鸭 # 查询操作向哈希表中输入键 key 得到值 value name: str hmap[15937] print(\n输入学号 15937 查询到姓名 name) # 删除操作在哈希表中删除键值对 (key, value) hmap.pop(10583)在上面这段代码里学号就是key姓名就是value键值对在哈希表中一一对应、互不干扰。读者可以在仓库根目录执行python3 codes/python/chapter_hashing/hash_map.py直接看到添加、查询、删除三个阶段的完整输出。《Hello 算法》为这一节提供了 Python、C、Java、C#、Go、Swift、JavaScript、TypeScript、Dart、Rust、Kotlin、Ruby 共 12 种语言的对照实现C 语言未内置哈希表见 array_hash_map.c 的自建方案。各语言在初始化 / 添加 / 查询 / 删除四个动作上的 API 对应关系可汇总如下便于横向迁移语言容器类型添加查询删除Pythondicthmap[key] valuehmap[key]hmap.pop(key)Cunordered_mapK,Vmap[key] valuemap[key]map.erase(key)JavaMapK,V/HashMapmap.put(key, value)map.get(key)map.remove(key)C#DictionaryK,Vmap[key] valuemap[key]map.Remove(key)Gomap[K]Vhmap[key] valuehmap[key]delete(hmap, key)Swift[Key: Value]map[key] valuemap[key]!map.removeValue(forKey:)JavaScriptMapmap.set(key, value)map.get(key)map.delete(key)TypeScriptMapK, Vmap.set(key, value)map.get(key)map.delete(key)DartMapK, Vmap[key] valuemap[key]map.remove(key)RustHashMapK, Vmap.insert(key, value)map.get(key)map.remove(key)KotlinHashMapK, Vmap[key] valuemap[key]map.remove(key)RubyHashhmap[key] valuehmap[key]hmap.delete(key)提醒Rust 的get/remove返回Option如OptionString、OptionString需要先解包再取值Swift 直接取下标的查询返回可选值示例中使用!强制解包。这两处细节体现了容器好用但语言所有权/可选值语义不同的差异动手实现时需格外留意。哈希表的三种遍历方式除了按键取值哈希表还有三种常用的遍历方式遍历键值对、单独遍历键、单独遍历值。仍以 Python 为例# 遍历键值对 Key-Value for key, value in hmap.items(): print(key, -, value) # 单独遍历键 Key for key in hmap.keys(): print(key) # 单独遍历值 Value for val in hmap.values(): print(val)仓库里每种语言都给出了对应的遍历写法可以对照学习其惯用语法C范围for (auto kv : map)取出kv.first/kv.second或用迭代器map.begin()到map.end()遍历Javamap.entrySet()得到键值对集合kv.getKey()/kv.getValue()map.keySet()与map.values()分别遍历键与值C#foreach (var kv in map)访问kv.Key/kv.Value以及map.Keys/map.ValuesGofor key, value : range hmap单循环即可同时拿到键值忽略其一只需写成for key : range hmap或for _, value : range hmapJavaScript/TypeScriptmap.entries()、map.keys()、map.values()三个迭代器注意 JS 侧Map自带插入序语义Dartmap.forEach((key, value) { ... })以及map.keys/map.valuesRustfor (key, value) in map借用遍历map.keys()/map.values()单独遍历Kotlinfor ((key, value) in map)、map.keys、map.valuesRubyhmap.entries.each { |key, value| ... }、hmap.keys.each、hmap.values.eachSwiftfor (key, value) in map以及map.keys/map.values。用数组 哈希函数手写一个最小哈希表理解内置容器很容易让人忽略底层机制。为了看清哈希表为什么这么快我们先考虑最简单的情况只用一个数组来实现哈希表。这里把数组中的每个空位称为桶bucket每个桶可以存放一个键值对。这样一来查询操作就简化为两步——先找到key对应的桶再从桶中取出value。那么如何基于key定位到对应的桶答案是通过哈希函数hash function。哈希函数的作用是把一个很大的输入空间映射到一个较小的输出空间在哈希表中输入空间是所有可能的key输出空间是所有桶也就是数组下标。换句话说只要输入一个key就能用哈希函数算出该键值对在数组中的存储位置。哈希函数的计算过程分为两步先用某种哈希算法hash()算出key的哈希值再将哈希值对桶数量数组长度capacity取模得到该key对应的桶下标index。其公式可概括为index hash(key) % capacity假设数组长度capacity 100、哈希算法取最简单的hash(key) key那么哈希函数就退化为key % 100。下图以学号为key、姓名为value展示了这一工作过程每个学号经过取模后都能唯一落到 100 个桶中的某一个。仓库中的 array_hash_map.py 正是这一思路的完整落地先用Pair类把key与value封装成键值对再让ArrayHashMap维护 100 个桶class Pair: 键值对 def __init__(self, key: int, val: str): self.key key self.val val class ArrayHashMap: 基于数组实现的哈希表 def __init__(self): 构造方法初始化数组包含 100 个桶 self.buckets: list[Pair | None] [None] * 100 def hash_func(self, key: int) - int: 哈希函数 index key % 100 return index def get(self, key: int) - str | None: 查询操作 index: int self.hash_func(key) pair: Pair self.buckets[index] if pair is None: return None return pair.val def put(self, key: int, val: str): 添加和更新操作 pair Pair(key, val) index: int self.hash_func(key) self.buckets[index] pair def remove(self, key: int): 删除操作 index: int self.hash_func(key) # 置为 None 代表删除 self.buckets[index] None这段代码把上文公式完整体现出来hash_func实现index hash(key) % capacity本例中capacity即数组长度 100put用哈希函数定位桶并放入Pairget先定位桶、判空后返回Pair.valremove则将对应桶置空以表示删除。仓库中的 Java 版 array_hash_map.java 与 C 版 array_hash_map.cpp 结构完全一致可作为跨语言对照。哈希冲突必然存在扩容是降低冲突的第一手段上述一个桶存一个键值对的实现有一个前提假设不同的key要散落到不同的桶。但从本质上看哈希函数把所有key构成的输入空间映射到数组所有下标构成的输出空间而输入空间往往远大于输出空间因此理论上一定存在多个输入对应同一个输出的情况——这就是哈希冲突的根源。用上文的哈希函数举例只要key的后两位相同key % 100的结果就必然相同。例如查询学号 12836 与 20336 两个学生时12836 % 100 36 20336 % 100 36两个不同学号被映射到了同一个桶 36。如下图所示结果变成了两个学号指向同一个姓名这显然无法满足一一对应的语义。这种多个输入对应同一输出的现象被称为哈希冲突hash collision。冲突无法从根上消除却可以被显著稀释。容易想到哈希表容量 $n$ 越大多个key落入同一桶的概率就越低、冲突就越少。因此扩容哈希表是降低冲突概率最直接的手段——教材中的例子是扩容前键值对(136, A)与(236, D)发生冲突扩容后二者被分到不同桶冲突随即消失。扩容并非没有代价它有两点显著开销全量迁移类似数组扩容哈希表扩容必须把所有键值对从原表搬到新表本身就很耗时重算位置扩容后容量capacity改变所有键值对都必须用哈希函数重新计算存储位置进一步推高计算成本。正因为扩容昂贵编程语言普遍采用预留足够大容量 阈值触发扩容的策略来避免频繁搬家。这里引出哈希表最重要的概念之一——负载因子load factor定义为元素数量 ÷ 桶数量用来衡量冲突的严重程度也常被当作扩容的触发条件。例如在 Java 中当负载因子超过 $0.75$ 时系统会把哈希表扩容到原来的 $2$ 倍。值得注意的是文档中的这个手写ArrayHashMap只是教学上的最小模型它尚未实现任何冲突处理逻辑一旦发生12836与20336同桶的写操作就会互相覆盖。生产级哈希表需要在冲突发生时怎么办上继续做文章。仓库对此也有完整的进阶实现可供对照阅读hash_map_chaining.pyJava/C/Go 等同名文件采用链式地址让每个桶挂一条链表或红黑树以容纳同桶键值对hash_map_open_addressing.py采用开放寻址冲突后按探测序列寻找下一个空桶simple_hash.py 与 built_in_hash.py展示不同哈希算法对散列质量的影响。这三类内容分别对应文档体系的后续两章——哈希冲突详解与哈希算法它们共同补全了定位桶 → 消解冲突 → 设计好哈希的完整知识闭环。小结与仓库查阅指引回顾本章核心结论哈希表以key → value映射实现 $O(1)$ 平均复杂度的增、删、查、改与数组/链表的 $O(n)$ 查询形成鲜明对比底层结构是桶数组 哈希函数定位公式为index hash(key) % capacity由于输入空间远大于输出空间哈希冲突在理论上必然存在降低冲突依赖提高容量控制冲突的工程抓手是负载因子如 Java 在超过 $0.75$ 时扩容至 $2$ 倍本文手写的ArrayHashMap只负责演示映射与定位真实系统还需链式地址或开放寻址来消解同桶冲突。想要亲手验证本文所有结论的读者可继续在仓库中查看与运行基本操作与遍历Python、Java、C最小哈希表实现Python、Java、C带冲突处理的完整实现链式地址、开放寻址配套教程哈希表章节总览、哈希冲突、哈希算法 与本章小结。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello 算法精讲：哈希表原理、O(1) 增删查改与扩容冲突实战
Hello 算法精讲哈希表原理、O(1) 增删查改与扩容冲突实战【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇技术指南以《Hello 算法》哈希表章节为骨架讲解哈希表如何通过键key到值value的映射实现 $O(1)$ 级元素查询并沿仓库中的真实源码逐层剖析从语言内置容器的增删查操作、三种遍历方式到手写数组 哈希函数的最小实现最后说清哈希冲突为何必然发生、负载因子与扩容机制如何生效。读完你将能对照 12 种主流语言完成哈希表的初始化、写入、查询、删除与遍历并能动手运行仓库自带的示例代码验证每一个结论。什么是哈希表用映射换取常数级查询哈希表hash table又称散列表。它不再依赖遍历后比较来查找元素而是直接通过键key与值value之间预先建立的映射关系定位数据。具体而言只要向哈希表中输入一个键key就能在 $O(1)$ 时间内取回对应的值value。教材用一个非常直观的例子引入给定 $n$ 个学生每人拥有姓名和学号两项数据。如果希望实现输入学号 → 返回姓名的查询功能只需要把学号作为key、姓名作为value存入哈希表即可。同样的功能用数组或链表也能实现但代价完全不同添加元素仅需将元素追加到数组链表尾部消耗 $O(1)$ 时间查询元素数组链表中数据是乱序的只能遍历所有元素逐个比对消耗 $O(n)$ 时间删除元素需要先线性查询到目标元素再执行删除同样是 $O(n)$ 时间。三种数据结构的效率对比如下操作数组链表哈希表查找元素$O(n)$$O(n)$$O(1)$添加元素$O(1)$$O(1)$$O(1)$删除元素$O(n)$$O(n)$$O(1)$对比可知哈希表把增、删、查、改的时间复杂度全部压到了 $O(1)$这正是它在缓存、索引、去重等高频场景中成为核心数据结构的原因。需要注意的是这个 $O(1)$ 是建立在良好散列与合理扩容策略之上的平均复杂度其前提与边界正是后文哈希冲突与扩容要回答的问题。哈希表常用操作初始化、添加、查询与删除哈希表的常见操作包括初始化、添加键值对、查询键值对和删除键值对。仓库中每个语言目录都提供了对应的可运行示例如 Python 版 hash_map.py、Java 版 hash_map.java、C 版 hash_map.cpp。下面以 Python 为例给出完整可执行代码Driver Code if __name__ __main__: # 初始化哈希表 hmap dict[int, str]() # 添加操作在哈希表中添加键值对 (key, value) hmap[12836] 小哈 hmap[15937] 小啰 hmap[16750] 小算 hmap[13276] 小法 hmap[10583] 小鸭 # 查询操作向哈希表中输入键 key 得到值 value name: str hmap[15937] print(\n输入学号 15937 查询到姓名 name) # 删除操作在哈希表中删除键值对 (key, value) hmap.pop(10583)在上面这段代码里学号就是key姓名就是value键值对在哈希表中一一对应、互不干扰。读者可以在仓库根目录执行python3 codes/python/chapter_hashing/hash_map.py直接看到添加、查询、删除三个阶段的完整输出。《Hello 算法》为这一节提供了 Python、C、Java、C#、Go、Swift、JavaScript、TypeScript、Dart、Rust、Kotlin、Ruby 共 12 种语言的对照实现C 语言未内置哈希表见 array_hash_map.c 的自建方案。各语言在初始化 / 添加 / 查询 / 删除四个动作上的 API 对应关系可汇总如下便于横向迁移语言容器类型添加查询删除Pythondicthmap[key] valuehmap[key]hmap.pop(key)Cunordered_mapK,Vmap[key] valuemap[key]map.erase(key)JavaMapK,V/HashMapmap.put(key, value)map.get(key)map.remove(key)C#DictionaryK,Vmap[key] valuemap[key]map.Remove(key)Gomap[K]Vhmap[key] valuehmap[key]delete(hmap, key)Swift[Key: Value]map[key] valuemap[key]!map.removeValue(forKey:)JavaScriptMapmap.set(key, value)map.get(key)map.delete(key)TypeScriptMapK, Vmap.set(key, value)map.get(key)map.delete(key)DartMapK, Vmap[key] valuemap[key]map.remove(key)RustHashMapK, Vmap.insert(key, value)map.get(key)map.remove(key)KotlinHashMapK, Vmap[key] valuemap[key]map.remove(key)RubyHashhmap[key] valuehmap[key]hmap.delete(key)提醒Rust 的get/remove返回Option如OptionString、OptionString需要先解包再取值Swift 直接取下标的查询返回可选值示例中使用!强制解包。这两处细节体现了容器好用但语言所有权/可选值语义不同的差异动手实现时需格外留意。哈希表的三种遍历方式除了按键取值哈希表还有三种常用的遍历方式遍历键值对、单独遍历键、单独遍历值。仍以 Python 为例# 遍历键值对 Key-Value for key, value in hmap.items(): print(key, -, value) # 单独遍历键 Key for key in hmap.keys(): print(key) # 单独遍历值 Value for val in hmap.values(): print(val)仓库里每种语言都给出了对应的遍历写法可以对照学习其惯用语法C范围for (auto kv : map)取出kv.first/kv.second或用迭代器map.begin()到map.end()遍历Javamap.entrySet()得到键值对集合kv.getKey()/kv.getValue()map.keySet()与map.values()分别遍历键与值C#foreach (var kv in map)访问kv.Key/kv.Value以及map.Keys/map.ValuesGofor key, value : range hmap单循环即可同时拿到键值忽略其一只需写成for key : range hmap或for _, value : range hmapJavaScript/TypeScriptmap.entries()、map.keys()、map.values()三个迭代器注意 JS 侧Map自带插入序语义Dartmap.forEach((key, value) { ... })以及map.keys/map.valuesRustfor (key, value) in map借用遍历map.keys()/map.values()单独遍历Kotlinfor ((key, value) in map)、map.keys、map.valuesRubyhmap.entries.each { |key, value| ... }、hmap.keys.each、hmap.values.eachSwiftfor (key, value) in map以及map.keys/map.values。用数组 哈希函数手写一个最小哈希表理解内置容器很容易让人忽略底层机制。为了看清哈希表为什么这么快我们先考虑最简单的情况只用一个数组来实现哈希表。这里把数组中的每个空位称为桶bucket每个桶可以存放一个键值对。这样一来查询操作就简化为两步——先找到key对应的桶再从桶中取出value。那么如何基于key定位到对应的桶答案是通过哈希函数hash function。哈希函数的作用是把一个很大的输入空间映射到一个较小的输出空间在哈希表中输入空间是所有可能的key输出空间是所有桶也就是数组下标。换句话说只要输入一个key就能用哈希函数算出该键值对在数组中的存储位置。哈希函数的计算过程分为两步先用某种哈希算法hash()算出key的哈希值再将哈希值对桶数量数组长度capacity取模得到该key对应的桶下标index。其公式可概括为index hash(key) % capacity假设数组长度capacity 100、哈希算法取最简单的hash(key) key那么哈希函数就退化为key % 100。下图以学号为key、姓名为value展示了这一工作过程每个学号经过取模后都能唯一落到 100 个桶中的某一个。仓库中的 array_hash_map.py 正是这一思路的完整落地先用Pair类把key与value封装成键值对再让ArrayHashMap维护 100 个桶class Pair: 键值对 def __init__(self, key: int, val: str): self.key key self.val val class ArrayHashMap: 基于数组实现的哈希表 def __init__(self): 构造方法初始化数组包含 100 个桶 self.buckets: list[Pair | None] [None] * 100 def hash_func(self, key: int) - int: 哈希函数 index key % 100 return index def get(self, key: int) - str | None: 查询操作 index: int self.hash_func(key) pair: Pair self.buckets[index] if pair is None: return None return pair.val def put(self, key: int, val: str): 添加和更新操作 pair Pair(key, val) index: int self.hash_func(key) self.buckets[index] pair def remove(self, key: int): 删除操作 index: int self.hash_func(key) # 置为 None 代表删除 self.buckets[index] None这段代码把上文公式完整体现出来hash_func实现index hash(key) % capacity本例中capacity即数组长度 100put用哈希函数定位桶并放入Pairget先定位桶、判空后返回Pair.valremove则将对应桶置空以表示删除。仓库中的 Java 版 array_hash_map.java 与 C 版 array_hash_map.cpp 结构完全一致可作为跨语言对照。哈希冲突必然存在扩容是降低冲突的第一手段上述一个桶存一个键值对的实现有一个前提假设不同的key要散落到不同的桶。但从本质上看哈希函数把所有key构成的输入空间映射到数组所有下标构成的输出空间而输入空间往往远大于输出空间因此理论上一定存在多个输入对应同一个输出的情况——这就是哈希冲突的根源。用上文的哈希函数举例只要key的后两位相同key % 100的结果就必然相同。例如查询学号 12836 与 20336 两个学生时12836 % 100 36 20336 % 100 36两个不同学号被映射到了同一个桶 36。如下图所示结果变成了两个学号指向同一个姓名这显然无法满足一一对应的语义。这种多个输入对应同一输出的现象被称为哈希冲突hash collision。冲突无法从根上消除却可以被显著稀释。容易想到哈希表容量 $n$ 越大多个key落入同一桶的概率就越低、冲突就越少。因此扩容哈希表是降低冲突概率最直接的手段——教材中的例子是扩容前键值对(136, A)与(236, D)发生冲突扩容后二者被分到不同桶冲突随即消失。扩容并非没有代价它有两点显著开销全量迁移类似数组扩容哈希表扩容必须把所有键值对从原表搬到新表本身就很耗时重算位置扩容后容量capacity改变所有键值对都必须用哈希函数重新计算存储位置进一步推高计算成本。正因为扩容昂贵编程语言普遍采用预留足够大容量 阈值触发扩容的策略来避免频繁搬家。这里引出哈希表最重要的概念之一——负载因子load factor定义为元素数量 ÷ 桶数量用来衡量冲突的严重程度也常被当作扩容的触发条件。例如在 Java 中当负载因子超过 $0.75$ 时系统会把哈希表扩容到原来的 $2$ 倍。值得注意的是文档中的这个手写ArrayHashMap只是教学上的最小模型它尚未实现任何冲突处理逻辑一旦发生12836与20336同桶的写操作就会互相覆盖。生产级哈希表需要在冲突发生时怎么办上继续做文章。仓库对此也有完整的进阶实现可供对照阅读hash_map_chaining.pyJava/C/Go 等同名文件采用链式地址让每个桶挂一条链表或红黑树以容纳同桶键值对hash_map_open_addressing.py采用开放寻址冲突后按探测序列寻找下一个空桶simple_hash.py 与 built_in_hash.py展示不同哈希算法对散列质量的影响。这三类内容分别对应文档体系的后续两章——哈希冲突详解与哈希算法它们共同补全了定位桶 → 消解冲突 → 设计好哈希的完整知识闭环。小结与仓库查阅指引回顾本章核心结论哈希表以key → value映射实现 $O(1)$ 平均复杂度的增、删、查、改与数组/链表的 $O(n)$ 查询形成鲜明对比底层结构是桶数组 哈希函数定位公式为index hash(key) % capacity由于输入空间远大于输出空间哈希冲突在理论上必然存在降低冲突依赖提高容量控制冲突的工程抓手是负载因子如 Java 在超过 $0.75$ 时扩容至 $2$ 倍本文手写的ArrayHashMap只负责演示映射与定位真实系统还需链式地址或开放寻址来消解同桶冲突。想要亲手验证本文所有结论的读者可继续在仓库中查看与运行基本操作与遍历Python、Java、C最小哈希表实现Python、Java、C带冲突处理的完整实现链式地址、开放寻址配套教程哈希表章节总览、哈希冲突、哈希算法 与本章小结。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考