Java集合--从本质出发理解HashMap
文章内容较长，放宽心，带着疑问慢慢读，总能找到你想要的答案。如何快速定位数据存储在内存地址的位置？
先提出一个问题：如何快速定位数据存储在内存地址的位置？
聪明的你会想到使用数组：根据首地址+单个节点存储大小 x 数组下标，便可快速计算出目标的内存地址，从而做到时间复杂度为O(1)的查找速度。但这一切都建立在物理存储空间连续的情况。
如果物理存储空间不连续？如何实现y=f(x)，根据x参数，通过f(x)函数，快速计算出y 目标地址呢？
在HashMap中，x参数就是key，这一切的计算都是围绕key进行展开的，这些计算可以简述为以下三行代码
int hashCode = key.hashCode();
int hash = hashCode ^ (hashCode >>> 16);
int index = (arrLen - 1) & hasharrLen变量为数组长度，你可以把这三行代码理解为f(x)，而参数x=key，计算结果为y=index，计算结果的index便是映射数组的下标。这个映射定位函数是多对一的函数，不同的key会得到相同的数组下标值。
在 HashMap 中，f(key) = hash(key) & (arrLen - 1) 就是一个哈希映射数组索引函数，不同的 key 可能映射到相同的数组索引，被称为映射冲突或桶冲突，但是常常被称为哈希冲突，这称呼经常让人摸不着头脑，因为它的表述并不准确。
哈希冲突和映射冲突的关系
[*]哈希函数hash(key)内部产生相同值 → 叫「哈希冲突」
[*]不同哈希值映射到同一个桶 → 叫「索引冲突」或「映射冲突」
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]