编辑“哈希（Hash）”（章节）

== 哈希函数的性质 ==
所有哈希函数都有如下一个基本特性：如果两个哈希值是不相同的（根据同一函数），那么这两个哈希值的原始输入也是不相同的。这个特性是哈希函数具有确定性的结果，具有这种性质的哈希函数称为单向哈希函数。但另一方面，哈希函数的输入和输出不是唯一对应关系的，如果两个哈希值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“哈希碰撞（collision）”，这通常是两个不同长度的输入值，刻意计算出相同的输出值。输入一些数据计算出哈希值，然后部分改变输入值，一个具有强混淆特性的哈希函数会产生一个完全不同的哈希值<ref>[http://www.azillionmonkeys.com/qed/hash.html Hash functions.] by Paul Hsieh</ref>。

典型的哈希函数都有非常大的定义域，比如SHA-2最高接受(2<sup>64</sup>-1)/8长度的字节字符串。同时哈希函数一定有着有限的值域，比如固定长度的比特串。在某些情况下，哈希函数可以设计成具有相同大小的定义域和值域间的单射。在密码学中，哈希函数必须具有不可逆性。

在哈希表中，哈希函数将一个键作为输入。键与数据或记录相关联，用于在数据存储和检索应用中标识它们。键可以是固定长度的（如整数）或可变长度的（如名字）。在某些情况下，键本身就是数据。哈希函数的输出是一个哈希码，用于索引存放数据或记录（或指向它们的指针）的哈希表。

哈希函数可以视为执行以下三个功能：

# '''将可变长度的键转换为固定长度的值'''（通常是机器字长或更小），通过使用诸如加法（ADD）或异或（XOR）等保持奇偶性的操作符进行分组处理；
# '''对键的位进行扰乱'''，使生成的值在键空间中均匀分布；
# '''将键值映射到小于或等于哈希表大小的值'''。

一个好的哈希函数需要满足两个基本属性：计算速度非常快，并且尽量减少输出值的重复（碰撞）。哈希函数通过生成理想的概率分布来提高其效率，使访问时间接近于恒定。然而，高的表负载因子、不利的键集和设计不良的哈希函数可能会导致访问时间接近于与表中项目数量成线性关系。

哈希函数可以设计成在最坏情况下也能提供最佳性能，在高表负载因子下保持良好性能，并在特殊情况下实现键到哈希码的完美（无碰撞）映射。其实现基于奇偶保持位操作（如XOR和ADD）、乘法或除法。

与哈希函数配套的必要机制是'''碰撞解决方法'''，通常使用辅助数据结构（如链表）或系统地探测哈希表中的空槽来解决碰撞问题。