集合框架

---

3. Map容器

3.1 Map容器的特点：

• Map 映射是一个存储键/值项的对象，键和值都是对象，给定一个键，可以查询到它的值；
• 键必须是唯一的，而值可以重复；
• 有些映射可以接受null键和null值，有的不行；
• 支持键/值对的接口
  
  • Map接口: 映射唯一关键字给值
  • Map.Entry接口: 描述映射中的元素，是Map类中的一个子类
  • SortedMap接口: 扩展Map以便关键字按升序排列

3.2 Map.Eetry接口

• Map.Entry接口代表映射项（键/值对）类型，是Map的嵌套类型；
• Map接口定义的entrySet()方法返回包含映射项Entry的集合（Set）,集合中元素是Map.Entry类型；
• 定义的方法：

- K getKey() //获得映射项的键 
- V getValue() //获得映射项的值
- V setValue(V value)  //设定映射项的值

3.3 HashMap——散列映射

哈希码的产生和使用
- 当调用对象的hashCode()方法时，就会返回当前的哈希码值。支持此方法是为了提高哈希表的性能；
- HashCode的常规协定：
- 如果根据 equals(Object) 方法，两个对象是相等的，那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。
- 这里说的 equals(Object)方法是指Object类中未被子类重写的equals方法
- 如果根据 equals(java.lang.Object) 方法，两个对象不相等，那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是，程序员应该知道，为不相等的对象生成不同整数结果可以提高哈希表的性能。

散列，哈希码原理

• HashMap类是基于哈希表的Map接口，并允许使用null键和null值；
• 除了不同步和允许使用null之外，HashMap与HashTable大致相同单线程建议使用HashMap；
• Hash表的数据结构是数组链表结构，HashMap通过计算Key的HashCode，把值存储在对应HashCode的下表元素中，把这种关系叫做散列映射；

源代码：

int hash=hash（key.hashCode()）;//计算Key的哈希码，并把哈希码传到散列表,怎么放？看下一句
int i=indexFor(hash, table.lenngth);//把散列值和数组的长度进行计算，最终得到Entry元素存放的下标

• 散列映射不保证它的元素顺序，元素加入散列映射的顺序并不一定是它们被迭代读出的顺序；
• 加载因子 fillRatio（0-1）: HashMap也是动态扩容的，比如加载因子为0.75，HashMap会在元素个数达到容量75%的时候扩容；

源代码：

//HashMap调用默认构造方法在底层产生一个默认长度为16的Entry数组
public HashMap(){
     this.loadFactor=DEFAULT_LOAD_FACTOR;//loadFacor是一个静态常量，即fillRitio=0.75
     threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR); //规定阈值是容量的0.75倍
     table=new Entry[DEFAULT_INITIAL_CAPACITY];// 初始化了一个给定容量的数组，这数组就叫entry！
     init();
}

• 冲突: 理想情况下，不同key的哈希码应该不相同，但是当HashMap容量不足的时候，有可能会对不同的key计算出相同的HashCode,相同的HashCode得到相同的散列值，这时候就发生了冲突。
• 冲突发生后， 会有两种情况发生：
  
  • 散列值相同，key相同：新的值会直接将旧的值覆盖
  • 散列值相同，key不同：新的值放在Entry元素里，旧的值拿出来，以链表的形式追加在原来的位置上。
    所以，HashMap内部的结构准确说是：数组链表结构
    
    源代码：

//接上面两行代码
for(Entry e=table[i]; e!=null; e=e.next){
     Object k;
     //如果与这个位置上已有元素的hash码相等，或者键相等，新的值就会覆盖原来的值.
     //被覆盖的值以链表的形式，连接在该位置上
     if(e.hash==hash && ((k=e.key)==key)||key.equals(k)){
         V oldValue=e.value;
         e.value=calue;
         e.recordAccess(this);
         return oldValue; 
     }
     //如果没有冲突，就直接的新的键/值对放进去
     addEntry(hash,key,value,i);
} 

• 链表结构的作用：在散列值有限的情况下，Entry元素上连着的链表为不同键/值对提供了额外的空间。但是链表不宜过长，否则会影响容器的性能。

源代码：

public V get(Object key){
     if(key==null)
          return getForNullKey();
     int hash=hash(key.hashCode());
     for(Entry e=table[indexFor(hash,table,length)];e!=null;e=e.next){
          Object k;
          if(e.hash==hash&&((k=e.key)==key)||key.equals(k)){
              return e.value; 
          }
     }
     return null;
}

• 加载因子的大小与冲突发生的概率有一定关系，加载因子越大，冲突发生的概率越大。

方法摘要

• HashMap实现Map接口并扩展AbstractMap,本身并没有增加任何新的方法。

– int size() //返回容器内映射对的个数
– void clear() //从此映射中移除所有映射关系
– Object clone() //返回比HashMap实例的浅表版本，并不复制键和值本身
– boolean isEmpty() //容器是否为空
– boolean containsKey(Object Key) //判断容器是否包含指定的键
– boolean containsValue(Object value) //判断容器是否包含指定的值
– V get(Object key) //根据键获取对应的
– V put(K Key, V value) //添加键/值对到容器内
– void putAll(Map a) //将指定映射集合复制到新的映射，这些映射关系将替换此映射目前针对指定映射中所有键的所有映射关系
– V remove(Object key) //删除Map容器中给定的键
– Collection values() //获取Map容器中所有的值
– Set KeySet() //返回此映射中关联指定值和指定键
– Set<Map.Entry> entrySet() //返回包含映射关系的Set视图

• 构造方法：

– HashMap() //默认加载一个具有默认初始容量和默认加载因子的HashMap
– HashMap(Map p) //构建一个与指定Map相同的新的HashMap
– HashMap(int capacity) //构建一个带指定初始容量的HashMap
– HashMap(int capacity, float fillRatio) //加载一个指定初始容量和指定加载因子的HashMap

Demo1：验证Map容器的散列特性，Map元素的遍历访问方法

• Map是键/值对的容器，
• Set也是一种容器，在Map操作中充当临时过渡的容器
• HashMap是利用哈希散列表存放这些键/值对的容器，HashMap是Map的一种情况
• HashMap中的键/值对有两种访问方式：
  -Set KeySet() //返回Map中所有的键，再通过get(key)得到所有的值
  -Set

package Collection;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class HashMapDemo1 {
     public static void main(String[] arge){
         HashMap map=new HashMap();
         map.put("Jack","铁蛋儿");
         map.put("Jack","二狗子");  //键相同，后者覆盖前者
         map.put("Danny","小明");
         map.put("Rose","二丫");
         System.out.println("Size of map"+map.size());
         System.out.println(map);
         //通过遍历key的索引get(key)获取Map中的键/值项
         //获取容器中所有的键
         //得到key的同时，索引对应的值
         Set keys=map.keySet();
         for(String key:keys){
             System.out.println(key+"--"+map.get(key));  //得到key的同时，索引对应的值
         }

         //获取容器中所有的值
         Collection vals=map.values();
         for(String val:vals){
             System.out.println(val);
         }
         //通过map.entry()方法，获取Map中的键/值项
         //当我们调用put(key, value)方法的时候，首先会把key和value封装到Entry这个静态内部类对象中，把Entry对象再添加到数组中
         //所以我们想获取Map中所有键/值对的话，只要获取输入中的所有Entry对象
         //再调用map.entry中的getKey()方法和getValue()方法就可以得到键/值对
         Set> entrys=map.entrySet();
         for(Entry entry : entrys){
             System.out.println(entry.getKey()+"--"+entry.getValue());
         }
     }
}

Demo2：重写hashCode()方法和equals()方法

package Collection;

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo2 {
     public static void main(String[] args){
          Map map=new HashMap();
          map.put(new Stu("Lily",20),"小黄");
          map.put(new Stu("Jack",22),"铁蛋");
          map.put(new Stu("Andy",20),"小明");
          map.put(new Stu("Lily",20),"李雷");

          /*不重写stu的hashCode()方法和equals()方法时
 map中有四个键/值对，因为源代码调用的是比较对象的equals方法
 第一个Stu对象和第四个Stu对象是不同的对象*/

          /*重写hashCode()方法和equals()方法后
 第一个Stu对象和第四个Stu对象被判断为相等*/

          System.out.println(map.size());
          System.out.println(map);:
     }
}
class Stu{
     private String name;
     private int age;

     public Stu(String name, int age) {
          super();
          this.name = name;
          this.age = age;
     }
     public String getName() {
          return name;
     }
     public void setName(String name) {
          this.name = name;
     }
     public int getAge() {
          return age;
     }
     public void setAge(int age) {
          this.age = age;
     }
     @Override
     public int hashCode() {
          final int prime = 31;
          int result = 1;
          result = prime * result + age;
          result = prime * result + ((name == null) ? 0 : name.hashCode());
          return result;
     }
     //重写的equals方法，定义只要stu类内的所有类型元素对应相等就返回ture。
     @Override
     public boolean equals(Object obj) {
          if (this == obj)
              return true;
          if (obj == null)
              return false;
          if (getClass() != obj.getClass())
              return false;
          Stu other = (Stu) obj;
          if (age != other.age)
              return false;
          if (name == null) {
              if (other.name != null)
                   return false;
          } else if (!name.equals(other.name))
              return false;
          return true;
     }
}

3.4 HashMap——数映射

TreeMap
- TreeMap类通过使用红黑树实现Map接口
- TreeMap提供按排序顺序存储键/值对的有效手段，同时允许快速检索
- 不像散列映射，数映射保证它的元素按照键字升序排序
- 如果键字没有明显的自然顺序， 可以根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
- TreeMap实现了SortedMap并扩展了AbstractMap,它本身并没有定义其他方法
- TreeMap构造方法：

- TreeMap() // 使用键的自然顺序构造一个新的、空的树映射。
- TreeMap(Comparator comp) // 构造一个新的、空的树映射，该映射根据给定比较器进行排序。
- TreeMap(Map m) // 构造一个与给定映射具有相同映射关系的新的树映射，该映射根据其键的自然顺序 进行排序。
- TreeMap(SortedMap m) // 构造一个与指定有序映射具有相同映射关系和相同排序顺序的新的树映射。

Demo1：TreeMap默认的排序效果

package Collection;

import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;

public class TreeMapDemo1 {
    public static void main(String[] args){
        TreeMap tmap=new TreeMap();
        tmap.put("Jack", "铁蛋儿");
        tmap.put("Andy", "二丫");
        tmap.put("Moomen", "妮娜");
        tmap.put("Sunny", "杨洋");
        tmap.put("Sunny", "朝阳");
        //按照首字母的自然顺序生序排序
        System.out.println(tmap);
        //通过增强for循环遍历entry元素得到键值对
        Set> entrys=tmap.entrySet();
        for(Entry entry:entrys){
            System.out.println(entry.getKey()+"--"+entry.getValue()); 
        }
    }
}

Comparator接口和Comparable接口
- TreeMap的Key存储引用类型数据，需要满足一定的条件
- 要么引用类型实现Comparator接口
- 要么为该TreeMap容器提供实现Comparable接口的比较器对象

Demo2：重写TreeMap排序算法的两种方式

package Collection;

import java.util.Comparator;
import java.util.TreeMap;

public class TreeMapDemo2 {
    public static void main(String[] args){
        TreeMap pdata=new TreeMap(new Comparator(){
            //重写了comparator里面的compare()方法
            @Override
            public int compare(pers o1, pers o2) {
                /*if(o1.getAge()-o2.getAge()>0){
 return 1;
 }else if(o1.getAge()-o2.getAge()<0)
 return -1;
 return 0;*/
                //按名字的字典顺序排列：相同的名字会被认为是一个键
                /*return o1.getName().compareTo(o2.getName());*/
                //如果名字相同，再比较年龄
                if(o1.getName().compareTo(o2.getName())>0){
                    return 1;
                }else if(o1.getName().compareTo(o2.getName())<0){
                    return -1;
                }else 
                    return o1.getAge()-o2.getAge();
            }
        });
        pdata.put(new pers("Jack",20), "张三");
        pdata.put(new pers("Rose",20), "小红");
        pdata.put(new pers("Jimmy",24), "李四");
        pdata.put(new pers("Kimmi",22), "赵四");
        pdata.put(new pers("Jack",20), "乐乐");
        //pers类型的数据没有自然顺序，不能直接放入TreeMap
        //solution1：Comparable接口的重写比较规则compareTo()
        //solution2:重写构造方法：TreeMap(Comparator comp)
        System.out.println(pdata);
        }
}
class pers /* implements Comparable*/{
    private String name;
    private int age;
    public pers(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    /*@Override
 public int compareTo(pers o){
 if(this.age-o.getAge()>0){
 return 1;
 }else if(this.age-o.getAge()<0)
 return -1;
 return 0;
 }*/
}