一、红黑树和哈希表的对比
- 时间复杂度： 红黑树增删改查的时间复杂度都是
O(logN)，这个是相对稳定的，即使最差情况下，时间复杂度不会改变。哈希表增删改查的时间复杂度为O(1)。并且查找速度和数据量大小基本无关。但是时间复杂度不太稳定，在插入或删除操作时，如果发生哈希冲突了，最坏的时间复杂度能达到O(n)。 - 存储的数据是否有序：红黑树存储的数据有序，遍历时按照 key 的大小顺序排列。哈希表存储的数据无序。
- 范围查找的效率：红黑树可以进行范围查找。哈希表想要范围查找的话，需要遍历整个哈希表。
- 缓存利用率：红黑树较低，红黑树节点之间通过指针连接，可能存在不同的节点存储的不同的内存块，访问时缓存命中率低。哈希表因为存储在一个数组中，因此访问时缓存命中率高。
- 占用内存：红黑树可能占用的内存可能会小一点，仅仅需要为其存在的节点分配内存。而哈希表需要提前分配足够的内存空间存储列表。
二、解决哈希冲突
- 链地址法：哈希表的节点存储着一个链表，对于重复 hash_key 的节点，存储在哈希表节点的链表上即可。像 java 中的哈希表使用链地址法，当链表长度大于 8 时，转换成红黑树存储。
- 线性探测法：从发生冲突的节点起，依次判断下一个节点是否为空，当达到最后一个节点时，再从哈希表表头依次判断。直到碰到空闲的节点，或者探测完所有节点为止。
- 平方探测法：发生冲突时，用发生冲突的节点下标 index，加上
1^2、2^2、3^2、4^2 ... N^2。即index+1^2, index+2^2, index+3^2 ...直到找到空闲单元。在实际操作中，平方探测法不能探测全部剩余的元素。不过在实际应用中，能探查到一半节点也就可以了。若探查到一半节点仍找不到一个空闲节点，表明此哈希表太满，应该重新建立。 - 再哈希法：同时构造多个哈希函数，第一个哈希函数计算出来的 key 冲突时，在用第二个哈希函数计算 key，直到冲突不再产生。这种方法会增加计算时间。
- 建立公共溢出区：将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出的节点统一放到溢出区中。
三、c++的 unordered_map 解决哈希冲突方法
在哈希表中，数组的每一个元素称为桶（bucket）。在每个桶中存储的是一个哨兵节点，指向一个链表。插入时采用头插法，所以新增一个元素的时间复杂度还是为 O(1)。
当一个桶中的链表长度太长时，查找和删除的时间复杂度会变高为 O(N)。因此当哈希表中的负载因子（元素个数与桶的个数的比值）大于等于最大负载因子时，哈希表就会发生 rehash 行为。即先进行扩容，分配一块更大的内存，来容纳更多的桶。然后将原来哈希表中的元素重新插入到新的桶中。相当于，rehash 过后，桶的数量增加了，而元素的个数不变。
不同编译器的扩容策略可能不同，不过目前 msvc 和 g++ 中的最大负载因子为 1，也就是哈希表中元素个数和桶的个数相同时，即可触发 rehash 过程。