热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HashMap的get方法的流程分析(源码)

流程首先根据hash方法获取到key的hash值然后通过hash&(length-1)的方式获取到key所对应的Node数组下标(length对应数组长度)首先判断此结点是否为空



流程


  1. 首先根据 hash 方法获取到 key 的 hash 值
  2. 然后通过 hash & (length - 1) 的方式获取到 key 所对应的Node数组下标 ( length对应数组长度 )
  3. 首先判断此结点是否为空,是否就是要找的值,是则返回空,否则进入第二个结点。
  4. 接着判断第二个结点是否为空,是则返回空,不是则判断此时数据结构是链表还是红黑树
  5. 链表结构进行顺序遍历查找操作,每次用 == 符号 和 equals( ) 方法来判断 key 是否相同,满足条件则直接返回该结点。链表遍历完都没有找到则返回空。
  6. 红黑树结构执行相应的 getTreeNode( ) 查找操作。


源码分析

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//Node数组不为空,数组长度大于0,数组对应下标的Node不为空if ((tab = table) != null && (n = tab.length) > 0 &&//也是通过 hash & (length - 1) 来替代 hash % length 的(first = tab[(n - 1) & hash]) != null) {//先和第一个结点比,hash值相等且key不为空,key的第一个结点的key的对象地址和值均相等//则返回第一个结点if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;//如果key和第一个结点不匹配,则看.next是否为空,不为null则继续,为空则返回nullif ((e = first.next) != null) {//如果此时是红黑树的结构,则进行处理getTreeNode()方法搜索keyif (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);//是链表结构的话就一个一个遍历,直到找到key对应的结点,//或者e的下一个结点为null退出循环do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}

remove,put,containsKey 都可以参照 get 的流程,面试的话是没有问题的。put 的话涉及到 - 扩容 和 - 红黑树的升级,remove 会涉及到 - 红黑树的退化,其他流程大体上是一样的。都是获取到 hash 值,根据 hash 值得到数组下标,进行遍历操作。


HashMap知识点总结(附源码分析链接)


推荐阅读
author-avatar
Melody-Zhu1988
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有