《Java零基础教学》是一套深入浅出的 Java 编程入门教程。全套教程从Java基础语法开始，适合初学者快速入门，同时也从实例的角度进行了深入浅出的讲解，让初学者能够更好地理解Java编程思想和应用。

本教程内容包括数据类型与运算、流程控制、数组、函数、面向对象基础、字符串、集合、异常处理、IO 流及多线程等 Java 编程基础知识，并提供丰富的实例和练习，帮助读者巩固所学知识。本教程不仅适合初学者学习，也适合已经掌握一定 Java 基础的读者进行查漏补缺。

前言

HashMap是Java中非常常用的数据结构之一，它能够高效地进行键值对的操作，因此在实际开发中非常常见。本文将探究HashMap的底层实现原理，包括HashMap的数据结构、哈希算法、哈希冲突解决方法等内容。

摘要

本文将介绍HashMap的底层实现原理，包括HashMap的数据结构、哈希算法、哈希冲突解决方法等内容。对于想要深入了解HashMap的Java开发者，本文将提供一些有用的知识和思路。作者将通过源码解析方式，深入探究HashMap的底层实现原理。

HashMap

数据结构

HashMap是基于哈希表实现的，它是一个数组和链表的组合体。具体来说，它由一个Node类型的数组table组成，每个Node节点包含一个key-value键值对和一个指向下一个Node节点的指针，形成了链表结构。当链表长度超出一定阈值时，链表会被转换成红黑树结构，以提高查询效率。

下面是部分源码：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

static final int MAXIMUM_CAPACITY = 1 << 30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

static final int MIN_TREEIFY_CAPACITY = 64;

transient Node<K,V>[] table;

源码展示如下：

HashMap 包路径位于util下，目录：java.util.HashMap

解释一下：如上HashMap源码定义了一些常量和一个名为"table"的transient类型的数组变量。该数组中的元素是Node类型，用于存储HashMap中的元素。其中常量的含义如下：

• DEFAULT_INITIAL_CAPACITY: HashMap的默认初始容量，即创建HashMap时初始数组大小为16。
• MAXIMUM_CAPACITY: HashMap的最大容量，即数组长度最大为2的30次方。
• DEFAULT_LOAD_FACTOR: HashMap的默认负载因子，当HashMap中元素数量超过容量*负载因子时，HashMap会进行扩容操作。
• TREEIFY_THRESHOLD: 当链表中节点数量超过该阈值时，HashMap会将链表转化为红黑树，提高查询效率。
• UNTREEIFY_THRESHOLD: 当红黑树中节点数量小于该阈值时，HashMap会将红黑树转化为链表，节省空间。
• MIN_TREEIFY_CAPACITY: 当HashMap容量小于该值时，不进行树化操作（即使链表长度超过TREEIFY_THRESHOLD），因为树化后会浪费空间。

哈希算法

在HashMap中，哈希算法的核心就是要确定key-value键值对在Node数组(table)中的位置。为了达到这个目的，HashMap使用了Java中的Object.hashCode()方法。该方法返回的是一个int类型的哈希码。HashMap会对该哈希码进行一些运算并且对数组长度取模，以得到该键值对在数组中的位置。具体来说，HashMap使用了以下式子计算哈希码：

    final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

可以看到，该式子首先调用了key的hashCode()方法获得哈希码h，然后对h进行运算，最终得到一个int类型的哈希码返回。

如何解决哈希冲突？

在HashMap中，哈希冲突是指两个不同的key所计算得到的哈希码相同的情况。为了解决这个问题，HashMap使用了链表和红黑树两种数据结构。

当两个key计算得到的哈希码相同时，HashMap会在Node数组对应的位置上形成一个链表。新插入的节点会被插入链表的头部。在使用get方法时，HashMap首先根据key的哈希码找到对应的链表，然后顺序遍历链表中的所有节点查找相应的value。

当链表长度超过一定阈值时，链表会被转换成红黑树结构。红黑树是一种自平衡的二叉查找树，它能够快速定位相应的键值对，查找时间复杂度为log N。在使用get方法时，如果某个节点的链表长度超过阈值，那么该节点的链表将会被转换为红黑树。当红黑树节点数少于一定数量时，红黑树会被转换回链表结构。

下面是部分源码：

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}


final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

解读一下：这段代码实现了Map接口的get方法，获取指定key对应的value值。首先通过计算hash值和key来获取对应的Node节点，如果该节点的key和查找的key相等，则返回该节点的value值；否则遍历该节点的下一个节点，直到找到对应的节点或者遍历完所有节点都没有找到，最后返回null表示该Map中不存在该key的映射。如果查找到的节点是红黑树的节点，则通过红黑树的查找方法获取该节点。

HashMap 的实现

接下来，我们将实现自己的 HashMap 类，并提供测试用例来验证实现是否正确。

HashMap 类

我们的 HashMap 类将实现以下功能：

• 添加元素：void put(K key, V value)
• 获取元素：V get(K key)
• 删除元素：V remove(K key)
• 获取元素个数：int size()

public class MyHashMap<K, V> {
    private Entry<K, V>[] table;
    private int size;

    public MyHashMap() {
        this.table = new Entry[16];
    }

    public void put(K key, V value) {
        int index = getIndex(key);
        Entry<K, V> entry = table[index];

        while (entry != null) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
            entry = entry.next;
        }

        Entry<K, V> newEntry = new Entry<>(key, value);
        newEntry.next = table[index];
        table[index] = newEntry;
        size++;
    }

    public V get(K key) {
        int index = getIndex(key);
        Entry<K, V> entry = table[index];

        while (entry != null) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
            entry = entry.next;
        }

        return null;
    }

    public V remove(K key) {
        int index = getIndex(key);
        Entry<K, V> entry = table[index];
        Entry<K, V> previous = null;

        while (entry != null) {
            if (entry.key.equals(key)) {
                if (previous == null) {
                    table[index] = entry.next;
                } else {
                    previous.next = entry.next;
                }
                size--;
                return entry.value;
            }
            previous = entry;
            entry = entry.next;
        }

        return null;
    }

    public int size() {
        return size;
    }

    private int getIndex(K key) {
        if (key == null) {
            return 0;
        }
        int hash = key.hashCode();
        return (hash ^ (hash >>> 16)) & (table.length - 1);
    }

    static class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> next;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }
}

测试用例

如下是HashMap常用的一些方法测试用例，以便辅助大家更好的学习。示例代码如下：

测试put和get

    //测试put和get
    @Test
    public void testPutAndGet() {
        Map hashMap = new HashMap();

        hashMap.put(1, "a");
        hashMap.put(2, "b");
        hashMap.put(3, "c");

        Assertions.assertEquals(3, hashMap.size());
        Assertions.assertEquals("a", hashMap.get(1));
        Assertions.assertEquals("b", hashMap.get(2));
        Assertions.assertEquals("c", hashMap.get(3));
    }

执行情况如下：

测试size方法

    @Test
    public void testSize() {
        Map hashMap = new HashMap();

        hashMap.put(1, "a");
        hashMap.put(2, "b");
        hashMap.put(3, "c");

        Assertions.assertEquals(3, hashMap.size());
    }

执行情况如下：

测试remove方法

    @Test
    public void testRemove() {
        Map hashMap = new HashMap();

        hashMap.put(1, "a");
        hashMap.put(2, "b");
        hashMap.put(3, "c");

        Assertions.assertEquals("b", hashMap.remove(2));
        Assertions.assertEquals(2, hashMap.size());
        Assertions.assertEquals(null, hashMap.get(2));
    }

执行情况如下：

全文小结

综上所述，HashMap是一种基于哈希表的数据结构，它能够快速地存储、检索和删除键值对。HashMap的底层实现原理涉及哈希函数、数组、链表等多个方面，需要我们在实际应用中灵活运用。

最后

大家如果觉得看了本文有帮助的话，麻烦给个三连（点赞、分享、转发）支持一下哈。