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 |