Java集合面试高频问题---集合框架体系（2）🐔
Java集合--HashMap（二叉树，散列表）
hashmap 相关面试题
二叉树
满二叉树（了解）
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。
国内定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
国外(国际)定义:a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.大意为：如果一棵二叉树的结点要么是叶子结点，要么它有两个孩子结点，这样的树就是满二叉树。
国内定义的满二叉树
从图形形态上看，满二叉树外观上是一个三角形。从数学上看，满二叉树的各个层的结点数形成一个首项为1，公比为2的等比数列。
完全二叉树（了解）
叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。显然，一颗满二叉树必定是一颗完全二叉树，而完全而二叉树不一定是满二叉树。
完全二叉树的特点是：
1）只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；
2）对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个
二叉搜索树
可以快速搜索，插入
比如查找右边二叉树上的 5，所有的查找都是从根节点开始的，从第一层开始找，知道第三层找到了 5。
极端的二叉树，退化成了链表
红黑树（特殊的二叉搜索树）
红黑树的五个性质（为了保证平衡）
红黑树的时间复杂度（O（logn））
散列表（哈希表 key-value结构）
通过散列函数转换为数组下标存储其对应的值
散列函数的基本要求
散列冲突（即使是比较好的 hash 算法也不太好保证没有 hash碰撞）
拉链法解决哈希冲突
拉链法时间复杂度--插入O(1)
拉链法时间复杂度--查找与删除O(n)
改造为红黑树之后--O(logn)
改造为红黑树后可以防止 ddos攻击，避免大量 hash 冲突导致遍历变慢
