以 jdk1.7 为例说明:
HashMap map = new HashMap();
在实例化以后, 底层创建了长度是 16 的一维数组 Entry[] table(数组的类型为 Entry, 数组名称为 table).
... 可能已经执行过多次 put 操作...
map.put(key1,value1):
首先,(需要知道放在数组中的位置)调用 key1 所在类的 hashCode()计算 key1 哈希值, 此哈希值经过某种算法计算以后, 得到在 Entry 数组中的存放位置.
1. 如果此位置上的数据为空, 此时的 key1-value1 添加成功.
2. 如果此位置上的数据不为空,(意味着此位置上存在一个或多个数据(以链表形式存在)), 比较 key1 和已经存在的一个或多个数据的哈希值:
2.1 如果 key1 的哈希值与已经存在的数据的哈希值都不相同, 此时 key1-value1 添加成功.---- 此时 key1-value1 和原来的数据以链表的方式存储.
2.2 如果 key1 的哈希值和已经存在的某一个数据 (key2-value2) 的哈希值相同, 继续比较: 调用 key1 所在类的 equals(key2)方法, 进行比较:
2.2.1 如果 equals()返回 false: 此时 key1-value1 添加成功.---- 此时 key1-value1 和原来的数据以链表的方式存储.
2.2.2 如果 equals()返回 true: 使用 value1 替换 value2. 想当于此时的 put 方法具有修改功能.
在不断的添加过程中, 会涉及到扩容问题, 当超出临界值 (且要存放的位置非空) 时, 扩容. 默认的扩容方式: 扩容为原来容量的 2 倍, 并将原有的数据复制过来.
jdk 1.8 相较于 jdk 1.7 在底层实现方面的不同:
1. new HashMap(): 底层没有在刚开始就创建一个长度为 16 的数组.
2. jdk 1.8 底层创建的数组是: Node 类型的 Node[], 而非 Entry[].
3. 在首次调用 put()方法时, 底层才会创建长度为 16 的数组.
4. jdk 1.7 底层结构只有: 数组 + 链表. jdk8 中底层结构: 数组 + 链表 + 红黑树.
4.1 形成链表时, 七上八下(jdk 1.7: 新的元素指向旧的元素. jdk 1.8: 旧的元素指向新的元素).
4.2 当数组的某一个索引位置上的元素以链表形式存在的数据个数> 8 且当前数组的长度> 64 时,
此时此索引位置上的数据改为使用红黑树存储, 提高了查找元素的速度.
DEFAULT_INITIAL_CAPACITY : HashMap 的默认容量: 16
DEFAULT_LOAD_FACTOR:HashMap 的默认加载因子: 0.75
threshold: 扩容的临界值,= 容量 * 填充因子: 16 * 0.75 ---> 12
TREEIFY_THRESHOLD:Bucket 中链表长度大于该默认值, 转化为红黑树 : 8
MIN_TREEIFY_CAPACITY: 桶中的 Node 被树化时最小的 hash 表容量 : 64
JDK 1.8 中 HashMap 源码:
- public class HashMap<K,V> extends AbstractMap<K,V>
- implements Map<K,V>, Cloneable, Serializable {
- private static final long serialVersionUID = 362498820763181265L;
- static final int DEFAULT_INITIAL_CAPACITY = 1 <<4; // aka 16
- static final int MAXIMUM_CAPACITY = 1 << 30;
- 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;
- 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;
- }
- public final K getKey() { return key; }
- public final V getValue() { return value; }
- public final String toString() { return key + "=" + value; }
- public final int hashCode() {
- return Objects.hashCode(key) ^ Objects.hashCode(value);
- }
- public final V setValue(V newValue) {
- V oldValue = value;
- value = newValue;
- return oldValue;
- }
- public final boolean equals(Object o) {
- if (o == this)
- return true;
- if (o instanceof Map.Entry) {
- Map.Entry<?,?> e = (Map.Entry<?,?>)o;
- if (Objects.equals(key, e.getKey()) &&
- Objects.equals(value, e.getValue()))
- return true;
- }
- return false;
- }
- }
- public HashMap() {
- this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
- }
- public HashMap(Map<? extends K, ? extends V> m) {
- this.loadFactor = DEFAULT_LOAD_FACTOR;
- putMapEntries(m, false);
- }
- public V put(K key, V value) {
- 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;
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- 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;
- if (++size> threshold)
- resize();
- afterNodeInsertion(evict);
- return null;
- }
- final Node<K,V>[] resize() {
- Node<K,V>[] oldTab = table;
- int oldCap = (oldTab == null) ? 0 : oldTab.length;
- int oldThr = threshold;
- int newCap, newThr = 0;
- if (oldCap> 0) {
- if (oldCap>= MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return oldTab;
- }
- else if ((newCap = oldCap <<1) < MAXIMUM_CAPACITY &&
- oldCap>= DEFAULT_INITIAL_CAPACITY)
- newThr = oldThr <<1; // double threshold
- }
- else if (oldThr> 0) // initial capacity was placed in threshold
- newCap = oldThr;
- else { // zero initial threshold signifies using defaults
- newCap = DEFAULT_INITIAL_CAPACITY;
- newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- }
- if (newThr == 0) {
- float ft = (float)newCap * loadFactor;
- newThr = (newCap <MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
- (int)ft : Integer.MAX_VALUE);
- }
- threshold = newThr;
- @SuppressWarnings({"rawtypes","unchecked"})
- Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
- table = newTab;
- if (oldTab != null) {
- for (int j = 0; j <oldCap; ++j) {
- Node<K,V> e;
- if ((e = oldTab[j]) != null) {
- oldTab[j] = null;
- if (e.next == null)
- newTab[e.hash & (newCap - 1)] = e;
- else if (e instanceof TreeNode)
- ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
- else { // preserve order
- Node<K,V> loHead = null, loTail = null;
- Node<K,V> hiHead = null, hiTail = null;
- Node<K,V> next;
- do {
- next = e.next;
- if ((e.hash & oldCap) == 0) {
- if (loTail == null)
- loHead = e;
- else
- loTail.next = e;
- loTail = e;
- }
- else {
- if (hiTail == null)
- hiHead = e;
- else
- hiTail.next = e;
- hiTail = e;
- }
- } while ((e = next) != null);
- if (loTail != null) {
- loTail.next = null;
- newTab[j] = loHead;
- }
- if (hiTail != null) {
- hiTail.next = null;
- newTab[j + oldCap] = hiHead;
- }
- }
- }
- }
- }
- return newTab;
- }
- final void treeifyBin(Node<K,V>[] tab, int hash) {
- int n, index; Node<K,V> e;
- if (tab == null || (n = tab.length) <MIN_TREEIFY_CAPACITY)
- resize();
- else if ((e = tab[index = (n - 1) & hash]) != null) {
- TreeNode<K,V> hd = null, tl = null;
- do {
- TreeNode<K,V> p = replacementTreeNode(e, null);
- if (tl == null)
- hd = p;
- else {
- p.prev = tl;
- tl.next = p;
- }
- tl = p;
- } while ((e = e.next) != null);
- if ((tab[index] = hd) != null)
- hd.treeify(tab);
- }
- }
来源: http://www.bubuko.com/infodetail-3130277.html