DEV Community
·
HashMap简要介绍
💡
原文约400字/词，阅读约需2分钟。
📝
内容提要
HashMap是一种存储键值对的数据结构，通过哈希函数将输入映射为数组索引。负载因子表示数组的填充程度，通常在70%或80%时会扩展数组以减少碰撞。插入时可采用开放寻址或链式存储，链式存储效率更高。
🎯
关键要点
- HashMap是一种存储键值对的数据结构。
- 哈希函数将输入映射为数组索引，返回值称为哈希值。
- 负载因子表示数组的填充程度，通常在70%或80%时会扩展数组。
- 当哈希函数产生的哈希值已存在时，会发生碰撞。
- 插入时可采用开放寻址或链式存储，链式存储效率更高。
- 开放寻址会寻找下一个可用位置，插入复杂度为O(n)。
- 链式存储使用结构如链表或平衡树，插入复杂度为O(1)。
❓
延伸问答
什么是HashMap？
HashMap是一种存储键值对的数据结构。
哈希函数的作用是什么？
哈希函数将输入映射为数组索引，返回值称为哈希值。
负载因子在HashMap中有什么意义？
负载因子表示数组的填充程度，通常在70%或80%时会扩展数组以减少碰撞。
HashMap中如何处理碰撞？
碰撞发生时，可以采用开放寻址或链式存储，链式存储效率更高。
开放寻址和链式存储的插入复杂度分别是多少？
开放寻址的插入复杂度为O(n)，链式存储的插入复杂度为O(1)。
HashMap何时会扩展数组？
当负载因子达到70%或80%时，HashMap会扩展数组以减少碰撞的概率。
➡️
