Java8 HashMap 源码阅读笔记

发表于

简介

散列（英语：Hashing）是电脑科学中一种对资料的处理方法，通过某种特定的函数/算法（称为散列函数/算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜索的数据结构（称为散列表）。

HashMap是Java程序中使用频率很高的类，用于处理映射/键值对，是散列表ADT的一种实现。

根据官方文档的介绍，HashMap有如下几个特点：

  • 允许键为null
  • 允许映射的值为null
  • 不保证映射的顺序
  • 非同步

结构概览

HashMap采用数组+链表+红黑树的设计

Imgur

根据书上和网上的一些资料，为了使key均匀分布，表的大小最好是素数，不过HashMap不是这样设定的，后文会看到。

当两个关键词散列到了同一个值(把这种情况称为冲突)，采用分离链接法解决冲突

实现

属性

哈希桶数组，长度为2^n

1
2
3
4
5
6
7
8
9
10
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    ...
}

1
2
3
transient int size;
int threshold;
final float loadFactor;

size:key-value映射的数量
load factor(装填因子)：bucket装填程度的最大比例，默认0.75
threshold: capacity * load factor

hash

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash函数看起来很简单，将hashcode与自身高位异或

计算index = (n - 1) & hash

分析HashMap的put方法

put大致的实现思路为：\
对于key的hashCode()，算出hash值；\
根据hash值和数组长度算出index；\
如果没碰撞直接放到bucket里；\
如果节点已经存在就覆盖value；\
如果碰撞了，以链表的形式存在buckets后；\
如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，以红黑树的形式存在；\
如果size超过threshold，就要resize

resize