==
Map 是 Key-Value
对映射的抽象接口,该映射不包括重复的键,即一个键对应一个值。 HashMap
是 Java Collection Framework
的重要成员,也是Map族(如下图所示)中我们最为常用的一种。简单地说, HashMap`` 是基于哈希表的 Map 接口的实现,以
Key-Value 的形式存在,即存储的对象是
Entry (同时包含了 Key 和 Value) 。在
HashMap 中,其会根据hash算法来计算
key-value`的存储位置并进行快速存取。
HashMap<String, Integer> map = new HashMap<String, Integer>(); map.put("语文", 1); map.put("数学", 2); map.put("英语", 3); map.put("历史", 4); map.put("政治", 5); map.put("地理", 6); map.put("生物", 7); map.put("化学", 8); for(Entry<String, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); }
HashMap
是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作,并允许使用 null
值和 null
键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
HashMap
的实例有两个参数影响其性能: 初始容量
和 加载因子
。 容量
是哈希表中桶的数量, 初始容量
只是哈希表在创建时的容量。 加载因子
是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash
操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。
在 Java 编程语言中,最基本的结构就是两种,一个是数组,另外一个是指针(引用),HashMap 就是通过这两个数据结构进行实现。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。
HashMap 底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个 HashMap 的时候,就会初始化一个数组。
HashMap构造函数
public HashMap(int initialCapacity, float loadFactor) { 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); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); init(); }
HashMap共有4个构造函数
// 默认构造函数。 HashMap() // 指定“容量大小”的构造函数 HashMap(int capacity) // 指定“容量大小”和“加载因子”的构造函数 HashMap(int capacity, float loadFactor) // 包含“子Map”的构造函数 HashMap(Map<? extends K, ? extends V> map)
它包括几个重要的成员变量: table, size, threshold, loadFactor
。
table
Entry 是一个 static class
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; …… }
Entry 就是数组中的元素,每个 Entry 其实就是一个 key-value 对,它持有一个指向下一个元素的引用,这就构成了链表。
PUT储存源码
public V put(K key, V value) { // 对key的hashCode()做hash return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // tab为空则创建 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 计算index,并对null做处理 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 节点存在 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 该链为树 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 该链为链表 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 写入 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 超过load factor*current capacity,resize if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
put函数大致的思路为:
hashCode() TREEIFY_THRESHOLD old value load factor*current capacity
当程序试图将一个 key-value
对放入 HashMap
中时,程序首先根据该 key的 hashCode()
返回值决定该 Entry
的存储位置:如果两个 Entry
的 key
的 hashCode()
返回值相同,那它们的存储位置相同。如果这两个 Entry
的 key 通过 equals
比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry的 value,但key不会覆盖。如果这两个 Entry
的 key 通过 equals
比较返回 false,新添加的 Entry
将与集合中原有 Entry
形成 Entry 链
,而且新添加的 Entry
位于 Entry 链
的头部。
GET取出源码
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 直接命中 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 未命中 if ((e = first.next) != null) { // 在树中get if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 在链表中get do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
首先计算 key 的 hashCode,找到数组中对应位置的某一元素,如果是第一个然后通过 key 的 equals 方法在对应位置的链表或者树中查找需要的元素。
简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据 hash 算法来决定其在数组中的存储位置,再根据 equals 方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry 时,也会根据 hash 算法找到其在数组中的存储位置,再根据 equals 方法从该位置上的链表中取出该Entry。
在get和put的过程中,计算下标时,先对hashCode进行hash操作,然后再通过hash值进一步计算下标,如下图所示:
在对hashCode()计算hash时具体实现是这样的:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
可以看到这个函数大概的作用就是:高16bit不变,低16bit和高16bit做了一个异或。
当 HashMap 中的元素越来越多的时候,hash 冲突的几率也就越来越高,因为数组的长度是固定的。当 HashMap 中的元素个数超过 数组大小 *loadFactor
时,就会进行数组扩容, loadFactor
的默认值为 0.75,在resize的过程,简单的说就是把数组扩充为2倍,之后重新计算元素位置,把节点再放到新的数组中。resize的注释是这样描述的: 当超过限制的时候会resize,然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。
例如我们从16扩展为32时,具体的变化如下所示:
能表示的范围*2,多了一字节的范围。因此元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色)。
因此,我们在扩充HashMap的时候,不需要重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。
(h = k.hashCode()) ^ (h >>> 16)
,主要是从速度、功效、质量来考虑的,这么做可以在bucket的n比较小的时候,也能保证考虑到高低bit都参与到hash的计算中,同时不会有太大的开销。