![awk 如何处理哈希图中的冲突?](https://linux22.com/image/207237/awk%20%E5%A6%82%E4%BD%95%E5%A4%84%E7%90%86%E5%93%88%E5%B8%8C%E5%9B%BE%E4%B8%AD%E7%9A%84%E5%86%B2%E7%AA%81%EF%BC%9F.png)
是否awk
使用单独的链接、开放寻址,或者是否有自己的方式来处理哈希图中的冲突?
执行gawk
和nawk
实现相同的算法吗?
谢谢。
答案1
查看https://www.gnu.org/software/gawk/manual/gawk.html#Other-Environment-Variables
这指定了两个“影响 gawk 行为方式”的环境变量。有一个警告,这些是供 gawk 开发人员用于测试和调整的,并且可能会发生变化。
INT_CHAIN_MAX
这指定了 gawk 将在哈希链上维护的预期最大项目数,以管理由整数索引的数组。
STR_CHAIN_MAX
这指定了 gawk 将在哈希链上维护的预期最大项目数,以管理由字符串索引的数组。
因此,gawk 通过链接单个哈希中受影响的完整密钥来管理密钥哈希冲突。
目前尚不清楚当达到这个“最大值”时 gawk 会做什么,因为它无法轻松解析该单链。从其他材料(我现在找不到)我怀疑这些最大值是平均的整个数组的链长度:所以当超过平均值时,它可以分配一个更大的初始哈希,它将重新分配以前的冲突,然后重建所有链。
还知道“所有数组索引都是字符串”。而且,迭代由小整数索引的数组确实按数字顺序迭代(最多可达数千个数量级的限制)。 Gawk 可能比预期更具启发性。例如,它可以将每个数组保留为小整数的直接索引查找,以及其他字符串的散列。