结构上，底层使用数组+单向链表+红黑树的结构，节点数大于8时会转为红黑树，节点数小于6时会转为单向链表。
首先每一个元素都是链表的数组，当添加一个元素（key-value）时， 就首先计算元素 key 的 hash 值，以此确定插入数组的位置，但是可能存在同一 hash 值的元素已经被放到数组的同一位置，这是就添加到同一 hash 值的元素的后面，他们在数组的同一位置形成链表，同一链表上的 Hash 值是相同的，所以说数组存放的是链表，而当链表长度太长时，链表就转换为红黑树。
当链表数组的容量超过初始容量的 0.75 时，再散列将链表数组扩大 2 倍，把原链表数组的元素搬移到新的数组中
直接看源码。
常量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 初始容量为2的4次方即16(aka:Also Known As)
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量为2的30次方
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子，当数量达到容量的0.75倍则扩容
static final int TREEIFY_THRESHOLD = 8; // 树化阈值8，即节点数大于8时会转为红黑树
static final int UNTREEIFY_THRESHOLD = 6; // 树退化阈值，即节点数小于6时会转为单向链表
static final int MIN_TREEIFY_CAPACITY = 64; // 最小树形化阈值，红黑树最小长度为 64成员变量
transient Node<K,V>[] table; // HashMap的哈希桶数组，用于存放表示键值对数据的Node元素。
transient Set<Map.Entry<K,V>> entrySet; // HashMap将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。
transient int size; // HashMap中实际存在的键值对数量
transient int modCount;
// HashMap的数据被修改的次数，
// 这个变量用于迭代过程中的Fail-Fast机制，其存在的意义在于保证发生了线程安全问题时，
// 能及时的发现（操作前备份的count和当前modCount不相等）并抛出异常终止操作。
int threshold; // 扩容阈值，当HashMap的size大于threshold时就会执行resize操作自动扩容容量为原来的二倍
final float loadFactor; // 负载因子，默认值为0.75f，计算HashMap的实时装载因子的方法为：size/capacity构造函数
//指定容量大小和负载因子大小
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException(""Illegal initial capacity: "" +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException(""Illegal load factor: "" +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//指定容量大小
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//默认的构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//传入一个Map集合,将Map集合中元素Map.Entry全部添加进HashMap实例中
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}数据结构
数组元素Node[]
是HashMap内部的静态类：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// Node构造函数Node
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash; // Hash值
this.key = key; // 键
this.value = value; // 值
this.next = next; // 下一个节点
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + ""="" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}红黑树TreeNode
也是HashMap内部的静态类，TreeNode的代码很多，分类来看：
成员变量和构造方法
TreeNode<K,V> parent; // red-black tree links 父节点
TreeNode<K,V> left; // 左子树
TreeNode<K,V> right;// 右子树
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // 颜色属性
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}方法
// 返回当前节点的根节点
final TreeNode<K,V> root() {...}
// 将跟节点移至最前
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {...}
// 使用给定的哈希和键，从根节点p开始查找指定的节点
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {...}
// 为根节点调用find()方法
final TreeNode<K,V> getTreeNode(int h, Object k) {...}
// 用于不可比较或HashCode相同时进行比较的方法
static int tieBreakOrder(Object a, Object b) {...}
// 构建红黑树
final void treeify(Node<K,V>[] tab) {...}
// 树退化
final Node<K,V> untreeify(HashMap<K,V> map) {...}
// 键值对插入红黑树
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {...}
// 移除树节点
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) {...}
// 在HashMap进行扩容时会调用到
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {...}
// 左旋
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {...}
// 右旋
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {...}
// 插入平衡算法（插入后）
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {...}
// 删除平衡算法
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) {...}
// 检查不变量
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {...}
HashMap常用方法
Hash值计算
// 将传入的参数key本身的hashCode与h无符号右移16位进行二进制异或运算得出一个新的hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}put()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);// 这里传入了计算后的hash值
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 若table为空，则使用resize扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 根据传入的hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); // 新建节点
else {
// 当table[i]!=null时
Node<K,V> e; K k;
// 如果table[i]的首个元素和key相同，则直接覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果table[i]的首个元素和key相同，则直接覆盖
else if (p instanceof TreeNode)
// 如果table[i]的首个元素和key不相同，则先判断table[i]是否为红黑树，若是则直接在树中插入键值对
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 如果table[i]不是红黑树，则判断链表长度是否大于8，大于8将链表转换为红黑树，再执行插入操作
// 否则进行链表的插入操作
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 若节点数大于等于8
// 转换为红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key:key已经存在，将新value替换旧value值具体操作
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) // 判断是否需要扩容
resize();
afterNodeInsertion(evict);
return null;
}- 获取Node数组table对象和长度，并判断table是否为空：
- 若table为空，则调用resize()扩容；
- 若table不为空，判断要插入的key和插入位置的元素是否相同：
- 若相同，则直接覆盖；
- 若不同，则先判断是否是红黑树：
- 若是红黑树，则按红黑树的方式插入；
- 若不是红黑树，则判断其长度是否大于8，大于8则先转为红黑树，再执行插入，否则进行链表的插入操作
- 最后判断是否需要扩容。
get()方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 当table不为null，table长度大于0，指定位置不为null时，才更进一步查询，否则直接返回null。
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node 先判断第一个存在的节点的key是否和查询的key相等。
((k = first.key) == key || (key != null && key.equals(k))))
return first;// 如果相等，直接返回该节点。
if ((e = first.next) != null) { // 若first节点和要查询的不一致，且其下一个节点不为null时。
if (first instanceof TreeNode)
// 当这个table节点上存储的是红黑树结构时，在根节点first上调用getTreeNode方法，在内部遍历红黑树节点，查看是否有匹配的TreeNode。
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 当这个table节点上存储的是链表结构时，则检索链表来查询结果。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e; // 成功后返回。
} while ((e = e.next) != null);
}
}
return null;
}- 首先table要满足三个条件才能继续深入查询：table不为null，table长度大于0，指定位置不为null。
- 先判断第一个存在的节点的key是否和查询的key相等。
- 如果相等，则直接返回该节点。
- 如果不想等，则判断它的下一个节点是否为null。
- 当table的这个节点上为红黑树结构时，在根节点first上调用getTreeNode方法，在内部遍历红黑树节点，查看是否有匹配的TreeNode
- 当这个table节点上存储的是链表结构时，则检索链表来查询结果。
resize()方法（扩容机制）
重新设置table大小，并返回新的HashMap的数据。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 旧table
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 扩容前的容量
int oldThr = threshold; // 扩容前的扩容阈值
int newCap, newThr = 0; // 扩容后的容量，扩容后的扩容阈值
if (oldCap > 0) { // 若扩容前的容量大于0
if (oldCap >= MAXIMUM_CAPACITY) { // 若扩容前的容量若超过最大容量，则不再进行扩充
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 若扩容后的容量小于最大容量，且扩容前的长度大于等于默认的初始化长度
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold 则扩容为原来的二倍
}
// 若扩容前的容量为0，且扩容前的扩容阈值大于0
else if (oldThr > 0) // initial capacity was placed in threshold
// 则扩容后的容量设为扩容前的扩容阈值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 若扩容前的容量为0，且扩容前的扩容阈值也为0，则新阀值和新容量使用默认值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 如果新阈值为0，则重新计算：阀值没有超过最大阀值，设置新的阀值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // 最后将新阈值赋给table的扩容阈值
// --------------------------------------------------------------------------------
@SuppressWarnings({""rawtypes"",""unchecked""})
//创建新的 Hash 表
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//遍历旧的 Hash 表
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 释放旧空间
if (e.next == null) // 当这个节点只有一个数据时
newTab[e.hash & (newCap - 1)] = e; // 将这个数据直接赋给新table中指定的hash位置
else if (e instanceof TreeNode) // 当这个节点是一个红黑树时，则按红黑树的方式赋给新table
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order 当这个节点是一个链表时
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}参考： 数据结构解析-HashMap HashMap的结构以及核心源码分析
Ahaa, its pleasant dialogue regarding this piece of writing at
this place at this website, I have read all that, so now me
also commenting here.
My website – singapore