认识达内从这里开始

认真做教育专心促就业

HashMap解析

发布：烟台达内
来源：互联网
时间：2017-10-14 17:03

    put方法步骤

    我们虽然都是用put(key,value)这个方法,但其内部主要是使用putVal()方法.

    介绍一下putVal()的5个参数:

    hash,hash值,就是通过这个值确定键值对放在数组哪个位置,公式是(数组长度-1)&hash.

    key、value,没啥说的.

    onlyIfAbsent,布尔值,如果是true,key值不存在的情况下才往里put,如果存在的话就不执行put操作,这样就不会修改原来的值了.

    evict,布尔值,如果是false,则代表这是一个创建的操作.

    说一下主要的步骤:

    1、如果table数组为空或长度为0,则执行初始化操作.

    2、根据hash值确定键值对要放的位置,如果这个位置上没有元素,则直接放进去.

    另外,看过hash()代码我们应该知道,如果key是null,返回的hash就是0,所以key为null的键值对肯定放在table[0]这个位置.

    再多说一下HashTable在put的代码里,先判断value,如果为null就抛出异常.然后在计算hash的时候直接用key的hashCode,可想而知,如果key为null是一定报异常的.

    ConcurrentHashMap在put的代码里,首先就判断KV,如果二者有一个为空就抛异常.

    所以HashTable、ConcurrentHashMap是不允许KV是null的.

    3、如果位置上有元素,则需要做详细的处理,这一段代码是HashMap的主代码.在JDK1.8中,如果链表的长度大于8,则将其转化为红黑树,这个回头写一篇讲讲,本文还是拿链表来说.

    3.1、先判断链表的第一个键值对,如果新旧两个键值对的hash相同,并且Key相同(两个key==,或者在key不为null的情况下,新旧键值对的key的equals()是true),则说明新旧键值对的Key是相同的,直接替换.为什么要做这样的判断操作,可以看《Java面试题 Part17 手写HashMap(二)》"对象做Key"这一节的说明.

    3.2、如果第一个不匹配,就往下遍历链表,执行与上一步一样的判断Key的步骤,如果相同,把这个Node提出来,跳出循环,把Value替换成新值;如果不同就往下遍历,直到最后一个,都没有的话,就链表尾端新建一个.

    3.3、最后如果size超过阈值,执行扩容操作.

    get方法步骤

    了解了put方法,基本上也就很容易理解get方法的步骤了.最重要的还是判断key,如果新旧两个键值对的hash相同,并且Key相同(两个key==,或者在key不为null的情况下,新旧键值对的key的equals()是true),则说明这就是我们要获取的键值对.

    步骤依然是先定位所在数组的位置,获取第一个链表元素进行key校验,不同的话往下遍历链表进行key校验,直到获取指定的元素.

    remove方法步骤

    remove是调用了removeNode()方法.步骤主要是两大块,第一步就是通过Key,先把要删除的元素找出来,这个跟get步骤基本一致,不再赘述.

    第二步是删除.这里有两个地方要说一下,对应Key的Node已经取出来了,删不删还是有两种选择的,一种是只要Key对上了,不管Value是什么,都删;还有一种是,不仅Key要对上,Value也要对上,才执行删除操作.

    烟台达内：因为是链表,所以删起来很简单方便.先获取链表第一个元素,如果与要删除的元素相同,则直接把数组table此索引下的元素改为链表的next元素即可.

    table[索引]=原Node.next;

    原链表:

原链表

如果要删除的元素是第一个A,则:

新链表

    Node的组成在第一篇里有描述.

    在第一步找要删除的Node代码中,有一个临时的Node,在代码里是p,这个是存放要删除Node的前一个Node,在下面就用得上了.

    如果第一个不是,则直接把p这个Node的next指向要删除Node的next.

    即p.next=node.next;

    原链表: