美文网首页
HashMap学习笔记

HashMap学习笔记

作者: camlboy | 来源:发表于2017-05-19 14:31 被阅读45次

    先上图,图片来自于此处

    152128351581.png
    搜索了一些资料硬是没搞明白为什么table数组中有的存了好几个数据,有的存了一个,table里面搞了一个链表,为什么有链表呢,是因为hash碰撞导致的,详细请阅读此处,
    public V put(K key, V value) {
            //当key为null,调用putForNullKey方法,保存null与table第一个位置中,这是HashMap允许为null的原因
            if (key == null)
                return putForNullKey(value);
            //计算key的hash值
            int hash = hash(key.hashCode());                  ------(1)
            //计算key hash 值在 table 数组中的位置
            int i = indexFor(hash, table.length);             ------(2)
            //从i出开始迭代 e,找到 key 保存的位置
            for (Entry<K, V> e = table[i]; e != null; e = e.next) {
                Object k;
                //判断该条链上是否有hash值相同的(key相同)
                //若存在相同,则直接覆盖value,返回旧value
                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++;
            //将key、value添加至i位置处
            addEntry(hash, key, value, i);
            return null;
        }
    

    根据这段put源码来理解一下,keynull,保存一个键为null的键值对,当然下回还可以再put一个键为null的值,HashMap会帮你覆盖的,HashMap利用键的hashcode处理putget操作大家都知道,key不为null我们计算keyhash值,然后根据hash值获取在table数组中的位置,根据数组下标获取到对应位置的Entry对象,我们在table中存储的hashMap的一个内部类Entry,其包含属性keyvaluehash值,next节点,这个好处很多,一是在发生hash碰撞时保持在table同一个位置保持链表结构,二是在get时非常方便获取value值。然后我们在第一次找到的Entry节点不为空是,然后根据key和节点中保存的相关信息进行多条件比对,如果命中,直接返回Entry对应的value,如果没有命中,继续根据节点的next属性寻找下一个Entry节点,根据key进行命中比对,若命中找到对应key的value进行覆盖,没有命中将该元素保存在链头(最先保存的元素放在链尾)。

    若根据table[i]找到的节点为空,则直接进行保存。

    void addEntry(int hash, K key, V value, int bucketIndex) {
            Entry<K, V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
            if (size++ >= threshold)
                resize(2 * table.length);
        }
    

    此处代码我们可以看到,我们始终会让新加入的Entry在保存在table中,替换之前已有的元素,最新元素指向上一个元素,这样就形成了一个指向链,当然前提是我们计算出来的bucktIndex处有元素存在,若不存在则直接保存,指向的也就是空了,后面如果此处刚好发生hash碰撞则会产生指向链。

    有序map主要是两大类,TreeMap和LinkedHashMap,
    TreeMap会对插入的元素进行自然排序,也可以自定义comparator自定义排序规则。
    LinkedHashMap遍历元素时会按照插入的顺序循环,linkedhashmap主要靠双向循环列表来实现顺序的,其内部数据结构和hashmap基本一致,数组中不同内存地址中的链表互相连接,从而保证我们在迭代的时候按照链表顺序取出数据

    相关文章

      网友评论

          本文标题:HashMap学习笔记

          本文链接:https://www.haomeiwen.com/subject/rvsyxxtx.html