# Luna Tech

Tutorials For Dummies.

# 0. 前言

Dictionary 有时候也被称作 Map，存的是 key-value pairs。

• key 必须 unique，用 key 可以找到对应的 value

• 所有的 dictionary 都必须提供 key-value pair 的增改查删功能以及根据 key 找 value 的功能

比如下图中给到了key 93，我们就需要输出这个 key 对应的 value ->be

The abilities to put a key-value pair into the map and then look up a data value associated with a given key are the fundamental operations that all maps must provide.

Map 是一个抽象数据类型，它的定义是：

• a collection of key-value pairs where values can be accessed via their associated key

Operation 包括：

• Constructor: Map()
• 增加新的键值对：put(key, value) 当 map 中不存在同样的 key 时，把这个新的键值对加进去；
• 查找：get(key) 在 map 中查找这个 key，返回对应的 value
• ……

# 2. Implementing a Dictionary in Python

Our analysis showed that this technique could potentially yield a 𝑂(1)O(1) search. However, performance degraded due to issues such as table size, collisions, and collision resolution strategy.

# 3. Skip List 跳表

## Skip List 是什么？

A skip list is basically a two-dimensional linked list where the links all go forward (to the right) or down. The head of the list can be seen in the upper-left corner. Note that this is the only entry point into the skip list structure.

##组成元素：Data Node

• holds key and associated value
• 每个data node 有两个reference，一个向下，一个向右

Header nodes 只有两个 reference - down and next.

next 指向 a linked list of data nodes.

down 指向 the next lower header node.

## Towers

• tower 是被 data node 的 down reference 联系在一起的；
• tower 的高度可能是不同的；

Towers are linked together by the down reference in the data node.

## Level

• 排序是用 key 来排序的；

• 我们把这种 collection 叫做 level，level 从 0 开始，0 是底层；

• level 0 是一个包含所有 node 的 collection；

• 当我们往 level 更高一点走的时候，我们的 node 数量会减少（注意！！！），这也是 skip list 的一个重要特性，能帮助我们更有效地进行查找；

• 每个 level 的 node 数量是直接跟 tower 的高度相关的。

Levels are named starting with 0 at the lowest row. Level 0 consists of the entire collection of nodes. Every key-value pair must be present in the level-0 linked list. However, as we move up to higher levels, we see that the number of nodes decreases. This is one of the important characteristics of a skip list and will lead to our efficient search. Again, it can be seen that the number of nodes at each level is directly related to the heights of the towers.

# 4. Skip List - Code

SkipList 的 constructor 只需要设置一个 head，初始化为 None。

When a skip list is created there are no data and therefore no header nodes. The head of the skip list is set to None. As key-value pairs are added to the structure, the list head refers to the first header node which in turn provides access to a linked list of data nodes as well as access to lower levels.

class HeaderNode:
def __init__(self):
self._next = None
self._down = None

@property
def next(self):
return self._next

@property
def down(self):
return self._down

@next.setter
def next(self, value):
self._next = value

@down.setter
def down(self, value):
self._down = value

class DataNode:
def __init__(self, key, value):
self._key = key
self._data = value
self._next = None
self._down = None

@property
def key(self):
return self._key

@property
def data(self):
return self._data

@property
def next(self):
return self._next

@property
def down(self):
return self._down

@data.setter
def data(self, value):
self._data = value

@next.setter
def next(self, value):
self._next = value

@down.setter
def down(self, value):
self._down = value

class SkipList:
def __init__(self):


# 5. Searching a Skip List

2. go horizontal - key=31, 31<77 => move forward
3. there’s no node from 31 at level 3, drop down to level 2
4. look to the right, node with key=77 => search successfully found node
5. return “of”

Note: 只有 level 0 才包含所有 node。

Since each level is an ordered linked list, a key mismatch provides us with very useful information.

## Code

def search(self, key):

while current:
if current.next is None:
current = current.down
else:
if current.next.key == key:
return current.next.data
else:
if key < current.next.key:
current = current.down
else:
current = current.next
return None


# 6. Adding Key-Value Pairs to a Skip List

1. search skip list，找到这个新 key 应该所在的位置（就是做一次 search）；

我们最终会到达 level 0

2. 然后 create a new data node，加入 level 0 的 linked list 里面

3. 同时我们还要记录整个查找的路径（利用 stack），方便我们在 insert 的时候把经过的 level 都加上新的 data node

The height of the tower for the new entry will not be predetermined but instead will be completely probabilistic. In essence, we will “flip a coin” to decide whether to add another level to the tower. Each time the coin comes up heads, we will add one more level to the current tower.

## Tower 高度 - 模拟抛硬币

return 0 => tail

Each time a new level is added to the tower, a new data node and a new header node are created. Depending on the random nature of the coin flip, the height of the towers for any particular key is bound to change each time we build the skip list.

from random import randrange
def flip():
return randrange(2)


## Code for inserting new data node

def insert(self, key, value):
temp = DataNode(key, value)
top = temp
while flip() == 1:
if tower.is_empty():
temp = DataNode(key, value)
temp.down = top
top = temp
else:
next_level = tower.pop()
temp = DataNode(key, value)
temp.down = top
temp.next = next_level.next
next_level.next = temp
top = temp
else:


## Code (TBC)

This time we pop the insert stack to get the next higher insertion point as the tower grows. Only after the stack becomes empty will we need to return to creating new header nodes.

# 这段代码感觉有点奇怪...
tower = Stack()
while current:
if current.next is None:
tower.push(current)
current = current.down
else:
if current.next.key > key:
tower.push(current)
current = current.down
else:
current = current.next

lowest_level = tower.pop()
temp = DataNode(key, value)
temp.next = lowest_level.next
lowest_level.next = temp
top = temp


# 7. Building the Map

class Map:
def __init__(self):
self.collection = SkipList()

def put(self, key, value):
self.collection.insert(key, value)

def get(self, key):
return self.collection.search(key)


# 8. Analysis of a Skip List

Tower 的最大高度 = $log2^n + 1$，用 big O 来表示就是 $O(logn)$.

## Search method

We drop down a level when one of two events occurs. Either we find a data node with a key that is greater than the key we are looking for or we find the end of a level.

If we are currently looking at some data node, the probability that one of those two events will happen in the next link is 1/2. This means that after looking at 2 links, we would expect to drop to the next lower level (we expect to get heads after two coin flips).

# 9. 结语

Maps (dictionaries) are associative memory organization structures.