Map接口的使用

Map知识点

Map简介
将键映射到值的对象。一个映射不能包含重复的键;每个键最多只能映射到一个值。此接口取代 Dictionary 类,后者完全是一个抽象类,而不是一个接口。
Map 接口提供三种collection 视图,允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。映射顺序 定义为迭代器在映射的 collection 视图上返回其元素的顺序。某些映射实现可明确保证其顺序,如 TreeMap 类;另一些映射实现则不保证顺序,如 HashMap 类。
将键值对放到Map里面的工作是由Map.Entry这个接口进行的,它是一个静态接口,在这个接口里面只有五个方法,分别是

boolean equals(Object o) 
     比较指定对象与此项的相等性。 
 K getKey() 
     返回与此项对应的键。 
 V getValue() 
     返回与此项对应的值。 
 int hashCode() 
     返回此映射项的哈希码值。 
V setValue(V value) 
     用指定的值替换与此项对应的值(可选操作)。 

每次增加键值对的时候,都会调用这五个方法。由于不能有相同的键值,所有要判断键值是否相等,同时,一个键只能映射一个值。

Map的实现之HashMap

HashMap也是我们使用非常多的Collection,它是基于哈希表的 Map 接口的实现,以key-value的形式存在。在HashMap中,key-value总是会当做一个整体来处理,系统会根据hash算法来来计算key-value的存储位置,我们总是可以通过key快速地存、取value。

  1. 我们知道在Java中最常用的两种结构是数组和模拟指针(引用),几乎所有的数据结构都可以利用这两种来组合实现,HashMap也是如此。实际上HashMap是一个“链表散列”,它的工作原理就是这样:每次初始化一个HashMap的时候,就会初始化一个table数组,这个数组的元素都是entry节点,每个数组都是一个链表的索引。
  2. 首先判断key是否为null,若为null,则直接调用putForNullKey方法。若不为空则先计算key的hash值,然后根据hash值搜索在table数组中的索引位置,如果table数组在该位置处有元素,则通过比较是否存在相同的key,若存在则覆盖原来key的value,否则将该元素保存在链头(最先保存的元素放在链尾)。若table在该处没有元素,则直接保存。所以数组的索引其实就是一个链表的表头,通过表头我们可以遍历该链表的所有数据。Entry是HashMap的一个内部类,使用它的作用其实就是建立一个链表,每一个Entry都存了下一个节点的对象,也就是一个一个对象里存有下一个对象,这样就可以构成我们的链表。所有,在找打数组索引后,我们按照key的值进行链表的遍历排查,如果遍历链表(null链表也可以遍历!)key不重复,则将将加入的键值对作为链表的表头,将其他的元素挂在后面就可以了。如果存在相同的key,则将value的值覆盖就可以。
    1. 一是链的产生。这是一个非常优雅的设计。系统总是将新的Entry对象添加到bucketIndex处。如果bucketIndex处已经有了对象,那么新添加的Entry对象将指向原有的Entry对象,形成一条Entry链,但是若bucketIndex处没有Entry对象,也就是e==null,那么新添加的Entry对象指向null,也就不会产生Entry链了。

    2. 二、扩容问题。
      随着HashMap中元素的数量越来越多,发生碰撞的概率就越来越大,所产生的链表长度就会越来越长,这样势必会影响HashMap的速度,为了保证HashMap的效率,系统必须要在某个临界点进行扩容处理。该临界点在当HashMap中元素的数量等于table数组长度*加载因子。但是扩容是一个非常耗时的过程,因为它需要重新计算这些数据在新table数组中的位置并进行复制处理。所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。

  3. 一开始的 transient Entry[] table = (Entry[]) EMPTY_TABLE;是一个空的数组?不是,如下:这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%(len-1)获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。这样,我们可以在一个很小的数组里面,存放很多的Entry(每个Entry有key,value,next),如果hashCode不一样,那么即使存放在同一个数组下标下面,在存放的时候,key和value是不一样的,可以顺利操作,但是如果key的hashCode一样的话,那么会存放在相同的table[index]下,这时候有,由于hashCode一样,前面我们知道,要保证一个对象的不重复,不仅需要hashCode还有equals,其实equals才是最重要的,equals相等的话,两个对象一定是一样的,但是为了提高效率,hashCode不一样的时候,两个对象一定是不一样的(后面这句话可以提高效率,所有一般先比较hashcode,hashCode一样的时候,为了确保正确才使用equals!!),所以,即使碰撞,我们由于equals的存在,可以很简单的解决。如果真的是同一个key,则直接覆盖value,否则就是一个新的Entry的简单加入,也就是链表的数据增加而已。

    public V put(K key, V value) {
    if (key == null)
    return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
    }
    }
    
    modCount++;
    addEntry(hash, key, value, i);
    return null;
    } 
    

TreeMap

这个其实和我们的Set里面的TreeSet一样,自定义的类使用的话,要实现Comparable接口,注意到这一点就可以。