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

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

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

共收到 4 条回复

散列的实现是建立一个大数组 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. 真的在学数据结构的时候, 处理哈希冲突会有很多策略的.

#3楼 @karloku 嗯 谢谢了

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