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)] 这个容器里。你问的这个函数就是在做这件事,分配索引位置。
hash(key)
big_array[hash(key)]
具体到这函数的实现,它通过 key.hash 算出一个 hash 值。由于这个 hash 值可能比你 aDict 这个容器数组的索引范围大,就再用 %(取余) 来映射。
key.hash
#1 楼 @karloku 嗯 书里 aDict 有 255 个容器。 这种办法不会出现重复分配到一个索引的问题吗?书里没有做这方面的处理
#1 楼 @zix 会的。由于空间有限,任何 hash 算法都会碰到哈希冲突,只是概率的高低。 这书里应该只是简单的做一个简单的 Hash. 真的在学数据结构的时候,处理哈希冲突会有很多策略的。
#3 楼 @karloku 嗯 谢谢了