前言：
关于java基础，在hashMap底层原理这个问题上可以说是非常经典的问题了；下面就讨论下hashMap的底层原理；
另外个人整理了一些资料，有需要的朋友可以直接点击领取。
JDK1.7 HashMap的底层源码:
HashMap 的存储结构:
HashMap的存储结构是数组+链表的结合（在jdk1.8之后，添加了红黑树结构（具体看下面jdk1.8介绍））
，当实例化一个HashMap时，系统会建立一个长度为capacity的entry数组，在这个数组中可以存
储元素的位置，我们称为“桶”（bucket）,；每个bucket都有自己的索引，系统可以通过索引快速的
查到到bucket中的元素；（底层通过hash算法，把元素存储到对应的索引中的bucket中，如果有多的就存储到
对应的链表中）每个bucket中都带有一个引用变量用来指向下一个元素（链表了）；因此，在一个bucket中
就生成了一条entry链；entry是hashMap中的基本组成单元，每个entry包含了一哥key-value键值对；
entry是HashMap中的一个静态内部类（初始化）；
static class Entry<K,V> implements Map.Entry<K,V>{
final K key;
V value;
Entry<K,V> next; // 存储指向下一个entry的引用，单链表结构；
int hash; // 对key的hashcod值进行hash运算的得到的值，存储在entry中，避免重复运算
/**
* create new entry
*/
Entry(int h,K K,V v,Entry<K,V> n){
value=v;
next=n;
key = k;
hash=h;
}
}
而jdk1.8之后为Node(除了给hash值加了final修饰外，表示不可变之外没有什么变化)：
static class Node<K,V> implements Map.Entry<K,V>{
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash,K key,V value,Node<K,V> next){
this.hash=hash;
this.key=key;
this.value=value;
this.next=next;
}
}
经过以上分析，hashMap的存储结构可以用下图来表示:
元素中hash值的算法为：key的hash值%len（数组/桶 的长度）；
构造方法：
先看下hashMap中的几个重要的属性
//1<<4=2的4次方 默认的初始容量为16；
static final int Default_INITIAL_CAPACITY=1<<4;
// 最大容量为2的30次方
static final int MAXIMUM_CAPACITY=1>>30;
// 默认的装载因子
static final float DEFUALT_LOAD_FACTOR=0.75F;
// HashMap内部的存储结构为一个数组，此处的数组为空，即没有初始化之前的状态
static final Entry<?,?>[] EMPTY_TABLE={};
// (向下转型)空的存储实体 transient表示不需要序列化的属性
transient Entry<K,V>[] table=(Entry<K,V>)EMPTY_TABLE;
// 实际存储key-value键值对的个数
transient int size;
// 阈值，当table=={} 值，该值为初始容量（16）；当table被填充时，threshold的值为capacity*loadFactor;hashMap在进行扩容时需要参照threshold;
int threshold;
// 负载因子，代表了table的填充度有多少，默认的值为0.75
final float loadFactor;
// 快速失败（由于hashMap是线程非安全性的，所以在hashMap参与迭代的过程中，如果出现了其他线程参与而导致hashMap的结果发生了改变（如，put，remove操作），需要抛出ConcurrentModifactionException异常）
transient int modCount;
// 默认的threshold的值；
// Integer类中 @Native public static final int MAX_VALUE = 0x7fffffff; integer最大取值方位21亿
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFUALT=Integer.MAX_VALUE;
//计算hash值时的key
transient int hashSeed=0;
jdk1.8之后：（jdk1.8之后添加了红黑树，当超过8时，转化为红黑树，当到6时，换为数组+链表的结构；中间7为缓冲）
private static final long serialVersionUID = 362498820763181265L;
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
* 当链表的数组长度为8时，转化为红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
* 数组长度为6时，又转换回来
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
* 最小树形化阈值：当hash表中的容量>64时，链表才会转化为红黑树
* 如果桶中的数量过大，不是为树形化（转为红黑树），而是要进行扩容
* 为了避免扩容，树形化的选择冲突，这个值不能小于4*TREEINF_THRESHOLD
*/
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
HashMap 有4个构造器（如果构造器没有自带参数，那么会使用默认的16初始容量和0.75的加载因子）
//通过初始容量和状态因子来构造HashMap
public HashMap(int initialCapacity,float loadFactor){
//参数有效性的检查
if(initialCapacity<0){
throw new IllegalArgumentException("Illegal initial Argument" +initialCapacity);
}
if(initialCapacity>MAXIMUM_CAPACITY)
initialCapacity=MAXIMUM_CAPACITY;
if(loadFactor<=0 || Float.isNaN(loadFactor)){
threw new IllegalArgumentException("Illegal loadFactory Aragument"+loadFactor);
}
this.loadFactory=loadFactory;
threshold=initialCapacity;
init(); // 在hashMap中没有具体的实现，不过在其子类linkedHashMap中就会有对应的实现
}
// 通过扩容因子来构造HashMap，容量默认值16
public HashMap(int initialCapacity ){
this(initialCapacity,Default_LOAD_FACTOR);
}
// 无参构造函数
public HashMap(){
this(DEFAULT_INITIALCAPACITY,DEFAULT_LOAD_FACTORY);
//通过其他Map来初始化HashMap，容量通过Map中的size来计算，转载因子为0.75
public HashMap(Map<? extends K,? extends V> m){
this(Math.max((int) (m.size()/DEFAULT_LOAD_FACTOR)+1,DEFAULT_INITAL_CAPACITY),DEFAULT_LOAD_FACTOR);
//初始化HashMap的底层数组结构
inflateTable(threshold);
// 添加m中的元素
putAllForCreate(m);
}
}
网友评论