hashmap的实现原理
hashmap是由数组，链表，红黑树和hash算法实现的一个快速存取key-value的集合
hashmap的底层是一个Entry类型的数组，用来保存Entry对象，也就是我们要存入的key-value键值对
Entry是定义在Map接口中的一个内部接口，它具有key，value两个字段，在hashmap中内使用部类Node实现Entry接口并将其扩展成一个链表
put操作
当把一个key-value放入map集合时，首先使用hash算法对key进行散列，得到一个int类型的hashcode，再将hashcode对数组长度取余
得到该key-value在数组中的索引，如果该索引处没有元素，则直接将key-value构建成一个Entry对象，放入该处。若已存在元素
则遍历以该元素为头节点的链表，将当前key-value的key与该位置链表中每个元素的key进行equals比较
如果遇到相同的key，则替换掉原有key对应的value值，否则将当前元素添加到链表尾，如果该位置链表的长度大于8，则以红黑树的形式来保存key-value
get操作
将key进行散列，得到一个hashcode，并将该hashcode对数组长度取余，得到该key在数组中的索引，如果数组在该索引处无元素，则直接返回null
若有元素，则遍历以该元素为头节点的链表，将当前key与链表中每个节点的key进行equals比较，若遇到相同的key则，则返回该key对应的value值
否则返回null
数组：数组在内存中的表现是一段连续的内存空间，当知道某个元素在数组中的下标时，我们可以快速的计算出这个元素的内存地址，从而取出这个元素
链表：链表在逻辑上是连续的，但在内存上的表现是分碎的，即个个节点可能存在各处。链表的优势在于快速插入和删除，但对链表的遍历是非常慢的
红黑树：是一种相对平衡的二叉树，它的查询和增删效率介于数组和链表之间
hash算法：是一种将key散列成数组中指定索引的技术
为什么当数组中某个位置的链表长度大于8时，要将链表替换成红黑树
因为链表的遍历成本比较大，当链表的长度过长时，我们对这个链表的遍历会很慢，而红黑树的查询效率比链表要快
原文：https://www.cnblogs.com/misterwu/p/13607961.html