hashmap原理详解

哈希表的原理基于哈希函数，用于将键映射到特定的存储位置，以便快速访问数据。

基本原理：

1. 哈希函数：哈希表的核心是哈希函数，它接受一个键作为输入并生成一个固定大小的哈希码（或哈希值）。这个哈希码通常是一个整数，它可以用来确定存储位置。
2. 存储数组：哈希表内部通常包括一个固定大小的数组，通常是连续的内存空间。数组的大小通常会大于哈希表中的元素数量，以避免碰撞（后面会解释）。
3. 哈希冲突：由于哈希函数将不同的键映射到相同的位置，可能会发生哈希冲突。哈希表需要解决这些冲突，常见的方法包括链地址法（Chaining）和开放地址法（Open Addressing）。
   1. 链地址法：在数组的每个位置存储一个链表（或其他数据结构），具有相同哈希码的键被存储在同一位置的链表中。
   2. 开放地址法：在碰撞发生时，继续寻找下一个可用的位置。这可能涉及线性探测、二次探测等策略。
4. 存储和检索：存储时，哈希表使用哈希函数计算键的哈希码，然后找到相应的存储位置，将键-值对存储在那里。检索时，哈希表使用相同的哈希函数找到存储位置，并返回与键关联的值。
5. 性能：哈希表的性能通常非常出色，因为它允许常量时间复杂度的存储和检索操作，即 O(1)。这是因为哈希函数通常能够将键均匀地映射到数组的不同位置。
6. 调整大小：当哈希表的负载因子（已存储元素数量与数组大小之比）超过某个阈值时，通常需要调整数组的大小，以避免性能下降。这通常包括创建新的更大数组，重新哈希存储的元素，并将其放入新数组中。