type
status
date
slug
summary
tags
category
icon
password
Property
List是一种顺序列表，如果有一个存储学生Student实例的List，要在List中根据name查找某个指定的Student的分数，应该怎么办？最简单的方法是遍历
List并判断name是否相等，然后返回指定元素：这种需求其实非常常见，即通过一个键去查询对应的值。使用
List来实现存在效率非常低的问题，因为平均需要扫描一半的元素才能确定，而Map这种键值（key-value）映射表的数据结构，作用就是能高效通过key快速查找value（元素）。用
Map来实现根据name查询某个Student的代码如下：通过上述代码可知：
Map<K, V>是一种键-值映射表，当我们调用put(K key, V value)方法时，就把key和value做了映射并放入Map。当我们调用V get(K key)时，就可以通过key获取到对应的value。如果key不存在，则返回null。和List类似，Map也是一个接口，最常用的实现类是HashMap。如果只是想查询某个
key是否存在，可以调用boolean containsKey(K key)方法。如果我们在存储
Map映射关系的时候，对同一个key调用两次put()方法，分别放入不同的value，会有什么问题呢？例如：重复放入
key-value并不会有任何问题，但是一个key只能关联一个value。在上面的代码中，一开始我们把key对象"apple"映射到Integer对象123，然后再次调用put()方法把"apple"映射到789，这时，原来关联的value对象123就被“冲掉”了。实际上，put()方法的签名是V put(K key, V value)，如果放入的key已经存在，put()方法会返回被删除的旧的value，否则，返回null。始终牢记：Map中不存在重复的key，因为放入相同的key，只会把原有的key-value对应的value给替换掉。
此外，在一个
Map中，虽然key不能重复，但value是可以重复的：遍历Map
对
Map来说，要遍历key可以使用for each循环遍历Map实例的keySet()方法返回的Set集合，它包含不重复的key的集合：同时遍历
key和value可以使用for each循环遍历Map对象的entrySet()集合，它包含每一个key-value映射：Map和List不同的是，Map存储的是key-value的映射关系，并且，它不保证顺序。在遍历的时候，遍历的顺序既不一定是put()时放入的key的顺序，也不一定是key的排序顺序。使用Map时，任何依赖顺序的逻辑都是不可靠的。以HashMap为例，假设我们放入"A"，"B"，"C"这3个key，遍历的时候，每个key会保证被遍历一次且仅遍历一次，但顺序完全没有保证，甚至对于不同的JDK版本，相同的代码遍历的输出顺序都是不同的！遍历Map时，不可假设输出的key是有序的！
equals和hashCode
Map是一种键-值（key-value）映射表，可以通过key快速查找对应的value。
以HashMap为例，观察下面的代码：
HashMap之所以能根据key直接拿到value，原因是它内部通过空间换时间的方法，用一个大数组存储所有value，并根据key直接计算出value应该存储在哪个索引：
如果
key的值为"a"，计算得到的索引总是1，因此返回value为Person("Xiao Ming")，如果key的值为"b"，计算得到的索引总是5，因此返回value为Person("Xiao Hong")，这样，就不必遍历整个数组，即可直接读取key对应的value。当使用
key存取value的时候，就会引出一个问题：放入
Map的key是字符串"a"，但是，当获取Map的value时，传入的变量不一定就是放入的那个key对象。换句话讲，两个
key应该是内容相同，但不一定是同一个对象。测试代码如下：因为在
Map的内部，对key做比较是通过equals()实现的，这一点和List查找元素需要正确覆写equals()是一样的，即正确使用Map必须保证：作为key的对象必须正确覆写equals()方法。我们经常使用
String作为key，因为String已经正确覆写了equals()方法。但如果我们放入的key是一个自己写的类，就必须保证正确覆写了equals()方法。我们再思考一下
HashMap为什么能通过key直接计算出value存储的索引。相同的key对象（使用equals()判断时返回true）必须要计算出相同的索引，否则，相同的key每次取出的value就不一定对。通过
key计算索引的方式就是调用key对象的hashCode()方法，它返回一个int整数。HashMap正是通过这个方法直接定位key对应的value的索引，继而直接返回value。因此，正确使用
Map必须保证：- 作为
key的对象必须正确覆写equals()方法，相等的两个key实例调用equals()必须返回true；
- 作为
key的对象还必须正确覆写hashCode()方法，且hashCode()方法要严格遵循以下规范：
- 如果两个对象相等，则两个对象的
hashCode()必须相等；
- 如果两个对象不相等，则两个对象的
hashCode()尽量不要相等。
即对应两个实例
a和b：- 如果
a和b相等，那么a.equals(b)一定为true，则a.hashCode()必须等于b.hashCode()；
- 如果
a和b不相等，那么a.equals(b)一定为false，则a.hashCode()和b.hashCode()尽量不要相等。
上述第一条规范是正确性，必须保证实现，否则
HashMap不能正常工作。而第二条如果尽量满足，则可以保证查询效率，因为不同的对象，如果返回相同的
hashCode()，会造成Map内部存储冲突，使存取的效率下降。以
Person类为例：把需要比较的字段找出来：
- firstName
- lastName
- age
然后，引用类型使用
Objects.equals()比较，基本类型使用==比较。在正确实现
equals()的基础上，我们还需要正确实现hashCode()，即上述3个字段分别相同的实例，hashCode()返回的int必须相同：注意到
String类已经正确实现了hashCode()方法，我们在计算Person的hashCode()时，反复使用31*h，这样做的目的是为了尽量把不同的Person实例的hashCode()均匀分布到整个int范围。和实现
equals()方法遇到的问题类似，如果firstName或lastName为null，上述代码工作起来就会抛NullPointerException。为了解决这个问题，我们在计算hashCode()的时候，经常借助Objects.hash()来计算：所以，编写
equals()和hashCode()遵循的原则是：equals()用到的用于比较的每一个字段，都必须在hashCode()中用于计算；equals()中没有使用到的字段，绝不可放在hashCode()中计算。另外注意，对于放入
HashMap的value对象，没有任何要求。既然
HashMap内部使用了数组，通过计算key的hashCode()直接定位value所在的索引，那么第一个问题来了：hashCode()返回的int范围高达±21亿，先不考虑负数，HashMap内部使用的数组得有多大？实际上
HashMap初始化时默认的数组大小只有16，任何key，无论它的hashCode()有多大，都可以简单地通过：把索引确定在0～15，即永远不会超出数组范围，上述算法只是一种最简单的实现。
第二个问题：如果添加超过16个
key-value到HashMap，数组不够用了怎么办？添加超过一定数量的
key-value时，HashMap会在内部自动扩容，每次扩容一倍，即长度为16的数组扩展为长度32，相应地，需要重新确定hashCode()计算的索引位置。例如，对长度为32的数组计算hashCode()对应的索引，计算方式要改为：由于扩容会导致重新分布已有的
key-value，所以，频繁扩容对HashMap的性能影响很大。如果我们确定要使用一个容量为10000个key-value的HashMap，更好的方式是创建HashMap时就指定容量：虽然指定容量是
10000，但HashMap内部的数组长度总是2n，因此，实际数组长度被初始化为比10000大的16384（214）。最后一个问题：如果不同的两个
key，例如"a"和"b"，它们的hashCode()恰好是相同的（这种情况是完全可能的，因为不相等的两个实例，只要求hashCode()尽量不相等），那么，当我们放入：时，由于计算出的数组索引相同，后面放入的
"Xiao Hong"会不会把"Xiao Ming"覆盖了？当然不会！使用
Map的时候，只要key不相同，它们映射的value就互不干扰。但是，在HashMap内部，确实可能存在不同的key，映射到相同的hashCode()，即相同的数组索引上，肿么办？我们就假设
"a"和"b"这两个key最终计算出的索引都是5，那么，在HashMap的数组中，实际存储的不是一个Person实例，而是一个List，它包含两个Entry，一个是"a"的映射，一个是"b"的映射：
在查找的时候，例如：
HashMap内部通过
"a"找到的实际上是List<Entry<String, Person>>，它还需要遍历这个List，并找到一个Entry，它的key字段是"a"，才能返回对应的Person实例。我们把不同的
key具有相同的hashCode()的情况称之为哈希冲突。在冲突的时候，一种最简单的解决办法是用List存储hashCode()相同的key-value。显然，如果冲突的概率越大，这个List就越长，Map的get()方法效率就越低，这就是为什么要尽量满足条件二：如果两个对象不相等，则两个对象的hashCode()尽量不要相等。
hashCode()方法编写得越好，HashMap工作的效率就越高。