资深软件开发工程师，业余马拉松选手。
我们知道Map是一种键-值（key-value）映射表，可以通过key快速查找对应的value。
以为例，观察下面的代码：
之所以能根据直接拿到，原因是它内部通过空间换时间的方法，用一个大数组存储所有，并根据key直接计算出应该存储在哪个索引：
如果的值为，计算得到的索引总是，因此返回为，如果的值为，计算得到的索引总是，因此返回为，这样，就不必遍历整个数组，即可直接读取对应的。
当我们使用存取的时候，就会引出一个问题：
我们放入的是字符串，但是，当我们获取的时，传入的变量不一定就是放入的那个对象。
换句话讲，两个应该是内容相同，但不一定是同一个对象。测试代码如下：
因为在的内部，对做比较是通过实现的，这一点和查找元素需要正确覆写是一样的，即正确使用必须保证：作为的对象必须正确覆写方法。
我们经常使用作为，因为已经正确覆写了方法。但如果我们放入的是一个自己写的类，就必须保证正确覆写了方法。
我们再思考一下为什么能通过直接计算出存储的索引。相同的对象（使用判断时返回）必须要计算出相同的索引，否则，相同的每次取出的就不一定对。
通过计算索引的方式就是调用对象的方法，它返回一个整数。正是通过这个方法直接定位对应的的索引，继而直接返回。
因此，正确使用必须保证：
- 作为的对象必须正确覆写方法，相等的两个实例调用必须返回；
- 作为的对象还必须正确覆写方法，且方法要严格遵循以下规范：
- 如果两个对象相等，则两个对象的必须相等；
- 如果两个对象不相等，则两个对象的尽量不要相等。
即对应两个实例和：
- 如果和相等，那么一定为，则必须等于；
- 如果和不相等，那么一定为，则和尽量不要相等。
上述第一条规范是正确性，必须保证实现，否则不能正常工作。
而第二条如果尽量满足，则可以保证查询效率，因为不同的对象，如果返回相同的，会造成内部存储冲突，使存取的效率下降。
正确编写的方法我们已经在编写equals方法一节中讲过了，以类为例：
把需要比较的字段找出来：
- firstName
- lastName
- age
然后，引用类型使用比较，基本类型使用比较。
在正确实现的基础上，我们还需要正确实现，即上述3个字段分别相同的实例，返回的必须相同：
注意到类已经正确实现了方法，我们在计算的时，反复使用，这样做的目的是为了尽量把不同的实例的均匀分布到整个范围。
和实现方法遇到的问题类似，如果或为，上述代码工作起来就会抛。为了解决这个问题，我们在计算的时候，经常借助来计算：
所以，编写和遵循的原则是：
用到的用于比较的每一个字段，都必须在中用于计算；中没有使用到的字段，绝不可放在中计算。
另外注意，对于放入的对象，没有任何要求。
既然内部使用了数组，通过计算的直接定位所在的索引，那么第一个问题来了：返回的范围高达±21亿，先不考虑负数，内部使用的数组得有多大？
实际上初始化时默认的数组大小只有16，任何，无论它的有多大，都可以简单地通过：
把索引确定在0 ~ 15，即永远不会超出数组范围，上述算法只是一种最简单的实现。
第二个问题：如果添加超过16个到，数组不够用了怎么办？
添加超过一定数量的时，会在内部自动扩容，每次扩容一倍，即长度为16的数组扩展为长度32，相应地，需要重新确定计算的索引位置。例如，对长度为32的数组计算对应的索引，计算方式要改为：
由于扩容会导致重新分布已有的，所以，频繁扩容对的性能影响很大。如果我们确定要使用一个容量为个的，更好的方式是创建时就指定容量：
虽然指定容量是，但内部的数组长度总是2n，因此，实际数组长度被初始化为比大的（214）。
最后一个问题：如果不同的两个，例如和，它们的恰好是相同的（这种情况是完全可能的，因为不相等的两个实例，只要求尽量不相等），那么，当我们放入：
时，由于计算出的数组索引相同，后面放入的会不会把覆盖了？
当然不会！使用的时候，只要不相同，它们映射的就互不干扰。但是，在内部，确实可能存在不同的，映射到相同的，即相同的数组索引上，肿么办？
我们就假设和这两个最终计算出的索引都是5，那么，在的数组中，实际存储的不是一个实例，而是一个，它包含两个，一个是的映射，一个是的映射：
在查找的时候，例如：
内部通过找到的实际上是，它还需要遍历这个，并找到一个，它的字段是，才能返回对应的实例。
我们把不同的具有相同的的情况称之为哈希冲突。在冲突的时候，一种最简单的解决办法是用存储相同的。显然，如果冲突的概率越大，这个就越长，的方法效率就越低，这就是为什么要尽量满足条件二：
方法编写得越好，工作的效率就越高。
要正确使用，作为的类必须正确覆写和方法；
一个类如果覆写了，就必须覆写，并且覆写规则是：
- 如果返回，则返回值必须相等；
- 如果返回，则返回值尽量不要相等。
实现方法可以通过辅助方法实现。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/3286.html