基于JDK 1.8.0。
简介：
HashMap的底层是通过一个邻接表来实现的。就是，将每个单链表的头结点保存在 一个数组里面。既然用到了数组，数组是不可变的。所以就需要动态扩容。
特点：
- 底层实现：邻接表。可以理解成数组链表。
- 线程安全：线程不安全。
- 扩容：需要扩容。
- 是否可以存放null：可以使用null作key
- 是否有序：
- 效率：直接通过函数计算出value的位置，效率非常高。
- 是否可以重复：一个key只能对应1个value。重复的key会覆盖掉前面的value。
源码分析：
HashMap基础的属性如下：
首先有3个常量。
//默认的容量16 。
static final int DEFAULT_INITIAL_CAPACITY = 16
//最大容量1073741824。左移运算，1转换成二进制然后，左移30位。
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认负载系数。当构造函数没有指定负载系数的时候就会使用。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
接下来是4个变量：
//Entry是HashMap的静态内部类。就是用Entry对象来存储K-V的。这个数组的每个元素又是一个单链表。
transient Entry<?,?>[] table;
//map的大小，map保存的键值对个数。
transient int size;
//临界值，用来标志是否需要扩容，如果键值对个数超过这个临界值，将会先扩容。
int threshold;
//负载系数，用来衡量HashMap的容量是否需要扩容的程度。用来计算临界值的。
final float loadFactor;
构造函数：
HashMap有4个构造函数，有1个需要传初始容量和负载系数的函数是主要的函数，另外3个都是调用这个函数的。
- 需要传入初始容量和构造因子的构造函数。
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
//判断初始容量是否合法，如果小于0，则抛出非常参数异常。
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);
//强制设定，容量为2的倍数。
//位移运算每左移1位，容量就增加2倍
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
//设置负载系数
this.loadFactor = loadFactor;
//计算并且设置好临界值。临界值取 容量*负载系数 和 最大容量+1 小的那个。
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//新建数组，数组大小=容量
table = new Entry[capacity];
init();
}
2.用一个Map作为构造函数的参数，先调用构造函数，然后调用putAllForCreate方法将map复制到table属性里面。需要计算出初始容量： （map的长度 / 默认的负载系数）+1 ，如果比默认的长度（16）小的话，就取默认的长度。
/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
剩下的两个构造函数，一个是不用传任何参数， 然后调用2个参数的构造函数，创默认的初始化容量和默认的负载系数当做参数传入。另一个是需要传入初始化容量，加上默认的负载系数，这两个作为参数调用2个参数的构造函数。
在分析添加方法之前，有5个方法需要了解和分析的。分别是：
- hash() 计算出hash值
- indexFor() 用于计算新的entry元素在table的存放位置；
- resize() 对HashMap进行扩容；
- transfer() 将旧的table元素转移到新的table元素中；
- addEntry() 添加键值对；
/**
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, which defends against poor quality hash functions. This is
* critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits.
*/
final int hash(Object k) {
//如果k是字符串类型，则直接返回字符串对象的hash32()方法的结果。
if (k instanceof String) {
return ((String) k).hash32();
}
int h = hashSeed ^ k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
//只是简单地将h和长度-1 进行与运算
return h & (length-1);
}
/**
* Rehashes the contents of this map into a new array with a
* larger capacity. This method is called automatically when the
* number of keys in this map reaches its threshold.
*
* If current capacity is MAXIMUM_CAPACITY, this method does not
* resize the map, but sets threshold to Integer.MAX_VALUE.
* This has the effect of preventing future calls.
*
* @param newCapacity the new capacity, MUST be a power of two;
* must be greater than current capacity unless current
* capacity is MAXIMUM_CAPACITY (in which case value
* is irrelevant).
*/
void resize(int newCapacity) {
//保存当前的table。
Entry<?,?>[] oldTable = table;
//获取当前的table的长度。
int oldCapacity = oldTable.length;
//如果旧的容量已经是最大值了，就不能再扩容了，只能设置临界值为最大值。
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//新建一个新的entry数组，容量为新的容量，然后将就的数组转移到新的数组里面。
Entry<?,?>[] newTable = new Entry<?,?>[newCapacity];
transfer(newTable);
//设置当前的table为新的table
table = newTable;
//重新计算临界值。
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* Transfers all entries from current table to newTable.
*/
@SuppressWarnings("unchecked")
void transfer(Entry<?,?>[] newTable) {
//将当前的entry数组保存在src里面
Entry<?,?>[] src = table;
//保存新的容量
int newCapacity = newTable.length;
//用新的table替换旧的table的元素。
for (int j = 0; j < src.length; j++ ) {
//获取当前table的第j个元素
Entry<K,V> e = (Entry<K,V>) src[j];
while(null != e) {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = (Entry<K,V>) newTable[i];
newTable[i] = e;
e = next;
}
}
//清空table，方便GC。
Arrays.fill(table, null);
}
添加键值对。这个方法主要是做扩容判断。真正执行扩容的方法是resize(),执行将键值对放进table的是createEntry()方法。
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果大小大于等于临界值，并且目标存储位置不为空，则扩容并重新计算hash值和目标存储位置。
if ((size >= threshold) && (null != table[bucketIndex])) {
//进行扩容。
resize(2 * table.length);
//重新计算hash值
hash = (null != key) ? hash(key) : 0;
//重新计算存储的位置索引
bucketIndex = indexFor(hash, table.length);
}
//创建一个entry并且加入到table里面
createEntry(hash, key, value, bucketIndex);
}
添加元素
添加键值对的方法有5个。公开的只有2个，添加单个键值对的put()，和添加一个map的putAll()。其余的都是私有的，提供给公开方法调用的，分别是使用null
作为key的putForNullKey()方法。添加的时候直接创建键值对的putForCreate()。添加多个键值对的时候直接创建键值对的putAllForCreate()。
1 put添加一个键值对。会进行扩容判断和扩容。
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
//如果key为null。则调用放入nullkey的方法并返回。
if (key == null)
return putForNullKey(value);
//根据key计算出hash值。
int hash = hash(key);
//利用hash值和table的长度，算出位置i。
int i = indexFor(hash, table.length);
@SuppressWarnings("unchecked")
//获取table第i个元素的值。
Entry<K,V> e = (Entry<K,V>)table[i];
//判断key是否重复，如果重复了，就覆盖value并返回旧的value。
for(; e != null; e = e.next) {
Object k;
//如果e的hash值和key计算出来的hash值相等，并且key一致，则覆盖e的value并返回原先的value。
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
//这个方法什么也不做，应该是预留方法。
e.recordAccess(this);
return oldValue;
}
}
modCount++;//修改次数加1 。
//增加entry。将在这个方法里面进行扩容。
addEntry(hash, key, value, i);
return null;
}
- putAll()方法用map做参数，将一个map添加到当前的map。
/**
* Copies all of the mappings from the specified map to this map.
* These mappings will replace any mappings that this map had for
* any of the keys currently in the specified map.
*
* @param m mappings to be stored in this map
* @throws NullPointerException if the specified map is null
*/
public void putAll(Map<? extends K, ? extends V> m) {
//获取将要添加的键值对的个数，如果是0，则直接返回。
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return;
/*
* Expand the map if the map if the number of mappings to be added
* is greater than or equal to threshold. This is conservative; the
* obvious condition is (m.size() + size) >= threshold, but this
* condition could result in a map with twice the appropriate capacity,
* if the keys to be added overlap with the keys already in this map.
* By using the conservative calculation, we subject ourself
* to at most one extra resize.
*/
//判断是否需要扩容，如果需要，则进行扩容。
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = table.length;
while (newCapacity < targetCapacity)
newCapacity <<= 1;
if (newCapacity > table.length)
resize(newCapacity);
}
//循环调用put方法，将键值对一个一个put进去。
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
- 私有的putForNullKey() 用null作为key。添加一个键值对。
/**
* Offloaded version of put for null keys
*/
//用null为key的value放进table数组的首位，如果首位已经有值，则连接为首结点。
//如果已经有null为key的键值对，则覆盖旧的value。返回旧的value。
private V putForNullKey(V value) {
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)table[0];
for(; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
- 私有的putForCreate() 。 快速添加一个元素，不用判断扩容。
/**
* This method is used instead of put by constructors and
* pseudoconstructors (clone, readObject). It does not resize the table,
* check for comodification, etc. It calls createEntry rather than
* addEntry.
*/
private void putForCreate(K key, V value) {
//结算出hash值，和存储索引。
int hash = null == key ? 0 : hash(key);
int i = indexFor(hash, table.length);
/**
* Look for preexisting entry for key. This will never happen for
* clone or deserialize. It will only happen for construction if the
* input Map is a sorted map whose ordering is inconsistent w/ equals.
*/
//判断key是否有重复，如果重复则覆盖旧值并返回。
for (@SuppressWarnings("unchecked")
Entry<?,V> e = (Entry<?,V>)table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
//创建一个键值对。不判断扩容。
createEntry(hash, key, value, i);
}
- 私有的 putAllForCreate(); 快速添加多个键值对的版本。只是简单地循环调用putForCreate() 方法。
private void putAllForCreate(Map<? extends K, ? extends V>
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
删除元素
删除元素有1个公开的方法。只有删除单个元素的remove(Object key)； 另外2个包访问权限的方法分别是：removeEntryForKey（）, 实际上是提供给remove方法调用的。实际的删除元素的方法； removeMapping() 删除一个键值对，传入的参数类型，实际上必须是Map的内部类Entry。 删除元素只能单个删除，不能多个删除。
根据key删除单个键值对remove()。 只是简单的调用removeEntryForKey()方法。removeEntryForKey()方法是包权限的，不公开的。
/**
* Removes the mapping for the specified key from this map if present.
*
* @param key key whose mapping is to be removed from the map
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
/**
* Removes and returns the entry associated with the specified key
* in the HashMap. Returns null if the HashMap contains no mapping
* for this key.
*/
final Entry<K,V> removeEntryForKey(Object key) {
//根据key计算出hash值和存储索引 i
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
//循环找出对应的结点，然后删除结点，最后size-1.
@SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
获取值
根据key获取值也只有1个get() 方法。get() 方法只是简单地调用了getEntry() 方法。
public V get(Object key) {
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
//getEntry方法的实现思路也是计算出hash值和存储索引，然后根据索引来循环找出key和hash值相等的value，如果有则返回，如果没有则返回null。
/**
* Returns the entry associated with the specified key in the
* HashMap. Returns null if the HashMap contains no mapping
* for the key.
*/
@SuppressWarnings("unchecked")
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry<?,?> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return (Entry<K,V>)e;
}
return null;
}
总结
HashMap没有实现同步，所以不是线程安全的。
扩容是按照2的倍数扩容的。负载系数默认是0.75, 临界值=容量*负载系数，如果当前大小超过了临界值，则进行扩容；扩容需要复制旧的键值对到新的table里面去，需要损耗一定的性能；如果在能预估map的容量的情况下，尽量给HashMap一个初始的容量。初始容量=目标容量/0.75 + 1。
网友评论