如何HashMap源码以支持查询？

目录回顾HashMap简介类签名常量变量构造方法tableSizeFor方法添加元素putVal方法获取元素getNode方法总结 本文一是总结前面两种集合，补充一些遗漏，再对HashMap进行简单介绍。 回顾 因为前两篇ArrayList和LinkedList都是针对单独的集合类分析的，只见树木未见森林，今天分析HashMap，可以结合起来看一下java中的集合框架。下图只是一小部分，而且为了方便理解去除了抽象类。 Java中的集合（有时也称为容器）是为了存储对象，而且多数时候存储的不止一个对象。 可以简单的将Java集合分为两类： 一类是Collection，存储的是独立的元素，也就是单个对象。细分之下，常见的有List，Set，Queue。其中List保证按照插入的顺序存储元素。Set不能有重复元素。Queue按照队列的规则来存取元素，一般情况下是“先进先出”。 一类是Map，存储的是“键值对”，通过键来查找值。比如现实中通过姓名查找电话号码，通过身份证号查找个人详细信息等。 理论上说我们完全可以只用Collection体系，比如将键值对封装成对象存入Collection的实现类，之所以提出Map，最主要的原因是效率。 HashMap简介 HashMap用来存储键值对，也就是一次存储两个元素。在jdk1.8中，其实现是基于数组+链表+红黑树，简单说就是普通情况直接用数组，发生哈希冲突时在冲突位置改为链表，当链表超过一定长度时，改为红黑树。 可以简单理解为：在数组中存放链表或者红黑树。 完全没有哈希冲突时，数组每个元素是一个容量为1的链表。如索引0和1上的元素。 发生较小哈希冲突时，数组每个元素是一个包含多个元素的链表。如索引2上的元素。 当冲突数量超过8时，数组每个元素是一棵红黑树。如索引6上的元素。 下图为示意图，相关结构没有严格遵循规范。 类签名 public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable 如下图 实现Cloneable和Serializable接口，拥有克隆和序列化的能力。 HashMap继承抽象类AbstractMap的同时又实现Map接口的原因同样见上一篇LinkedList。 常量 //序列化版本号 private static final long serialVersionUID = 362498820763181265L; //默认初始化容量为16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //最大容量，2的30次方 static final int MAXIMUM_CAPACITY = 1 << 30; //默认负载因子，值为0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; //以下三个常量应结合看 //链表转为树的阈值 static final int TREEIFY_THRESHOLD = 8; //树转为链表的阈值，小于6时树转链表 static final int UNTREEIFY_THRESHOLD = 6; //链表转树时的集合最小容量。只有总容量大于64，且发生冲突的链表大于8才转换为树。 static final int MIN_TREEIFY_CAPACITY = 64; 上述变量的关键在于链表转树和树转链表的时机，综合看： 当数组的容量小于64是，此时不管冲突数量多少，都不树化，而是选择扩容。 当数组的容量大于等于64时， 冲突数量大于8，则进行树化。 当红黑树中元素数量小于6时，将树转为链表。