HashMap学习笔记

先上图，图片来自于此处

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源码来理解一下，key为null，保存一个键为null的键值对，当然下回还可以再put一个键为null的值，HashMap会帮你覆盖的，HashMap利用键的hashcode处理put，get操作大家都知道，key不为null我们计算key的hash值，然后根据hash值获取在table数组中的位置，根据数组下标获取到对应位置的Entry对象，我们在table中存储的hashMap的一个内部类Entry，其包含属性key，value，hash值，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基本一致，数组中不同内存地址中的链表互相连接，从而保证我们在迭代的时候按照链表顺序取出数据