u8,u8国际,u8国际官方网站,u8国际网站,u8国际网址,u8国际链接,u8体育,u8体育官网,u8体育网址,u8注册,u8体育网址,u8官方网站,u8体育APP,u8体育登录,u8体育入口
哈希表的概念请参阅他人文章，关于哈希冲突的解决这篇文章基本都整理到了，还有几个常见的面试题。
主要有：常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。
BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算法本质是相似的。
通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi，将相应元素存入其中。
其中H（key）为哈希函数，m为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。
这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
（坏处是只能探测到哈希表长度的一半，会浪费一定空间，但若是真的探测到一半的位置了，说明哈希函数的设置有问题，应重选哈希函数）
具体实现时，应建立一个伪随机数发生器，（如i=(i+p)%m），并给定一个随机数做起点。
例如，已知哈希表长度m=11，哈希函数为：H（key）=key%11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。
如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3+1）%11=4，仍然冲突，再找下一个哈希地址为H2=（3+2）%11=5，还是冲突，继续找下一个哈希地址为H3=（3+3）%11=6，此时不再冲突，将69填入5号单元。
如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3+12）%11=4，仍然冲突，再找下一个哈希地址为H2=（3-12）%11=2，此时不再冲突，将69填入2号单元。
如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，………，则下一个哈希地址为H1=（3+2）%11=5，仍然冲突，再找下一个哈希地址为H2=（3+5）%11=8，此时不再冲突，将69填入8号单元。
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数
组T[0…m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
1）优点：①对于记录总数频繁可变的情况，处理的比较好（也就是避免了动态调整的开销）②由于记录存储在结点中，而结点是动态分配，不会造成内存的浪费，所以尤其适合那种记录本身尺寸（size）很大的情况，因为此时指针的开销可以忽略不计了③删除记录时，比较方便，直接通过指针操作即可
2）缺点：①存储的记录是随机分布在内存中的，这样在查询记录时，相比结构紧凑的数据类型（比如数组），哈希表的跳转访问会带来额外的时间开销②如果所有的key-value对是可以提前预知，并之后不会发生变化时（即不允许插入和删除），可以人为创建一个不会产生冲突的完美哈希函数（perfecthashfunction），此时封闭散列的性能将远高于开放散列③由于使用指针，记录不容易进行序列化（serialize）操作
1）优点： ①记录更容易进行序列化（serialize）操作 ②如果记录总数可以预知，可以创建完美哈希函数，此时处理数据的效率是非常高的
2）缺点： ①存储记录的数目不能超过桶数组的长度，如果超过就需要扩容，而扩容会导致某次操作的时间成本飙升，这在实时或者交互式应用中可能会是一个严重的缺陷
②使用探测序列，有可能其计算的时间成本过高，导致哈希表的处理性能降低 ③由于记录是存放在桶数组中的，而桶数组必然存在空槽，所以当记录本身尺寸（size）很大并且记录总数规模很大时，空槽占用的空间会导致明显的内存浪费 ④删除记录时，比较麻烦。比如需要删除记录a，记录b是在a之后插入桶数组的，但是和记录a有冲突，是通过探测序列再次跳转找到的地址，所以如果直接删除a，a的位置变为空槽，而空槽是查询记录失败的终止条件，这样会导致记录b在a的位置重新插入数据前不可见，所以不能直接删除a，而是设置删除标记。这就需要额外的空间和操作。
(1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
(3)开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
(4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
相同：两者都是键-值对的集合，关联容器的一种。两者中的元素都是pair，同时拥有实值和键值。两者都不允许有两个相同的键值（实值可以相同）。两个的外部接口调用基本一致。
不同：内部实现机理不同，即map内部实现了一个红黑树；unordered_map内部实现了一个哈希表。（两者的比较成为红黑树与哈希表的比较）。由于内部实现机理不同（底层实现）造成以下不同。
map的有序性：红黑树（非严格平衡二叉树），该结构具有自动排序的功能，因此map内部的所有元素都是有序的。
unordered_map的无序性：哈希表不会根据key值大小进行排序，存储时是根据key的hash值判断元素是否相同，因此unordered_map内部元素是无序的。
map的运行效率：红黑树可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。
定义：RB-tree是一个需满足以下规则的二叉搜索树 每个结点不是红色就是黑色 根结点为黑色 每个叶结点（空结点）是黑色的
每个红色结点的两个子结点都是黑色的 从任一节点到其每个叶子结点的所有路径都包含相同数目的黑色节点。 为什么红黑树是一种好的搜索树
一棵内部有n个结点的红黑树的高度至多为2∗logn（性质4）。这保证了红黑树任意操作的复杂度都是O(logn)。
目的：红黑树在插入，删除过程中可能会破坏原本的平衡条件导致不满足红黑树的性质，这时候一般情况下要通过左旋、右旋和重新着色这个三个操作来使红黑树重新满足平衡化条件。
左旋 右旋 重新着色 哈希表 定义：散列表（Hash table，也叫哈希表），是根据关键码值(Key
value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希函数 直接寻址法 数字分析法、 平方取中法 折叠法 随机数法 除留余数法 解决碰撞（冲突）： 开放寻址法：Hi=(H(key) +
RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
链地址法：如果遇到冲突，会在原地址新建一个空间，然后以链表结点的形式插入到该空间。
不同关键字通过相同哈希计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
查找索引当然会很快，不过只有无冲突的hash table复杂度才是O(1)，一般是O（c），c为哈希关键字冲突时查找的平均长度。
开放地址法是当发生冲突时，使用某种探查技术在散列表中形成一个探查序列，按照这个序列逐个单元查找，直到找到合适的位置。线性探测法使得大量元素在相邻地址出现“聚集”现象，降低效率。主要是解决冲突算法选择不好，如果选择平方探测法即二次探测再散列，则可以有效减少堆积问题（难以避免）！
std::unordered_map使用哈希表来存储元素，元素并不是有序存储。
unordered_map比ordered_map更占用内存，因为需要额外的内存来存储哈希表。 查找时间复杂度
std::unordered_map最佳的查找时间复杂度是O(1)，如果哈希函数不是很好的话，最糟糕的复杂度会是O(n)。