问题的源头：HashMap数据结构是？

　　数组加链表，1.8增加了红黑树，那么为什么？以前我可能会回答：“数组的特点查找快，增删慢，链表查找慢，增删快，数组加链表是结合两者优点”，其实这种描述并不对，因为在使用HashMap的时候数组插入并不慢，而链表增删快的特点也没有发挥出来，因为每次put都需要遍历一遍判断key值是否相等，那么使用链表的原因其实是不得已而为之。那么设计者最初可能只想使用数组，但是单单使用数组的时候一旦发生hash冲突，那么就需要进行数组的扩容，这样经常扩容的开销是很大的。所以使用了链表来缓解哈希冲突对扩容的需求，减少扩容次数。

　　理想情况下可能会使用多层数组结构，每一层使用哈希算法定位到下一层……？？？什么算法可以做到……？？？

　　至于为什么使用红黑树？当链表很长的时候查找效率就很低了，改为红黑树提高查找效率O（logn），但是结点比链表要多了一倍，属于空间换时间。

　　为什么不使用其他树？相对AVL树，红黑树的插入更快……？？？