访问Python字典的时间复杂度

Question

我正在编写一个简单的Python程序。

我的程序似乎受字典的线性访问，即使算法是二次运算，其运行时间也呈指数增长。
我使用字典来记忆值。这似乎是一个瓶颈。

我正在散列的值是点的元组。每个点是：（x，y），0 <= x，y <= 50
字典中的每个键是：2-5个点的元组：（（x1，y1），（x2，y2），（x3， y3），（x4，y4））

键被读取的次数比其被写入的次数多。

我是否纠正python dict受到此类输入的线性访问时间的困扰？

据我所知，集合具有对数访问时间的保证。
如何在Python中使用集合（或类似的东西）模拟字典？

编辑 根据请求，这是备注功能的（简化）版本：

def memoize(fun):
    memoized = {}
    def memo(*args):
        key = args
        if not key in memoized:
            memoized[key] = fun(*args)
        return memoized[key]
    return memo

Answer 1

请参阅时间复杂度。python
dict是一个hashmap，因此，如果hash函数不好并导致大量冲突，则它的最坏情况就是O（n）。但是，这是非常罕见的情况，其中添加的每个项目都具有相同的哈希值，因此被添加到同一链中，这对于主要的Python实现而言是
极 不可能的。平均时间复杂度当然是O（1）。

最好的方法是检查并查看正在使用的对象的哈希值。的CPython的字典用途诠释PyObject_Hash（的PyObject * O） ，其是相当于hash(o)。

经过快速检查后，我尚未设法找到两个散列为相同值的元组，这将表明查找为O（1）

l = []
for x in range(0, 50):
    for y in range(0, 50):
        if hash((x,y)) in l:
            print "Fail: ", (x,y)
        l.append(hash((x,y)))
print "Test Finished"

键盘（24小时可用）