在Java中，HashMap 是一个常用的数据结构，它实现了Map接口，允许我们通过键值对的形式存储和快速查找数据。HashMap的底层是基于哈希表（hash table）的实现，它的高效性和灵活性使其在各种编程场景中广受欢迎。本文将详细介绍HashMap的原理、使用方法、优缺点，并提供一些常见的面试题。

主体

1. HashMap的基本概念

JDK1.7的数据结构是 数组 + 链表

说⼀下JDK1.8的数据结构吧： JDK1.8的数据结构是 数组 + 链表 + 红⿊树 。

HashMap是一个散列表，它存储键值对（key-value pairs），每个键对应一个唯一的值。HashMap不保证顺序，并且允许null值作为键或值。

import java.util.HashMap;
 
public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);
 
        System.out.println(map.get("one"));  // 输出: 1
    }
}

2. HashMap的工作原理

HashMap使用哈希表来存储数据。键的哈希值通过hash()方法计算，然后通过哈希函数将哈希值映射到数组的索引位置上。通过链地址法（chaining）来解决哈希冲突，即在每个数组索引处存储一个链表（Java 8及之后版本采用红黑树以提高性能）。

public int hash(Object key) {

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

3. HashMap的常用操作

添加元素： 使用put()方法。

插入流程：

获取元素： 使用get()方法。

int value = map.get("two");

查找流程：

• 移除元素： 使用remove()方法。

map.remove("three");

遍历元素：

for (Map.Entry<String, Integer> entry : map.entrySet()) {

  System.out.println(entry.getKey() + ": " + entry.getValue());

}

4. HashMap的优缺点

优点：

快速查找： 平均时间复杂度为O(1)。

灵活： 可以存储不同类型的对象，允许null键和值。

缺点：

非线程安全： 多线程情况下需要手动同步。

不保证顺序： 插入顺序和遍历顺序可能不同。

5.jdk1.8对HashMap主要做了哪些优化呢？

1. 数据结构

变化：从数组 + 链表改为数组 + 链表或红黑树。

原因：当发生哈希冲突时，元素会被存储在链表中。如果链表过长，则转换为红黑树，将查找时间复杂度由 O(n) 降低至 O(logn)。

2. 链表插入方式

变化：从头插法改为尾插法。

说明：在 JDK 1.7 中，新元素被放置到链表头部；而在 JDK 1.8 中，遍历链表并将新元素放置到链表尾部。

原因：JDK 1.7 的头插法在扩容时可能导致链表反转，在多线程环境下可能会产生环状结构，而尾插法则避免了这一问题。

3. 扩容（rehash）机制

变化：采用更简单的判断逻辑来决定新位置。

说明：JDK 1.7 在扩容时需要重新计算每个元素的新哈希值以确定其在新数组中的位置；JDK 1.8 则通过更简化的逻辑直接确定新位置，通常是原索引或者原索引加上新增容量大小。

原因：这种改变提高了扩容操作的效率。

4. 扩容时机

变化：从先判断是否需要扩容再进行插入，变更为先执行插入操作，之后再判断是否需要扩容。

原因：这样可以减少不必要的扩容检查次数，尤其是在频繁插入但不经常达到扩容阈值的情况下。

5. 散列函数

变化：减少了散列函数的操作次数。

说明：JDK 1.7 的散列函数执行了四次位移和异或操作，而 JDK 1.8 只执行一次。

原因：尽管多次操作可能提供更好的分布性，但实际上边际效益不大，简化后的散列函数提高了计算速度且对于大多数应用场景来说足够有效。

总结

HashMap是Java中一个强大且高效的集合类，用于快速查找和存储键值对。理解其工作原理和常用操作对于提高编程效率和解决复杂问题非常有帮助。

常见面试题

HashMap的底层实现原理是什么？

如何解决HashMap中的哈希冲突？

HashMap和Hashtable的区别是什么？

在什么情况下HashMap会发生扩容？

为什么HashMap不是线程安全的？如何实现线程安全的HashMap？

————————————————

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/jgk666666/article/details/140160507