Hash table 的几个问题

[fantasycz]

刚看了视频，有几个关于hash table的问题。

1. _load_factor为什么用装饰@Property？@Property有什么特殊的么，不装饰可以么？

2. 第90行，if key in self:。 这里能用in 是应为之前定义了__contains__是吧。

3. 在没有冲突的情况下，同一个hash函数，同一个key值，对于不同大小的hash table，得到的index是一样的么？这是必要条件，还是也可以不一样？比如hash table 的大小是5的时候，在没有冲突的情况下，hash(3) = 2， 那当hash table的大小变成10的时候，hash(3)一定要等于2么？

4. _rehash函数里面， 110行， 如果旧的slot 是empty的，不需要放在新的hash里面么？比如在旧的hash table里第5个slot有数A，又加了一个数B，hash值也是5，冲突，然后经过计算，B被放到了第6个slot。然后我们删掉第5个slot里的A，第五个slot是empty。 这时候rehash一下，第五个slot的状态是unsed。如果查找B，首先计算得到的是5，但是发现slot 5是unused， 会返回None。 所以是不是应该empty的slot也要考虑。

5. 第60行hash(key)，是用了python自带的hash的函数，如果不用python的hash函数，怎么能将所有的key map到数字呢？

[PegasusWang]

1. 不使用 property 也可以，不过每次就需要调用函数来返回。
2. 对的，这里 __contains__ 实现可以使用 in 操作。
3. index 是可以不一样的，目前hash 函数其实适合 hash table 长度有关。
4. 搬迁的过程就是把之前所有有元素的值搬过去，新的 hash 表里得到的下标已经不是原来的值了，被删除的元素就不用考虑了，你直接算B 的hash得到下标的槽就可以找到 b。
5. 可以看下 siphash 的实现，如果你感兴趣可以看下 cpython 里或者 redis hash 的实现。真正的实现还是很复杂的，要考虑不同的数据类型的。

参考：

• https://www.laurentluce.com/posts/python-dictionary-implementation/
• https://stackoverflow.com/questions/2070276/where-can-i-find-source-or-algorithm-of-pythons-hash-function