HashMap 详解 - Gukie/interview GitHub Wiki

开始之前，必须解释下以下算数的结果：

int result = a & b;

result是不会大于 (a与b中的最小值)的。因为：只有a或者b 表示为二进制时，全部都是1，才会等于a或者b

  • 首先，底层实现是一个 Node的数组
  • Node是一个对象,类似链表的结构，里面有 hash，key，和 next

PUT

map.put(key,value) Node[] nodeArr = .... int nodeLen = nodeArr.length

  • 获取数组Node的下标，算法为：key.hashcode & (nodeLen)
  • 获取数组中的某个元素之后，比如是 nodeItem
  • 如果nodeItem为null，创建一个node，然后直接插入
  • 如果nodeItem不为null，再用 key 跟 nodeItem的key 进行比较，这时候就会用到 key的 equals方法
  • 如果key 跟 nodeItem的key 相等，直接就替换；否则遍历 nodeItem的next，将新的node插入到链表的最末尾

从上可知， put的时候，需要使用到 Key的 hashcode() 跟 equals() 两个方法 也可以知道， hashcode相等的时候，equals可能不一定会相等 so： 重写hashcode 或 equals 中的任意一个方法的时候，最好一起重写，并且尽量保持 hashcode能跟 equals具有一定的对等性： 即 hashcode不一致，equals就不相等;反之亦然

afterNodeInsertion

Put的时候，默认会调用afterNodeInsertion()， 该方法可以将Map中存在时间最久的元素删除掉 但默认是不会的，如果将该方法用起来，需要重写 removeEldestEntry 方法(该方法默认返回false)

void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) { //从head开始，head肯定是存在时间最长的元素
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

GET

map.get(key)
Node[] nodeArr = ....
int nodeLen = nodeArr.length
  • 通过 hashcode 计算数组下表： key.hashcode & (nodeLen)
  • 找到下表之后，找到对应的元素，nodeItem，如果是null，返回null
  • 否则, 比较： nodeItem.hashcode==key.hashcode && (用key的equals比较key是否跟nodeItem的key相等)
  • 相等的话，返回； 否则找NodeItem的next，然后再重复
  • 直到找到，或者直到遍历完整个链表都没有找到元素

resize()

当PUT的时候，会检查当前 size 是否大于 threshold (该值=capacity * load_factor, 一般的，load_factor为0.75) 如果大于的话，就resize

resize做以下几件事：

  • capacity会在老的基础上扩充一倍
  • threshold也会在 oldThreshold的基础上扩充一倍
  • 将数组中的元素，重新计算数组下表，并映射到新的下标上去

重新映射的时候，做以下事情：

for(int i = 0;i<oldCapacity;i++){
 Node nodeItem = Nodes[i];
}
  • 如果nodeItem 的next为null，则下标为= nodeItem.hashcode & (newcapacity-1)
  • 如果nodeItem的next不为null，会将 nodeItem移到 Nodes[i+oldCapacity] 或者Nodes[i] 上，Source code如下：
Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            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;
                        }

关于resize，有几个问题不理解：

  • 为什么不是直接将 nodeItem移过去？ 而是要计算一下
  • 如果[i+oldCapacity] 跟别的元素的 [nodeItem.hashcode & (newcapacity-1)] 相等了，这不就冲突了吗？就会丢失数据的
⚠️ **GitHub.com Fallback** ⚠️