大数据------javase基础------day15

Map

• Map接口的特点

Map接口是键值对集合，每个元素均包含键和值两个对象

无序（存入顺序和遍历顺序不一致）

• 键值对特点：

（1）键唯一，不可重复；但值可以重复

（2）键和值一一映射，一个键对应一个值（值可以是单个值也可以是个数组或集合）

• 创建Map接口方式

（1）以多态的方式创建

（2）具体的实现类HashMap

Map接口常用方法

方法解释

public V put(K key, V value)

将键值对存入集合

public V get(Object key)

返回指定键映射到的值，如果此映射不包含键的映射，则返回

null

。 （即用键取值）

pulblic int size()

返回此映射中键 - 值映射的数量。 （即返回该集合中键值对元素数量）

public V remove(Object key)

如果存在，则从该映射中移除键的映射（可选操作）。（即使用键作为检索条件来删除键值对）

default boolean remove(Object key, Object value)

仅当指定键当前映射到指定值时才删除该条目的条目。

public boolean isEmpty()

如果此映射不包含键 - 值映射，则返回

true

。(即判断该集合是否为空)

public boolean containsKey(Object key)

如果此映射包含指定键的映射，则返回

true

。 （即判断该集合中是否存在指定的键）

public boolean containsValue(Object value)

如果此映射将一个或多个键映射到指定值，则返回

true

。（即判断该集合中是否有指定的值）

default V replace(K key, V value)

仅当指定键当前映射到某个值时，才替换该条目的条目。 （即用新值替换当前键所映射的值）

default boolean replace(K key, V oldValue, V newValue)

仅当前映射到指定值时，才替换指定键的条目。
注意：使用put方法时，若要存入的键是集合中已经存在的键的话，则此时会用新值替换掉原来该键所对应的值

publicclassTestOne{publicstaticvoidmain(String[] args){Map map =newHashMap<>();
        map.put("班长","美国");
        map.put("学委","中国");//存入键值对
        map.put("体委","俄罗斯");
        map.put("文委","意大利");
        map.put("班委","意大利");String s =(String) map.get("班长");//取出键所对应的值System.out.println(s);System.out.println(map);System.out.println("---------------------------");
        map.remove("学委");//使用键作为检索条件来删除键值对System.out.println(map);System.out.println("---------------------------");
        map.remove("班委","意大利");System.out.println(map);System.out.println("---------------------------");System.out.println(map.isEmpty());System.out.println("---------------------------");System.out.println(map.containsKey("班委"));//判断集合中是否有指定的键System.out.println("---------------------------");System.out.println(map.containsValue("意大利"));//判断该集合中是否有指定的值System.out.println("---------------------------");
        map.replace("班长","朝鲜");System.out.println(map);System.out.println("---------------------------");// 仅当前映射到指定值时，才替换指定键的条目System.out.println(map.replace("文委","德国","日本"));System.out.println("---------------------------");
        map.put("文委","韩国");System.out.println(map);}}

Map接口的遍历

• 注意

（1）Map集合不能用iterator迭代器遍历，因为iterator()方法属于Collection集合中的方法

（2）Map集合也不能用增强for循环遍历，因为其底层用的是iterator迭代器遍历

（3）Map集合也不能用传统for循环遍历，因为其没有下标

（4）Map接口的遍历需要遍历键，因为每个键对应一个值

• 用到的方法
  方法解释

  public Set<K> keySet()
  

  返回此映射中包含的键的

  Set
  

  视图。 （即返回键集，该键集会被存入不可重复的Set集合，从而可以使用iterator迭代器遍历）

  public Collection<V> values()
  

  返回此映射中包含的值的

  Collection
  

  视图。 （即返回值集，该值集会被存入可重复的Collection集合，从而可以使用iterator迭代器进行遍历）

  public Set<Map.Entry<K,V>> entrySet()
  

  返回此映射中包含的映射的

  Set
  

  视图。 （即返回键值对集）用到的静态嵌套类****解释

  static interface Map.Entry<K,V>
  

  映射条目（键值对）。 （即将获取到的键值转型为键值对）静态嵌套类Entry中的方法****解释

  public K getKey()
  

  返回与此条目对应的键。

  public V getValue()
  

  返回与此条目对应的值。
  问题

（1）为什么键集存入Collection集合中的Set集合？

因为键是无序且不可以重复的，而Set集合刚好是无序且不可重复的，所以若想要对Map集合进行遍历则需要先将其键集转换为Set集合，然后利用Collection集合中特有的方法iterator方法进行迭代器遍历

（2）为什么值集存入Collection集合？

因为值是跟着键走的，因为键是无序的，所以值是无序的，又因为虽然键是不能重复的，但是值是可以重复的，所以无法使用Collection集合中的两个子集合（List和Set），只能使用Collection集合

• 遍历方式一------利用键集遍历

publicclassTestTwo{publicstaticvoidmain(String[] args){Map map =newHashMap<>();
        map.put("班长","美国");
        map.put("学委","中国");//存入键值对
        map.put("体委","俄罗斯");
        map.put("文委","意大利");
        map.put("班委","意大利");Set keys = map.keySet();//返回键集---该键集会被存入Set集合，从而可以使用iterator迭代器遍历Iterator iter = keys.iterator();//获取键集迭代器while(iter.hasNext()){String key =(String) iter.next();String value =(String) map.get(key);System.out.println(key +"="+ value);}}}

• 遍历方式二------利用值集遍历

publicclassTestThree{publicstaticvoidmain(String[] args){Map map =newHashMap<>();
        map.put("班长","美国");
        map.put("学委","中国");//存入键值对
        map.put("体委","俄罗斯");
        map.put("文委","意大利");
        map.put("班委","意大利");Collection col = map.values();Iterator iter = col.iterator();while(iter.hasNext()){String value =(String) iter.next();System.out.println(value);}}}

• 遍历方式三------利用键值集遍历

publicclassTestFour{publicstaticvoidmain(String[] args){Map map =newHashMap<>();
        map.put("班长","美国");
        map.put("学委","中国");//存入键值对
        map.put("体委","俄罗斯");
        map.put("文委","意大利");
        map.put("班委","意大利");Set set = map.entrySet();//返回键值对Set集合Iterator iter = set.iterator();//返回迭代器对象while(iter.hasNext()){Map.Entry entry =(Map.Entry) iter.next();//将获取到的元素转换为键值对System.out.println(entry);//打印出键值对String key =(String) entry.getKey();//返回键String value =(String) entry.getValue();//返回值System.out.println("key = "+ key +"\n"+"value = "+ value);System.out.println("------------------------------");}}}

• Map接口的实现类

Map接口的常用实现类：HashMap、TreeMap、LinkedHashMap和Properties

HashMap和HashTable

• 异同

（1）HashMap线程不安全，允许使用null键和null值，效率高，推荐使用

（2）HashTable线程安全，任何非null对象都可以用作键或值，效率低，不推荐使用

（3）底层用相同的方式（哈希表）存储元素

• HashMap的实例有两个影响其性能的参数：初始容量和负载因子

（1）初始容量只是创建哈希表时的容量

（2）是在自动增加容量之前允许哈希表获取的完整程度的度量。 当哈希表中的条目数超过默认加载因子（0.75）和当前容量的乘积时，哈希表将被重新哈希（即，重建内部数据结构），以便哈希表具有大约两倍的桶数。

• HashMap特点 （1）创建HashMap对象时会为负载因子进行默认赋值为0.75 （2）第一次调用put方法时初始化一个长度为16的数组 （3）当集合中的元素数超过默认负载因子（0.75）和数组长度的乘积时按照原来数组长度的两倍扩容 （4）在JDK1.8之前，HashMap底层使用链表+数组存储元素；在JDK1.8之后，HashMap底层使用链表+数组+红黑树存储 （5）在JDK1.8之后，若一个链表元素超过8个且此时数组长度达到64，则将链表结构变为红黑树
• HashMap源码解析 （1）负载因子 （2）调用put方法 因为创建Map集合时是利用HashMap多态的方式创建的，所以调用的put方法为HashMap类中的put方法，以上源码截图即为HashMap类中的put方法，其中HashMap源码中的putVal方法代码及解释如下：

finalVputVal(int hash,K key,V value,boolean onlyIfAbsent,boolean evict){//tab为键值对数组，p为当前节点元素，n为当前数组长度，i为计算所得到的数组索引(即本次元素在数组中的下标)Node<K,V>[] tab;Node<K,V> p;int n, i;if((tab = table)==null||(n = tab.length)==0)
        n =(tab =resize()).length;//通过哈希码计算数组索引i并检查该位置的节点p是否为null，若为null则在该位置存入一个新节点if((p = tab[i =(n -1)& hash])==null)
        tab[i]=newNode(hash, key, value,null);//通过哈希码计算数组索引i并检查该位置的节点p不为null（代表该节点处有元素）else{Node<K,V> e;K k;//判断当前节点处的元素的哈希值与要存入的元素的哈希值是否相等且当前节点处的元素的键是否等于要存入的元素的键以及两键是否相等，若成立则说明要存入的元素与原元素相同则不执行新增操作//该if判断等同于hashcode和equals方法的结合体if(p.hash == hash &&((k = p.key)== key ||(key !=null&& key.equals(k))))
            e = p;//将新元素赋值给老元素//若不成立则说明要存入的元素与原元素不相同，此时需要判断要新增的元素节点是否是TreeNode的对象（即判断当前要存的节点是否是树节点（即红黑树）的对象），若是则存入树中elseif(p instanceofTreeNode)
            e =((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//若新增的元素节点不是树节点的对象则代表当前节点是链表中的节点，将该节点插入链表中else{//遍历循环链表，直至链表末尾for(int binCount =0;;++binCount){//将链表的下一个节点赋给e并判断该节点是否为空，若为空则将节点p作为一个新节点添加到链表中if((e = p.next)==null){
                    p.next =newNode(hash, key, value,null);//判断链表增加节点后长度是否达到树化的阈值，若达到则调用方法将链表转化为树if(binCount >=TREEIFY_THRESHOLD-1)// -1 for 1sttreeifyBin(tab, hash);break;//退出循环执行循环体后的代码}//若存在与要插入的节点相同的节点则直接跳出循环if(e.hash == hash &&((k = e.key)== key ||(key !=null&& key.equals(k))))break;
                p = e;将当前链表节点赋给p
            }}if(e !=null){// existing mapping for keyV oldValue = e.value;if(!onlyIfAbsent || oldValue ==null)
                e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if(++size > threshold)resize();afterNodeInsertion(evict);returnnull;}

if ((tab = table) == null || (n = tab.length) == 0)

该句代码中table的代码为

transient Node<K, V>[] table

if((tab = table)==null||(n = tab.length)==0)
    n =(tab =resize()).length;

table

的初始化是在

putVal

方法中进行的，当第一次添加元素时，

table

会被初始化为具有默认容量的数组。所以第一次使用put方法时集合中无元素，最开始table为空，此句代码含义为：将装数据的数组赋值给键值对数组tab，然后判断tab是否为null或者当前数组tab的长度是否为0，若是（就证明无法添加新元素）则需要利用HashMap源码中的resize方法来返回一个扩容后的新数组并将其赋给tab然后将该扩容后的新数组的长度赋值给n

if((p = tab[i =(n -1)& hash])==null)
    tab[i]=newNode(hash, key, value,null);

通过哈希码计算数组索引i并检查该位置的节点p是否为null，若为null则在该位置创建一个新节点

注意：为什么用(n-1)&hash ？

保证计算出的索引值在数组长度范围内

用到的resize方法的代码如下：

finalNode<K,V>[]resize(){//将当前元素数组赋给oldTab------旧节点数组Node<K,V>[] oldTab = table;//记录当前oldTab旧节点数组的长度；若为空则代表第一次存储元素，将长度记为0，否则记为当前数组长度int oldCap =(oldTab ==null)?0: oldTab.length;//记录长度*负载因子之后得出的旧的扩容临界值（即旧的阈值），用于判断是否需要进行扩容。其中临界值threshold在HashMap类的构造器中利用其方法tableSizeFor计算int oldThr = threshold;//newCap为新的数组长度，newThr为新的扩容临界值---即定义新的容量和新的阈值int newCap, newThr =0;//判断是否是第一次存储元素，若不是则执行if代码if(oldCap >0){//判断旧节点数组长度是否大于常量（static final int MAXIMUM_CAPACITY= 1 << 30）,该常量为HashMap的最大容量if(oldCap >=MAXIMUM_CAPACITY){//若旧节点数组长度大于HashMap的最大容量则将阈值设为最大值常数2^31 -1,表示不再进行扩容，直接返回旧节点数组
                threshold =Integer.MAX_VALUE;return oldTab;}//将旧节点数组长度扩大两倍赋给新节点newCap并判断若新容量小于MAXIMUM_CAPACITY（HashMap的最大容量）并且旧容量大于等于DEFAULT_INITIAL_CAPACITY（为HashMap的默认初始容量，为16），则将新阈值设为旧阈值的两倍。elseif((newCap = oldCap <<1)<MAXIMUM_CAPACITY&&
                     oldCap >=DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr <<1;// double threshold}//若是第一次存储元素则判断旧阈值是否大于0elseif(oldThr >0)// initial capacity was placed in threshold
            newCap = oldThr;//若是第一次存储元素且旧阈值为0------即旧节点容量和旧阈值均为0  时，则将新容量设置为默认初始容量16，将新阈值设置为默认负载因子与默认初始容量的乘积12else{// zero initial threshold signifies using defaults
            newCap =DEFAULT_INITIAL_CAPACITY;
            newThr =(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);}//若新阈值为0则判断新容量小于最大容量并且新容量乘以负载因子小于最大容量并为新阈值赋值if(newThr ==0){float ft =(float)newCap * loadFactor;
            newThr =(newCap <MAXIMUM_CAPACITY&& ft <(float)MAXIMUM_CAPACITY?(int)ft :Integer.MAX_VALUE);}
        threshold = newThr;//更新阈值（扩容的临界值）@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab =(Node<K,V>[])newNode[newCap];
        table = newTab;if(oldTab !=null){for(int j =0; j < oldCap;++j){Node<K,V> e;if((e = oldTab[j])!=null){
                    oldTab[j]=null;if(e.next ==null)
                        newTab[e.hash &(newCap -1)]= e;elseif(e instanceofTreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else{// preserve orderNode<K,V> loHead =null, loTail =null;Node<K,V> hiHead =null, hiTail =null;Node<K,V> next;do{
                            next = e.next;if((e.hash & oldCap)==0){if(loTail ==null)
                                    loHead = e;else
                                    loTail.next = e;
                                loTail = e;}else{if(hiTail ==null)
                                    hiHead = e;else
                                    hiTail.next = e;
                                hiTail = e;}}while((e = next)!=null);if(loTail !=null){
                            loTail.next =null;
                            newTab[j]= loHead;}if(hiTail !=null){
                            hiTail.next =null;
                            newTab[j + oldCap]= hiHead;}}}}}return newTab;}