我正在研究一本书中的哈希算法并遇到了这条线
索引是3 + 2 + 17%10 = 22%10 = 2
[我可以理解,它指的是索引为2,%
是一个提示,但太深奥了,难以理解。
在下面解释该索引来自何处,即是本书的练习
假设您有以下四个适用于字符串的哈希函数:A。对于所有输入,返回“ 1”。 B.使用字符串的长度作为指数。 C.使用字符串的第一个字符作为索引。所以,全部以a开头的字符串被散列在一起,依此类推。 D.每个地图素数的字母:a = 2,b = 3,c = 5,d = 7,e = 11,依此类推上。对于字符串,哈希函数是所有字符的总和对哈希的大小取模。例如,如果您的哈希大小为10,并且字符串是“ bag”,索引是3 + 2 + 17%10 = 22%10 =2。对于以下每个示例,这些哈希函数将提供一个良好的分配?假设哈希表大小为10个插槽。5.5电话簿,其中键是名称,值是电话号码。名称如下:Esther,Ben,Bob和Dan。答案:哈希函数C和D将提供良好的分布。
插槽索引必须是[0,9]范围内的整数。余数函数(针对除数10)以最统一的方式将所有整数映射到该范围。
这里的关键是散列大小为10。这意味着我们有10个存储桶可以存放字符串。因此,对于字符串的分发,其余部分用于确定将字符串降到哪个降压。在此示例中,将存储桶2。