新手问题 笨方法学 Ruby 中 hash_key (aDict,key) 如何理解?

zix · 2016年08月14日 · 最后由 zix 回复于 2016年08月15日 · 2313 次阅读
def Dict.hash_key(aDict,key)
  return key.hash % aDict.length
end

其中 aDict 是一个数组名称,key 是一个键。 书中说这个函数的作用是给键在 aDict 分配一个容器,这要如何理解呢?

散列的实现是建立一个大数组 big_array, key 传入固定的 hash 函数算出 hash(key) 值作为 index 索引。把 value 存在 big_array[hash(key)] 这个容器里。你问的这个函数就是在做这件事,分配索引位置。

具体到这函数的实现,它通过 key.hash 算出一个 hash 值。由于这个 hash 值可能比你 aDict 这个容器数组的索引范围大,就再用 %(取余) 来映射。

#1 楼 @karloku 嗯 书里 aDict 有 255 个容器。 这种办法不会出现重复分配到一个索引的问题吗?书里没有做这方面的处理

#1 楼 @zix 会的。由于空间有限,任何 hash 算法都会碰到哈希冲突,只是概率的高低。 这书里应该只是简单的做一个简单的 Hash. 真的在学数据结构的时候,处理哈希冲突会有很多策略的。

需要 登录 后方可回复, 如果你还没有账号请 注册新账号