HashMap的底层原理

hashmap是一个以key,value形式存储的集合,在JDK1.7中是以数组+链表的数据结构,在JDK1.8中是数组+链表+红黑树的数据结构,他在对数据操作时继承了数组的线性查找和链表的寻址修改

hashmap是线程不安全的 : 

1.  在JDK1.7中会造成环形链和数据丢失的情况
2.  在JDK1.8中hashmap的put过程会造成数据覆盖的情况
3. put过程 : 
   1. 会对key计算求hash值,判断是否发生哈希碰撞(计算出的哈希值相同)
   2. 发生了碰撞就放入bucket桶里面,没有发生哈希碰撞就以链表的形式链接到后面
   3. hashmap的存储过程 : 如果链表的长度大于8会转为红黑树,如果链表的长度小于6会从红黑树转为链表
   4. 然后就会去判断节点上是否有值 ,有值的话会覆盖旧值
   5. 如果桶满了会进行扩容2倍在重排

其实hashmap主要的目的就是存储数据结构的,查询的方式通过哈希算法计算的

首先他的结构组成分为 : 

1. 数组结构 :
   1. 他是采用一段连续的存储单元来存储数据的
      1. 查询 : 由于数组元素下标是连续且自增的所以在做查询时可以直接通过下标找到对应的节点,一般在查询频繁的场景下使用最多
      2. 增删 : 当插入一个元素时,这个元素在数组中是没有下标的,需要将元素添加到数组中的某个位置,那么在该元素之后的下标都会向后移动,以至于后面的节点也要有相应的改变,删除会造成下标向前移动
   2. ArrayList : 就是一个基于数组结构的集合,查询快,增删慢,
      1. 他还有一个扩容机制 : 它的默认容量是10,在使用ArrayList做增删时,他会创建一个新的数组且这个数组是原数组容量的1.5倍,并将原数组中的元素拷贝一份到新的数组中去,所以一般我们使用ArrayList做增删时需要指定它的容量
2. 链表结构 : 
   1. 链表是一种物理存储单元上非连续,非顺序的存储结构,它的特点是增删快,查询慢
      1. 查询 : 它的查询需要通过头节点将整个链表都遍历一次,以至于查询效率很慢
      2. 增删 : 新增时上一个节点指向插入的节点,插入的节点指向下一个节点;只需要去改变指针的指向就可以完成增删操作
   2. LinkedList : 是基于链表结构的,查询慢,增删快

哈希算法 : 

1. 哈希算法(不可逆的,幂等性的算法)也叫作散列算法,也就是把任意长度值(key)通过散列算法变换成固定长度的key(地址),通过这个地址进行访问的数据结构,他通过把关键码值映射到表中一个位置来访问记录,从而加快查找速度
2. 将lies计算出来的ascii码相加
3. 然后除以10取模
   1. 为什么不直接存储,要进行取模?
      1. 因为数组是采用一段连续的存储单元来存储数据的,直接存储的话值会很大,其中会浪费很多的空间,取模的目的就是为了节省内存空间
         1. 取模会出现的问题 :
            • 会发生哈希冲突(哈希碰撞) :
              • lies的值通过ascii码计算的总和
              • foes的值通过ascii计算的总和
              • lies和foes取模之后的值相同,虽然他两是不同的key,但是数组存同一个下标元素时会进行覆盖,这就是哈希碰撞
            • 哈希碰撞解决方式 : 
              • 使用链表解决 : 根据链表的指针,可以让lies指向foes,让foes去匹配下标,如果匹配lies不相等,则去匹配下一个节点foes,最终找到这个foes
              • 这也是JDK1.8中引入红黑树的原因 : hashmap的存取过程
                • 创建一个hasdmap集合并指定它的容量
                • 往集合中添加元素时,当容量不够,就只能把这个数据放到链表上,链表是无线延长的,又因为链表的查询速度是比较慢的,那么哈希冲突也就会变得十分严重,查询末端数据的性能也就会变得很低(总结 : jdk1.7的hashmap需要解决链表过长查询效率低下的问题)
                • 在jdk1.8中 : 使用红黑树去判断小中大(也就是左边的小于右边的),他的插入速度慢,而链表插入快,删除快