UnOrderedMap UnSortedMap --> C++

哈希表（无序组织）

哈希表如果只有key 没有 value 是HashSet

哈希表如果有key 有 value 是HashMap

哈希表在使用的过程中所有的增删改查都是常数时间（比较大）

如果存放的是基础类型，内部按值传递，内存占用局势这个东西的大小

如果传入的不是基础类型，哈希表是直接把内存地址做一个拷贝，放到哈希表里面，一律是8字节

有序表：

OrdereSet OrdereMap -->C++

可以理解为一种集合结构

如果只有key，没有value是TreeSet

如果有key 有value 是TreeMap

内部根据key有序组织

性能和哈希表相比是差一点的是O（logN）级别的

红黑树（基于颜色变量）时间复杂度O（logN）

最优二叉树 转换机制 由2-3-4树转换

1.每个节点不是红色就是黑色

2.根结点永远是黑色

3.每个叶子结点都是黑色，并且是null

4.如果一个节点是红色的，那么它的子节点一定是黑色（不会出现相邻的红色节点）

5.从根节点到任意一个叶子节点 路径上黑色节点数目相同（黑色高度一致性，限制路径上黑色节点的数量）

重要结论：在红黑树上没有一条路径比其他路径长超过两倍，最多两倍（2log（n+1））

最短路径：黑+黑+黑

最长路径： 黑+红+黑+红+黑+红 交替

时间复杂度：比较层数

在插入一个数后，需要进行双红纠正：

1.节点左右旋转

2.改变节点颜色

AVL数（基于左右子树的高度差），size-balance-tree和跳表等都属于有序表结构，知识底层具体实现不同

如果放入的是基础类型，内部按值传递

如果不是基础类型，必须提供比较器，内部按引用传递

回文结构：

慢指针一次走一步，快指针一次走两步，可以实现找到中点（具体问题，具体分析，需要设计）笔试里面可以使用栈快速解决，面试的时候需要考虑到空间问题，使用快慢指针找到中点位置，然后让中点指向空，后面的数指向中点，再从左右两侧开始比对是否相同，都到中点后停止比对，再将链表恢复成之前的样子返回值

栈方法

不加入堆的方法

新老链表问题

使用hashmap

不使用

环 找第一个如环节点，如果一个链表有环那么就不可能绕完环再绕出来

一个快指针一个慢指针，两个指针一定会在环内相遇，且由于快指针是慢指针的两倍速度，所以在环内不会超过两圈，再相遇时把快指针放回到头部，并且都设为一次走一步，最终两个指针会在节点处相遇。

两个长度不一样的链表，如果想要找他们的相交点，如果长链表长度100，锻炼表长度80，此时需要长链表先走20步，然后两个表一块走，因为在相交时候 后面的长度一定是一样的。找这种需要先判断链表最低端的地址是否相同。

两个有环链表，返回第一个相交节点，如果不相交返回null

分为三种情况