4-Map接口

1. Map接口体系

|----Map: since JDK1.2  双列数据，存储key-value对的数据

        |----HashMap: since JDK1.2 作为Map的主要实现类；线程不安全的，效率高；可存储null的key和value

             |----子类 LinkedHashMap: since JDK1.4， 保证在遍历map元素时，可以按照添加的顺序实现遍历。

                     原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。

                     对于频繁的遍历操作，此类执行效率高于HashMap。

        |----TreeMap: since JDK1.2 保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序

                     底层使用红黑树

        |----Hashtable: since JDK1.0 作为古老的实现类；线程安全的，效率低；不能存储null的key和value

             |----子类 Properties:常用来处理配置文件。key和value都是String类型

     HashMap的底层：数组+链表   （jdk7及之前）

                                   数组+链表+红黑树  （jdk 8）

Map结构的理解：

   Map中的key:无序的、不可重复的，使用Set存储所有的key  ---> key所在的类要重写equals()和hashCode() （以HashMap为例）

   Map中的value:无序的、可重复的，使用Collection存储所有的value --->value所在的类要重写equals() containsValue方法会使用equals

   一个键值对：key-value构成了一个Entry对象。

   Map中的entry:无序的、不可重复的，使用Set存储所有的entry

 Map与Collection并列存在。用于保存具有映射关系的数据:key-value

 Map 中的 key 和 value 都可以是任何引用类型的数据

 Map 中的 key 用Set来存放， 不允许重复，即同一个 Map 对象所对应的类，须重写hashCode()和equals()方法

 常用String类作为Map的“键”

 key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value

 Map接口的常用实现类： HashMap、 TreeMap、 LinkedHashMap和Properties。 其中， HashMap是 Map 接口使用频率最高的实现类

2.  JDK7 HashMap

HashMap的底层实现原理？以jdk7为例说明：

     HashMap map = new HashMap():

     在实例化以后，底层创建了长度是16的一维数组 Entry[] table。

     ...多次put之后...

     map.put(key1,value1):

     首先，调用key1所在类的hashCode()计算key1哈希值，此哈希值（比较大）经过某种算法（哈希函数、散列函数）计算以后，得到在Entry数组中的存放位置。

     如果此位置上的数据为空，此时的key1-value1（Entry）添加成功。 ----情况1

     如果此位置上的数据不为空，(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据的哈希值：

             如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1（Entry）添加成功。----情况2

             如果key1的哈希值和已经存在的某一个数据(key2-value2,Entry)的哈希值相同，继续比较：调用key1所在类的equals(key2)方法，比较（不同的对象可能存在hash值相同的情况）

                     如果equals()返回false:此时key1-value1添加成功。----情况3

                     如果equals()返回true:使用value1替换value2。

      补充：关于情况2和情况3：此时key1-value1和原来的数据以链表的方式存储。

在不断的添加过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

部分源码分析：

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;

    this.loadFactor = loadFactor;
    // 临界值 = 容量 * 加载因子， 初始状态是 16 * 0.75
    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 初始状态长度为16的 Entry数组
    table = new Entry[capacity];
    useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    init();
}

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    // 获取 key 对象的 hash值
    int hash = hash(key);
    // 通过hash值，获取该key在数组中的下标
    int i = indexFor(hash, table.length);
    // i位置有数据
    for (Entrye = table[i]; e != null; e = e.next) {
        Object k;
        // 先判断 hash 值是否相等，如果所有的元素跟要添加的元素，hash值不相等，那么跳出循环，添加元素
        // 如果hash值相等，那么判断地址是否一样，然后判断两个对象是否equals
        // 如果地址都一样，那么进入if，替换原有key对应的的value
        // 如果地址不一样，但是equals返回true，说明两个对象相等， 那么也替换原有key对应的value
        // 如果所有的hash值相等，但是equals都不相等，那么就需要添加这个 Entry
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // i位置没有数据， 那么直接可以添加 Entry 元素
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
       // 如果要添加元素的位置为空，那么可以添加
       // 如果大于等于临界值，并且要添加的位置不为空，那么就扩容为原来的2倍
       if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    // 不需要扩容那么 重新创建 Entry
    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entrye = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

3.  JDK 8 HashMap

jdk8 相较于jdk7在底层实现方面的不同：

     1. new HashMap():底层没有创建一个长度为16的数组

     2. jdk 8底层的数组是：Node[],而非 Entry[]，其实内容一样

     3. 首次调用put()方法时，底层创建长度为16的数组

     4. jdk7底层结构只有：数组+链表。jdk8中底层结构：数组+链表+红黑树。

        4.1 形成链表时，七上八下（jdk7:新的元素指向旧的元素。jdk8：旧的元素指向新的元素）

         4.2 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所数据改为使用红黑树存储。

     HashMap map = new HashMap():

     在实例化以后，底层只是初始化了一个加载因子 this.loadFactor = DEFAULT_LOAD_FACTOR; ，该值为0.75，

     首次map.put(key1,value1):底层初始化一个长度为 16 的 Node数组

多次put之后...

     首先，调用key1所在类的hashCode()计算key1哈希值，此哈希值（比较大）经过某种算法（哈希函数、散列函数）计算以后，得到在Node数组中的存放位置(也就是常说的hash bucket)。

     如果此位置上的数据为空，此时的key1-value1（Node）添加成功（需要判断是否满足转换为红黑树的条件）

     如果此位置上的数据不为空，(意味着此位置上存在一个或多个数据(以链表或树形式存在)),比较key1和已经存在的一个或多个数据

     的哈希值：

             如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1（Entry）添加成功。（需要判断是否满足转换为红黑树的条件）

             如果key1的哈希值和已经存在的某一个数据(key2-value2,Entry)的哈希值相同，继续比较：调用key1所在类的equals(key2)方法，比较：（不同的对象可能存在hash值相同的情况）

                     如果equals()返回false:此时key1-value1添加成功

                     如果equals()返回true:使用value1替换value2

在不断的添加过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

DEFAULT_INITIAL_CAPACITY : HashMap 的默认容量，16

     DEFAULT_LOAD_FACTOR：HashMap 的默认加载因子：0.75，兼顾了数组的利用率，也兼顾了链表不能太长

     threshold：扩容的临界值，= 容量 * 填充因子：16 * 0.75 => 12

     TREEIFY_THRESHOLD： Bucket 中链表长度大于该默认值，转化为红黑树: 8

     MIN_TREEIFY_CAPACITY：桶中的 Node 被树化时最小的 hash 表容量 : 64

部分源码分析：

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// hash(key) 获取hash值
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Nodep; int n, i;
    // 首次的时候 数组的大小为16，临界值为 12
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
        
    // i 要存放的数组的索引位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果是null， 添加元素成功
        tab[i] = newNode(hash, key, value, null);
    else {
        Nodee; K k;
        // 如果 hash值相等，或者是同一个对象，或者equals返回true，那么即将添加的元素已有， 走下面的替换逻辑
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 是一个 红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        // 是链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表长度大于8 的时候，可能需要转换为红黑树， treeifyBin中还会判断是否转换为红黑树 treeifyBin
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果跟链表上的元素比较的时候，元素相同，那么跳出循环，下面走替换逻辑
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 替换逻辑
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}


final Node[] resize() {
    Node[] oldTab = table;
    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
        // 首次分别是 16 和 12 ， 加载因子 0.75 
        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[] newTab = (Node[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Nodee;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    NodeloHead = null, loTail = null;
                    NodehiHead = null, hiTail = null;
                    Nodenext;
                    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;
}


final void treeifyBin(Node[] tab, int hash) {
    int n, index; Nodee;
    // 如果数组的长度为 小于 64，数组扩容， 大于等于 64，转换为红黑树
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNodehd = null, tl = null;
        do {
            TreeNodep = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

4. LinkedHashMap的底层实现

能够记录元素添加的先后顺序，遍历的时候，按顺序遍历

在HashMap基础上增加了 before 和 after 的引用

static class Entryextends HashMap.Node{
    Entrybefore, after;
    Entry(int hash, K key, V value, Nodenext) {
        super(hash, key, value, next);
    }
}

5.CurrentHashMap 分段锁

6. Map中常用的方法

总结：常用方法：

添加：put(Object key,Object value)

删除：remove(Object key)

修改：put(Object key,Object value)

查询：get(Object key)

长度：size()

遍历：keySet() / values() / entrySet()

6.1 添加、删除、修改操作

Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中

void putAll(Map m):将m中的所有key-value对存放到当前map中

Object remove(Object key)：移除指定key的key-value对，并返回value

void clear()：清空当前map中的所有数据

//MapMethodTest.java
package com.ylaihui.mapitf;

import java.util.HashMap;

public class MapMethodTest {
    public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put("111","aaa");
        map.put("222","bbb");
        map.put("333","ccc");
        map.put("444","ddd");
        map.put("222","eee");

        System.out.println(map);  // {111=aaa, 222=eee, 333=ccc, 444=ddd}

        HashMap map1 = new HashMap();
        map1.put("111","abc");
        map1.put("222","abc");

        map.putAll(map1);
        System.out.println(map);  // {111=abc, 222=abc, 333=ccc, 444=ddd}

        map.remove("111");
        System.out.println(map);  // {222=abc, 333=ccc, 444=ddd}

        map.clear();
        System.out.println(map.size()); // 0
    }
}

6.2 元素查询的操作

Object get(Object key)：获取指定key对应的value

boolean containsKey(Object key)：是否包含指定的key

boolean containsValue(Object value)：是否包含指定的value

int size()：返回map中key-value对的个数

boolean isEmpty()：判断当前map是否为空

boolean equals(Object obj)：判断当前map和参数对象obj是否相等

//MapMethodTest2.java
package com.ylaihui.mapitf;

import java.util.HashMap;

public class MapMethodTest2 {
    public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put("111","aaa");
        map.put("222","bbb");
        map.put("333","ccc");
        map.put("444","ddd");

        Object obj = map.get("333");
        System.out.println(obj);  // ccc

        boolean b = map.containsKey("111");
        System.out.println(b);  // true

        b = map.containsValue("ccc");
        System.out.println(b);  // true

        System.out.println(map.size()); // 4

        System.out.println(map.isEmpty());  // false

        HashMap map1 = new HashMap();
        map1.put("333","ccc");
        map1.put("111","aaa");
        map1.put("222","bbb");
        map1.put("444","ddd");

        System.out.println(map.equals(map1)); // true
    }
}

6.3 Map的遍历操作

Set keySet()：返回所有key构成的Set集合

Collection values()：返回所有value构成的Collection集合

Set entrySet()：返回所有key-value对构成的Set集合

//MapMethodTest3.java
package com.ylaihui.mapitf;

import java.util.*;

public class MapMethodTest3 {
    public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put("111","aaa");
        map.put("222","bbb");
        map.put("333","ccc");

        // 通过 Set 集合遍历 所有的key， 通过key获取 value
        Set set = map.keySet();
        Iterator it = set.iterator();
        while(it.hasNext()){
            Object next = it.next();
            Object value = map.get(next);
            System.out.println("key:" + next + ", value:" + value);
        }

        // 遍历所有的value
        Collection values = map.values();
        Iterator iterator = values.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }

        // 遍历所有的 Entry，通过Entry的getKey 和 getValue获取 k-v
        Set set1 = map.entrySet();
        Iterator it1 = set1.iterator();
        while (it1.hasNext()){
            Object next = it1.next();
            //System.out.println(next.getClass());
            Map.Entry next1 = (Map.Entry) next;
            System.out.println(next1.getKey() + ":" + next1.getValue());
        }
    }
}
/*
key:111, value:aaa
key:222, value:bbb
key:333, value:ccc
aaa
bbb
ccc
111:aaa
222:bbb
333:ccc
 */

7. TreeMap的使用-自然排序

涉及到排序

可自然排序和定制排序

向TreeMap中添加key-value，要求key必须是由同一个类创建的对象

因为要按照key进行排序：自然排序 、定制排序

注意： 不能按照value排序

//LinkedHashMapTest.java
package com.ylaihui.mapitf;

import java.util.*;

class Order implements Comparable{
    int id;
    Date date;

    @Override
    public String toString() {
        return "Order{" +
                "id=" + id +
                ", date=" + date +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Order order = (Order) o;
        return id == order.id &&
                Objects.equals(date, order.date);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, date);
    }

    public Order(int id, Date date) {
        this.id = id;
        this.date = date;
    }

    public Order() {
    }

    @Override
    public int compareTo(Object o) {
        if(o instanceof Order){
            Order order = (Order) o;
            return this.id - order.id;
        }else
            throw new RuntimeException("不能比较的类型");
    }

}

public class LinkedHashMapTest {
    public static void main(String[] args) {
        LinkedHashMap map = new LinkedHashMap();

        Order o1 = new Order(111, new Date());
        Order o2 = new Order(222, new Date());
        Order o3 = new Order(333, new Date());
        Order o4 = new Order(444, new Date());

        map.put(o1,"o1");
        map.put(o2,"o2");
        map.put(o3,"o3");
        map.put(o4,"o4");

        Set set = map.entrySet();
        Iterator it = set.iterator();
        while (it.hasNext()){
            Object next = it.next();
            Map.Entry entry = (Map.Entry) next;
            System.out.println( entry.getKey() +":"+entry.getValue());
        }

    }
}

8.TreeMap的使用-定制排序

//TreeMapTest1.java
package com.ylaihui.mapitf;

import java.util.*;

class Book{
    int id;
    String name;

    @Override
    public String toString() {
        return "Book{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Book book = (Book) o;
        return id == book.id &&
                Objects.equals(name, book.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }

    public Book(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public Book() {
    }
}
public class TreeMapTest1 {
    public static void main(String[] args) {
        TreeMap map = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Book && o2 instanceof Book){
                    Book b1 = (Book) o1;
                    Book b2 = (Book) o2;
                    return -Integer.compare(b1.id, b2.id);
                }
                else
                    throw new RuntimeException("不能比较的类型");
            }
        });

        Book b1 = new Book(111, "ylaihui");
        Book b2 = new Book(222, "ylaihui");
        Book b3 = new Book(555, "ylaihui");
        Book b4 = new Book(444, "ylaihui");

        map.put(b1,"ylaihui1");
        map.put(b2,"ylaihui2");
        map.put(b3,"ylaihui3");
        map.put(b4,"ylaihui4");

        Set set = map.entrySet();
        Iterator it = set.iterator();
        while (it.hasNext()){
            Object next = it.next();
            Map.Entry entry = (Map.Entry) next;
            System.out.println(entry.getKey() +":"+entry.getValue());
        }
    }
}
/*
Book{id=555, name='ylaihui'}:ylaihui3
Book{id=444, name='ylaihui'}:ylaihui4
Book{id=222, name='ylaihui'}:ylaihui2
Book{id=111, name='ylaihui'}:ylaihui1
 */

9. Hashtable

 Hashtable是个古老的 Map 实现类， JDK1.0就提供了。不同于HashMap，Hashtable是线程安全的。

 Hashtable实现原理和HashMap相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用。

 与HashMap不同， Hashtable 不允许使用 null 作为 key 和 value

 与HashMap一样， Hashtable 也不能保证其中 Key-Value 对的顺序

 Hashtable判断两个key相等、两个value相等的标准， 与HashMap一致。

10. Properties的使用

Properties 类是 Hashtable 的子类，该对象用于处理属性文件

由于属性文件里的 key、 value 都是字符串类型，所以 Properties 里的 key和 value 都是字符串类型

存取数据时，建议使用setProperty(String key,String value)方法和getProperty(String key)方法

Properties:常用来处理配置文件。key和value都是String类型

jdbc.properties

name=root 

password=12345678

//PropertiesTest.java
package com.ylaihui.mapitf;

import java.io.FileInputStream;
import java.io.IOException;
import java.util.Properties;

public class PropertiesTest {
    public static void main(String[] args) {
        Properties pr = new Properties();

        try {
            pr.load(new FileInputStream("jdbc.properties"));
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
        }

        System.out.println(pr.getProperty("name"));
        System.out.println(pr.getProperty("password"));
    }
}