[数据结构与算法]设计一个新的数据结构，可以等概率地随机获得字典中的键

初步思路：新数据结构维护一个列表，维护添加进来的键

每次给数据结构设值和删除的时候，额外维护一个列表，从列表中添加和删除键。在做随机取键的时候，从该列表中随机选一个键。
但额外维护的列表，会导致这个数据结构在删除值的时候，无法O(1)地从列表中删除指定的键。

新数据结构使用字典，映射索引到键

核心的思路是，在每次设值的时候，将该键映射到一个值。然后在每次删除键的时候，能在O(1)时间内找到这个映射值。
每次设值的时候可以将键映射到当前字典的大小，在删除任意键N的时候，找到该键的映射值N1，将当前映射到字典大小M1的键M，将其映射值M1改为N1。
参考代码如下：

class RandomChoiceDict(object):
    def __init__(self):
        self.mapping = {}  # wraps a dictionary e.g. {'a':'Alice', 'b':'Bob', 'c':'Carrie'}
        # the arbitrary mapping mentioned above
        self.idToKey = {}  # e.g. {0:'a', 1:'c' 2:'b'} or {0:'b', 1:'a' 2:'c'}, etc.
        self.keyToId = {}  # needed to help delete elements
        
	def __getitem__(self, key):  # O(1)
        return self.mapping[key]

    def __setitem__(self, key, value):  # O(1)
        if key in self.mapping:
            self.mapping[key] = value
        else: # new item
            newId = len(self.mapping)
            self.mapping[key] = value
            # add it to the arbitrary bijection
            self.idToKey[newId] = key
            self.keyToId[key] = newId

    def __delitem__(self, key):  # O(1)
        del self.mapping[key]  # O(1) average case
                               # see http://wiki.python.org/moin/TimeComplexity
        emptyId = self.keyToId[key]
        largestId = len(self.mapping)  # about to be deleted
        largestIdKey = self.idToKey[largestId]  # going to store this in empty Id

        # swap deleted element with highest-id element in arbitrary map:
        self.idToKey[emptyId] = largestIdKey
        self.keyToId[largestIdKey] = emptyId

        del self.keyToId[key]
        del self.idToKey[largestId]
        
    def randomItem(self):  # O(1)
        r = random.randrange(len(self.mapping))
        k = self.idToKey[r]
        return (k, self.mapping[k]

参考

https://www.codenong.com/10840901/