map

突然发现一个华科大佬的博客，学习一波

map是一种映射结构，能够存取键值对（键是唯一的）

map通常有两种实现方式：哈希表（std::unordered_map）、红黑树（std::map）

哈希表

哈希表的查找删除均为O(1)

哈希表是一种空间换时间的算法，现在我们要存储一组键值对，假设键的范围是0~99，那么我们就开辟一个大小为100的数组，数组中存储了指向值的指针，于是我们就可以通过Key去数组中找指针，再找到值

value = a[key];

不过开辟大小为100的数组过于昂贵了，只开辟大小为10的数组，Key去找值时先取模，再去数组中找指针

value = a[key%10];

不过这样也带来了一个问题，我们无法区分key==21和key==31，这种情况我们称之为哈希冲突，我们称21和31为同义词

解决哈希冲突的方式有：

开放地址法
拉链法

拉链法

Key取模后去数组中找指针，这个指针是一个链表的头，遍历链表，找到对应Key的value

这种方法非同义词间不会影响

point = a[key%10];
while(point != nullptr)
{
    if(point->key != key)
    {
        point = point->next;
    }
    else
    {
    	break;    
    }
}
value = point->value;

红黑树

红黑树的查找删除为O(logN)，但是空间效率更高

红黑树是一种自平衡的二叉搜索树，每个节点是黑色或红色

二叉搜索树

二叉搜索树（BST）：排序二叉树，任意一个根节点，其左子树Key均小于根，其右子树Key均大于根

BST的操作复杂度取决于树的高度，但某些情况下BST会退化为一条链

平衡二叉树

平衡二叉树（AVL）：左右子树的高度差不能大于1，操作过程中树一旦不稳定，就会进行旋转，以重新恢复平衡

红黑树

红黑树左右子树高度差不能超过一倍

所有null节点都认为是黑色。
一个红节点不能有红色孩子，即红色节点之间不能相邻。
红黑树中的节点到其任意叶子节点路径上的黑节点个数相同。
新插入的节点都是红色，在平衡过程中可能变色。

红黑树比平衡二叉树更容易保持平衡，于是效率更高

参考

辜飞俊的博客