加强哈希表

我们的目的是在不改变哈希表增删改复杂度的前提下，能够按照插入顺序访问键，并且不受扩容缩容。 实现方式：

1. 链表：将这些键值对插入双链表中，每次将键插入table数组时，将键同时添加至链表末端。
   • 这样从head开始遍历就能按照插入顺序访问。
   • 我们可以在O(1)的时间复杂度内：
     • 通过键查找到对应的双链表节点，进而找到对应键的值
     • 插入新的键值对，因为哈希表本身插入操作的时间复杂度为O(1)，且双链表的首尾插入操作时间复杂度也为O(1)
     • 删除指定的键值对，因为哈希表本身删除操作的时间复杂度为O(1)，且双链表删除给定节点的时间复杂度也为O(1)¹
   • 代码实现如下： ```python class MyLinkedHashmap:

   class Node: def init(self, key, value): self.key = key self.value = value self.prev = None self.next = None

   def init(self): self.head = self.Node(None, None) self.tail = self.Node(None, None) self.head.next = self.tail self.tail.prev = self.head self.map = dict()

   def get(self, key): if key not in self.map: return None return self.map[key].value

   def add(self, key, value): if key not in self.map: newNode = self.Node(key, value) newNode.next = self.tail newNode.prev = self.tail.prev self.tail.prev.next = newNode self.tail.prev = newNode self.map[key] = newNode return self.map[key].value = value

   def remove(self, key): if key not in self.map: return oldNode = self.map[key] oldNode.prev.next = oldNode.next oldNode.next.prev = oldNode.prev del oldNode

   def keys(self): keylist = [] p = self.head.next while p != self.tail: keylist.append(p.key) p = p.next return keylist

   if name == “main”: map = MyLinkedHashmap() map.add(“a”, 1) map.add(“b”, 2) map.add(“c”, 3) map.add(“d”, 4) map.add(“e”, 5)

    print(map.keys()) #['a', 'b', 'c', 'd', 'e']
    map.remove("c")
    print(map.keys()) #['a', 'b', 'd', 'e']  ```
   

2. 数组：想要添加一个randomKey()的API，能够在O(1)的时间复杂度内返回随机²键。
   • 在标准数组中实现该功能仅需要使用随机数生成器从[0, size)内生成一个索引即可。
   • 然而，我们的哈希表如果使用线性探测法，其中是可能存在空洞的，随机数如果恰好命中空洞，就会产生错误。
     • 如果我们向左或向右线性查找，找到一个非空元素返回呢？该方法会产生两种错误：1. 不是均匀随机的，沿固定方向查找会导致某一侧元素被选中的概率更大。2. 该算法时间复杂度为O(N)。
     • 如果被选中空洞就重新调用随机数生成，多来几次呢？该算法也不行，时间复杂度依赖随机数，不是O(1)了。
   • 如果哈希表使用拉链法，不仅需要随机一个索引，还需要随机链表中一个节点，这样做每个节点被选中的概率又不一样了。
   • 如果使用keys方法遍历整个table，存入一个数组再随机索引倒是能够使所有键被选中的概率相等，但时间复杂度又会是O(N)。
   • 因此我们新增一个数组来维护哈希表中所有键并以此返回随机键，这样能既保证所有键被选中的概率相同也能维持O(1)的时间复杂度不变：
     • 这样的话remove方法则需要改变，因为不仅需要删除map中的key，还要删除数组中的key，并且需要保证哈希表元素的连续性。因此可以这样：将欲删除的元素交换到数组尾部再进行删除。然而这样做会导致数组中的元素顺序被打乱，但是目前场景下没有顺序要求因此无所谓。

     • import random
       
       class Node:
           def __init__(self, key, value):
               self.key = key
               self.value = value
                       
       class MyArrayHashMap:
           def __init__(self):
               #真实储存键值对的数组
               self.array = []
               #储存key和key的索引
               self.map = {}
                       
           def get(self, key):
               if key not in self.map:
                   return None
               index = self.map[key]
               return self.array[index].value
                   
           def add(self, key, value):
               if key not in self.map:
                   self.array.append(Node(key, value))
                   self.map[key] = len(self.array) - 1
                   return
               index = self.map[key]
               self.array[index].value = value
                       
           def remove(self, key):
               if key not in self.map:
                   return 
               index = self.map[key]
               node = self.array[index]
               #1. 将欲删去元素与末尾元素互换位置
               last = self.array[-1]
               self.array[index] = last
               self.array[-1] = node
                       
               #2. 修改map中对应索引
               self.map[last.key] = index
                       
               #3. 删除数组中最后一个元素
               self.array.pop()
                       
               #4. 删除map中对应键值对
               self.map.pop(node.key)
                       
           def randomKey(self):
               index = random.randint(0, len(self.array) - 1)
               return self.array[index].value
                   
       if __name__ == "__main__":
           map = MyArrayHashMap()
           map.add(1, 1)
           map.add(2, 2)
           map.add(3, 3)
           map.add(4, 4)
           map.add(5, 5)
                   
           print(map.get(1))
           print(map.randomKey())
                   
           map.remove(4)
           print(map.randomKey())
           print(map.randomKey())
       

1. 前文中实现链表时为删除指定索引的链表节点，该操作的时间复杂度为O(N)，因为需要遍历到该索引位置。而在这里我们并不需要遍历，我们直接通过哈希表拿到了键值映射的链表节点，因此直接删除仅需要O(1)的时间复杂度。 ↩︎

2. 一般来说，我们提到随机均是指均匀随机，即每个元素被选中的可能性相同。 ↩︎