Java之HashMap原理

Java之HashMap原理

HashMap是基于映射(键值对)处理的数据数据结构。是程序员使用的频率最高的数据结构之一，在jdk1.8之后引入红黑树，优化底层数据结构。
传统的数据的数据结构是在内存中申请一段连续的内存空间，查询的时间复杂度为O(1)，而插入和删除是O(n)，因为伴随着数据的移动。

哈希算法

就是将一个任意长度的key通过散列算法转换成固定长度的key(地址)，通过这个地址进行访问，加快查找速度，通常使用hashcode+取模的方式。1.8中将hash码的前16位参与到取模运算中，不确定性增强，降低数据碰撞的概率。

数据结构

1.7中采用的是数组加链表的形式进行存储，而1.8之后使用的是数组+链表+红黑树作为数据结构，同时1.7中采用的是头插法，1.8采用的是尾插法，当链表长度到达8的时候，链表转为红黑树。1.7中扩容之后需要进行rehash，需要对数据进行重新hash，计算得到在新的hash表中位置。1.8中是通过高位与运算来计算元素是否需要移动。(e.hash&oldCap)元素的hash&原长度，如果结构等于0的时候代表不需要移动，否则就需要移动，移动的新地址等于原下表位置+原数组长度，所以不需要所有元素都进行运算移动。

两种hashmap线程安全的方式 Collections.syncchronizedMap()

如上图所示，构造方法中需要传入Map，然后对其进行封装，相当于返回了一个代理对象，同时使用sychronized锁住对象，而且大部分的代码基本上都是锁住了代码，所以性能会比较差。

ConcurrentHashMap

重写了HashMap，使用了新的锁机制，把HashMap进行了拆分，拆分成了多个独立的块，这样高并发的情况下减少了锁冲突的的几率，使用了CAS指令来确保原子性和互斥性，当多个线程恰好 *** 作到同一个segment上面，只能有一个线程可以执行，性能会比较好，但是代码比较繁琐，因为需要进行多种情况判断。

HashMap进行扩容的时候为什么是两倍？

HashMap中的负载因子是0.75（遵循泊松分布，涉及到统计学），也就是当key值数量到达了数组长度的百分之七十五的时候会进行扩容，减少Hash碰撞。扩容时算法：(n - 1) & hash。因为进行的是位运算，比如当前数组长度为16(2的n次方)，那么对应的二进制就是10000，减1之后就是01111，这样的话进行hash与运算，因为和1进行运算之后同样是1的时候结果是1，其他情况都是0，如果同0进行与运算，不管是1还是0结果都是0，那么相对于1来说，0的重复概率就较高，相当于hash冲突的概率也会随之增大，所以进行扩容的时候是2倍。而且初始容量默认是16，如果传入不是16，也会将其转化成2的n次幂，代码如下：

 
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

解决hash冲突的方式

1、开放定址法，就是一旦发生冲突那么就寻找下一个空的散列地址，如果散列表足够大，那么空的地址总会找到。
2、再hash法，就是发生冲突的时候，使用不同的hash方法计算，直到无冲突，增加了计算时间。
3、链地址法，每个hash表节点都有一个next指针，多个hash表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以通过这个单向链表连接起来。如果链表中个数达到8个，1.8之后会转化成红黑树。
4、建立公共溢出区，凡是发生hash冲突的都放入溢出表中。

hashMap为什么用红黑树，而不是用AVL树

AVL树，也叫作平衡二叉树，就是保证,任意节点的左右两棵树的高度不能相差过1，所以也被称为高度平衡二叉树，所以增加和删除可能需要通过一次或多次树旋转来平衡这个树。
红黑树，也是平衡二叉树，但是规则不同，每个节点都有一个单独的存储位，来记录当前节点是红还是黑，通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，确保没有一条路径会比其他路径多出2倍，所以红黑树是一个弱平衡二叉树，从根到叶子的最长路径不会超过最短路径的2倍，只要不超过这个限制就不会进行树旋转。所以调整频率比较低，对增删比较友好。