HashMap
底层实现
Hash的实现时数组加链表
如图所示
而hashMap我们每一次get 只获取 第一个值。
初始容量和负载因子##
因为put的时候可能需要做扩容，扩容会导致性能损耗，所以如果可以预知Map大小的话，可以设置合理的初始大小和负载因子来避免HashMap的频繁扩容导致的性能消耗。
默认为16与0.75
就是在插入第12(16*0.75)个的时候进行rehash
put 源码
public V put(K key, V value) {
//如果table为空
// static final Entry<?,?>[] EMPTY_TABLE = {};
// 为table 充气 想想一下 其实是扩容
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//当key为null，调用putForNullKey方法，保存null与table第一个位置中，这是HashMap允许为null的原因
if (key == null)
return putForNullKey(value);
int hash = hash(key);
//获取应该在table 中的下标
int i = indexFor(hash, table.length);
//遍历寻找与key相同的位置
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))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//修改次数 +1
modCount++;
//添加新的entry到i位置中
addEntry(hash, key, value, i);
return null;
}
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
* 添加一个新的条目（key-value-hascode）到固定的桶，
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果当前的size大于阀值，并且要存的位置不为null 扩容至当前容量的2倍
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
//重新计算位置
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization). This version needn't worry about resizing the table.
*
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
* 创建条目并添加
*/
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++;
}2017.06.25 add 几个新的1.8的api ，并且hashmap的源码底层数据结构已经变成 数组+链表+红黑树，当链表的长度大于8时转为红黑树
package com.wuhulala.javase.collection;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.HashMap;
import java.util.Map;
/**
* author： wuhulala
* date： 2017/6/25
* version: 1.0
* description: 作甚的
*/
public class HashMapTest {
private static final Logger logger = LoggerFactory.getLogger(HashMapTest.class);
public static void main(String[] args) {
Map<String, String> nameAddress = new HashMap<>();
nameAddress.put("xiaoming", "杭州市滨江区");
nameAddress.put("xiaohong", "杭州市江干区");
nameAddress.put("xiaolang", "杭州市滨江区");
nameAddress.put("xiaogou", "杭州市滨江区");
nameAddress.put("daming", "杭州市西湖区");
//1.8 如果key值不存在，写入value，否则直接返回value
nameAddress.putIfAbsent("daming", "杭州市下沙区");
print(nameAddress, "daming"); //(key，value) ---> (daming,杭州市西湖区)
//1.8 如果返回的值为null则删除这个映射
//否则写入新的值
nameAddress.compute("daming", (k, v) -> {
return "杭州市萧山区";
});
print(nameAddress,"daming"); //(key，value) ---> (daming,杭州市萧山区)
//1.8 如果这个映射的value为null才写入
nameAddress.computeIfAbsent("daming", (k) -> {
return "new address";
});
print(nameAddress,"daming"); //(key，value) ---> (daming,杭州市萧山区)
//1.8 如果这个映射的value不为null，并且返回的新值也不为null才写入
nameAddress.computeIfPresent("daming", (k, v) -> {
return "new address";
});
print(nameAddress,"daming"); //(key，value) ---> (daming,new address)
//O(n)
boolean isContainedAddress = nameAddress.containsValue("new address");
System.out.println(isContainedAddress);
//1，8 Map接口默认方法
nameAddress.replace("daming", "new address","test2");
print(nameAddress,"daming"); //(key，value) ---> (daming,test2)
nameAddress.replace("daming","test3");
print(nameAddress,"daming"); //(key，value) ---> (daming,test3)
nameAddress.put("daming","test4");
print(nameAddress,"daming"); //(key，value) ---> (daming,test4)
//1.8 遍历
nameAddress.forEach((key, value) -> {
System.out.println(key + "[" + value + "]");
});
//清空
nameAddress.clear();
}
private static void print(Map map, String key) {
logger.debug("(key，value) ---> ("+ key +"," + map.get(key) + ")");
}
}
2017.06.25 add 看到初始获取输入值最接近的2的整数次幂的值的函数tableSizeFor
tableSizeFor的功能（不考虑大于最大容量的情况）是返回大于输入参数且最近的2的整数次幂的数。比如10，则返回16。该算法源码如下：
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}详解如下：
先来分析有关n位操作部分：先来假设n的二进制为01xxx…xxx。接着
对n右移1位：001xx…xxx，再位或：011xx…xxx
对n右移2为：00011…xxx，再位或：01111…xxx
此时前面已经有四个1了，再右移4位且位与可得8个1
同理，有8个1，右移8位肯定会让后八位也为1。
综上可得，该算法让最高位的1后面的位全变为1。
最后再让结果n+1，即得到了2的整数次幂的值了。
现在回来看看第一条语句：
int n = cap - 1; 让cap-1再赋值给n的目的是令找到的目标值大于或等于原值。例如二进制1000，十进制数值为8。如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。减1后二进制为111，再进行操作则会得到原来的数值1000，即8。，如果我们for一边循环遍历或许需要1-31次，但是这个算法永远只需要4次。
该部分转自 http://www.cnblogs.com/loading4/p/6239441.html
1.8的put 也有了相应的改变
put方法调用了putVal方法put方法只是计算了一下hash值，并没有实现真正的逻辑。就像spring中的一些方法，真正做事的方法都要加上do前缀
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}我们详细看下putVal 方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 先声明些变量，但是最好声明的时候不要int n,i这种，当然这些框架代码无所谓了
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判断当前table是否为空。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果hash值对应的数组位置为空，那么直接创建一个新的节点并赋值到数组对应的位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果hash值与key都相等的话，说明已经找到对应的插入位置返回
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果当前位置的节点类型是TreeNode 说明链表已经转为了红黑树
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);
// 如果当前的容量已经大于了阈值(默认是8)
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 void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果表达不到树形化的条件,即当前hash表为空，或者hash表的容量还小于此阈值(MIN_TREEIFY_CAPACITY:64)
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;
// 循环当前hash值对应的hash表上的链表 开始把链表的节点的类型替换为TreeNode类型，统一用hd链接起来
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);
// 如果hash表当前位置存的的值不为空
if ((tab[index] = hd) != null)
//树化table
hd.treeify(tab);
}
}树形化的真正逻辑
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// 遍历所有节点
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
//把红黑树赋值到hash表对应的位置上
moveRootToFront(tab, root);
}static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
Node<K,V> rn;
//赋值
tab[index] = root;
//保证root是第一个节点，如果之前的第一个节点不为空的话，那么把它插入到root和root.next中间
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}