HashMap底层实现原理(JDK1.7版本)

• HashMap存储结构

首先我们看到HashMap的这样一条源代码

    
    transient Node[] table;

  我们可以很明显的注意到table是一个数组类型，这难道说明，HashMap的底层是依靠数组进行实现的吗？不着急，我们跟进Node中看看。

static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

从Node相关代码中我们发现了节点Node还设置了指向下一个节点Node的指针。所以我们可以知道，HashMap是一个依靠数组+链表来存储数据的容器。两者具体是如何进行综合使用的呢？请看图

相信大家从图中可以看出那部分使用了数组，那部分使用了链表吧。其实HashMap中之所以可以存储键值对，就是因为通过散列算法将键进行运算，通过运算作为下标来确定该将Node存放在数组的何处，但尽管如此，仍然存在一种可能，就是不同的键值通过散列算法运算后得到的结果相同，即他们在数组的位置是同一个地方，这就是所谓的哈希冲突，而HashMap之所以不仅仅使用数组作为底层结构而还将数组作为底层结构的原因，当存在哈希冲突时，就通过链表将存在数组同一位置的键值对插入到前键值对的后面，从而解决哈希冲突。