摘要
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
HashMap是Java程序员使用最频繁的的用于键值对(key value)数据处理的容器,在JDK1.7(Java Developmet Kit)时HashMap采取的是数组+链表的形式存储数据,JDK1.8对HashMap进行了存储结构上的优化,引入了红黑树数据结构,极大的增强了HashMap的存取性能!为什么会引入红黑树呢?因为HashMap存在一个问题,即使负载因子和Hash算法设计的再合理,也无法避免出现在链表上拉链过长的问题,如果极端情况下出现严重的Hash冲突,会严重影响HashMap的存取性能,于是HashMap在jdk1.8时,引入了红黑树,利用红黑树快速增删改查的特点来优化了HashMap的性能!
简介
Java为数据结构中的映射(键值对)定义了一个接口java.util.Map,这个接口有四个我们在开发中使用较为频繁的实现类,分别是HashMap<K, V>、Hashtable<K, V>、LinkedHashMap<K,V>、TreeMap<K,V>
序号 | 实现类 | 特点 |
---|---|---|
1 | HashMap<K, V> | 1、根据键的hashcode存储数据 2、允许一条记录的key为null,允许多条记录的value为null 3、非线程安全 |
2 | Hashtable<K, V> | 1、线程安全 2、性能较低,需要使用的场景可以用ConcurrentHashMap替换 |
3 | LinkedHashMap<K,V> | 1、访问具有顺序性,保存了插入顺序 2、可以通过构造函数入参来使其按照访问次序排序 |
4 | TreeMap<K,V> | 1、有序Map,可以通过排序比较器来自定义存储数据的排序规则,默认按照key的生序排列 2、使用时key需要实现Comparable接口或者通过构造函数传入自定义Comparator |
存储结构
jdk1.8以后HashMap采用数组+链表/红黑树的方式来存储数据
源码分析
主干
// HashMap的主干,也就是上面的绿色部分,是一个Node<K,V>数组,每个Node包含一个K-V键值对
transient Node<K,V>[] table;
节点元素
// Node<K,V>是HashMap的静态内部类,实现了Map接口中的内部Entry接口
static class Node<K,V> implements Map.Entry<K,V> {
// 记录当前Node的key的hash值,可以避免重复计算,空间换时间
final int hash;
// 键
final K key;
// 值
V value;
// 存储指向下一个Entry的引用,是单向链表结构
Node<K,V> next;
// ...
}
其他重要字段
// 默认的初始容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量,1左移30位
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认扩容因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转红黑树的链表长度
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 链表转红黑树的数组长度
static final int MIN_TREEIFY_CAPACITY = 64;
// 实际存储K-V键值对的个数
transient int size;
// 记录HashMap被改动的次数,由于HashMap非线程安全,modCount可用于FailFast机制
transient int modCount;
// 扩容阈值,默认16*0.75=12,当填充到13个元素时,扩容后将会变为32,
int threshold;
// 负载因子 loadFactor=capacity*threshold,HashMap扩容需要参考loadFactor的值
final float loadFactor;
构造函数
// 看一个参数比较全的构造函数,构造函数中并未给table分配内存空间,此构造函数HashMap(Map<? extends K, ? extends V> m)会给table分配内存空间
public HashMap(int initialCapacity, float loadFactor) {
// 判断初始化容量是否合法,如果<0则抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
// 判断initialCapacity是否大于 1<<30,如果大于则取 1<<30 = 2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 判断负载因子是否合法,如果小于等于0或者isNaN,loadFactor!=loadFactor,则抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
// 赋值loadFactor
this.loadFactor = loadFactor;
// 通过位运算将threshold设值为最接近initialCapacity的一个2的幂次方(这里非常重要)
this.threshold = tableSizeFor(initialCapacity);
}
hash算法实现
HashMap中的hash算法实现分为三步。其中第二步使用hash值高16位参与位运算,是为了保证在数组table的length比较小的时候,可以保证高低bit都参与到hash运算中,保证分配均匀的同时采用位运算,也不会有太多的性能消耗;其中第三步,当n是2的整数的幂次方是,hash&(n-1),相当于对hash值取模,而位运算比取模运算效率更高;具体流程可以通过图示查看。
第一步:通过key.hashCode()获取key的hashcode;
第二步:通过(h = key.hashCode()) ^ (h >>> 16)进行高16位的位运算;
第三步:通过(n - 1) & hash对计算的hash值取模运算,得到节点插入的数组所在位置。
HashMap之put方法
第一步:判断键值对数组table[i]是否为空/null,是则执行resize()扩容。
第二步:根据键key计算hash值得到插入数组的索引i,如果tab[i]== null则直接插入,执行第六步;如果tab[i] != null,执行第三步。
第三步:判断tab[i]的第一个元素与插入元素key的hashcode&equals是否相等,相等则覆盖,否则执行第四步。
第四步:判断tab[i]是否是红黑树节点TreeNode,是则在红黑树中插入节点,否则执行第五步。
第五步:遍历tab[i]判断链表是否大于8,大于8则可能转成红黑树(数组需要大于64),满足则在红
文章评论