hashmap源码分析
2018-09-15 本文已影响23人
Sophie12138
put操作流程图
通过源代码追踪的方式进行学习。
- put操作
- get操作
- remove操作
put操作
1.将值put，在源码中，存在几种情况
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)
// 如果table为null，或者table长度为0，则初始化table分配空间
n = (tab = resize()).length;
// (n - 1) & hash表达式为value要插入table中的位置
// 如果此位置的内容为null，说明可以直接将value插入，不会发生碰撞
if ((p = tab[i = (n - 1) & hash]) == null)
// 直接创建一个新的Node，并放到table相应的位置
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; // 直接覆盖值
// 如果定位到的位置，已经是变换为红黑树的位置，则put到此树上。
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 最后一种情况则是此位置为链表
else {
// 遍历链表
for (int binCount = 0; ; ++binCount) {
// 如果此节点的next为空，直接在后面插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果链表的长度超过了8，那么就进行树化
if (binCount >= TREEIFY_THRESHOLD - 1)
// 树化方法
treeifyBin(tab, hash);
break;
}
// 如果下一个节点不为null，且遍历到的此节点与要插入的值得hash相等，
// key相等，则直接覆盖
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
// put操作之后其实是有返回值得，如果是新值覆盖旧值
// 则返回旧值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//新值覆盖
e.value = value;
// 这个是空实现
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
++modCount;// 修改次数+1 和fastRemove()有关也和并发修改有关
if (++size > threshold) //如果大于了阙值 需要扩容的大小
resize(); //重新设置hash桶的大小，也有可能进行树化，见后面代码
afterNodeInsertion(evict);//空方法
return null;
}
2.将链表转换为双向链表
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 判断是否有将链表变为红黑树的必要，如果数组长度 < 64
// 则是对数组进行扩容，而不是转换链表，因为转换链表的时间空间
// 花费也较高。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 扩容
resize();
// 如果元素数组长度已经大于等于MIN_TREEIFY_CAPACITY，就有必要进行结构转换
// 判断链表的头结点是否为空
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); // 继续遍历链表
// 到目前为止 也只是把Node对象转换成了TreeNode对象，把单向链表
// 转换成了双向链表，把转换后的双向链表，替换原来位置上的单向链表
if ((tab[index] = hd) != null)
hd.treeify(tab);//将双向链表转换为红黑树
}
}
3.进行红黑树转换
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// 将当前节点赋值给x
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//获取x的下一个节点
next = (TreeNode<K,V>)x.next;
//设置x的左右为null
x.left = x.right = null;
if (root == null) { // 红黑树根节点为null
x.parent = null;
//根节点为黑色
x.red = false;
//根节点为x
root = x;
}
else { // 根节点不为null
// 获取K key
K k = x.key;
//获取hash
int h = x.hash;
//获取数据的类型
Class<?> kc = null;
//开始循环构建 将根节点复制给p
for (TreeNode<K,V> p = root;;) {
//ph 当前节点的hash值
int dir, ph;
// dir 判断左右用的
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)
// 当hash相等，并且没有比较器的时候，进行另外的一种方式比较
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
//如果p节点的左儿子或者右儿子为null，那么就开始创建，否则就继续往下面找
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 通过大小比较判断，如果新的p（原来p的子节点） 为null
// x.parent就是当前的p
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 红黑树的插入，把新的节点插入到当前树中，
// 新的节点的parent就是你当前遍历的节点
// 而且当前遍历的节点的左儿子/右儿子已经确定
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
4.平衡树结构
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//插入的节点必须是红色的，除非是根节点
x.red = true;
//遍历到x节点为黑色,整个过程是一个上滤的过程
//xp=x.parent;xpp=xp.parent;xppl=xpp.left;xppr=xpp.right;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//如果xp的黑色就直接完成，最简单的情况
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//如果x的父节点是x父节点的左节点
if (xp == (xppl = xpp.left)) {
//x的父亲节点的兄弟是红色的（需要颜色翻转）
if ((xppr = xpp.right) != null && xppr.red) {
//x父亲节点的兄弟节点置成黑色
xppr.red = false;
//父几点和其兄弟节点一样是黑色
xp.red = false;
//祖父节点置成红色
xpp.red = true;
//然后上滤（就是不断的重复上面的操作）
x = xpp;
}
else {
//如果x是xp的右节点整个要进行两次旋转,先左旋转再右旋转
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
//以左节点镜像对称
else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
5.扩容
// 扩容方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// oldCap是HashMap数组的大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 如果老的HashMap容量已经到达最大阈值了，
// 没法扩容了，直接将阈值设置为最大并返回
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
}
// oldCap不大于0，就说明是初始化的情况。
// 如果已经有阈值，则初始化的时候HashMap的容量就是阈值的大小
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 如果阈值也没有初始化，那就都用默认的值
else {
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);
}
// 这里如果是初始化的情况，newThr=16*0.75=12，所以当size>12时就会触发扩容
threshold = newThr;
// 生成新的数组，如果是初始化，会生成一个长度为16的数组
@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);
// 不是红黑树，那就是链表了
// 下面也是Java8中的一个优化点
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;
// 这里把hash值与oldCap做与操作，而oldCap是2的倍数，所以低位肯定都是0
// 比如说第一次扩容的时候oldCap是16，也就是00010000，
// 那这里就要看hash的高一位也就是000?xxxx中的？是1还是0了
// 如果是0，那意思就是在新的数组里面的索引跟以前的一样；如果是1，那新的索引就是以前的下标+16
// 后面再扩容时也是一样，再高一位是0，索引不变；
// 如果是1，索引变为原索引+oldCap
// 这么做的目的是将链表中的一些节点分散到新的数组中去
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;
}
get操作
1.检查数组，链表，树三种情况
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) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
2.红黑树中查找
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
remove操作
1.根据key删除节点
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
2.删除节点,matchValue如果为true，则只当value也相等的时候才删除节点
* movable用于红黑树中，当为false时，只删除树中的节点而不移动其他节点
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//要删除的就是第一个节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//否则那就说明有多个哈希冲突的节点，那可能是链表也可能是红黑树了
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
//是链表的话就得循环查找了
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//node不为null，说明找到要删除的节点了
//这里会根据其他条件来进行处理
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//下面是单链表删除节点
//如果要删除的是第一个节点，那得把后面的节点补到数组里面
else if (node == p)
tab[index] = node.next;
//如果删除的是链表中的其它节点，把链表接上
else
p.next = node.next;
++modCount;
--size;
//这里是供LinkedHashMap调用的方法
afterNodeRemoval(node);
return node;
}
}
return null;
}
附录
hash算法：
https://www.cnblogs.com/lzl2016/p/6648259.html
-
查重与分组问题
某公司正在做一个寻找走失儿童的公益项目，现在有一个函数，可以输入两个图片，并返回这个儿童是否重复。请你设计一个系统，帮助他们寻找儿童。
网友可以同时上传一批图片 系统能够把所有图片分类并归为一组 网友上传图片后，网页要尽快返回该照片所在的组。A：假设你现在有一个机器，请写出你的数据结构与处理流程，设计的思路。
B：如果你有多台机器，如果缩短请求的时间？
A：我们可以把它分解为两个部分，一个是数据结构一个是上传流程。
(1). 对于数据结构来说，一个是对儿童信息进行包装，另一个是实现儿童信息的高效查找。对于儿童信息包装类来说，除了加入儿童的图片，姓名，生日等基本信息外，特别要注意重写equals与hashCode，这个equals就是题目所说的比较函数。对于查找的实现来说，首先我们建立一个HashSet，用于存储儿童信息。网友上传后，服务器通过对图像计算出特征Hash值，并查Hash表，如果HashCode相同，则返回所在的组；如果不相同，就加入hash表中。(2). 对于多图上传问题，使用生产者-消费者阻塞队列就可以实现尽快的依次返回照片所在的组。
B:
考虑将Hash计算后取余，分配给其他计算机进行存储与查询，我就想到这一个…..其它的嘛，大家帮我想想。
常规做法，Select反代，管道回调
TOP10的实现
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
这个题目与上个题目类似，我们选择使用HashMap，key为查询值，val为计数，内存使用为 3 * 256 M == 768M < 1G，然后我们不断的put就可以了，伪代码
HashMap<String, Integer> map = new HashMap<String,Integer>();
//如果内存再多点的话，我们就可以把初始化容量凑个1024的整数，减少扩容损失。
while(fileLog.hasNext()){
String queue = fileLog.next();
map.put(queue, map.get(queue) + 1);
}
接着使用堆排序遍历即可，堆的大小为10，复杂度为10xO(LogN)。
综上，O(10^7) +10 * O(Log(3×10^6));
使用WeakHashMap作为缓冲
在动态代理等耗时操作中，为了实现复用，使用了HashMap实现缓存，下面的一个例子是Picasso的Transformation操作
public final class PaletteTransformation implements Transformation {
private static final PaletteTransformation INSTANCE = new PaletteTransformation();
private static final Map<Bitmap, Palette> CACHE = new WeakHashMap<>();
public static PaletteTransformation instance() {
return INSTANCE;
}
public static Palette getPalette(Bitmap bitmap) {
return CACHE.get(bitmap);
}
private PaletteTransformation() {
}
@Override
public Bitmap transform(Bitmap source) {
Palette palette = Palette.generate(source);
CACHE.put(source, palette);
return source;
}
@Override
public String key() {
return "PaletteTransformation";
}
}
