1.HashMap底层实现原理，红黑树，B+树，
B树的结构原理，volatile关键字，CAS（比
较与交换）实现原理
首先HashMap是Map的一个实现类，而Map存储形式是键值对(key,value)的。可以看成是
一个一个的Entry。Entry所存放的位置是由key来决定的。
Map中的key是无序的且不可重复的，所有的key可以看成是一个set集合，如果出现Map
中的key如果是自定义类的对象，则必须重写hashCode和equals方法，因为如果不重写，
使用的是Object类中的hashCode和equals方法，比较的是内存地址值不是比内容。
Map中的value是无序的可重复的，所有的value可以看成是Collection集合，Map中的value
如果是自定义类的对象必须重写equals方法。
至于要重写hashCode和equals分别做什么用，拿hashMap底层原理来说：
当我们向HashMap中存放一个元素(k1,v1)，先根据k1的hashCode方法来决定在数组中存
放的位置。
如果这个位置没有其它元素，将(k1,v1)直接放入Node类型的数组中，这个数组初始化容量
是16，默认的加载因子是0.75，也就是当元素加到12的时候，底层会进行扩容，扩容为原
来的2倍。如果该位置已经有其它元素(k2,v2)，那就调用k1的equals方法和k2进行比较二
个元素是否相同，如果结果为true，说明二个元素是一样的，用v1替换v2，如果返回值为
false，二个元素不一样，就用链表的形式将(k1,v1)存放。
不过当链表中的数据较多时，查询的效率会下降，所以在JDK1.8版本后做了一个升级，
hashmap就是当链表中的元素达到8并且元素数量大于6Java基础中级面试4时，会将链表替换成红黑树才会
树化时，会将链表替换成红黑树，来提高查找效率。因为对于搜索，插入，删除操作多的情
况下，使用红黑树的效率要高一些。
原因是因为红黑树是一种特殊的二叉查找树，二叉查找树所有节点的左子树都小于该节点，
所有节点的右子树都大于该节点，就可以通过大小比较关系来进行快速的检索。
在红黑树上插入或者删除一个节点之后，红黑树就发生了变化，可能不满足红黑树的5条性
质，也就不再是一颗红黑树了，而是一颗普通的树，可以通过左旋和右旋，使这颗树重新成
为红黑树。红黑树的5条性质（根节点是黑色，每个节点是黑色或者是红色，每个叶子节点
是黑色，如果一个节点是红色它的子节点必须是黑色的，从一个节点到该节点的子孙外部节
点的所有路径上包含相同数目的黑点）
而且像这种二叉树结构比较常见的使用场景是Mysql二种引擎的索引，Myisam使用的是B
树，InnoDB使用的是B+树。
首先B树它的每个节点都是Key.value的二元组，它的key都是从左到右递增的排序，value
中存储数据。这种模式在读取数据方面的性能很高，因为有单独的索引文件，Myisam的存
储文件有三个.frm是表的结构文件，.MYD是数据文件，.MYI是索引文件。不过Myisam也
有些缺点它只支持表级锁，不支持行级锁也不支持事务，外键等，所以一般用于大数据存储。
另外对于HashMap实际使用过程中还是会出现一些线程安全问题：
HashMap是线程不安全的，在多线程环境下，使用Hashmap进行put操作会引起死循环，
导致CPU利用率接近100%，而且会抛出并发修改异常，导致原因是并发争取线程资源，修
改数据导致的，一个线程正在写，一个线程过来争抢，导致线程写的过程被其他线程打断，
导致数据不一致。
HashTable是线程安全的，只不过实现代价却太大了，简单粗暴，get/put所有相关操作都是
synchronized的，这相当于给整个哈希表加了一把大锁。多线程访问时候，只要有一个线程
访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发
场景中性能就会非常差。
为了应对hashmap在并发环境下不安全问题可以使用，ConcurrentHashMap大量的利用了
volatile，CAS等技术来减少锁竞争对于性能的影响。
在JDK1.7版本中ConcurrentHashMap避免了对全局加锁，改成了局部加锁（分段锁），分
段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访
问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/19602.html