基础概念

数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度O(1)，通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度O(n)。

线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理节点间的引用即可，时间复杂度为O(1)，而查找操作需要便利链表逐一进行比对，复杂度O(n)

红黑树：红黑树是一种特化的AVL数（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能

hashmap基础操作有put和get方法

put

hashmap存储数据时，先把value封装成一个node，接着调用key的hashcode方法，获取key的哈希码，再通过一个转换算法将hashcode转换成桶的下标

如图示key=8的节点

c此时数组当前下标的结构没有值

那就直接将这个node节点放在下标下

如果当前节点下标有值，如图示key=30节点（尾插法）

那么会将key=30和链表上的每一个值进行比较，如果equal都返回false，那么就会key所在的node节点追加到链表的最后面，如果key和链表的某个节点equal=true，那么就会将key所在的node节点直接进行覆盖

get

现根据key值计算出hashcode，将hashcode通过算法转化成数组的下标，如果当前下标为null，则直接返回空，如果当前下表是一个链表，那会使用equal依赖和链表上的节点进行比较，如果都返回false，则返回空，如果其中有一个节点为 true ，则放回当前节点，JDK8之后，如果哈希表单向链表中元素超过8个，那么单向链表这种数据结构会变成红黑树数据结构，当红黑树上的节点数量小于6个，会重新吧红黑树变成单向链表数据结构，其核心目的也是提升和均衡搜索效率。

 对红黑树的理解

每个节点不是黑色就是红色，根节点是黑色的，如果一个节点是红色的，则它的两个孩子都是黑色的，对于每一个节点，从该节点到其所有后代叶结点的路径上，均包含相同数目的黑色节点，每一个叶子节点都是黑色的（红黑树是一个不完美的平衡二叉树），红黑树比平衡二叉树更为复杂，红黑树引入颜色的概念，引入红色的概念是使得红黑树的平衡条件得以简化（O(log₂)）,此外任何不平衡都会在三次旋转之内解决

1. hashmap默认是一个定长数组（扩容）
2. size：表示HashMap中存放KV的数量（为链表和树中的KV的总和）
3. capacity：容量，capacity是指HashMap中桶的数量，默认值为16.一般第一次扩容会扩容到32，之后好像是两倍。总之，容量都是2的幂。
4. loadFactory：转载因子，转载因子用来衡量HashMap满的程度。loadFactory的默认值为0.75f。计算HashMap的实时转载因子的方法为：size/capacity。而不是占用桶的数量去除以/capacity

loadFactory = 3/2=1.5 > 1.2  扩容 

 扩容 ：size = 4

threshold：表示当HashMap的size大于threashold时会执行 resize 操作

hashmap的注意事项

（1、）扩容是一个特别好性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容

（2、）负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊

当负载因子较大时，去给table数组扩容的可能性就会少，所以相对占用内存较少（空间上较少），但是每条entry链上的元素相对较多，查询的时间也会增长（时间上较多）

注意：设置initCapacity的时候，尽量设置为2的幂，这样会去掉计算比 initCapacity 大，且为 2 的幂的数的运算。

（3、）HashMap是线程不安全，不要在并发的环境中同时操作HashMap，建议使用 ConcurrentHashMap 

（4、）JDK1.8 引入红黑树大程度优化了 HashMap的性能