HashMap

• 　　数据结构：数组+链表

　　　　　　数组：采用一段连续的存储单元来存储数据  查询快 插入慢

　　　　　　链表：是一种物理存储单元上非连续，非顺序的存储结构  插入删除快 查询慢（查询需要头开始）

• 算法：　　
  • 　　　　hash算法，也叫散列，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间 　　通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。　　
  • 　　hashmap中根据key的hashcode值取模算出key的下标。
  
• 

   

   

 hash冲突和碰撞 

　　　　1.7

 1.8后链表优化为红黑树

　　链表数据过大查询比较慢

　　链表长度超过8后，采用红黑树（红黑树的结构 小中大，左中右）

　　　　原因：红黑树插入比较慢（需要维护红黑树结构），数据进行左旋交换

HashMap

原文：https://www.cnblogs.com/ethereal-y/p/14985965.html