跳表原理设计与实现

template<typename K, typename V>

class Node {

public:

Node() {}

Node(K k, V v, int);

~Node();

// 获取key 关键词

K get_key() const;

// 获取value 值

V get_value() const;

void set_value(V);

// 线性数组，用于保存指向不同级别的下一个节点的指针

// 意思就是对于一个节点来说，可能会在不同层次然后不同层的下一个节点是什么就存在这个二维数组里面（可以对照OneNote笔记的图片看）

Node<K, V> **forward;

// 代表节点所在层次

int node_level;

private:

K key;

V value;

};

// 从最高层开始找

for (int i = _skip_list_level; i >= 0; i--) {

while (current->forward[i] && current->forward[i]->get_key() < key) {

current = current->forward[i];

}

}

// 到达第0层，并将指针推进到右边的节点，我们搜索这个节点

current = current->forward[0];

// 相等，找到了这个节点

if (current and current->get_key() == key) {

std::cout << "Found key: " << key << ", value: " << current->get_value() << std::endl;

return true;

}

std::cout << "Not Found Key:" << key << std::endl;

return false;

template<typename K, typename V>

int SkipList<K, V>::insert_element(const K key, const V value) {

// 为了满足多线程，要加锁

mtx.lock();

// _header是指向头节点的指针

Node<K, V> *current = this->_header;

// 创建update数组，并且初始化

// update是一个数组，用于放置node->forward[i]（node不同级别的下一个节点），即以后应该被操作的节点。

// 这里是什么原理呢：和单链表做类比，就是待插入位置的前一个节点prev，具体可以看OneNote笔记

Node<K, V> *update[_max_level+1];

memset(update, 0, sizeof(Node<K, V>*)*(_max_level+1));

// 从跳表的最高层开始 不断找待插入的位置

for(int i = _skip_list_level; i >= 0; i--) {

// 当前节点（初始为头节点）的下一个节点 不为空

// 并且 当前节点的下一个节点的值 小于要插入的节点指

while(current->forward[i] != NULL && current->forward[i]->get_key() < key) {

current = current->forward[i];

}

// current节点后面就是待插入节点的位置，放到update数组中记录下来

update[i] = current;

}

// 达到0级，即最底层，并将指针指向右边的节点，这是想要插入的键。

current = current->forward[0];

// 如果当前节点的键值等于搜索到的键值，我们就得到它

if (current != NULL && current->get_key() == key) {

std::cout << "key: " << key << ", exists" << std::endl;

mtx.unlock();

return 1;

}

// 如果current是NULL，意味着我们已经到达了本级的终点。

// 如果当前的键不等于键，意味着我们必须在update[0]和当前节点之间插入节点。

// fix 20220831 ylx

else if (current == NULL || current->get_key() != key ) {

// 给节点生成一个随机等级

int random_level = get_random_level();

// 如果随机等级大于跳表的当前等级，则用头的指针初始化更新值。

// 就是从之前的最高层 到 随机等级之间，这些层次都是空的，将头节点（最底层）作为待插入节点的prev节点

if (random_level > _skip_list_level) {

for (int i = _skip_list_level + 1; i < random_level + 1; i++) {

update[i] = _header;

}

_skip_list_level = random_level;

}

// 创建新的节点

Node<K, V>* inserted_node = create_node(key, value, random_level);

// 插入节点

// 类比单链表，上面update数组，获取到了待插入位置的前一个节点prev

// inserted_node->next = prev->next (next即forward) (prev即update)

// prev->next = inserted_node

for (int i = 0; i <= random_level; i++) {

inserted_node->forward[i] = update[i]->forward[i];

update[i]->forward[i] = inserted_node;

}

std::cout << "Successfully inserted key:" << key << ", value:" << value << std::endl;

_element_count ++;

}

// 操作完了后解锁

mtx.unlock();

return 0;

}