HashMap底层实现原理

HashMap采用Node<K,V> 数组来存储key-value对，每一个键值对组成了一个Node实体，Node类实际上是一个单向的链表结 构，它具有Next指针，可以连接下一个Node实体。,JDK1.8 之前，数组 + 链表 存储结构,缺点就是哈希函数很难使元素百分百的均匀分布，这会产生一种极端的可能，就是大量的元素存在一个桶里,JDK1.8 之后：数组 + 链表 + 红黑树,,存储结构,
,java集合中的快速失败：modCount,// 快速失败是Java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast。,//举个例子：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就可能会抛出
ConcurrentModificationException异常，从而产生fast-fail快速失败。,HashMap中遍历算法如下：,JDK1.8中,是通过hashCode()的高16位异或低16位实现的:(h=k.hashCode())^(h>>>16),主要是从速度,功效和质量来考虑的,减少系统的开销,也不会造成因为高位没有参与下标的计算,从而引起的碰撞。,,hash 计算过程与putval函数的应用,高16bit不变，低16bit和高16bit做了一个异或（得到的hashCode转化为32位二进制，前16位和后16位低16bit和高16bit做了一个异或）,如果当n即数组长度很小，假设是16的话，那么n – 1即为1111 ，这样的值和hashCode直接做按位与操作，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。降低了Hash冲突的概率,保证了对象的hashCode的32位值只要有一位发生改变,整个hash()返回值就会改变。尽可能的减少碰撞。,存储对象时,将K/V键值传给put()方法:,i.如果K的hash值在HashMap中不存在,则执行插入,若存在,则发生碰撞;,ii.如果K的hash值在HashMap中存在,且它们两者equals返回true,则更新键值对;,iii.如果K的hash值在HashMap中存在,且它们两者equals返回false,则插入链表的尾部(尾插法)或者红黑树中(树的添加方式)。(JDK1.7之前使用头插法、JDK1.8使用尾插法),Q：默认初始化大小是多少？为啥是这么多？为啥大小都是2的幂？,A：hash运算的过程其实就是对目标元素的Key进行hashcode，再对Map的容量进行取模，而JDK 的工程师为了提升取模的效率，使用位运算代替了取模运算，这就要求Map的容量一定得是2的幂。HashMap的容量为什么是2的n次幂，和这个putval方法中（n – 1) & hash的计算方法有着千丝万缕的关系，符号&是按位与的计算，这是位运算，计算机能直接运算，特别高效，按位与&的计算方法是，只有当对应位置的数据都为1时，运算结果也为1，当HashMap的容量是2的n次幂时，(n-1)的2进制也就是1111111***111这样形式的，这样与添加元素的hash值进行位运算时，能够（充分的散列），使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞。,,Q:HashMap如何有效减少碰撞？,A: 扰动函数：促使元素位置分布均匀，减少碰撞几率 、使用final对象，并采用合适的equals()和hashCode()方法