字典的实现有多种方法，性能较高的有树类的实现和基于hash的实现。前者查找的时间复杂度为O(lgN)，后者查找的时间复杂度为O(1)。当然，这两个时间级别是在数量级别上的对比，并不是实际单个键值查询时的性能对比。因为基于hash的字典本身的查询性能取决于hash函数的性能、质量。如果hash函数设计得非常慢，单个键值的查询基于hash实现的字典不一定比树类实现的字典要快。
不过，使用常规的hash函数，hash实现的字典在查找性能上都由于树类实现的。另外，使用树类结构实现的字典更消耗空间。但，树类实现的字典的一个优势是，它能保存插入顺序。而使用hash并不能保证有序，因为键一经过hash后就随机地均匀分布于有限的hash空间中了。字典的存储保证插入的有序性就是我们称为的有序字典。那么问题来了，我们一方面要字典有序存储，另外一方面要字典拥有hash实现的字典的插入性能？
有一个很tricky的方法，我们使用额外的空间保证key有序（使用链表或数组有序存储key），但实际存储依然是无序的hash符号表。当外部进行有序访问时，访问保存key的数组或链表就可以有序获得key，进而有序获得hash符号表中的元素。上面的思路也是典型的空间换时间思想，牺牲了O(n)的空间以达到“有序”。
另外一种实现是LinkedHashMap。无措，Java集合框架中的一种数据结构。它的底层实现原理是通过HashMap建立<键-结点>的快速映射关系，通过双向链表中每个结点保存实际的键值。因此，HashMap用于O(1)时间定为结点，结点用于存储实际的键值，双向链表保持字典的有序。
trick的实现方式
接下来我们给出简单的实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class OrderedDict:
def __init__(self):
self._root = dict()
self._ordered = []
def set(self, key, value):
if key in self._root:
return
self._root[key] = value
self._ordered.append(key)
def get(self, key):
return self._root.get(key, None)
def delete(self, key):
if key in self._root:
del self._root[key]
self._ordered.remove(key)
def keys(self):
return tuple(self._ordered)
def values(self):
return tuple([self._root[key] for key in self._ordered])
def items(self):
for key in self._ordered:
yield key, self._root[key]
def __repr__(self):
return 'OrderedDict([{}])'.format(', '.join(str(item) for item in self.items()))
|
使用了self._ordered来有序存储key。外部需要有序访问时用上该变量。例如调用self.items函数时，生成器有序输出字典的键值对。
对于Go语言的实现，可以使用链表来代替数组或切片，避免底层数组有限而动态扩展内存。
双链表+HashMap的实现方式
定义双链表结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| from functools import total_ordering
@total_ordering
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
self.prev = None
def __repr__(self):
return 'Node<{}:{}>'.format(self.key, self.value)
def __eq__(self, node):
return self.key == node.key
def __gt__(self, node):
return self.key > node.key
|
定义LinkedHashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class LinkedHashMap:
def __init__(self):
self._map = dict()
self._head = None
self._tail = None
def get(self, key):
return self._map.get(key, None)
def set(self, key, value):
node = Node(key, value)
self._map[key] = node
if self._head is None:
self._head = node
self._tail = node
else:
self._tail.next = node
node.prev = self._tail
self._tail = node
def delete(self, key):
node = self._map.get(key, None)
if node:
node.value = value
return
node = self._map.pop(key, None)
if node:
if node.prev is None and node.next is None:
self._head = None
self._tail = None
elif node.prev is None:
self._head = node.next
node.next.prev = node.prev
elif node.next is None:
self._tail = node.prev
node.prev.next = node.next
else:
node.prev.next = node.next
node.next.prev = node.prev
node.next = None
node.prev = None
return node
|
delete操作的编写优点繁，但还有一种更优雅的方法，就是_tail和_head做哨兵结点，充当头尾结点，而不是直接指向头尾结点。
用于遍历操作的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| def _traverse_linked_list(self):
p_node = self._head
while p_node:
yield p_node
p_node = p_node.next
def keys(self):
for node in self._traverse_linked_list():
yield node.key
def values(self):
for node in self._traverse_linked_list():
yield node.value
def items(self):
for node in self._traverse_linked_list():
yield node.key, node.value
def __repr__(self):
return 'LinkedHashMap([{}])'.format(', '.join(str(item) for item in self.items()))
|
编写简单的测试用例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| def testing():
m = LinkedHashMap()
m.set('a', 1)
m.set('b', 2)
m.set('c', 3)
print(m)
print(m.get('a'))
print(m.get('b'))
print(m.get('c'))
print(m.delete('a'))
m.set('d', 4)
print(m.delete('c'))
print(m)
print(list(m.items()))
print(list(m.keys()))
print(list(m.values()))
|
LinkedHashMap能保持O(1)时间复杂度插入、读取、删除，也能保持元素的有序，由于是双链表结构，能在O(1)时间复杂度完成结点键的换位，很适合实现高性能的LRU算法。在有序字典的基础上，不难实现有序集合。
完。
