HashMap

pexels-julia-larson-6113297.jpg

介绍：

HashMap（非线程安全）也算是一个数据容器，用来存储数据的，只不过存储的是<key,value>对；底层数据结构是一个实现了Map.Entry<K,V>接口的Node数组，有默认的capacity和load factor，这两个参数设置的具体的值会对HashMap的性能有一定的影响。

关键知识点：

• permits null values and the null key.
• unsynchronized.Map --> m = Collections.synchronizedMap(new HashMap(...))
• makes no guarantees as to the order of the map.
• initial capacity:默认=16，the number of buckets.
• load factor:默认0.75

类图：

HashMap类图.png

核心点：

HashMap继承与AbstractMap，AbstractMap实现了Map接口，HashMap内部的Node内部类实现了Map.Entry<K, V>接口。
其实HashMap的底层数据结构不仅仅包括一个Node类型的数组，也会有链表或者红黑树（jdk1.8以后）。当出现hash冲突的时候，就会出现链表的结构，当链表的长度（TREEIFY_THRESHOLD）大于8的时候，就会调用treeifyBin()方法转换成红黑树结构。

转换成红黑树.png

构造的红黑树如果不满足红黑树的特点，会调用balanceInsertion(root, x)方法来旋转...

红黑树旋转.png
红黑树又出来了...
红黑树的时间复杂度O(lgn)。
二叉树又出来了...其实所有的事物的出现都是有原因的，是那些有才华的大师们精心设计好的；所以要尽量的去顺藤摸瓜，弄清楚表象背后的东西...也就是本质。

• 二叉树：n (n >= 0)个节点的有限集合,该集合或者为空集(称为空二叉树),或者有一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的节点组成.

• 满二叉树：

  
  满二叉树.png

• 完全二叉树：

  
  完全二叉树.png
• 二叉查找树特点：
  左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大。
  有可能会退化成一个链表，时间复杂度变成O(n)，所以又引入平衡二叉查找树。
• 平衡二叉查找树：
  核心特点：树的左右两边的层级数相差不会大于1。
  解决了二叉查找树退化为近似链表的缺点。
  核心缺点：由于他的核心特点，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树，会严重影响性能。
  为了解决平衡二叉查找树的核心缺点，就引入了红黑树...
  具体这些算法是如何实现的，在工作中如果涉及到了的话，再去深入一下，体会大师的内心...

扩展树：

B树和B+树（多叉树），在数据库索引技术里大量使用...

• B树：

  
  B树.png

• B+树：

  
  B+树.png

B+树.png

总结：

从树的各种演化路程中可以看到，都是采用二分法和数据平衡策略来提升查找数据的速度；每一次的演变都是一次思想上的升华...
人确实很聪明，不愧于高级动物的称号...其实人与人之间在小时候的差距本没有那么大，随着年龄的增长，差距却越来越明显了...每个人的成就都不一样...
从大的方面说，我认为有两个方面的原因，一就是小时候的教育和性格的培养环境差距很大；二就是长大后，自己有没有通过不断的接触那些有价值的东西，然后自驱动自己去不断的学习和尝试,...反复如此，才能弥补小时候的缺失...
不过话又说回来了，每个人都有自己的路，不管这条路的风景如何，都是他自己的...没有真正意义的成功和失败，只有相对的，我记得有一句话说的很好：成功就是按照自己的方式过完一生...很有借鉴意义。