Java集合（Map篇）

一.Map

a.使用Map

        i.键值（key-value）映射表的数据结构，能高效通过key快速查找value（元素）。
        ii.Map是一个接口，最常用的实现类是HashMap。
        iii.重复放入k-v不会有问题，但是一个key只能关联一个value。Map中不存在重复的key，因为放入相同的key，只会把原有的key-value对应的value给替换掉。

        iv.实际上，V put(K key, V value)方法，如果放入的key已经存在，put()方法会返回被删除的旧value，否则，返回null。

        v.在一个Map中，虽然key不能重复，但是value可以重复。

b.遍历Map

        i.keySet()
                1.遍历key，可以使用for each循环遍历Map的keySet()方法返回的Set集合，它包含不重复的key的集合。

        ii.entrySet()
                1.同时遍历key和value，可以使用for each循环遍历Map对象的entrySet()集合，它包含每一对key-value映射。

c.HashMap中key的两大作用

        i.通过key相等的比较获取value，所以正确重写equals()方法。
        ii.通过key计算hashCode()确定value存储的索引位置，所以正确重写hashCode()方法。

d.总结

        i.Map是无序集合，遍历Map时，不可假设输出的key是有序的。
        ii.Map是一种映射表，可以根据key快速查找value。
        iii.最常用的一种Map实现时HashMap。

hashCode方法

a.HashMap之所以能根据key快速查找value，原因是它内部通过空间换时间的方法，用一个大数组存储所有的value，并根据key直接计算出value应该存储在哪个索引。

b.在Map内部，对key的比较是通过equals()实现的，所以存，取的key不一定是同一个对象，只要内容相同就可以。这点和List查找元素需要正确重写equals()是一样的，即正确使用Map必须保证：作为key的对象必须正确重写equals()方法。

c.通过key计算索引的方式就是调用key对象的hashCode()方法，它返回一个int整数。HashMap正是通过这个方法直接定位key对应的value的索引，继而直接返回value。

d.正确使用Map必须保证：
        i.作为key的对象必须正确重写equals()方法，相等的两个key实例调用equals()方法必须返回true；
        ii.作为key的对象必须正确重写hashCoed()方法：
                1.如果两个对象相等，则hashCode()必须相等。
                2.如果两个对象不相等，则hashCode()尽量不要相等。
                注意：如果两个对象不相等，hashCode()相同，会造成Map内部存储冲突（哈希冲突），影响存取效率。

e.正确实现hashCode()，必须在正确实现了equals的基础上。
        i.要正确使用HashMap，作为key的实例必须正确重写equals()和hashCode()方法；
        ii.使用Objects.hash()方法计算。
        iii.编写equals()和hashCode()遵循的原则：equals()用于比较的每个字段，都必须进行hashCode()计算；equals()没有用到的字段，绝不能放在hashCode()中计算。
        iv.对于放入HashMap的value对象，没有任何要求。
        v.hashCode()方法编写的越好，HashMap的工作效率就越高。

f.扩展
        i.HapMap初始化时默认数组大小是16，内部可自动扩容，扩容后重新确定hashCode()计算的索引位置，会影响效率。
        ii.初始化HashMap时可指定容量大小。
                1.Map<String, Integer> map = new HashMap<>(10000);
        iii.使用Map时，即使不同的两个key的hashCode()相同，只要key不相同，它们映射的value就互不干扰。
        iv.在HashMap内部，确实可能存在不同的key，映射到相同的hashCode()。
        v.把不同key具有相同hashCode()的情况称为哈希冲突。

使用EnumMap

a.key对象是enum类型，内部是以一个非常紧凑的数组存储value，并且根据enum类型的key直接定位到内部数组的索引，并不需要计算hashCode()，不但效率最高，还不浪费空间。
b.使用Enum集合时，总是用Map接口引用。

TreeMap

a.特点

        i.有一种Map，在内部会对Key排序，就是SortedMap，SortedMap是接口，实现类是TreeMap。
        ii.SortedMap保证遍历时以Key的顺序来进行排序，使用TreeMap时，放入的Key必须实现Comparable接口。String，Integer这些类已经实现了Comparable接口，可以直接作为Key使用。
        iii.对于放入TreeMap的Value对象，没有任何要求。

        iv.如果作为Key的class是自定义的类没有实现Comparable接口，那么，必须在创建TreeMap的同时指定一个自定义排序算法，否则运行报错，TreeMap内部根据比较结果对Key进行排序。

        v.自定义排序算法时，必须正确实现相等，小于，大于逻辑，缺一不可！通过排序比较相等的Key，定位对应的Value。

b.总结

i.不需要重写equals()和hashCode()，因为TreeMap不使用equals()和hashCode()。
ii.作为SortedMap的key必须实现Comparable接口，或者传入Comparator。
iii.使用TreeMap时，对key的比较需要正确实现相等，小于，大于逻辑。