本文共 7613 字,大约阅读时间需要 25 分钟。
(1)HashMap在Java中是一个类。它是通过键值对结构来存取数据的。底层是通过数组+链表/红黑树实现的。
(2) HashMap的特点是 “无序”、 “键唯一“。 (3)注意:HashMap中的key和value都允许为null。
(1)HashMap继承自AbstractMap这个抽象类,实现了Map、Cloneable、Serializable接口。
/**(1)类的定义*/public class HashMapextends AbstractMap implements Map , Cloneable, Serializable { ........ }
(2)默认初始容量为2的4次幂(16),并且HashMap的容量必须为2的n次方。当在第一次添加元素时,会默认生成一个长度为16的数组。
(3)HashMap的最大容量为2的30次方。 (4)当构造函数中未指定时使用的负载因子默认为0.75f。当数组元素超过容量的0.75时HashMap就会自动扩容。 (5)在 jdk1.8中当链表的长度必须大于等于2小于等于8。当超过8时就会转换成树的结构。(红黑树)。当树中元素小于6时,就会自动回退成链表的结构。 (6)树化的表的最小容量为64。如果树中的结点过多的话,则会调整表的容量,然后重新计算,重新存储在不同的位置上。 *最少为 4 * TREEIFY_THRESHOLD 以避免调整大小和树阈值之间的冲突。
//(2)初始容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //(3) 最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; //(4)默认负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //(5)链表与树之间转换的阈值 static final int TREEIFY_THRESHOLD = 8;//链表树化 static final int UNTREEIFY_THRESHOLD = 6;//树链表化 //(6) static final int MIN_TREEIFY_CAPACITY = 64;//树化的表的最小容量
HashMap 中对静态内部类Node的定义。其中包括属性 hash,key,value,以及引用next。
/** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */ static class Nodeimplements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node 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) { //更改元素的值,将旧的value覆盖掉并且返回 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; } }
定义hash函数,计算key的hash值,来确定存储的索引。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
我们在添加元素时会调用HashMap的put这个api,来完成元素的添加。
基本原理: (1) 根据hash函数得到索引值,如果这个位置没有元素就直接插。 (2)如果有元素的话就要判断这个对象的hashcode与已有对象的hashcode是否相等?(注意:不同key的hashcode可能相同哦!) (3)如果不相等,则直接在链表的末尾创建一个结点,将要存储的对象插入进去就行。 (4)但如果hashcode值相等,则要通过equals()方法来判断key是否相等,若不相等则直接插入;否则:hashcode值和key都相等,则说明这个对象已经存在,由于hashMap的key的唯一性,则会覆盖掉这个已存在对象的旧的值,完成put操作。
底层源码如下:
(1)添加的的put方法,去调用putVal()方法来实现元素的真正的添加。
/*** (1)添加的的put方法,去调用putVal方法来实现元素的真正的添加。*/public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
(2)将元素添加进去的代码。其中hash是通过key计算出的hash值onlyIfAbsent如果为true, 则不改变已经存在的值evict如果是false, 则表处于创建模式。
/***(2)将元素添加进去的代码。其中hash是通过key计算出的hash值onlyIfAbsent如果为true, 则不改变已经存在的值evict如果是false, 则表处于创建模式*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node 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 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 )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; }
(3)resize()方法:来重新确定table的容量(初始化或加倍大小),并将重新变化后的table返回。扩容之后计算新的索引的高位,如果是0则索引位置不变;如果是1,则新索引的位置=原来索引的位置+原来数组的长度。
*① 如果为空,则分配在阈值范围内符合初始容量的值。
*②否则,在新表中容量为 2 次方。
final Node[] resize() { Node [] 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 [] newTab = (Node [])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node 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 )e).split(this, newTab, j, oldCap); else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node 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; }
关于HashMap的一些api的简单使用,在JCF框架处有简单的示例,如果有需要可以去了解一下。
以上就是我对HashMap的简单认识,有问题感谢大家指出,共同学习,共同进步!!!转载地址:http://zujvi.baihongyu.com/