映射是最重要的数据结构之一，动态数组也可以看做特殊的映射。映射的优势是，它的增删改查性能都很好。增->增加key，删->删除key，改->更改某key的vakue，查->给定key查询value。

映射结构

C++ STL 对映射有两种实现，红黑树和哈希表。

红黑树

红黑树是在AVL树发展的二叉有序平衡树。AVL树通过左旋、右旋实现了高度平衡树，查询更改性能稳定O(n/2)，但频繁插入删除会造成经常的rebalance，造成插入、删除性能下降。

红黑树有以下要求

  1. 每个节点都是红色或黑色。
  2. 根节点始终是黑色。
  3. 每个叶节点（NIL 或空节点）是黑色。（实际红黑树叶子节点是黑色的NIL，NIL不存储数据，存储数据的“叶子节点”可以为红色）
  4. 从任意节点到其每个叶节点的所有路径中，包含相同数量的黑色节点。
  5. 红色节点的两个子节点必须是黑色（红色节点不能有两个连续的红色节点）。

rbtree

插入操作时，新插入的节点被视为红色（孩子是黑色的NIL）。如果新插入节点的父节点为黑色，插入后不需要调整。只有当插入节点的父节点为红色，才需要调整。

删除操作类似，删除的节点如果是红色，调整较少；只有删除的节点是是黑色，才需要重新调整

具体后面有时间再分析吧2333

STL 哈希表

哈希表的实现主要有两部分 1. hash计算索引 2. 哈希碰撞处理

哈希表需要根据类型key计算hash key，来确定变量在hash表的位置。C++ hash函数使用std::hash模版函数计算hash key

  1. 对于整数类型，通常直接返回值本身或经过简单混淆的值（如乘以某个大素数）。
  2. 浮点型，std::hash 会将其二进制表示重新解释为整数，然后对该整数值计算哈希。
  3. 字符串类型，std::hash<std::string> 通常使用简单的字符串哈希算法, 例如DJB2 算法。DJB2通过逐字符累积计算哈希值，每次累积时将现有的哈希值乘以一个素数（通常是 33），再加上当前字符的 ASCII 值。
  4. 指针，通常直接使用指针的值（地址）

哈希碰撞处理，通常使用开链法。

在hash表碰撞不严重的情况下，哈希表的增、删、改、查时间复杂度都是O(1)。另外，由于hash表的数组是预先分配好的，动态处理比红黑树简单很多。例如hash表可以通过key数量除以数组长度作为负载因子来判断是否应该扩容缩容。（相比下，红黑树没有扩缩容的概念？）

hash表的数组（slot）长度通常选择素数（减少冲突），或者选择2的幂次，容易使用按位操作（hash & (bucket_count - 1)）来快速定位索引。

hash表扩缩容也称为rehash，数组size为素数的扩容，size选择距离扩容前size两倍最近的素数；数组size为2的幂次的扩容，size直接乘2即可。

rehash单线程场景下，rehash操作在用户程序进程执行（可以在调用插入命令后触发，也可手动调用rehash函数触发）。

多线程情况下，rehash往往由后台线程执行，需要考虑和前台io线程的冲突。一般来说，前台io线程或后台扫描线程根据负载因子，触发rehash，rehash首先创建扩容后的数组。创建完后通知前台io线程数据正在rehash。

rehash是从旧表读数据，向新表插数据。本质是个增操作，单位是key

  1. 增操作
    1. 如果数据在旧表不存在，则直接新hash表增加key，多线程的数据增操作很重，需要对整个hash表（或分段）加锁
    2. 如果数据已存在，则判断key是否rehash完毕。如果rehash完毕，在新表删除旧key然后加新key; 没有rehash则旧表删除旧key,新表增加新key；如果正在rehash，需要等rehash完抢到锁，然后在新表删除旧key然后加新key
  2. 删操作
    1. 数据在旧表不存在，报错
    2. 数据在旧表存在，类似增操作。需要看key的rehash状态，rehash完在新表删除，否则在旧表删除
  3. 改操作
    1. 数据在旧表不存在，报错
    2. 数据在旧表存在，如果key rehash完毕，在新表改；否则在旧表改
  4. 查操作
    1. 先查询新表，新表查询不到则查询旧表。

哈希表的rehash是一个数据迁移操作，对表迁移有很大参考意义。更进一步

  1. hash表支持将某个value从key1，移动到key2，需要是原子的（即文件系统的rename）。多线程时需要对key1和key2加锁，需要避免死锁。此外，rehash时应该怎么处理？
  2. hash表怎么拆分，key锁，插入锁，怎么优化。

问题1, rehash时，可能出现key1在旧hash表, key2在新hash表。为了死锁避免，一张表或一个segment只同时刻允许一次rename（可使用单线程多协程实现），为了保证rename的原子性（即删除key1,增加key2两个操作需要原子性），可以使用事务。更复杂的，两张表可能不在一个机器上，需要更复杂的死锁避免，同时为了保证原子性需要分布式事务。

跳跃表

hash表的的数据排布是无序的，常用的有序替代品是跳跃表skiplist。redis，leveldb, rocksdb的有序内存集合都是使用跳跃表实现。由于内存数据不能持久化，redolog+跳跃表的组合是kv单机存储引擎最常见的组合。

使用redolog的表迁移(rehash)，可以选择让新表一直replay redolog来让数据和旧表保持一致。但这种办法不能实现彻底的热迁移，当检测到写请求少时（例如晚上），旧表会禁止用户写入，等待新表replay完毕，将新表配置成接受读写请求的表。期间会有短暂的写不可用，不可用时间主要来自等待新表replay完毕和必要的数据校验。这种表迁移比较简单，尤其当表被拆分到多个机器中（分布式表），只需要让机器1和机器2能共享相同的redolog文件。例如把redolog存储到hdfs中，当机器A的表尝试rehash到机器2时，只需要机器2 replay写到hdfs中的机器1的redolog即可。replay过程中，数据读写照常在机器1进行，直到监控到写请求少，进行短暂的禁写等待机器2replay完毕，然后通知placement该表的后续读写路由到机器2，即可。

越简单的实现越安全，越可控。所以生产上尤其是分布式系统中，表迁移大多数借助replay redolog实现。

JAVA hashmap和线程安全hash表

java 的hashmap实现和C++的unordered_map大同小异，采用头插法处理碰撞，非线程安全。

java的每个对象都会有hashcode函数，hashcode可被重写，默认使用对象的地址。hashcode决定了对象插入到hash表时的hash key。

前面说到，hash表多线程增删操作很重，需要对全表加写锁；改操作只需要对key加写锁。java hashtable的线程安全就是通过全表加锁实现。

为了降低锁的粒度，JAVA ConcurrentHashMap 实现segment->table两级哈希表。定位元素需要进行两次Hash，第一次 Hash 定位到 Segment，第二次 Hash 定位到元素所在的链表的头部。加锁只需要对segment加写锁，不影响其他segment。

使用多级hash表还可以降低存储空间的占用，可参考MMU 虚拟内存->物理内存映射的哈希表。对于两个key 10、499，一张哈希表需要512个slot，两张哈希表只需要256+26=282个slot。

JAVA volatile关键字保证的可见性可以实现多线程查询操作无锁，通过使用volatile修饰key，get操作不用加锁。使用final修饰常量，也可以保证查操作无锁。

golang的map和sync.Map

golang的map是非协程安全的，go提供协程安全map sync.Map。

golang map 使用开链法处理冲突。初始时map的键值对存放到哈希桶中，哈希桶是一个对象，可以放置 8 个键值对。超出哈希桶后的键值对存放到溢出桶，溢出桶就是开链法的链表。

sync.Map的实现比较特殊，使用了两个原生map，一个叫read，仅用于读；一个叫dirty，用于存储最新写入的key-value数据。read map相当于读缓存

  1. 写操作：直接写入dirty map
  2. 读操作：先读read map，没有再读dirty map

Python的dict

Python的映射称之为字典，dict

python使用P开放地址法（Open Addressing） 来解决冲突。当计算出的索引位置已被占用时，通过一定的规则寻找下一个空闲位置。Python 字典采用了一种变体的开放地址法，称为 探测（Probing），通常是线性探测或伪随机探测。

当字典中的元素数量接近数组的容量时，数组会扩展到原来容量的两倍。

Python的可变对象（如列表）不可哈希，不能作为字典的键。只有不可变对象（如字符串、元组）才可以作为dict的键。

dict不是线程安全的

其他常见数据结构的实现

TODO