大师兄的数据结构学习笔记(十四）: 词典

大师兄的数据结构学习笔记(十三）: KD树
 大师兄的数据结构学习笔记(十五）: 串

一、关于符号表

符号表(symbol table)包括词典(dictionary)结构和映射(map),笼统的称作词典。
词典结构和映射，逻辑上都是由一组数据构成的集合，其中各元素都是由关键码(key)和数据项(value)合成的词条(entry)。
词典结构和映射都支持静态查找和动态更新。
区别在于，词典允许多个词条拥有相同的关键码，而映射要求关键码互异。
符号表不要求词条之间根据关键码比大小，在词条内部，也不需要按照大小次序来组织数据项。

二、实现词典

词典的主要接口如下：

接口	功能
get(key)	若关键码key存在，则返回对应的数据项value；否则返回NULL。
put(key,value)	插入词条(key,value)。
remove(key)	若关键码key存在，则删除对应词条；否则返回NULL。

template <typename K, typename V>
//字典条目
struct Entry {
    K key; V value;
    Entry(K k = K(), V v = V()) :key(k), value(v) {}
    Entry(const Entry<K, V>& e) :key(e.key), value(e.value) {}
    bool operator<(const Entry<K, V>& e) { return key < e.key; }
    bool operator>(const Entry<K, V>& e) { return key > e.key; }
    bool operator==(const Entry<K, V>& e) { return key == e.key; }
    bool operator!=(const Entry<K, V>& e) { return key != e.key; }
};

template<typename K, typename V>
//字典结构
struct Dictionary
{
    virtual int size() const = 0;
    virtual bool put(K, V) = 0;
    virtual V* get(K k) = 0;
    virtual bool remove(K k) = 0;
};

词典可以用任何一种平衡二叉搜索树实现，但由于这类实现方法都假设“关键码可以比大小”，所以实现的并非严格意义上的字典结构。
通常使用跳转表和散列表实现。

三、跳转表

1. 从单链表到跳转表

在单链表中，查询某个数据需要通过遍历，时间复杂度为 $O (n)$ 。
如果每格n个元素增加一级索引，则可以通过索引跳转到链表的某一段，用更少的步数查询数据。
以此类推，可以通过不断地增加索引，提升查询效率。
以上方法其实是通过单链表实现了二分查找。
这种链表加多级索引的结构，就是跳转表(Skiplist)。

2. 关于跳转表

跳转表基于链表的结构，但为了增加索引，节点需要包含上下左右四个方向的指针，即四联表(quadlist)。
需要用两个链表来构成跳转表结构，其中，每一个水平链表称为一层(level)，纵向链表的规模称为层高，从S0-Sh，元素的数量递减，最底层的S0包含有表中所有的数据项；同时，同一个数据项可能在几层都出现，沿纵向组成塔(tower)，从而也需要给每一个节点定义上下两个指针。

template<class T>
// 四联表节点
struct QualdListNode
{
    T entry; //词条
    QualdListNode<T>* pred; //前驱
    QualdListNode<T>* succ; //后继
    QualdListNode<T>* above; //上邻
    QualdListNode<T>* below; //下邻

    QualdListNode(
        T e = T(), QualdListNode<T>* p = nullptr,
        QualdListNode<T>* s = nullptr,
        QualdListNode<T>* a = nullptr,
        QualdListNode<T>* b = nullptr) :
        entry(e), pred(p), succ(s), above(a), below(b) {};

    QualdListNode<T>* insertAsSuccAbove(T const& e, QualdListNode<T>* b = nullptr); // 插入新结点，以当前节点为前驱，以节点b为下邻
};

template<class T>
// 插入新结点，以当前节点为前驱，以节点b为下邻
QualdListNode<T>* QualdListNode<T>::insertAsSuccAbove(T const& e, QualdListNode<T>* b)
{
    QualdListNode<T>* node;
    node->T = e;
    node->below = b;
    node->above = b->above;
    b->above = node;
    return node;
}

template<class T>
//四联表
class QuadList
{
public:
    QuadList(); //构造函数
    ~QuadList(); //构造函数
    int size() const; //获得规模
    bool is_empty() const; //是否为空
    QualdListNode<T>* first() const; //首节点
    QualdListNode<T>* last() const; //尾节点
    T remove(QualdListNode<T>* p); //删除结点
    QualdListNode<T>* insertAfterAbove(T const& e, QualdListNode<T>* p, QualdListNode<T>* b = nullptr); //插入结点
private:
    int _size;
    bool empty();
    QualdListNode<T>* header;
    QualdListNode<T>* trailer;
    bool valid(QualdListNode<T>* p); //判断是否合法
protected:
    void init(); // 创建时初始化
    int clear(); // 清除所有节点
};

template<class T>
//构造函数
QuadList<T>::QuadList()
{
    init();
}

template<class T>
//析构函数
QuadList<T>::~QuadList()
{
    clear();
    delete header;
    delete trailer;
}

template<class T>
//获得规模
int QuadList<T>::size() const
{
    return _size;
}

template<class T>
//是否为空
bool QuadList<T>::is_empty() const
{
    return _size == 0;
}

template<class T>
//首节点
QualdListNode<T>* QuadList<T>::first()const
{
    return header;
}

template<class T>
//尾节点
QualdListNode<T>* QuadList<T>::last() const
{
    return trailer;
}

template<class T>
//判断是否合法
bool QuadList<T>::valid(QualdListNode<T>* p)
{
    return p && (p != header) && (p != trailer);
}

template<class T>
//判断是否为空
bool QuadList<T>::empty()
{
    return _size == 0;
}

template<class T>
//初始化表
void QuadList<T>::init()
{
    header = new QualdListNode<T>; //头哨兵节点
    trailer = new QualdListNode<T>; //尾哨兵节点
    header->succ = trailer; //横向哨兵
    header->pred = nullptr;
    trailer->pred = header;
    trailer->succ = nullptr;
    header->above = nullptr;
    header->below = nullptr;
    trailer->above = nullptr;
    trailer->below = nullptr;
    _size = 0;
}

template<class T>
//删除所有节点
int QuadList<T>::clear()
{
    int oldsize = _size;
    while (_size > 0)
    {
        remove(header->succ);
        return oldsize;
    }
}

template<class T>
//删除节点
T QuadList<T>::remove(QualdListNode<T>* p)
{
    p->pred->succ = p->succ;
    p->succ->pred = p->pred;
    T e = p->entry;
    delete p;
    return e;
}

template<class T>
//插入结点
QualdListNode<T>* QuadList<T>::insertAfterAbove(T const& e, QualdListNode<T>* p, QualdListNode<T>* b)
{
    _size++;
    return p->insertAsSuccAbove(e, b);
}

尽管不必要的重复词条会浪费一定的空间，但是通过空间换时间提高了跳转表的结构效率,跳转表的查询和动态操作仅需要O(logn)的时间。。
如果每个词条都有很多重复，不仅接近于链表O(n)的效率，更是没有必要的浪费。因此约定，在Sk中出现的节点，也出现在Sk+1中的概率为1/2，也就是说，总体上，每一层节点只有它下一层节点数量的的一半。

template<typename K, typename V>
//跳转表
class Skiplist :public Dictionary<K, V>, public List<QuadList<Entry<K, V>>* >
{
protected:
    bool skipSearch(ListNode<QuadList<Entry<K, V>>*>*& qlist, QualdListNode<Entry<K, V>>*& p, K& k); //内部查找算法
public:
        int size() const { return empty() ? 0 : last()->data->size(); };
        int level() { return List:: size(); };
        bool put(K k, V v); //插入词条
        V* get(K k);
        bool remove(K k);
};

template<typename K, typename V>
//内部查找算法
bool Skiplist<K,V>::skipSearch(ListNode<QuadList<Entry<K, V>>*>*& qlist, QualdListNode<Entry<K, V>>*& p, K& k)
{
    while (true) //遍历每一层
    {
        while (p->succ && (p->entry.key <= k)) //从前到后找更大的key
        {
            p = p->succ;
        }
        p = p->pred; //往回走一个结点
        if (p->pred && (k == p->entry.key))
        {
            return true;
        }
        qlist = qlist->succ; //转入后一层
        if (!qlist->succ) //查询失败
        {
            return false;
        }
        p = (p->pred) ? p->below : qlist->data->first(); // 转至当前塔的下一个结点
    }
}

template<typename K, typename V>
//插入词条
bool Skiplist<K,V>::put(K k, V v)
{
    Entry<K, V> e = Entry<K, V>(k, v); //待插入词条
    if (empty())
    {
        insertAsFirst(new QuadList<Entry<K, V>>); //插入首个Entry
    }
    ListNode<QuadList<Entry<K, V>>*>* qlist = first(); //四联表顶层
    QualdListNode<Entry<K, V>>* p = qlist->data->first(); //首节点
    if (skipSearch(qlist, p, k)) //如果找到结点
    {
        while (p->below)
        {
            p = p->below; //转到塔底
        }
    }
    qlist = last();
    QualdListNode<Entry<K, V>>* b = qlist->data->insertAfterAbove(e, p);
    while (rand() & 1)
    {
        while (qlist->data->valid(p) && !p->above)
        {
            p = p->pred;
        }
        if (!qlist->data->valid(p))
        {
            if (qlist == first())
            {
                insertAsFirst(new QuadList<Entry<K, V>>);
            }
            p = qlist->pred->data->first()->pred;
        }
        else
        {
            p = p->above;
        }
        qlist = qlist->pred;
        b = qlist->data->insertAfterAbove(e, p, b);
    }
    return true;
}

template<typename K, typename V>
V* Skiplist<K, V>::get(K k)
{
    if (empty())
    {
        return nullptr;
    }
    ListNode<QuadList<Entry<K, V>>*>* qlist = first(); //从顶层获得quadlist
    QualdListNode<Entry<K, V>>* p = qlist->data->first(); //首节点开始
    return skipSearch(qlist, p, k) ? &(p->entry.value) : nullptr; //返回值
}

template<typename K, typename V>
bool Skiplist<K, V>::remove(K k)
{
    if (empty()) //空表
    {
        return false;
    }
    ListNode<QuadList<Entry<K, V>>*>* qlist = first();
    QualdListNode<Entry<K, V>>* p = qlist->data->first();
    if (!skipSearch(qlist, p, k)) //如果搜索不到词条
    {
        return false;
    }
    do {
        QuadListNode<Entry<K, V>>* lower = p->below; //记住下一层结点
        qlist->data->remove(p); //删除当前层结点
        p = lower;
        qlist = qlist->succ;
    } while (qlist->succ);
    
    while (!empty() && first()->data->empty())
    {
        List::remove(first());
    }
    return true;
}

四、散列表

1. 数组、链表和散列表

数组的特点是寻址容易，但是插入和删除困难。
链表的特点是寻址困难，插入和删除容易。
散列表结合了数组和链表的特性，寻址容易，插入和删除也容易。
以上图为例，左边的 $keys$ 很明显是个数组，数组的每个成员包括一个指针，指向一个链表 $bucket$ 的头。
根据元素的一些特征(hash function)把元素分配到不同的链表中去。
也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

2. 关于散列表

散列表(Hash table,也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构，不用像数组或链表一样需要遍历。
逻辑上由一系列可存放词条的单元组成，这些单元也称作桶(bucket)。
桶按照逻辑次序在物理上连续排列，通常使用数组保存，称作桶数组(bucket array)。
若桶数组的容量为 $R$ ,则其合法秩的区间 $[0,R)$ 也称作地址空间(address space)。
散列表的查询速度非常快，几乎是O(1)的时间复杂度。

3.关于完美散列

如果每个桶恰好放进一个词条，即无空余又无重复，这种散列称为完美散列(perfect hashing)。
完美散列在时间和空间性能均达到最优。
完美散列在十分特定的条件下才成立，实际上并不常见。

4. 关于散列函数

散列函数(hash function)主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值。
也可以说，散列函数就是到一种数据内容和数据存放地址之间的映射关系： $hash() : key -> hash(key)$ 。
散列函数的种类有很多，包括：

方法	简介
直接定址法	即 f(key) = a*key + b，f表示散列函数，a、b是常量，key是键值。
数字分析法	即对数字做左移、右移、反转等操作获取散列值。
除数留余法	即 f(key) = key % p，p 表示容器数量，这种方式通常用在将数据存放到指定容器中，如何决定哪个数据放到哪个容器，比如分表后插入数据如何处理（此时p表示拆分后数据表的数量），分布式Redis如何存放数据（此时p表示几台Redis服务器）。
随机数法	即 f(key) = random(key)，比如负载均衡的random机制。

5. 关于散列冲突

散列冲突指的是 key1 != key2 的情况下，通过散列函数处理，hash(key1) == hash(key2)，即不同的key获得了相同的哈希值。
由于散列值是非负整数，总量是有限的，但是现实世界中要处理的键值是无限的，将无限的数据映射到有限的集合，肯定避免不了冲突。
装载因子 = 元素个数/散列表长度，装载因子越大，说明空闲位置越少，冲突越多，散列表的性能越低。
对于散列冲突，可以通过以下方法来解决：

5.1 开放寻址法

开放寻址法的核心思想是: 如果出现了散列冲突，就重新探测一个空闲位置。

1) 线性探测法(Linear Probing)

插入数据：当往散列表中插入数据时，如果某个数据经过散列函数之后，存储的位置已经被占用了，就从当前位置开始，依次往后查找（到底后从头开始），看是否有空闲位置，直到找到为止。

查找数据：通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素是否相等，若相等，则说明就是我们要查找的元素；否则，就顺序往后依次查找。如果遍历到数组的空闲位置还未找到，就说明要查找的元素并没有在散列表中。

删除数据：为了不让查找算法失效，可以将删除的元素特殊标记为deleted，当线性探测查找的时候，遇到标记为deleted的空间，并不是停下来，而是继续往下探测。

2) 二次探测(Quadratic probing)

线性探测每次探测的步长为1，即在数组中一个一个探测，而二次探测的步长变为原来的平方。

3) 双重散列(Double hashing)

使用一组散列函数，直到找到空闲位置为止。

5.2 链表法

把一个文件的记录分为若干存储桶，每个存储桶包含一个或多个页块，一个存储桶内的各页块用指针连接起来，每个页块包含若干记录。散列函数h把关键码值K转换为存储桶号，即h(K)表示具有关键码值K的记录所在的存储桶号。
插入数据：当插入的时候，我们需要通过散列函数计算出对应的散列槽位，将其插入到对应的链表中即可，所以插入的时间复杂度为O(1)。
查找或删除数据：当查找、删除一个元素时，通过散列函数计算对应的槽，然后遍历链表查找或删除。对于散列比较均匀的散列函数，链表的节点个数k=n/m，其中n表示散列表中数据的个数，m表示散列表中槽的个数，所以是时间复杂度为O(k)。
两种方法对比：

方法	优点	缺点	适用场景
开放寻址法	1、数据存储在数组，可以有效利用CPU缓存加速查询速度 2、序列化简单	1、删除需要特殊标记已删除数据 2、所有数据存储在一个数组，发生冲突时，解决的代价更高，造成装载因子不能太大，使得更加浪费内存空间	1、数据量小 2、装载因子小
链表法	1、内存利用率高，需要时再申请 2、对大装载因子容忍度高，可大于1	1、因为链表需要存储指针，存储指针需要消耗内存，不适合小对象存储 2、链表节点不是连续空间，因此CPU缓存不友好	1、存储大对象、大数据量的散列表 2、支持更多优化策略，如红黑树代替链表。

5.3 实现散列表

#pragma once
#include <iostream>
#include <string>
#include <vector>
using namespace std;

template<class T>
//散列表节点
struct Node
{
    T key;
    string name;
    Node<T>* next;
};

template<class T>
//散列表
class hashTable
{
public:
    hashTable(); //构造函数
    void insert(T key, string name); //插入
    void del(T key);
    void del(T key,string name); //删除
    Node<T>* search(T key);
    Node<T>* search(T key,string name);
private:
    void insert(Node<T>* node);
    void del(Node<T>* node); 
private:
    vector<Node<T>*> _map;
    int _hash(T key);  //哈希函数
};

template<class T>
int hashTable<T>::_hash(T key)
{
    return (key * 50) % 41; //hashfunciton算法
}

template<class T>
hashTable<T>::hashTable()
{
    _map.resize(100);
    for (int i = 0; i <= 50; i++)
    {
        _map[i] = nullptr;
    }
}

template<class T>
//插入
void hashTable<T>::insert(Node<T>* node)
{
    node->next = _map[_hash(node->key)];
    _map[_hash(node->key)] = node;
}

template<class T>
void hashTable<T>::insert(T key, string name)
{
    Node<T>* node = new Node<T>;
    node->key = key;
    node->name = name;
    insert(node);
}

template<class T>
//删除
void hashTable<T>::del(Node<T>* node)
{
    del(node->key, node->name);
}

template<class T>
void hashTable<T>::del(T key)
{
    if (_map[_hash(key)] == nullptr)return; //如果没有对应key
    int num = _hash(key);
    Node<T>* node = _map[num];
    while (_map[num])
    {
        node = _map[num];
        _map[num] = node->next;
        delete node;
    }
}

template<class T>
void hashTable<T>::del(T key, string name)
{
    if (_map[_hash(key)] == nullptr)return;
    int num = _hash(key);
    Node<T>* p = _map[num];
    Node<T>* q = _map[num];
    while (p)
    {
        if (p->name == name)break;
        q = p;
        p = p->next;
    }
    if (q == _map[num] && p == q)
    {
        _map[num] = p->next;
    }
    else
    {
        q->next = p->next;
    }
}

template<class T>
//查找
Node<T>* hashTable<T>::search(T key)
{
    return _map[_hash(key)];

}

template<class T>
//查找
Node<T>* hashTable<T>::search(T key,string name)
{
    if (!_map(_hash(key)))return nullptr;
    Node<T>* node = _map[_hash(key)];
    while (node)
    {
        if (node->name == name)
        {
            return node;
        }
        node = node->next;
    }
    return nullptr;
}