Hash Functions: Principles and Applications | 哈希函数原理及其应用

📚 Hash Functions: Principles and Applications | 哈希函数原理及其应用

A hash function is a mathematical algorithm that takes an input (or ‘key’) of arbitrary length and produces a fixed-size output, typically called a hash value, digest, or hash code. In computer science, hash functions underpin many essential data structures and security protocols.

哈希函数是一种数学算法，它将任意长度的输入（或称“键”）转换为固定长度的输出，通常称为哈希值、摘要或哈希码。在计算机科学中，哈希函数是许多重要数据结构与安全协议的基础。

1. What Is a Hash Function? | 什么是哈希函数

Formally, a hash function h maps a domain D of potentially unbounded size to a finite, fixed range of size m. For a given key K, the function returns h(K), which can be used as an index into an array of size m.

从形式上讲，哈希函数 h 将可能无限大的定义域 D 映射到大小为 m 的有限固定值域。对于给定的键 K，函数返回 h(K)，该值可以作为大小为 m 的数组的下标。

h(K) → index in [0, m – 1]

Consider a simple hash function for integer keys: h(K) = K mod m. If m = 10 and K = 47, then h(47) = 7, so the key 47 would be stored at array position 7. The same calculation is repeated every time the key is searched for.

考虑一个简单的整数键哈希函数：h(K) = K mod m。若 m = 10，K = 47，则 h(47) = 7，因此键 47 将被存储在数组的位置 7。每次查找该键时都重复同样的计算。

2. Key Properties of Hash Functions | 哈希函数的核心性质

A good hash function must satisfy several important properties. First, it must be deterministic: the same input always produces the same output. Second, it should be efficient to compute, ideally in O(1) time or O(L) time where L is the length of the input.

良好的哈希函数必须满足若干重要性质。首先，它必须是确定性的：相同的输入总是产生相同的输出。其次，它应当计算高效，理想情况下为 O(1) 时间，或 O(L) 时间，其中 L 是输入长度。

Third, the output must have a fixed length regardless of the input size. Fourth, the outputs should be uniformly distributed across the range, meaning that each index is roughly equally likely to be produced

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）