HashMap 根据键的 hashCode 值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null,允许多条记录的值为 null。HashMap 非线程安全,即任一时刻可以有多个线程同时写 HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections 的 synchronizedMap 方法使 HashMap 具有线程安全的能力,或者使用 ConcurrentHashMap。我们用下面这张图来介绍 HashMap 的结构。
Jdk1.7实现 数组+链表 上图中,每个绿色的实体是嵌套类 Entry 的实例, Entry 包含四个属性: key, value, hash 值和用于单向链表的 next 。 1. capacity:当前数组容量,始终保持 2^n ,可以扩容,扩容后数组大小为当前的 2 倍。 2. loadFactor:负载因子,默认为 0.75 。 3. threshold:扩容的阈值,等于 capacity * loadFactor Jdk1.8实现 数组+链表+红黑树二、Hashmap源码-put方法
transient Node[] table; 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 [] tab; Node p; int n, i; //数组为空时,初始化 if ((tab = table) == null || (n = tab.length) == 0) //resize()这里只是初始化数组 n = (tab = resize()).length; //计算hash值对应数组的位置,为空就直接添加节点 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; //hash和key都相同,进行覆盖 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); //链表长度大于8而且数组长度大于64,树化 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)//key不相同时,每次插入一条数据自增1. 当size大于threshold resize(); afterNodeInsertion(evict); return null; }
1.首先获取Node数组table对象和长度,若table为null或长度为0,则调用resize()方法进行初始化table数组和长度。
2.根据hash值计算出数组中对应桶的位置是否为Null,若为Null ,直接添加节点
3.若判定不为Null,我们的判断再做分支
3.1 首先对hash和key值进行判断,如果都相同,则直接覆盖原来的数据
3.2 若进行判断为false,则判断是否为是一颗红黑树, 若判定成功则在红黑树中查找符合条件的节点并将其回传赋给e
3.3 若上面判断都为false,说明这个桶上是一个链表结构,向单向链表中添加数据若单向链表的长度大于等于8并且在treeifyBin(tab, hash)里判断数组长度大于64,就将其转为红黑树保存,记录下一个节点,对e进行判定若成功则返回旧值
4.最后判定数组是否需要扩容
static final int hash(Object key) {
int h;
//计算hashCode并且使用hashCode的低16位和高16位进行异或操作,目的使hashCode值足够分散
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
在下面Hashmap第一次进行调用resize()数组时,DEFAULT_INITIAL_CAPACITY 这个参数强调了Hashmap的数组长度必须是2的倍数。在hash值计算中可以利用位运算去代替取模运算。在hash值计算时,可以看到源码中他将hashCode的高16位和低16位进行一个异或运算,使用hashCode可以充分的使用,使值能相对分散(一个不错的策略)。
五、Hashmap源码-resize方法final Node[] resize() { Node [] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { //MAXIMUM_CAPACITY = 1 << 30 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //2倍扩容 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) / newCap = oldThr; else { //初始化时 //DEFAULT_INITIAL_CAPACITY = 1 << 4; 强调初始容量是2的整数倍 //DEFAULT_LOAD_FACTOR = 0.75f; 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); //这里看出hashMap扩容不是在原来位置就是原来位置加原来数组长度的位置 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
1.判断数组大小是否足够,足够则直接返回旧数组
2.(1)若旧数组长度大于2的30次方,则直接把数组长度设置成Integer最大值。
(2)若旧数组左移一位(两倍扩容)后,长度小于2的30次方且大于16,进行两倍扩容
3.确定下一次数组的长度, 将新数组赋予当前数组
4.通过for循环将旧数组中的值存入扩容后的新数组中
4.1 获取旧数组中指定桶下的Node对象 赋予e, 并将旧表中的桶位置数据置空。
4.2 若e的下面没有其他节点则将e直接赋到新数组中桶的位置
4.3 若e的类型为TreeNode(红黑树)
4.3.1 分割树,将新数组和旧数组分割成两个树,并判断桶处节点的长度是否需要转换成红黑树放入新数组存储
4.3.2 通过doWhile循环,不断获取新旧数组的节点
4.3.3 通过判定将旧数据和新数据存储到新数组指定的位置



