awk 计算字符串的哈希

示例

尽管在awk中实现一种标准的哈希算法可能是一项繁琐的任务,但是定义可用作文本文档句柄的哈希函数要容易得多。这种功能很有用的实际情况是为给定名称的项目(例如测试用例)分配简短ID,以便用户可以将简短ID用作对项目的引用,而不是提供其详细描述。

散列函数需要字符转换为数字代码,这是通过使用在脚本的开始初始化查找表来实现的。该散列然后函数使用模算术变换,非常经典的方法来散列计算来计算。

出于演示目的,我们添加了一条规则,用它们的哈希来装饰输入行,但是使用该函数不需要此规则:

BEGIN{
  for(n=0;n<256;n++) {
    ord[sprintf("%c",n)] = n
  }
}

function hash(text, _prime, _modulo, _ax, _chars, _i)
{
  _prime = 104729;
  _modulo = 1048576;
  _ax = 0;
  split(text, _chars, "");
  for (_i=1; _i <= length(text); _i++) {
    _ax = (_ax * _prime + ord[_chars[_i]]) % _modulo;
  };
  return sprintf("%05x", _ax)
}

# Rule to demonstrate the function
#  These comments and the following line are not relevant
#  to the definition of the hash function but illustrate
#  its use.

{ printf("%s|%s\n", hash($0), $0) }

我们将上面的程序保存到文件中hash.awk,并在简短的古典英语书名清单中进行演示:

awk -fhash.awk<<EOF
Wuthering Heights
Jane Eyre
Pride and Prejudice
The Mayor of Casterbridge
The Great Gatsby
David Copperfield
Great Expectations
The Return of the Soldier
Alice's Adventures in Wonderland
Animal Farm
EOF

输出是

6d6b1|Wuthering Heights
7539b|Jane Eyre
d8fba|Pride and Prejudice
fae95|The Mayor of Casterbridge
17fae|The Great Gatsby
c0005|David Copperfield
7492a|Great Expectations
12871|The Return of the Soldier
c3ab6|Alice's Adventures in Wonderland
46dc0|Animal Farm

当应用于我最喜欢的小说的6948条非空白行时,此哈希函数不会产生任何冲突。