简介

HashMap 是 Java 中常用的数据结构，它实现了 Map 接口，并提供快速查找、插入和删除操作。

底层数据结构

HashMap 的底层数据结构是数组和链表（或红黑树）的组合，被称为哈希表（HashTable）。数据以键值对的形式存储，每个键值对都封装在一个 Entry 对象中。 插入键值对时，首先根据键的哈希值计算数组中的位置（桶）。如果多个键的哈希值相同，则它们将形成链表（或红黑树）。

查找效率

哈希表的目的是提高数据查找效率。理想情况下，每个键都有一个唯一的哈希值，从而直接定位到桶，实现 O(1) 查找效率。

冲突处理

不同的键可能具有相同的哈希值，导致冲突。HashMap 使用链表和红黑树来解决冲突。 查找键时，HashMap 根据哈希值定位桶，然后在链表（或红黑树）中查找。由于哈希值计算很快，因此可以快速定位桶，提高查找效率。 当链表长度较长时，HashMap 将其转换为红黑树，以提高效率。当链表长度低于阈值时，红黑树将转换回链表以节省空间。

删除操作

删除键值对时，HashMap 根据哈希值找到桶，然后在链表（或红黑树）中查找并删除。删除时间复杂度取决于链表（或红黑树）长度，但平均为 O(1)。

线程安全性

需要注意的是，HashMap 不是线程安全的。在多线程环境中使用时，可能导致数据不一致。可使用 ConcurrentHashMap 来解决此问题。

应用

HashMap 在开发中广泛用于缓存系统、索引结构和分布式计算。

性能优化

HashMap 的性能可以通过调整负载因子和初始容量来优化。还需要正确实现键的 hashCode() 和 equals() 方法。

总结

HashMap 是一种高效的数据结构，它使用哈希表实现快速查找、插入和删除操作。它在多线程环境中是非线程安全的，可以使用 ConcurrentHashMap 来解决此问题。HashMap 在实际应用中广泛使用，但需要谨慎处理极端情况和键的正确实现。

---

2020-01-17：java中，HashMap底层数据结构是什么？

HashMap的数据结构为：数组+(链表或红黑树)

hashmap的数据结构

为什么采用这种结构来存储元素呢？

数组的特点：查询效率高，插入，删除效率低。

链表的特点：查询效率低，插入删除效率高。

在HashMap底层使用数组加（链表或红黑树）的结构完美的解决了数组和链表的问题，使得查询和插入，删除的效率都很高~

java 为什么使用hashmap

首先当我们需要存储数据的时候，动态数组虽然能够自动扩容，但是必须在初始时刻指定初始容量。而对于那些在编译时无法确定具体的数量即动态增长的数据，就需要用到Java集合类了。对于ArrayList 和 LinkedList，还有 Vector它们都有一些缺点，要么插入删除速度慢、要么就是遍历速度慢。那么有没有一种插入、删除、遍历都比较不错的集合类呢？于是 HashMap 就出现了。HashMap 是一个散列表，它存储的是一组键值对(key-value)的集合，并实现快速的查找。

（1）为了实现快速查找，HashMap 选择了数组而不是链表。以利用数组的索引实现 O(1) 复杂度的查找效率。

（2）为了利用索引查找，HashMap 引入 Hash 算法, 将 key 映射成数组下标: key -> Index。

（3）引入 Hash 算法又导致了 Hash 冲突。为了解决 Hash 冲突，HashMap 采用链地址法，在冲突位置转为使用链表存储。

（4）链表存储过多的节点又导致了在链表上节点的查找性能的恶化。为了优化查找性能，HashMap 在链表长度超过 8 之后转而将链表转变成红黑树，以将 O(n) 复杂度的查找效率提升至 O(log n)。

【综上】

HashMap 存在的意义就是实现一种快速的查找并且插入、删除性能都不错的一种 K/V（key/value）数据结构。

附上一位博主的高见：网页链接