一、python的字典不选用红黑树而用哈希表做数据结构的原因

哈希表是一种数据结构，它提供了快速的插入操作和查找操作，无论哈希表总中有多少条数据，插入和查找的时间复杂度都是O(1)，因为哈希表的查找速度非常快，相比之下，红黑树在大多数情况下具有 O(log n) 的时间复杂度，其中 n 是元素的数量。红黑树在某些情况下可能表现更好，但在非常大的数据集和频繁更新的场景下，哈希表通常会更快。另外，哈希表还具有较少的内存占用和更好的缓存性能（指缓存命中率高），因为它们可以使用连续的内存块，而红黑树则需要指针和链表来组织节点之间的关系。因此，python的字典一般选用哈希表做数据结构。

二、哈希表

1、哈希函数特点

哈希表的主要作用是加快查找速度，时间复杂度可以近似看成O(1)，了解哈希表首先得明白哈希函数。哈希函数的特点为：

其输入无限，输出有限。每次相同的输入一定得到相同的输出。不同的输入也可能产生相同的输出。（哈希碰撞）输出分布是绝对离散的，不会受输入的影响，即同样的面积在任何地方框点都是差不多的。（最重要，哈希函数主要利用这个性质）任何值模上一个数，最后一定得到0-该数的一个范围值。比如任何数模（或者说取余）上100，最后得到的值一定在0-99范围内。并且是绝对均匀分布。

哈希函数的目的是用于哈希表的名列前茅步数组查询，直接通过取模（哈希函数）就得到哈希表对应的位置。这一步的时间复杂度是O(1)。当出现数组的每个链表过长的时候，需要扩容。扩容之后全部每一条数据都得重新计算。

时间复杂度：哈希表每次增删改查的代价可以说是O(1)，虽然每次扩容的代价是O(logn)。一个原因是现实使用的工程数据量都是非常低的，另一个原因是离线技术，不占用用户使用的时候的时间。

2、哈希函数的缺点

当更多的数插入时，哈希表冲突的可能性就更大。对于冲突，哈希表通常有两种解决方案：名列前茅种是线性探索，相当于在冲突的地方后建立一个单链表，这种情况下，插入和查找以及删除操作消耗的时间会达到O(n)，且该哈希表需要更多的空间进行储存。第二种方法是开放寻址，他不需要更多的空间，但是在最坏的情况下（例如所有输入数据都被map到了一个index上）的时间复杂度也会达到O(n)。在决定建立哈希表之前，较好可以估计输入的数据的size。否则，resize哈希表的过程将会是一个非常消耗时间的过程。例如，如果现在你的哈希表的长度是100，但是现在有第101个数要插入。这时，不仅哈希表的长度可能要扩展到150，且扩展之后所有的数都需要重新rehash。哈希表中的元素是没有被排序的。然而，有些情况下，我们希望储存的数据是有序的。

3、哈希表的应用场景

C++中如unordered_map和unordered_set。哈希表适用于那种查找性能要求高，数据元素之间无逻辑关系要求的情况。例如做文件校验或数字签名。当然还有快速查询功能的实现。

三、红黑树

1、红黑树简介

红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明，在当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O(logN)时间内完成查找、增加、删除等操作。

2、为什么需要红黑树

对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡的二叉树，它的操作效率（查询，插入，删除）效率较高，时间复杂度是O(logN)。但是可能会出现一种极端的情况，那就是插入的数据是有序的（递增或者递减），那么所有的节点都会在根节点的右侧或左侧，此时，二叉搜索树就变为了一个链表，它的操作效率就降低了，时间复杂度为O(N)，所以可以认为二叉搜索树的时间复杂度介于O(logN)和O(N)之间，视情况而定。那么为了应对这种极端情况，红黑树就出现了，它是具备了某些特性的二叉搜索树，能解决非平衡树问题，红黑树是一种接近平衡的二叉树（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构，进而提升整体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。

3、红黑树的特性

在讲解红黑树性质之前，先简单了解一下几个概念：

parent：父节点sibling：兄弟节点uncle：叔父节点（parent 的兄弟节点）grand：祖父节点（parent 的父节点）

首先，红黑树是一个二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡（最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上黑色节点相同时，最长路径刚好是最短路径的两倍）。它同时满足以下特性：

节点是红色或黑色根是黑色叶子节点（外部节点，空节点）都是黑色，这里的叶子节点指的是最底层的空节点（外部节点），下图中的那些null节点才是叶子节点，null节点的父节点在红黑树里不将其看作叶子节点红色节点的子节点都是黑色红色节点的父节点都是黑色从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

延伸阅读1：红黑树的效率

红黑树的查找，插入和删除操作，时间复杂度都是O(logN)。查找操作时，它和普通的相对平衡的二叉搜索树的效率相同，都是通过相同的方式来查找的，没有用到红黑树特有的特性。但如果插入的时候是有序数据，那么红黑树的查询效率就比二叉搜索树要高了，因为此时二叉搜索树不是平衡树，它的时间复杂度O(N)。插入和删除操作时，由于红黑树的每次操作平均要旋转一次和变换颜色，所以它比普通的二叉搜索树效率要低一点，不过时间复杂度仍然是O(logN)。总之，红黑树的优点就是对有序数据的查询操作不会慢到O(logN)的时间复杂度。