2020.10.12 java集合（1）Hashmap
Hashmap
- 哈希表（散列表）
- 红黑树
- Hashmap的底层数据结构
- Hashmap的基本操作
（一）哈希表
是什么
是一个固定大小的数组，区别于传统数组，是将关键字通过一定的哈希函数，映射到哈希数组的合适位置。映射的规则叫做哈希函数（散列函数）。
为什么
哈希函数是数据位置与特征的映射关系，根据数据的特征经过哈希函数就可找到数据的存放位置，不需要遍历，由此可以提高数据查找的效率。
哈希冲突
出现原因：
根据哈希函数数据被映射到同一个位置
解决办法：拉链法，开放定址，哈希再散列
（二）红黑树
是什么和为什么
为了避免二叉树深度过深而导致的查找耗时，所以引入红黑树。红黑树是一种自平衡的二叉查找树，难点在于，由于删除和插入破坏平衡时的修复操作。由于存在左分支，右分支，红色节点，黑色节点，父亲节点状况，叔叔节点状况，兄弟节点状况对于平衡的影响，所以经过枚举，它的平衡修复操作很多。
平衡规则
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
从性质5又可以推出：
性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点
（三）Hashmap的底层数据结构
数组+链表=>散列表 +红黑树
为了解决哈希冲突，采用了拉链法，当链表长度大于8时，链表转为红黑树
这个博客写的很详细，先到这里，后面有感悟了再写
hashmap