跳表&散列1-字典&跳表

继续是《数据结构算法与应用：C++语言描述》的笔记，这是第七章跳表和散列的内容，本节会介绍字典和跳表。

对于一个有n个元素的有序数组，用折半搜索法进行搜索需要的时间是 $O(logn)$ ,而对一个有序链表进行搜索所需要的时间是 $O(n)$ 。我们可以通过对有序链表上的全部或部分节点增加额外的指针，来提供搜索性能。在搜索时，可以通过这些指针来跳过链表中若干个节点，因此没有必要从左到右搜索链表中的所有节点。

增加了向前指针的链表叫做跳表。跳表采用随机技术决定链表中哪些节点应增加向前指针以及在节点中应增加多少个指针。采用这种随机技术，跳表中的搜索、插入和删除操作的时间均为 $O(logn)$ ,然而，最坏情况下下时间复杂性却变成 $\theta(n)$ 。而在一个有序数组或链表中进行插入/删除操作的时间为 $O(n)$ ,最坏情况下为 $\theta(n)$ 。

散列法是用来搜索、插入和删除记录的另一种随机方法。与跳表相比，它的插入/删除操作时间提高到 $\theta(1)$ ,最坏情况下仍为 $\theta(n)$ 。尽管如此，在经常将所有元素按序输出或按序号搜索元素时，跳表的执行效率将优于散列。

字典

字典(dictionary)是一些元素的集合。每个元素有一个称作key的域，不同元素的key各不相同。

抽象数据类型如下所示：

抽象数据类型Dictionary{
实例
    具有不同关键字的元素集合
操作
    Create(): 创建一个空字典
    Search(k,x): 搜索关键字为k的元素，结果放入x;如果没找到，则返回false，否则返回true；
    Insert(x): 向字典中插入元素x
    Delete(k,x): 删除关键字为k的元素，并将其放入x
}

若仅按照一个字典元素本身的关键字来访问该元素，则称为随机访问；而顺序访问是指按照关键字的递增顺序逐个访问字典中的元素。顺序访问需要借助于Begin(用来返回关键字最小的元素和Next（用来返回下一个元素）等操作来实现。

在有重复元素的字典与上述抽象数据类型定义的字典相似，只是它允许有相同的关键字。在有重复关键字的字典中，在搜索和删除时需要一个规则来消除歧义。也就是说，如果搜索或删除关键字为k的元素，那么在所有关键字为k的元素中应该返回或者删除哪一个。在有些字典应用中，可能需要，删除在某个时间以后插入的所有元素。

线性表描述

字典可以保存在线性序列( $e_1,e_2,\cdots$ )中，其中 $e_i$ 是字典中的元素，其关键字从左到右依次增大。这里可以根据公式化描述或者链表描述自定义类SortedList和SortedChain。

下面给出的是类SortedChain的定义。E表示链表元素的数据类型，K是链表中排序用到的关键字。

#ifndef SORTEDCHAIN_H_
#define SORTEDCHAIN_H_
#include<iostream>

template<class E,class K>
class SortedChainNode{
    friend SortedChain<E, K>;
private:
    K key;
    E data;
    SortedChainNode<E,K> * link;
};

template<class E, class K>
class SortedChain{
private:
    SortedChainNode<E, K>* first;
public:
    SortedChain(){ first = 0; }
    ~SortedChain();
    bool IsEmpty() const { return first == 0; }
    int Length() const;
    bool Search(const K& k, E& e)const;
    SortedChain<E, K>& Delete(const K& k, E&e);
    SortedChain<E, K>& Insert(const E& e);
    SortedChain<E, K>& DistinctInsert(const K& k, const E& e);
    void Output(std::ostream&) const;
};

#endif

下面给出搜索和删除操作的实现。

template<class E, class K>
bool SortedChain<E, K>::Search(const K& k, E& e)const{
    // 搜索与k匹配的元素，结果放入e，如果没有匹配的元素，则返回false

    SortedChainNode<E, K>* p = first;

    // 搜索与K相匹配的元素
    for (; p&& p->key != k; p = p->link){
    }
    if (p&&p->key == k){
        e = p->data;
        return true;
    }
    else{
        std::cout << "There is no key--" << k << " in sortedChain\n";
    }
    return false;
}

template<class E, class K>
SortedChain<E, K>& SortedChain<E, K>::Delete(const K& k, E& e){
    // 删除与k相匹配的元素，并将其放入e

    SortedChainNode<E, K>* p = first;
    // 跟踪p
    SortedChainNode<E, K>* tp = 0;

    for (; p && p->key != k; tp = p, p = p->link){
    }

    if (p && p->key == k){
        e = p->data;
        // 从链表中删除p所指向的元素
        if (tp)
            tp->link = p->link;
        else
            // p是链表首节点
            first = p->link;
        
        delete p;   
    }else
        std::cout << "There is no key--" << k << " in sortedChain\n";

    return *this;
}

插入操作如下所示：

template<class E, class K>
SortedChain<E, K>& SortedChain<E, K>::DistinctInsert(const K& k,const E& e){
    // 如果表中不存在关键值与e相同的元素，则插入e，否则引发异常BadInput

    SortedChainNode<E, K>* p = first;
    // 跟踪p
    SortedChainNode<E, K>* tp = 0;

    // 移动tp以便把e插入到tp之后
    for (; p && p->key != k; tp = p, p = p->link);

    if (p && p->key == k){
        std::cout << "There is already key--" << k << " in sortedChain,please choose another key.\n";
        return *this;
    }

    // 若没有出现重复关键值，则产生一个关键值为e的新节点
    SortedChainNode<E, K>* q = new SortedChainNode<E, K>;
    q->data = e;
    q->key = k;
    // 将新节点插入到tp之后
    q->link = p;
    if (tp)
        tp->link = q;
    else
        first = q;

    return *this;
}

类SortedChain提供了两种插入操作，上述DistinctInset操作保证链中所有元素有不同的关键字，而Insert允许有相同的关键字。

更详细的内容可以查看字典—链表实现

跳表描述

理想情况

在一个有序链表描述的具有n个元素的字典中进行搜索，至多需要进行n次比较，而如果在链表中部节点加一个指针，则比较次数可以减少到 $\frac{n}{2}+1$ 。搜索的时候，首先将欲搜索元素与中间元素进行比较，如果欲搜索的元素较小，则仅需搜索链表的左半部分，否则，只需搜索链表的右半部分。

如下图a所示是一个有序链表的七个元素，它有一个头节点和一个尾节点。节点中的数是该节点的值。对该链表搜索可能需要进行7次比较。如果使用图b的方法，在中间增加一个指针，则最坏情况下比较次数减少到4次。

还可以像图c中一样，再在左半部分和右半部分各增加一个指针，这样可以进一步减少最坏情况下的比较次数。在该图中有3条链，0级链就是图a中的初始链，1级链包括第二，四，六个元素，而2级链只包括第四个元素。

一个例子是要查找元素77，首先会跟40相比，由于 $70 \gt 40$ ,则在1级链中与75比较，然后 $77 \gt 75$ ，因此在0级链中与80比较，此时可以知道77不在字典中。

通常0级链包括n个元素，1级链包括 $\frac{n}{2}$ 个元素，2级链包括 $\frac{n}{4}$ 个元素，而每 $2^i$ 个元素就有一个i级链指针。当且仅当一个元素在0~i级链上，但不在i+1级（若该链存在）链上时，我们就是说该元素是i级链元素。所以图c中，40是2级链上唯一的元素，75是1级链元素，20、30、60、80是0级链元素。

图c所示的结构就是跳表（skip list）。在该结构中有一组有层次的链。0级链式包含所有元素的有序链表，1级链是0级链的一个子集。i级链是i-1级链的子集。

插入和删除

在进行插入和删除时，要想保持上图c的跳表结构，必须耗时 $O(n)$ 。注意到在这种结构中，有 $\frac{n}{2^i}$ 个元素为i级链元素，所以在进行插入时应尽量逼近这种结构。在进行插入时，新元素属于i级链的概率为 $\frac{1}{2^i}$ 。在确定新元素的级时，应考虑各种可能的情况。因此，把新元素作为i级链元素的可能性为 $p^i$ ,图c中p=0.5。对于一般的p，链的级数为 $\lfloor (log_{\frac{1}{p}}n) \rfloor + 1$ ,在这种情况下，每p个i-1级链就有一个在i级链中。

上图d是插入元素77的示例，新元素插在75和80之间，如图d中的虚线所示。插入时，要为新元素分配一个级，分配过程由随机数产生器完成。

若新元素为i级链元素，则仅影响由虚线断开的0~i级链指针。上图e给出新插入元素77作为1级链表时链表的结构。

对于删除操作，我们无法控制其结构。

级的分配

在级基本的分配过程中，可以观察到，在一般跳表结构中，i-1级链中的元素属于i级链的概率为p。假设有一随机数产生器所产生的数在0到RAND_MAX之间，则下一次所产生的随机数小于等于CutOff = p * RAND_MAX的概率为p。因此，若下一随机数小于等于CutOff,则新元素应在1级链上，然后继续确定新元素是否在2级链上，这将由下一个随机数来决定，如果新的随机数继续小于等于CutOff,重复这个过程，直到一个随机数大于CutOff为止。

所以可以用下列代码为要插入的元素分配级:

1
2
3

int lev = 0;
while(rand() <= CutOff)
    lev++;

这种方法潜在的缺点是可能为某些元素分配特别大的级，从而导致一些元素的级远远超过 $log_{\frac{1}{p}}N$ ,其中N为字典中预期的最大数目。为避免这种情况，可以设定一个上限lev。在有N个元素的跳表中，级MaxLevel的最大值为 $\lceil log_{\frac{1}{p}}N \rceil -1$ ,可以采用此值作为上限。

另一个缺点是即使采用上面给出的上限，但还是可能存在下面的情况，如在插入一个元素前有3条链，但在插入之后就有了10条链，此时，新插入元素的是9级，尽管在前面插入中没有出现3到8级的元素，也就是在此插入前并没有插入3到8级的元素。既然这些空级没有直接的好处，那么可以直接把新元素的级调整为3。

类SkipNode

跳表结构的头节点需要有足够的指针域，以满足可能构造最大级数的需要，而尾节点不需要指针域。每个存有元素的节点都有一个data域和（级数+1）个指针域。下面给出自定义类SkipNode，指针域由数组link表示，其中link[i]表示i级链指针。构造函数为指针数组分配空间，对于一个lev级链元素，其size值为lev+1。

template<class E, class K>
class SkipList;

template<class E, class K>
class SkipNode{
    friend SkipList<E, K>;
private:
    SkipNode(int size){
        link = new SkipNode<E, K>*[size];
    }
    ~SkipNode() { delete[] link; }

    E data;
    // 一维指针数组
    SkipNode<E, k> **link;
};

类SkipList

下面给出类SkipList的定义。MaxE是字典的最大容量。虽然给出的代码中允许元素数目超过MaxE，但若元素数目不超过MaxE，平均性能会更好一些。一个元素既在i-1级链上又在i级链上的概率是p，Large是一个比字典中任意一个数均大的值。尾节点的值为Large。0级链上的值（不包括头节点，因其没有值）从左到右按升序排列。

template<class E,class K>
class SkipList{
private:
    int Level();
    SkipNode<E, K>* SaveSearch(const K& k);
    // 所允许的最大级数
    int MaxLevel;
    // 当前非空链的个数
    int Levels;
    // 用于确定级号
    int CutOff;
    // 一个很大的key值
    K TailKey;
    // 头节点指针
    SkipNode<E, K>* head;
    // 尾节点指针
    SkipNode<E, K>* tail;
    // 指针数组
    SkipNode<E, K>** last;

public:
    SkipList(K Large, int MaxE = 10000, float p = 0.5);
    ~SkipList();
    bool Search(const K&k, E&e)const;
    SkipList<E, K>& Insert(const E& e);
    SkipList<E, K>& Delete(const K&k, E&e);
};

构造函数和析构函数如下所示：

template<class E, class K>
SkipList<E, K>::SkipList(K Large, int MaxE, float p){
    CutOff = p * RAND_MAX;
    MaxLevel = ceil(log(MaxE) / log(1 / p)) - 1;
    TailKey = Large;
    // 初始化随机发生器
    randomize();
    // 对级号进行初始化
    Levels = 0;

    // 创建头节点、尾节点以及数组last
    head = new SkipNode<E, K>(MaxLevel + 1);
    tail = new SkipNode<E, K>(0);
    last = new SkipNode<E, K> *[MaxLevel + 1];
    tail->data = Large;

    // 将所有级均置空，即将head指向tail
    for (int i = 0; i <= MaxLevel; i++)
        head->link[i] = tail;
}

template<class E, class K>
SkipList<E, K>::~SkipList(){
    SkipNode<E, K>* next;

    // 通过删除0级链来删除所有节点
    while (head != tail){
        next = head->link[0];
        delete head;
        head = next;
    }

    delete tail;

    delete[] last;
}

搜索、插入和删除函数均要求对E进行重载，以便在E的成员之间、E与K的成员之间进行比较。从K到E的赋值和转换也必须定义。当每个元素都有一个整数域data和一个长整数域key，且元素的值由key给出时，可使用下列程序定义的重载。

class element{
    friend void main(void);
public:
    operator long() const{ return key; }
    element& operator=(long y){
        key = y;
        return *this;
    }
private:
    int data;
    long key;
};

SkipList有两个搜索函数。当需要定位一个值为k的元素时，可使用共享成员函数Search。该函数从最高级链（Levels级，仅含一个元素）开始查找，一直到0级链。在每一级链中尽可能地逼近要查找的元素。当从for循环退出时，正好处在欲寻找元素的左边。与0级链中的下一个元素进行比较，即可确定要找的元素是否在跳表中。

第二个搜索函数是私有成员函数SaveSearch，由插入和删除操作来调用。SaveSearch不仅包含了Search的功能，而且可把每一级中遇到的最后一个节点存放在数组last之中。

template<class E, class K>
bool SkipList<E, K>::Search(const K& k, E& e)const{
    // 搜索与k相匹配的元素，并将找到的元素放入e，如果不存在则返回false
    if (k >= TailKey)
        return false;
    // 调整指针p，使其恰好指向可能与k相匹配的节点的前一个节点
    SkipNode<E, K>*p = head;
    for (int i = Levels; i >= 0; i--){
    // 逐级向下
        while (p->link[i]->data < k)
            // 在第i级链中搜索
            p = p->link[i];
    }
        
    // 检查是否下一个节点拥有关键值k
    e = p->link[0]->data;
    return (e == k);
}

template<class E, class K>
SkipNode<E, K>* SkipList<E, K>::SaveSearch(const K& k){
    // 搜索k并保存最终所得到的位置
    SkipNode<E, K>*p = head;
    for (int i = Levels; i >= 0; i--){
        // 逐级向下
        while (p->link[i]->data < k)
            // 在第i级链中搜索
            p = p->link[i];
        last[i] = p;
    }
    return (p->link[0]);
}

下面给出插入和删除操作的实现代码

template<class E, class K>
int SkipList<E, K>::Level(){
    // 产生一个随机级号，该级号<= MaxLevel
    int lev = 0;
    while (rand() <= CutOff)
        lev++;
    return (lev <= MaxLevel) ? lev : MaxLevel;
}

template<class E, class K>
SkipList<E, K>& SkipList<E, K>::Insert(const E& e){
    // 如果不存在重复，则插入e
    K k = e;
    if (k >= TailKey){
        std::cerr << "The key is larger than " << TailKey << "\n";
        return *this;
    }
    // 检查是否重复
    SkipNode<E, K>*p = SaveSearch(k);
    if (p->data == e){
        std::cerr << "The key is already in SkipList\n";
        return *this;
    }

    // 不重复，为新节点确定级号
    int lev = Level();
    if (lev > Levels){
        lev = ++Levels;
        last[lev] = head;
    }

    // 产生新节点，并将新节点插入p之后
    SkipNode<E, K>*y = new SkipNode<E, K>(lev + 1);
    y->data = e;
    for (int i = 0; i <= lev; i++){
        // 插入到第i级链
        y->link[i] = last[i]->link[i];
        last[i]->link[i] = y;
    }

    return *this;
}

template<class E, class K>
SkipList<E, K>& SkipList<E, K>::Delete(const K&k, E&e){
    // 删除与k相匹配的元素，并将删除的元素放入e。
    if (k >= TailKey){
        std::cerr << "The key is larger than " << TailKey << "\n";
        return *this;
    }
    // 检查是否存在与k相匹配的元素
    SkipNode<E, K>*p = SaveSearch(k);
    if (p->data ！= e){
        std::cerr << "The key is already in SkipList\n";
        return *this;
    }
    // 从跳表中删除节点
    for (int i = 0; i <= Levels && last[i]->link[i] == p; i++)
        last[i]->link[i] = p->link[i];

    // 修改级数
    while (Levels > 0 && head->link[Levels] == tail)
        Levels--;

    e = p->data;
    delete p;
    return *this;
}

当跳表中有n个元素的时候，搜索、插入和删除操作的复杂性均为 $O(n+MaxLevel)$ 。

更详细内容可以查看跳表的实现

小结

本节首先介绍了字典的定义以及使用链表描述来实现字典，然后介绍了跳表及其代码实现。