一.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的比较需要正确实现相等,小于,大于逻辑。