Java类集基础概念-Map篇

Map

1.定义

一次性保存两个对象（结构：key = value），最大特点：可以通过key找到对应的value值

Map接口是Java中保存二元偶对象（键值对）的最顶层接口

key值唯一，通过一个key值一定能唯一找到一个value值

2.常用方法

• public V put(K key,V value):向Map中添加数据
• public V get(K key):根据指定的key值取得相应的value值，若没有此key值，返回null
• public Set<Map.Entry<K,V>> entrySet():将Map集合变为Set集合
• public Set<K> keySet():返回所有Key值集合，key不能重复 （key值重复，再次put变为相应value的更新操作）
• public Collection<V> values():返回所有value值，value可以重复

3.常用子类

• HashMap(常用)
• Hashtable
• TreeMap
• ConcurrentMap

4.HahMap

4.1特点

• key,value均可为null
• key不可重复
• value可以重复

4.2出现版本

JDK1.2

4.3底层实现

哈希表+红黑树（JDK8后添加了红黑树）

4.4内部实现解析

HashMap的内部结构可以看作：数组（Node[] table）+链表

• 哈希值决定键值对在这个数组的寻址，哈希值相同的键值对，则链式存储；
• 如果链表大小超过阈值(TREEIFY_THRESHOLD,8)，链表会被改造为树形结构；

（1）先分析HashMap的构造函数；仅仅设置了初始值，可能使用了lazy-load原则

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
           

（2)分析put()

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
           

putVal()部分代码

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

• 如果tab为null，resize()会初始化tab;

（3）resize()分析

常量值：

MAXIMUM_CAPACITY = 1 << 30

DEFAULT_INITIAL_CAPACITY = 16

DEFAULT_LOAD_FACTOR = 0.75f

int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        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>[])new Node[newCap];
        table = newTab;
           

• 门限值通常以倍数调整（newThr = oldThr << 1），即当元素个数超过门限大小，则调整Map大小；

• 门限 = 负载因子 * 容量（newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)），如果没有指定，采用默认值；

• 扩容后，将原来的数组元素放置到新的数组中（table = newTab）；

根据代码分析：负载因子 * 容量 > 元素数量；负载因子在源码中设置值为0.75，不建议更改；

（4）树化分析

putVal()部分代码

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);
break;
           

treeifyBin()部分代码

int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {}
           

当binCount >= TREEIFY_THRESHOLD - 1时，

容量 < MIN_TREEIFY_CAPACITY =>扩容

容量 > MIN_TREEIFY_CAPACITY =>树化

树化的原因：安全问题

在元素放置过程中，一个对象哈希冲突，放置在同一个数组中，会形成一个链表，链表查询是线性的，会严重影响存取性能；

5.Hashtable

5.1特点

• key、value均不能为null

5.2出现版本

JDK1.0

5.3底层实现

哈希表

5.4HashMap和Hashtable比较

区别	HashMap	Hashtable
出现版本	JDK1.2	JDK1.0
性能	异步处理，性能高	同步处理，性能低
安全性	线程不安全	线程安全
null操作	允许存放null	不允许存放null

6.TreeMap

6.1特点

可排序（按照key值排序）---实现Comparable接口完成

结论：有Comparable出现的地方，判断数据就依靠compareTo（）方法完成，不再需要equals()与hashCode()

7.ConcurrentMap

7.1特点

java.util.Concurrent

线程安全集合

7.2出现版本

JDK1.5

8.关于Map中自定义类做key值

一定要覆写Object类的hashCode()与equals()

代码分析

（1）未覆写

class Person{
    private Integer age;
    private String name;
​
    public Person(Integer age, String name) {
        this.age = age;
        this.name = name;
    }
​
}
public class TestDemo {
    public static void main(String[] args) {
        Map<Person,String> map = new HashMap<>();
        map.put(new Person(15,"张三"),"zs");
        System.out.println(map.get(new Person(15,"张三")));
    }
}
           

输出:null

（2）覆写后

class Person{
    private Integer age;
    private String name;
​
    public Person(Integer age, String name) {
        this.age = age;
        this.name = name;
    }
​
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return this.age.equals(person.age) &&
                this.name.equals(person.name);
    }
​
    @Override
    public int hashCode() {
​
        return Objects.hash(age, name);
    }
}
public class TestDemo {
    public static void main(String[] args) {
        Map<Person,String> map = new HashMap<>();
        map.put(new Person(15,"张三"),"zs");
        System.out.println(map.get(new输出 Person(15,"张三")));
    }
}
           

输出：zs