编辑“︁哈希函数”︁

{{DISPLAYTITLE:哈希函数}}  
'''哈希函数'''（Hash Function）是计算机科学中用于将任意长度的输入（如字符串、文件或对象）映射为固定长度输出（通常为数字或字符串）的算法。它在[[数据结构与算法]]中扮演核心角色，广泛应用于[[哈希表]]、数据校验、密码学等领域。  

== 基本概念 ==  
哈希函数的核心特性包括：  
* '''确定性'''：相同输入始终产生相同输出。  
* '''高效性'''：计算速度快，时间复杂度通常为O(1)。  
* '''均匀性'''：输出应尽可能均匀分布，减少冲突（不同输入产生相同输出）。  

数学表示为：  
<math>h: U \rightarrow \{0, 1, \ldots, m-1\}</math>  
其中<math>U</math>为输入空间，<math>m</math>为输出范围大小。  

== 常见哈希函数 ==  
=== 除法哈希法 ===  
公式：  
<math>h(k) = k \mod m</math>  
* <math>m</math>通常选择质数以减少冲突。  

=== 乘法哈希法 ===  
公式：  
<math>h(k) = \lfloor m \cdot (k \cdot A \mod 1) \rfloor</math>  
* <math>A</math>为常数（建议取黄金分割比0.618）。  

=== SHA家族（密码学哈希） ===  
用于安全场景，如SHA-256：  
<syntaxhighlight lang="python">  
import hashlib  
hash_object = hashlib.sha256(b'Hello World')  
print(hash_object.hexdigest())  
</syntaxhighlight>  
'''输出'''：  
<pre>a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e</pre>  

== 哈希冲突处理 ==  
当不同输入映射到相同输出时，需通过以下方法解决：  
* '''链地址法'''：用链表存储冲突元素。  
* '''开放寻址法'''：线性探测、二次探测等。  

<mermaid>  
graph LR  
    A[Key1] -->|Hash| B[Index 2]  
    C[Key2] -->|Hash| B[Index 2]  
    B --> D[LinkedList: Key1 -> Key2]  
</mermaid>  

== 实际应用案例 ==  
=== 1. 哈希表快速查找 ===  
Python字典的实现：  
<syntaxhighlight lang="python">  
hash_table = {}  
hash_table["apple"] = 1  
hash_table["banana"] = 2  
print(hash_table.get("apple"))  # 输出: 1  
</syntaxhighlight>  

=== 2. 文件完整性校验 ===  
通过MD5校验下载文件：  
<syntaxhighlight lang="bash">  
md5sum important_file.zip  
</syntaxhighlight>  

== 进阶话题 ==  
* '''布隆过滤器'''：空间效率高的概率数据结构。  
* '''一致性哈希'''：分布式系统负载均衡技术。  

== 总结 ==  
哈希函数是高效数据处理的基石，理解其原理与实现能优化程序性能并解决实际问题。初学者应从简单哈希方法入手，逐步探索密码学哈希与冲突处理策略。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:非线性数据结构]]