什么是散列函数？HashMap 的实现原理是什么？

散列函数（Hash Function）是一种将输入数据（通常是任意大小的数据）映射为固定大小散列值（哈希值）的函数。散列函数的目标是将数据均匀地映射到哈希值域，以便在哈希表等数据结构中高效地查找、插入和删除数据。好的散列函数应该尽可能避免冲突（即不同的输入映射到相同的哈希值），并具有良好的性能特性，例如高效的计算速度和较低的冲突率。

Java中的HashMap是一种基于散列表（Hash Table）实现的数据结构，用于存储键-值对（key-value pairs）。它使用了散列函数将键映射到散列值，并将键-值对存储在对应的散列值位置上，从而实现了高效的数据查找和操作。

HashMap的实现原理如下：

1. 散列函数计算： 当用户向HashMap插入一个键-值对时，首先会通过散列函数计算键的散列值。Java中的Object类提供了hashCode()方法来获取对象的哈希码，但是可以根据实际需要重写该方法以提供更适合的散列值计算方式。

2. 散列冲突处理： 由于不同的键可能映射到相同的散列值，这种情况称为散列冲突。HashMap使用开放地址法（Open Addressing）或链地址法（Chaining）来处理散列冲突。

   • 开放地址法：当发生冲突时，继续探测散列表中下一个可用的位置，直到找到一个空槽来存储数据。这种方法需要保证在哈希表中有足够的空间来避免聚集现象。
   • 链地址法：在每个散列槽中维护一个链表或红黑树等数据结构，将映射到相同散列值的键-值对存储在同一个链表或树中。这样，当发生冲突时，新的键-值对可以简单地添加到链表的末尾，不需要移动其他元素。

3. 负载因子： HashMap会维护一个负载因子（Load Factor），它表示当前散列表中的元素数量与散列表大小的比率。当负载因子超过一定阈值时，HashMap会自动进行扩容操作，以保证散列表的性能。扩容操作会重新计算散列值，重新分配存储空间，并将所有键-值对重新插入新的散列表中。

总结起来，HashMap通过散列函数计算键的散列值，并通过散列冲突处理方式（开放地址法或链地址法）解决不同键映射到相同散列值的问题。当负载因子超过一定阈值时，自动扩容来维持较低的冲突率和高效的性能。