HashMap
**1、基于哈希表的Map接口的实现 **
此实现提供所有可选的映射操作，并允许使用null值和null键。（除了非同步和允许使用null之外，HashMap类与HashTable大致相同。）此类不保证映射的顺序，特别是它不保证顺序恒久不变。
**2、HashMap的实例有两个参数影响性能：初始值和加载因子 **
容量是哈希表中桶的数zh量，初始容量只是哈希表在创建时的容量
加载因子是哈希表在其容量自动增加之前可以多满的一种尺度，当哈希表中的条目数超出可加载因子与当前容量的乘机是，则要对该哈希表进项一个rehash操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
按照key关键字的哈希值和buckets数组的长度取模查找痛的位置，如果key的哈希值相同，Hash冲突（也是指向了同一个桶），则每一次新添加的作为头结点，而最先添加的在表尾。
HashMap中的桶的个数就是下图找那个0-n的数组的长度，存储第一个entry的位置叫桶（bucket），而桶中值存在一个值也就是链表的头结点，链表的每一个结点就是添加的一个值（HashMap内部的Entry的实例Entry有哪些属性之后再详说）
也可以这样理解，一个entry类型的存储链表的数据。数组的索引位置就是个个桶的索引的地址
从上图我们可以发现哈希链表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样规则存储到数组中呢？
一般情况是通过hash（key）%len获得，也就是元素的key的哈希值对应的数组长度的取模得到。比如上述哈希表中12%16=12、28%16=12、108%16=12、140%16=12。所以12,23,18以及140都是存储在数组下标为12的位置
HashMap简单总结
1、HashMap是链式数组（存储链式表的数组）实现查询速度可以，而且能快速的获取key对应的value
2、查询数据影响因素有容量和负载因子，容量大负载因子小查询速度快单浪费空间，反之则相反
3.数组的index值是（key关键字，hashcode为key的哈希值，len数组的大小）：hashcode%len的值来确定，如果容量大负载因子小则index相同（index相同也就指向了同一个桶）的概率小，链表长度小则查询速度快，反之index相同的概率大连表比较长查询速度慢。
4、对于HashMap以及其子类来说，他们采用hash算法来决定集合中元素的存储位置，当初始化HashMap的时候系统会创建一个长度为capacity的entry，这个数组里可以存储元素的位置称为桶（bucket），每个桶都有其指定索引，系统可以根据索引快速访问该桶中存储的元素。
5、无论何时HashMap中的每个桶都只存储一个（Entry对象）。由于entry对象可以包含一个引用变量踊跃指向下一个entry，因此可能出现HashMapde 桶
注意点
JDK1.8中使用一个Node数组来存储数据，但这个Node可能是链表结构，也可能是红黑树结构如果插入的keyhashcode相同，那么这些key也会被定位到Node数组的同一个格子中。
如果同一个格子类的key不超过8个，使用链表结构存储。如果超过了8个，那么会调用treefyBin函数，将链表转换为红黑树，那么即使hashcode完全相同，由于红黑树的特点，查找某个特定的元素，也只需要O（long n）的开销。
也就是说put和get的操作的时间复杂度最差只用0（long n）
需要注意：key的对象，必须正确的实现了Compare接口
二、TreeMap
1、红黑树是一种近视平衡的二叉查找树，它能欧保证任何一个节点的左右的子树的高度都不会超过二者中俄较低那个的一部，具体来说，红黑树是满足如下添加的二叉查找树（binary search tree）
- 每个节点要么是红色，要么是黑色
- 根节点必须是黑色的
- 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
- 对于每个节点，从该点至NUll（树尾端）的任何路径，都含有相同的黑色节点
在树的结构发生改变是（插入或者删除操作），往往会破坏上述条件3和4，需要通过调整使得查找树重新满足红黑树的条件。
2.TreeMap的底层使用的红黑树来实现，想TreeMap对象中翻入一个key-value键值对时，就会生成一个Entry对象，这个对象就会是红黑树的一个节点，其实这个和HashMap的一样，一个Entry对象作为一个节点，只是这些节点存放的方式不同。
3.存放每一个Entry对象是都会按照Key键的大小按照二叉树的规范进行存放，所以TreeMap中数据集是按照key从小到大排序的
TreeMap的总结：
程序添加新节点时，总是从树的根节点开始比较，即将根节点当成当前节点。若果新增节点大于当前节点并且当前节点的左右点存在，则以右节点为当前。如果新增节点小于当前节点并且当前节点的左节点的存在，则以左节点作为当前节点
如果新增节点等于当前节点，则用新增节点覆盖当前节点，并结束循环直到某个节点的左右子节点不存在，将新节点添加为该节点的子节点，如果新节点比该节点大，则添加其为右节点，如果新节点比该节点小，则添加为其左子节点。
