HashMap的基本实现原理及其扩展机制(精炼)一、HashMap的数据结构二、HashMap键值对的存储原理和方式三、HashMap的扩展机制Java 7中的HashMap扩展机制Java8中的HashMap扩展机制
一、HashMap的数据结构
1 .它是常用的数据结构，其中三种常用的数据结构为数组结构、链表结构、哈希表结构。
2 .优点：哈希表结构结合了数组结构和链表结构两大优点。 删除快，查询也快。
二、HashMap键值对的存储原理和方式：1.HashMap.Node key、value Node类是HashMap的静态内部类，实现Map.Entry key、value接口，put方法
2 .将key转换为hashcode值，并将value值与key相关联。
3 .调用put方法时，首先将k、v封装为Node对象(节点)，在下一层调用k的hashCode ) )方法来求出hash值。 每个数组的位置都是哈希值，key的hashcode值可以视为数组的后缀。 如果两个值的哈希值相同，则占据一个位置，用链表方式连接value，则他们成为链表。 如果下标位置没有任何元素，则在此位置添加节点。 假设在下标的对应位置有链表。 此时，拿着k和链表的各个节点的k进行equal。 如果所有equals方法都返回false，则此新节点将添加到链表的末尾。 如果其中一个equals返回true，则此节点的value将被复盖。
4 .如果key类型是可变对象，则必须重写hashcode和equals方法，以防止可变参数参与hash计算
用Java8优化hashmap，用相同的哈希值如果链表长度超过8，则从链表转换为红黑树
6.HashMap内部结构是数组[]table]和链表组合的复合结构，数组分为一个桶或槽，哈希值确定该数组中键值的寻址。 具有相同哈希值的键值对被保存为链表。 如果链表大小超过阈值(TREEIFY_THRESHOLD=8)，链表将被改造为树结构。
难点*HashMap红黑树原理分析：
1 .好处是避免在最极端的情况下链表变长，查询时效率非常低。
2 )红黑树查询)其访问性能接近折半搜索，时间复杂度为o(logn )；
3 .链表查找：在这种情况下，需要遍历所有元素。 时间复杂度o(n )；
4 .简而言之，红黑树是平衡二叉树，主要优点是“平衡”，即左右子树高度基本一致，防止树退化为链表，搜索的时间复杂度为log(n )。
5 .关于红黑树的内容，主要有以下特性。 1、各节点为红色或黑色，但根节点始终为黑色； 2、每个红色节点的两个子节点一定是黑色的； 3、红色节点不能连续(也就是说红色节点的孩子和父亲都不能是红色的)； 4 .从任一节点到其子树的各个叶节点的路径中包含相同数量的黑色节点； 5、所有叶节点均为黑色(此处称叶节点，但注意实际上是上图中的NIL节点)； 树结构改变时(插入或删除操作)，往往破坏上述条件3或条件4，需要调整搜索树使其再次满足红黑树的条件。 6 .数据结构图：
水桶数组键值对
备份
嘴-- key，value
口-- key，value----key，value---key，value
嘴-- key，value
嘴-- key，value
嘴-- key，value -- key，value
嘴-- key，value
7 .为什么随机增删、查询效率高？
1 .其他百度答案：添加删除是在链表中完成的，但查询只需扫描部分即可，效率很高。
2 .自我理解：添加删除：首先将k值转换为hashcode，然后根据下标找到链表添加删除。 数组的位置不变。 查询：查询不需要遍历所有链表，首先根据k的hashcode值找到下标，然后在equals中找到相应的value值。
放置在hashMap集合key部分的元素为什么需要重写equals方法？
因为equals方法缺省情况下比较两个对象的内存地址。
9.HashMap集合中的key依次调用两个方法： hashCode and equals方法。 这两种方法都需要重写。
原因：
hashcode改写的理由：
在HashMap中存储k1时，首先调用一个名为Key的类的hashcode方法来计算其hash值。 接下来，如果没有为名为Key的类定义hashcode方法，则会调用Object类的hashco
de方法，而Object类的hashcode方法返回的hash值是对象的地址。这时用k2去拿也会计算k2的hash值到相应的位置去拿，由于k1和k2的内存地址是不一样的，所以用k2拿不到k1的值equals重写原因：
重写hashcode方法仅仅能够k1和k2计算得到的hash值相同，调用get方法的时候会到正确的位置去找，但当出现散列冲突时，在同一个位置有可能用链表的形式存放冲突元素，这时候就需要用到equals方法去对比了，由于没有重写equals方法，它会调用Object类的equals方法，Object的equals方法判断的是两个对象的内存地址是不是一样，由于k1和k2都是new出来的，k1和k2的内存地址不相同，所以这时候用k2还是达不到k1的值 三、HashMap的扩容机制 Java 7 中Hashmap扩容机制 1.在put()方法中有调用addEntry()方法，这个方法里面是具体的存值，在存值之前还要判断是否需要扩容2.调用扩容的方法resize()3.扩容必须满足两个条件：1、 存放新值的时候当前已有元素的个数必须大于等于阈值2、 存放新值的时候当前存放数据发生hash碰撞（当前key计算的hash值换算出来的数组下标位置已经存在值）4.transfer()在实际扩容时候把原来数组中的元素放入新的数组中5.JDK7版本及以前使用是：
头插法：使用头插法在多线程扩容的时候可能会导致循环指向，从而在获取数据get()的时候陷入死循环，到是线程执行无法结束。
原因：有点类似于砌墙的砖头后来居上的感觉，先插入的会被逐步放到最底下，越后来的会被放在头部，并将next指针指向之前的头部，这样在扩容的时候，先取头部然后把头部放到新对应数组下标的链表处，由于头插法，最早取的会被最先放进并逐步变成最尾，如果多线程执行扩容，将数组下标3位置链表存入的A->B->C扩容时存入到新的数组（假设扩容后A/B/C还在同一个链表上），线程1取第一个元素A被挂起的时候，挂起的元素A元素的next指向B，而线程2放入新的链表时，A被先放但没有完成，线程2在放入B后，B的next指向之前放入的A，当线程1执行的时候本身A的next指向B，这样就行程了循环引用，最后存入C，并将C的next指向B，最终就变成C->B-><-A，在get()方法执行到该数组下标时，遍历链表查找的时候就会出现死循环。
6.因为上面这两个条件，所以存在下面这些情况：
1.就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。
2.当然也有可能存储更多值（超多16个值，最多可以存27个值）都还没有扩容。
原理：前11个值全部hash碰撞，存到数组的同一个位置（虽然hash冲突，但是这时元素个数小于阈值12，并没有同时满足扩容的两个条件。所以不会扩容），[在存入第12个元素的时候，还是存入前面11个元素所在的下标位置，因为存入之前此时比较当前元素个数 11<12(16*0.75)，所以在存入第12个元素的时候不会发生扩容，那么还有15个数据下标的位置是空的，后面所有存入的15个值全部分散到数组剩下的15个位置（这时元素个数大于等于阈值，但是每次存入的元素并没有发生hash碰撞，也没有同时满足扩容的两个条件，所以叶不会扩容），前面12+15=27，所以在存入第28个值的时候才同时满足上面两个条件，这时候才会发生扩容现象。
Java8中HashMap扩容机制1.Java8不再像Java7中那样需要满足两个条件，Java8中扩容只需要满足一个条件：当前存放新值（注意不是替换已有元素位置时）的时候已有元素的个数大于等于阈值（已有元素等于阈值，下一个存放后必然触发扩容机制）且扩容发生在存放后，即是数据存放后（先存放后扩容），判断当前存入对象的个数，如果大于阈值则进行扩容。
2.Java7中Hashmap底层采用的是Entry对数组，而每一个Entry对又向下延伸是一个链表，在链表上的每一个Entry对不仅存储着自己的key/value值，还存了一个当前对象的hash值和指向下一个地址的next Node节点。Java8中的Hashmap底层结构有一定的变化，还是使用的数组，但是数组的对象以前是Entry对，现在换成了Node对象（可以理解是Entry对，结构一样，存储时也会存key/value键值对、当前对象的hash值和指向下一个地址的next Node节点），以前所有的Entry向下延伸都是链表，Java8变成链表和红黑树的组合，数据少量存入的时候优先还是链表，当链表长度大于8，且总数据量大于64的时候，链表就会转化成红黑树，所以你会看到Java8的Hashmap的数据存储是数组+链表+红黑树的组合，如果数据量小于64则只有数组+链表，如果数据量大于64，且某一个数组下标数据量大于8，那么该处即为红黑树。
3.treeifyBin()方法判断是扩容还是将当前链表转红黑树
4.1）Java 8 在新增数据存入成功后进行扩容
（2）扩容会发生在两种情况下（满足任意一种条件即发生扩容）：
a 当前存入数据大于阈值即发生扩容
b 存入数据到某一条链表时，此时该链表数据个数大于8，且总数量小于64即发生扩容
（3）此外需要注意一点java7是在存入数据前进行判断是否扩容，而java8是在存入数据后再进行扩容的判断。
5.JDK8关于红黑树和链表的知识：
第一次添加元素的时候，默认初期长度为16，当往map中继续添加元素的时候，通过hash值跟数组长度取“与”来决定放在数组的哪个位置，如果出现放在同一个位置的时候，优先以链表的形式存放，在同一个位置的个数又达到了8个（代码是>=7,从0开始，及第8个开始判断是否转化成红黑树），如果数组的长度还小于64的时候，则会扩容数组。如果数组的长度大于等于64的话，才会将该节点的链表转换成树。在扩容完成之后，如果某个节点的是树，同时现在该节点的个数又小于等于6个了，则会将该树转为链表。
6.只有当数据量大于64才会有红黑树+链表