你们都想知道的HashMap实现原理和源码详细分析

HashMap实现原理和源码具体分析

ps：本博客基于Jdk1.8

学习要点：

1、知道HashMap的数据结构
2、相识HashMap中的散列算法
3、知道HashMap中put、remove、get的代码实现
4、HashMap的哈希冲突是什么？怎么处置处罚的？
5、知道HashMap的扩容机制
1、什么是HashMap？

HashMap 基于哈希表的 Map 接口实现，是以 key-value 存储形式存在 ，HashMap 的实现不是同步的，这意味着它不是线程安全的。它的 key、value 都可以为 null，此外，HashMap 中的映射不是有序的。
2、HashMap的特性

• Hash存储无序的
  
• key和value都可以存储null值，但是key只能存唯一的一个null值
  
• jdk8之前的数据结构是数组+链表，Jdk8之后酿成数组+链表+红黑树
  
• 阀值大于8并且数组长度大于64才会转为红黑树
  

3、HashMap的数据结构
JDK7的情况，是数组加链接，hash冲突时间，就转换为链表：

                               
登录/注册后可看大图

jdk8的情况，jdk8加上了红黑树，链表的数量大于8而且数组长度大于64之后，就转换为红黑树，红黑树节点小于6之后，就又转换为链表：

                               
登录/注册后可看大图

翻下HashMap源码，对应的节点信息：
static class Node implements Map.Entry {        // hashCode        final int hash;        final K key;        V value;        // 链表的next指针就不为null        Node next;        Node(int hash, K key, V value, Node next) {            this.hash = hash;            this.key = key;            this.value = value;            this.next = next;        }        // ...}        4、HashMap初始化使用

4.1、成员变量

public class HashMap extends AbstractMap    implements Map, Cloneable, Serializable {        /**     * 序列号版本号     */    private static final long serialVersionUID = 362498820763181265L;   /**     * 初始化容量，为16=2的4次幂     */    static final int DEFAULT_INITIAL_CAPACITY = 1 > 1;    n |= n >>> 2;    n |= n >>> 4;    n |= n >>> 8;    n |= n >>> 16;    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}这里涉及到计算机基本知识的，右移运算和或运算，下面给出图例：通过比力麻烦的计算得出n为16

                               
登录/注册后可看大图

往代码里翻，还找到下面这个构造方法public HashMap(Map