JavaSE — Map - 蔡不菜和他的uU们

1 HashMap

1.1 底层实现

1.1.1 哈希表是一个怎样的数据结构

数组+单向链表的结合体
数组：在查询方面效率很高，随机增删效率很低
单向链表：在随机增删方面效率很高，在查询方面效率很低
哈希表将以上的两种数据结构融合在一起，充分发挥它们各自的优点

1.1.2 为什么哈希表的增删，以及查询效率都很高

增删是在链表上完成的

查询也不需要都扫描，只要部分扫描，
key 会先后调用hashCode() 方法，equals方法

1.1.3 哈希表使用不当会出现的问题

哈希表使用不当时，无法发挥性能

假设将所有的hashcode返回的是一个固定值，那么会导致哈希表变成了纯单向链表，这种情况我们称为，散列分布不均匀
假设将所有的hashcode返回的是不一样的值，会导致底层哈希表变成一维数组，没有链表的概念了，也是散列分布不均匀的
散列分布均匀的，需要在重写hashcode方法时注意一定的技巧

1.2 特性

默认初始容量 16

hashmap集合初始化容量必须是2的倍数，官方推荐的，这是为了达到散列均匀，提高存取效率

扩容：默认加载因子为 0.75，达到75% 开始扩容为原来的两倍

加载因子 0.75

key部分的特点无序，不可重复

为什么无序，不可重复是怎么保证的，

equals方法来保证hashmap的key是不可重复的，如果重复了，value会被覆盖

HashMap 在JDK8 之后如果在单向链表上存储的元素超过 8个，单向链表会变成红黑树，当红黑树上元素少于6个，又会变为链表

hashMap 集合允许key和value为null，但是hashMap 的null 值只能有一个

1.3 源码

public class HashMap(){

Node<K,V> [] table;
// 静态内部类

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // 哈希值，是key的hashcode方法的执行结果 hash值可以通过hash函数，转换为数组下标
    final K key; // 存储到Map集合中的那个key
    V value; // 存储到Map集合中的那个value
    Node<K,V> next; // 下一个节点的内存地址

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}   
}

1.4 常用方法

remove(Object key) 移除指定键值对

replace(K key,V oldValue, V newValue) 更新键值对

1.5 HashMap的存取

1.5.1 map.put(K k,V v)

第一步：先将KV 封装成 Node 对象

第二步：底层调用hashcode（）方法得到hash值，然后通过哈希函数（哈希算法）将hash值转换为数组下标，下标位置上没有任何元素，就把node添加到这个位置，如果说下标对应的位置上有链表，此时会拿着key和链表上每一个节点进行equals，如果所有的equals方法返回都是false，那么这个新节点就会被添加到链表的末尾，如果其中一个equals返回了true，会把新节点的value进行替换，原来的value被覆盖

1.5.2 map.get(k)

先调用hashCode() 方法得到hashcode，通过hash函数，转换成数组下标，通过数组下标快速定位到某个位置上，如果这个位置上什么也没有，返回null，如果这个位置上有单向链表，那么会拿着key 和单向链表上的每个节点上的k进行equals ，如果所有的equals方法返回false，那么get方法返回null，只要其中有一个节点的k和参数k equals的时候返回true，那么此时这个节点的value就是我们要找的value，get方法返回这个要找的value

1.5.3 Map 存取

都是先调用hashCode() 然后调用 equals()

equals方法，有可能调用，也有可能不调用
不调用的情况，hashcode转换为数组下标，该位置没有元素，返回null，此时不会调用

1.6 HashMap的遍历

先使用keySet() 获取key集合，然后遍历key集合获取 get(key)

Set<Integer> set = map.keySet();

for(Integer key:set){
      System.out.println(key+"="+map.get(key));
}

使用entrySet()转换为set,然后再对set进行遍历效率较高（大数据量）

Set> set = map.entrySet();

for (Map.Entry item : set) {
     System.out.println(item);
}

Set> set = map.entrySet();

Iterator> it = entrySet.iterator();

while(it.hasNext()){
    System.out.println(it.next());
}

1.7 重要

hashcode方法和equals方法，可以直接使用IDEA工具生成，但是这两个方法需要同时生成

hashMap 集合允许key和value为null，但是hashMap 的null 值只能有一个

HashMap 在JDK8 之后如果在单向链表上存储的元素超过 8个，单向链表会变成红黑树，当红黑树上元素少于6个，又会变为链表

2 Hashtable

2.1 特性

Hashtable 不支持key为null，也不支持value为null，否则会报java.lang.NullPointerException

Hashtable 是线程安全的，方法都有synchronized修饰，但是效率较低，有新的解决方案

hashtable 初始化容量是11，默认加载因子 0.75 扩容到原来的两倍+1

3 Properties

3.1 特点

属性类对象继承Hashtable

线程安全

properties的key和value只能是string

3.2 常用方法

setProperty(K k,V v)  // 添加属性，底层是调用的map.put() 方法

getProperty(K k)

4 SortedMap接口

4.1 特点

SortedMap接口的存储元素的特点
由于继承了set接口，所以他的特点也是无序不可重复的，
但是放在SortedSet接口中的元素可以自动排序，
放到该集合中的元素是自动按照大小顺序进行排序的

5 TreeMap

5.1 特点

TreeMap集合采用的是，中序遍历方式

TreeMap集合key部分的时候，需要进行排序，实现方式有两种

放到集合中的元素实现java.lang.Comparable 接口
在构造TreeSet 或者 TreeMap 集合的时候给它传一个比较器对象，（匿名内部类的形式，或者新建一个比较器class传入）

5.2 底层数据结构二叉树

6 重要注意事项

存放在集合中的元素类型，需要重写equals方法

Map和Collection 没有继承关系

TreeSet集合，TreeMap集合采用的是，中序遍历方式

放到TreeSet或TreeMap集合key部分的时候，需要进行排序，实现方式有两种

放到集合中的元素实现java.lang.Comparable 接口在compareTo方法写排序规则
在构造TreeSet 或者 TreeMap 集合的时候给它传一个比较器对象，（匿名内部类的形式，或者新建一个比较器class传入）

6.1 Comparable 和 Comparator 怎么选择？

比较规则不轻易改变选择实现Comparable 接口，（例如 Integer，String，Date，）
比较规则有多种，并且需要进行切换，实现Comparator 接口

对set集合进行排序，需要先转换为list，然后再用Collections.sort()

构造方法中传入比较器对象，写比较规则

TreeSet ts  =new TreeSet<>(new Comparator() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
});

remove contain compareTo 方法底层调用的是equals方法

6.2 使用泛型

1.JDK 5.0 之后推出的新特性：泛型

2.泛型属于编译器阶段的新特性，只是给编译器参考的，运行阶段泛型没用

6.2.1 优点

保证了集合中元素的统一性

从集合中取出的元素类型是泛型指定类型，不需要进行大量的向下转型

6.2.2 缺点

导致集合中存储的元素缺乏多样性

大多数业务中，集合中元素类型还是统一的，所以还是能被接受的

6.2.3 自定义泛型

6.2.4 其他

JDK 8 之后引入了自动类型推断机制（又称为砖石表达式）

迭代时也需要指定迭代的泛型

7 Collections工具类

7.1 常用方法

Collections.synchronizedList(list) 将线程不安全的ArrayList 转换为线程安全的

Collections.sort(wu); 进行排序的list 存取的元素类型需要实现 comparable 接口

Collections.sort(myList 待排序数组, Comparator 比较器对象);