OrderedDict:维护插入顺序的有序字典

  |  

摘要: 维护插入顺序的有序字典

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


在文章 LRU:维护最近访问/插入的元素LFU:维护最频繁访问的元素 中,我们分别以模板题介绍了 LRU 和 LFU 的原理与实现。它们都属于有序字典的一种。

有序字典简单理解就是在字典的基础上保持有序,是一种哈希表+链表的结构。其原理是结合哈希表的高效查找以及链表的高效插入删除的优点,在保持哈希表高效增删改查的基础上,利用链表节点间有顺序的特性,维护元素的某种与增删改查有关的顺序。

这里的顺序根据需求可能是插入时间顺序 (OrderedDict)、访问时间顺序 (LRU)、访问频率顺序 (LFU) 等。

本文我们详细介绍 OrderedDict 的原理与实现,用 OrderedDict 解决 340. 至多包含 K 个不同字符的最长子串 并对比传统的滑动窗口+哈希表的方法。


维护插入顺序的字典

链表具有优秀的插入删除性能,因此如果在维护数据的过程中对数据插入顺序有需求的话,持有数据的数据结构用链表是不错的方案。

而链表由于查找的性能不太好,但是可以将数据的 key 和链表节点分别作为键和值交给哈希映射。查询的需求通过哈希映射找到节点,而插入顺序直接由链表的插入维护。

把 key 和链表节点放到哈希映射中,可以视为是对链表做了一层哈希索引,参考 加索引的链表

当需要通过 key 快速查询数据并且在维护数据过程中需要维护数据的插入顺序时,双向链表+哈希映射是比较好的解法

双向链表和哈希表我们此前都详细介绍过,并写过代码模板,参考文章:

OrderedDict

Python 中有序字典 OrderedDict 是 collections 提供的一种数据结构, 它提供了维护插入顺序的 dict 结构。但是需要注意当插入时 key 如果已经存在,则不会讲 key 调度到表头。

源代码: https://github.com/python/cpython/blob/master/Lib/collections/__init__.py

关键点:

1
2
3
4
5
6
7
一个继承自dict的键值对字典
继承的字典提供 __getitem__, __len__, __contains__, get 方法
所有方法的时间复杂度均与正常的字典一样.

内部的 self.__map 字典将key与双向链表的指针关联在一起
循环双向链表是以一个哨兵元素作为开始和结束节点的
哨兵元素永远不会被删除.

双向链表+哈希映射实现 OrderedDict

接口

put、get、remove 就是哈希表的插入,查询,删除。但是有一点变化,就要插入时,如果 key 已经存在,需要调度到表头。这里需要注意 Python 标准库里的 OrderedDict 在插入时,如果 key 已经存在,则不会自动调度到表头,需要自己用 move_to_end 操作,见后面的题解。

1
2
3
void put(int key, int value)
int get(int key)
int remove(int key)

再此基础上新增 remove_buttom ,删除最早插入的节点。

1
int remove_buttom()

哈希表和双向链表如果用 STL,则实现起来简单一些,见后面的题解代码。下面看一下哈希表和双向链表都用模板的实现代码。

数据结构设计

链表的容量用一个默认的很大的值。即不带容量限制和扩容。

链表的数据类型为 int,也是哈希表的键。

1
2
3
typedef int DLType;
const DLType DLTypeNULL = -1;
const int MAX_LEN = 1e6;

哈希表用比哈希表模板,容量提前计算好,不带扩容和重哈希。

哈希表的键为 int,值为自定义类型 ValueType,持有 int 类型的值和链表节点的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int INF = 1e9;
typedef int HashType;
struct ValueType
{
int value;
DLNode *list_node;
ValueType(int v=-1, DLNode *node=nullptr):value(v),list_node(node){}
bool operator==(const ValueType& v) const
{
return value == v.value && list_node == v.list_node;
}
bool operator!=(const ValueType& v) const
{
return !(*this == v);
}
};
const ValueType VALUENULL(-1, nullptr);

CloseHashTable 和 DoubleCircleList 两部分除了哈希表的值的类型自定义之外,其余的代码复制模板:

有序字典的数据结构如下,有序字典本身不带容量限制。

1
2
3
const int hashtable_capacity = 99991;
DoubleCircleList linkedlist;
CloseHashTable mapping;

完整代码 (C++,模板)

带插入顺序的字典,双向链表和哈希表分别使用代码模板 DoubleCircleListCloseHashTable

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
#include <iostream>

using namespace std;

typedef int DLType;
const DLType DLTypeNULL = -1;
const int MAX_LEN = 1e6;
struct DLNode
{
DLType val;
DLNode *next;
DLNode *prev;
DLNode(DLType x) : val(x), next(nullptr), prev(nullptr) {}
};

class DoubleCircleList
{
private:
// head 一直指向 dummy
// tail 在空表时指向 dummy,否则指向 head 的前一个节点
DLNode *head, *tail;
int length;
int capacity;

public:
DoubleCircleList(int N=MAX_LEN)
{
head = new DLNode(0);
head -> next = head;
head -> prev = head;
tail = head;
length = 0;
capacity = N;
}

bool removeHead()
{
if(isEmpty())
return false;
remove(get_head());
return true;
}

bool removeTail()
{
if(isEmpty())
return false;
remove(get_tail());
return true;
}

DLType getHead() const
{
if(isEmpty())
return DLTypeNULL;
return get_head() -> val;
}

DLType getTail() const
{
if(isEmpty())
return DLTypeNULL;
return get_tail() -> val;
}

DLNode* insertHead(DLType val)
{
if(isFull())
return nullptr;
return insert(head, val);
}

DLNode* insertTail(DLType val)
{
if(isFull())
return nullptr;
return insert(tail, val);
}

DLNode* insert(DLNode *pos, DLType val)
{
if(!pos || isFull())
return nullptr;
DLNode *cur = new DLNode(val);
cur -> next = pos -> next;
cur -> prev = pos;
pos -> next -> prev = cur;
pos -> next = cur;
if(tail == pos)
tail = cur;
++length;
return cur;
}

DLType get(DLNode *pos) const
{
if(!pos || is_dummy(pos))
return DLTypeNULL;
return pos -> val;
}

DLNode* remove(DLNode *pos)
{
if(!pos || is_dummy(pos) || isEmpty())
return nullptr;
if(tail == pos)
tail = tail -> prev;
--length;
pos -> prev -> next = pos -> next;
pos -> next -> prev = pos -> prev;
DLNode *result = pos -> next;
delete pos;
pos = nullptr;
if(isEmpty())
return nullptr;
if(is_dummy(result))
result = result -> next;
return result;
}

bool change(DLNode* pos, DLType val)
{
if(!pos || is_dummy(pos))
return false;
pos -> val = val;
return true;
}

DLNode* get_next(DLNode *pos) const
{
if(isEmpty())
return nullptr;
if(is_tail(pos))
return get_head();
return pos -> next;
}

DLNode* get_prev(DLNode *pos) const
{
if(isEmpty())
return nullptr;
if(is_head(pos))
return get_tail();
return pos -> prev;
}

bool is_dummy(DLNode *pos) const
{
return pos == head;
}

bool is_head(DLNode *pos) const
{
return (!isEmpty() && pos == head -> next);
}

bool is_tail(DLNode *pos) const
{
return (!isEmpty() && pos == tail);
}

DLNode* get_tail() const
{
if(isEmpty())
return nullptr;
return tail;
}

DLNode* get_head() const
{
if(isEmpty())
return nullptr;
return head -> next;
}


bool isEmpty() const
{
return head == tail;
}

int size() const
{
return length;
}

bool isFull() const
{
return length >= capacity;
}

void traverse() const
{
auto iter = head -> next;
while(iter != head)
{
cout << iter -> val << " ";
iter = iter -> next;
}
cout << endl;
}
};


const int INF = 1e9;
typedef int hashType;
struct ValueType
{
int value;
DLNode *list_node;
ValueType(int v=-1, DLNode *node=nullptr):value(v),list_node(node){}
bool operator==(const ValueType& v) const
{
return value == v.value && list_node == v.list_node;
}
bool operator!=(const ValueType& v) const
{
return !(*this == v);
}
};
const ValueType VALUENULL(-1, nullptr);

class CloseHashTable
{
private:
struct Node
{
hashType data;
ValueType item;
int state;
// 0: Empty -1: deleted
// >0: cnt / active
Node()
{
state = 0;
}
};

Node *arraytable;
int sizetable;
int (*key)(const hashType& x); // 将 key 变成一个整数,如果 key 本身是整数直接返回
const double A = 0.6180339887;

static int defaultKey(const int &k)
{
return k;
}

int hash1(const hashType& x) const
{
if(key(x) < 0)
return key(x) % sizetable;
return (key(x) + INF) % sizetable;
}

int hash2(const hashType& x) const
{
double d;
if(key(x) < 0)
d = (key(x) + INF) * A;
else
d = (key(x)) * A;
return (int)(sizetable * (d - (int)d));
}

public:
CloseHashTable(int length=20011, int (*f)(const hashType &x)=defaultKey)
{
sizetable = length;
arraytable = new Node[sizetable];
key = f;
}

~CloseHashTable()
{
delete [] arraytable;
}

ValueType findx(const hashType& x) const;
bool insertx(const hashType& x, const ValueType& v);
bool removex(const hashType& x);
};

ValueType CloseHashTable::findx(const hashType &x) const
{
int initPos = hash2(x);
int pos = initPos;

do
{
if(arraytable[pos].state == 0)
return VALUENULL;
if(arraytable[pos].state > 0 && key(arraytable[pos].data) == key(x))
return arraytable[pos].item;
pos = (pos + 1) % sizetable;
}while(pos != initPos);

return VALUENULL;
}

bool CloseHashTable::insertx(const hashType& x, const ValueType& v)
{
int initPos = hash2(x);
int pos = initPos;

do{
if(arraytable[pos].state <= 0)
{
arraytable[pos].data = x;
arraytable[pos].item = v;
arraytable[pos].state = 1;
return true;
}
else if(arraytable[pos].state > 0 && key(arraytable[pos].data) == key(x))
{
// 有重映射将用新值覆盖 item 改为将新值插入 items
arraytable[pos].item = v;
return true;
}
pos = (pos + 1) % sizetable;
}while(pos != initPos);

return false;
}

bool CloseHashTable::removex(const hashType &x)
{
int initPos = hash2(x);
int pos = initPos;

do
{
if(arraytable[pos].state == 0)
return false;
if(arraytable[pos].state > 0 && key(arraytable[pos].data) == key(x))
{
// 有重映射改为将节点下的所有 item 删掉,将 arraytable[pos].state 改为 -1 后返回
arraytable[pos].state = -1;
return true;
}
pos = (pos + 1) % sizetable;
}while(pos != initPos);

return false;
}

class OrderedDict
{
public:
OrderedDict()
{
linkedlist = DoubleCircleList();
CloseHashTable mapping(hashtable_capacity);
}

~OrderedDict(){}

void put(int key, int value)
{
ValueType v = mapping.findx(key);
if(v != VALUENULL)
{
DLNode *node = v.list_node;
linkedlist.remove(node);
mapping.removex(key);
}
DLNode *node = linkedlist.insertHead(key);
mapping.insertx(key, ValueType(value, node));
}

int get(int key) const
{
ValueType v = mapping.findx(key);
if(v == VALUENULL)
return -1;
else
return v.value;
}

int remove(int key)
{
ValueType v = mapping.findx(key);
if(v != VALUENULL)
{
DLNode *node = v.list_node;
linkedlist.remove(node);
mapping.removex(key);
return v.value;
}
else
return -1;
}

int remove_bottom()
{
int key = linkedlist.getTail();
ValueType v = mapping.findx(key);
if(v != VALUENULL)
{
// DLNode *node = v.list_node;
// linkedlist.remove(node);
linkedlist.removeTail();
mapping.removex(key);
return v.value;
}
else
return -1;
}

int size() const
{
return linkedlist.size();
}

void traverse() const
{
DLNode *head = linkedlist.get_head();
DLNode *iter = head;
do{
cout << iter -> val << " " << mapping.findx(iter -> val).value << "; ";
iter = linkedlist.get_next(iter);
}
while(iter != head);
cout << endl;
}

protected:
const int hashtable_capacity = 99991;
DoubleCircleList linkedlist;
CloseHashTable mapping;
};

340. 至多包含 K 个不同字符的最长子串

给你一个字符串 s 和一个整数 k ,请你找出 至多 包含 k 个 不同 字符的最长子串,并返回该子串的长度。

示例 1:
输入:s = “eceba”, k = 2
输出:3
解释:满足题目要求的子串是 “ece” ,长度为 3 。

示例 2:
输入:s = “aa”, k = 1
输出:2
解释:满足题目要求的子串是 “aa” ,长度为 2 。

提示:

1
2
1 <= s.length <= 5e4
0 <= k <= 50

算法1:滑动窗口 + 哈希表

159. 至多包含两个不同字符的最长子串 的解法相同。

滑窗左右边界为 left 和 right,都初始化为 0。然后向右移动 right 指针保证区间内含有不超过 k 个不同字符。当移动到含有 k + 1 个不同字符的时候,移动 left 指针直到区间内不含有超过 k + 1 个不同字符。

对于最好情况,如果字符串不超过 k 个不同字符。只需要一次遍历就可以得到结果,时间复杂度是 $O(N)$。

对于最坏情况,当输入字符串包含 n(n > k) 个不同字,每一步都需要花费 $O(k)$ 时间找到哈希表中的最小值,时间复杂度为 $O(Nk)$

代码 (C++)

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
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
if(s.empty() || k == 0) return 0;
int n = s.size();

int left = 0, right = left + 1;
unordered_map<char, int> mapping;
mapping[s[left]] = 1;
int result = 0;
while(true)
{
while(right < n)
{
auto it = mapping.find(s[right]);
if(it != mapping.end())
++(it -> second);
else if((int)mapping.size() < k)
mapping[s[right]] = 1;
else
break;
++right;
}
if(right >= n) return max(result, right - left);
result = max(result, right - left);
while((int)mapping.size() == k)
{
--mapping[s[left]];
if(mapping[s[left]] == 0)
mapping.erase(mapping.find(s[left]));
++left;
}
}
}
};

算法2:OrderedDict

为了达到 $O(N)$,需要一种数据结构,保证以下四种操作都可以在 $O(1)$ 时间完成,这正是 OrderdeDict 的功能:

  • 插入 key: put(key, value)
  • 获取 key(隐含判断 key 是否存在): get(key)
  • 删除 key: remove(key)
  • 获取最早插入的 key 并删除: remove_bottom()

这个需求与 LRU 的功能很像,从数据结构层面上看,相当于在哈希表的基础上增加了链表换取获取最早插入的key这个操作的 $O(1)$。

这个结构的目的是在哈希表的 $O(1)$ 插入查找删除的基础上使得主动地获取最早插入的key这个操作也 $O(1)$,而不是插入时空间不够了被动地获取最早的元素。因此与传统 LRU 有几个关键区别:

  • 没有容量限制
  • 插入时不会判断是否达到空间限制,以及达到空间限制的后续动作
  • 查询时不会将查询到的节点调度到表头

代码 (C++,模板)

以下代码是使用 STL 的 OrderedDict 代码模板。

将 OrderedDict 的实现改为前面的使用 CloseHashTableDoubleCircleList 的代码模板,可以进行测试。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class OrderedDict {
public:
OrderedDict() {}

int size() {
return linkedlist.size();
}

int get(char key) {
auto it = mapping.find(key);
if(it == mapping.end())
return -1;
else
return (it -> second).first;
}

void put(char key, int index) {
auto it = mapping.find(key);
if(it != mapping.end())
remove(key);
linkedlist.push_front(key);
mapping.insert(pair<char, pair<int, list<char>::iterator>>(key, pair<int, list<char>::iterator>(index, linkedlist.begin())));
}

void remove(char key) {
auto it = mapping.find(key);
if(it != mapping.end())
{
auto iter = (it -> second).second;
linkedlist.erase(iter);
mapping.erase(it);
}
}

int remove_bottom()
{
char key = linkedlist.back();
int index = mapping[key].first;
mapping.erase(mapping.find(key));
linkedlist.pop_back();
return index;
}

private:
unordered_map<char, pair<int, list<char>::iterator>> mapping;
list<char> linkedlist;
};

class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
if(s.empty() || k == 0) return 0;
int n = s.size();

int left = 0, right = 0;
OrderedDict mapping;
int result = 1;
while(right < n)
{
mapping.put(s[right], right);
++right;
if(mapping.size() == k + 1)
left = mapping.remove_bottom() + 1;
result = max(result, right - left);
}
return result;
}
};

代码 (Python)

直接用 Python 的 OrderedDict,注意代码中 move_to_end 的部分,这是因为 Python 标准库中的 OrderedDict 插入时若 key 已经存在,则不会调度相应节点到表头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from collections import OrderedDict

class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
if s is None or k == 0:
return 0
n = len(s)

left = right = 0
mapping = OrderedDict()
result = -1
while right < n:
if s[right] in mapping:
mapping.move_to_end(s[right], last=True)
mapping[s[right]] = right
right += 1
if len(mapping) == k + 1:
left = mapping.popitem(last=False)[1] + 1
result = max(result, right - left)
return result

Share