HashMap的概述:
基于哈希表的 Map 接口的实现。
此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。
(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)
此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。
迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。
所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。
HashMap 的实例有两个参数影响其性能:初始容量 和 加载因子。
容量 是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。
加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。
当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。
通常,默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。
加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点)。
在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。
如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。
如果很多映射关系要存储在 HashMap 实例中,则相对于按需执行自动的 rehash 操作以增大表的容量来说,使用足够大的初始容量创建它将使得映射关系能更有效地存储。
注意:此实现不是同步的。如果多个线程同时访问一个哈希映射,而其中至少一个线程从结构上修改了该映射,则它必须 保持外部同步。
(结构上的修改是指添加或删除一个或多个映射关系的任何操作;仅改变与实例已经包含的键关联的值不是结构上的修改。)
这一般通过对自然封装该映射的对象进行同步操作来完成。
如果不存在这样的对象,则应该使用 Collections.synchronizedMap 方法来“包装”该映射。
最好在创建时完成这一操作,以防止对映射进行意外的非同步访问,如下所示:
Map m = Collections.synchronizedMap(new HashMap(…));
由所有此类的“collection 视图方法”所返回的迭代器都是快速失败 的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器本身的 remove 方法,其他任何时间任何方式的修改,迭代器都将抛出 ConcurrentModificationException。
因此,面对并发的修改,迭代器很快就会完全失败,而不冒在将来不确定的时间发生任意不确定行为的风险。
注意:迭代器的快速失败行为不能得到保证,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证。
快速失败迭代器尽最大努力抛出 ConcurrentModificationException。
因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。
此类是 Java Collections Framework 的成员。
HashMap的桶(容量):
// 默认的初始桶(容量)是16,每次扩容都是x2 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 // 最大容量为(必须是2的幂且小于2的30次方,传入容量过大将被这个值替换) static final int MAXIMUM_CAPACITY = 1 << 30; // 默认加载因子为0.75, static final float DEFAULT_LOAD_FACTOR = 0.75f;
加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 resize 操作(即扩容)。
下面说下加载因子,如果加载因子越大,对空间的利用更充分,但是查找效率会降低(链表长度会越来越长);如果加载因子太小,那么表中的数据将过于稀疏(很多空间还没用,就开始扩容了),对空间造成严重浪费。
如果我们在构造方法中不指定,则系统默认加载因子为0.75,这是一个比较理想的值,一般情况下我们是无需修改的。
另外,无论我们指定的容量为多少,构造方法都会将实际容量设为不小于指定容量的2的次方的一个数,且最大值不能超过2的30次方。
HashMap的key和value可以为null:
get():
// 获取key对应的value public V get(Object key) { if (key == null) //如果key为null,调用getForNullKey() return getForNullKey(); //key不为null,调用getEntry(key); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } //当key为null时,获取value private V getForNullKey() { if (size == 0) { return null;//链表为空,返回null } //链表不为空,将“key为null”的元素存储在table[0]位置,但不一定是该链表的第一个位置! for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; } //key不为null,获取value final Entry<K,V> getEntry(Object key) { if (size == 0) {//判断链表中是否有值 //链表中没值,也就是没有value return null; } //链表中有值,获取key的hash值 int hash = (key == null) ? 0 : hash(key); // 在“该hash值对应的链表”上查找“键值等于key”的元素 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; //判断key是否相同 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e;//key相等,返回相应的value } return null;//链表中没有相应的key }
首先,如果key为null,则直接从哈希表的第一个位置table[0]对应的链表上查找。
记住,key为null的键值对永远都放在以table[0]为头结点的链表中,当然不一定是存放在头结点table[0]中。
如果key不为null,则先求的key的hash值,根据hash值找到在table中的索引,在该索引对应的单链表中查找是否有键值对的key与目标key相等,有就返回对应的value,没有则返回null。
put():
// 将“key-value”添加到HashMap中 public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null)// 若“key为null”,则将该键值对添加到table[0]中。 return putForNullKey(value); // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。 int hash = hash(key);//获取key的hash值 int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // 若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出! V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 若“key”对应的键值对不存在,则将“key-value”添加到table中 modCount++; //将key-value添加到table[i]处 addEntry(hash, key, value, i); return null; }
如果key为null,则将其添加到table[0]对应的链表中,putForNullKey的源码如下
// putForNullKey()的作用是将“key为null”键值对添加到table[0]位置 private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 如果没有存在key为null的键值对,则直接添加到table[0]处! modCount++; addEntry(0, null, value, 0); return null; }
如果key不为null,则同样先求出key的hash值,根据hash值得出在table中的索引,而后遍历对应的单链表,如果单链表中存在与目标key相等的键值对,
则将新的value覆盖旧的value,比将旧的value返回,如果找不到与目标key相等的键值对,或者该单链表为空,调用addEntry()方法将该键值对插入到改单链表的头结点位置(每次新插入的节点都是放在头结点的位置).
如果key为null,调用putForNullKey(),直接去遍历table[0]Entry链表,寻找e.key==null的Entry或者没有找到遍历结束。
如果找到了e.key==null,就保存null值对应的原值oldValue,然后覆盖原值,并返回oldValue
如果在putForNullKey()中,在table[0]Entry链表中没有找到也会调用addEntry方法添加一个key为null的Entry。
void addEntry(int hash, K key, V value, int bucketIndex) { //先判断大小 if ((size >= threshold) && (null != table[bucketIndex])) { // 若HashMap的实际大小不小于 “阈值”,则调整HashMap的大小 resize(2 * table.length);//扩容,每次增长2倍 hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex);//新增Entry。将“key-value”插入指定位置,bucketIndex是位置索引。 } void createEntry(int hash, K key, V value, int bucketIndex) { // 保存“bucketIndex”位置的值到“e”中 Entry<K,V> e = table[bucketIndex]; // 设置“bucketIndex”位置的元素为“新Entry”, // 设置“e”为“新Entry的下一个节点” table[bucketIndex] = new Entry<>(hash, key, value, e); size++;
注意这里new Entry<>()的构造方法,将key-value键值对赋给table[bucketIndex],并将其next指向元素e,这便将key-value放到了头结点中,并将之前的头结点接在了它的后面。
该方法也说明,每次put键值对的时候,总是将新的该键值对放在table[bucketIndex]处(即头结点处)。
同时也要注意,这个方法首先会判断是否要扩容,当现在的HashMap中的Entry数大于等于扩容临界值(capacity*load factor)并且index对应的地方没有Entry就扩容.HashMap每次扩容的大小为2倍原容量,
默认容量为16,hashmap的capacity会一直是2的整数幂。
// 重新调整HashMap的大小,newCapacity是调整后的单位 void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { //旧容量不小于最大容量(一般不会发生,反正我没遇到过) threshold = Integer.MAX_VALUE; return; } //一般扩容 // 新建一个HashMap,将“旧HashMap”的全部元素添加到“新HashMap”中, // 然后,将“新HashMap”赋值给“旧HashMap”。 Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
很明显,是新建了一个HashMap的底层数组,而后调用transfer方法,将就HashMap的全部元素添加到新的HashMap中(要重新计算元素在新的数组中的索引位置)。
// 将HashMap中的全部元素都添加到newTable中 void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }
遍历原表table ,从table[0]开始,e=table[0],不为null就创建一个临时Entry next引用e.的下一个Entry,然后把e放到新表中,头插到table[i]中,i由indexFor方法决定i(h&newCapacity),然后让e=next,继续遍历拷贝。
扩容之后继续插入要插入的Entry,这个时候就要重新hash了,因为旧表已经扩容了,若果key为nul任然是0。
然后进行真正的插入,调用 createEntry(hash, key, value, bucketIndex),
void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; } //进行头插,创建一个新的entry, Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }
新的entry复制到table[bucketIndex],并next引用原来的table[bucketIndex],完成。
……..
仅仅只是HashMap的普通扩容,就这么麻烦,如果再加上线程安全,而加同步的话,那么效率可想而知.并且,HashMap在高并发场景下调用transfer方法,可能会出现环形链表,导致程序死循环。