JavaSE核心API--查找表Map与散列表HashMap

java.util.Map等

1)理论讲解:重写key元素的hashCode方法和equals方法

HashMap是当今查询速度最快的数据结构---因为HashMap可以根据key元素的hashCode方法返回该元素在散列表内部数组的下标位置，从而可以不用遍历而直接
找到该元素

但是作为key元素的hashCode方法和equals方法的实现如果不妥当，就会降低散列表的查询性能
-----所以要妥善重写key元素的hashCode方法和equals方法，可以尽量避免出现链表

在HashMap中出现链表就会影响其查询性能，而出现链表的一个主要原因：
当两个key元素的hashCode值（hashCode方法返回的数字）相同时，但它们equals比较不为true的时候，则会在HashMap内部形成链表

hashCode决定该元素在HashMap内部数组的下标位置
equals方法决定HashMap是否认为这两个key为重复

hashCode方法与equals方法是Object定义的方法，这两个方法在API手册的Object类中有明确的说明：
  当我们需要重写一个类的equals或hashCode方法时要遵循下面几点要求：
    1.成对重写，当我们重写一个类的equals方法时就应当连同重写hashCode，反过来也一样
    2.一致性，当两个对象equals比较为true时，hashCode方法返回的数字必须相等，反过来则不是必须的，
      但是尽量保证当两个对象hashCode相同时equals比较也为true
    3.稳定性，当一个对象参与equals比较的属性值没有发生过改变的前提下，多次调用hashCode方法返回的数字应当不变（而不是返回随机数）

代码演示:

public class Key {
   private int x;
   private int y;

   @Override
   public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + x;
        result = prime * result + y;
        return result;
   }

   @Override
   public boolean equals(Object obj) {
        if (this == obj)
           return true;
        if (obj == null)
           return false;
        if (getClass() != obj.getClass())
           return false;
        Key other = (Key) obj;
        if (x != other.x)
           return false;
        if (y != other.y)
           return false;
        return true;
   }

}

2)理论讲解:Map与HashMap

java.util.Map查找表
Map的结构是一个多行两列的表格，其中左列称为key，右列称为value
Map总是以key-value对的形式保存数据，并且总是以key来获取对应的value
所以我们经常将要查询的数据作为value，将查询条件作为key，保存在Map中以便于根据条件快速查找对应的数据

java.util.HashMap散列表
HashMap是Map最常用的实现类，也是当今最快的查询结构

代码演示

public static void main(String[] args) {
    /*
     * Map要求指定两个泛型，分别说明key与value的类型
     */
    Map<String, Integer> map = new LinkedHashMap<>();// 内部数组初始个数为16，当元素占够四分之三数组就要扩容
    /*
     * V put(K k,V v) 
     * 将给定的键值对保存到Map中 
     * 注：
     * Map有一个要求，即Map中的key不允许重复，重复的标准是依靠key自身的equals比较结果
     * 所以put方法是有返回值的，若本次存放的key已经在Map中存在，则是替换value操作，那么返回值就是被替换的value，否则为null
     */
    /*
     * 若value的类型为包装类，切记不要用对应的基本类型接受put方法的返回值
     * 因为这会触发包装类自动拆箱，而put方法返回值有可能是null，这时若拆箱会发生空指针异常
     */
    map.put("语文", 99);
    map.put("数学", 98);
    map.put("英语", 97);
    map.put("物理", 96);
    map.put("化学", 99);
    System.out.println(map);

    /** 若本次存放的key已经在Map中存在，则是替换value操作，那么返回值就是被替换的value，否则为null */
    Integer num = map.put("语文", 77);
    System.out.println(map);
    System.out.println(num);
    /*
     * V get(Object key) 
     * 根据给定的key获取对应的value，若给定的key在Map中不存在则返回值为null
     */
    num = map.get("英语");
    System.out.println("英语：" + num);
    num = map.get("体育");
    System.out.println("体育：" + num);

    int size = map.size();
    System.out.println("size:" + size);
    /*
     * V remove(K k) 
     * 根据给定的key删除对应的这组键值对，返回值为该键值对中的value
     */
    num = map.remove("物理");
    System.out.println(map);
    System.out.println(num);
    /*
     * boolean containsKey(Object k) 
     * boolean containsKey(Object v)
     * 判断当前Map是否包含给定的key或value 包含的判断还是依靠元素自身equals比较的结果
     */
    boolean ck = map.containsKey("语文");
    boolean cv = map.containsValue(98);
    System.out.println("是否包含key：" + ck);
    System.out.println("是否包含value：" + cv);
}

3)理论讲解:Map的遍历

  Map的遍历三种方式：
   1.遍历所有的key 
   2.遍历所有key-value对 
   3.遍历所有的value(相对不常用)

代码演示:

public static void main(String[] args) {
//  Map<String, Integer> map = new HashMap<>();

    /*
     * LinkedHashMap是可以做到遍历顺序与put时的顺序一致的
     */
    Map<String, Integer> map = new LinkedHashMap<>();
    map.put("语文", 99);
    map.put("数学", 98);
    map.put("英语", 97);
    map.put("物理", 96);
    map.put("化学", 99);
    System.out.println(map);
    /*
     * 遍历所有的key Set keySet() 将当前Map中所有的key以一个Set集合形式返回 遍历该集合就等同于遍历了所有的key
     */
    Set<String> keySet = map.keySet();
    for (String key : keySet) {
        System.out.println("key:" + key);
    }
    /*
     * 遍历每组键值对 Set entrySet() 将当前Map中每组键值对(若干个Entry实例)以一个Set集合形式返回
     * 
     * java.util.Map.Entry 每个Entry实例表示Map中的一组键值对 常用方法： K getKey():获取其表示的键值对中的key V
     * getValue():获取其表示的键值对中的value
     */

    Set<Entry<String, Integer>> entrySet = map.entrySet();
    for (Entry<String, Integer> entry : entrySet) {
        String key = entry.getKey();
        Integer value = entry.getValue();
        System.out.println(key + ":" + value);
    }

    /*
     * 遍历所有的value Collection values() 将当前Map中所有的value以一个集合形式返回
     * 由于Map中不要求value不重复，所以其不以Set集合形式返回
     */
    Collection<Integer> values = map.values();
    for (Integer value : values) {
        System.out.println("value:" + value);
    }
}

4.小练习:统计字符串中每个字符出现的次数

public static void main(String[] args) {
    String str = "helloworld!this is java!i love java!";

    Map<Character, Integer> map = new HashMap<>();

    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (map.containsKey(c)) {// 如果字符c存在则表明该字符出现过
            int num = map.get(c);
            num = num + 1;
            map.put(c, num);
        } else {// 否则就添加到map中，个数为1
            map.put(c, 1);
        }
    }
    System.out.println(map);
}