Java的Map接口及HashMap、TreeMap、concurrentHashMap

1.Map接口

2.HashMap的遍历方式

（1）keySet（）方法

通过map.keySet()方法进行将所有的key变为一个集合set。然后通过遍历set集合（可以使用foreach或者迭代器）

得到每一个key 然后通过map.get(key)通过map得到value

（2）entrySet（）方法

Entry是一个键值对类型。

通过此方法能得到一个全是entry类型（也就是全为键值对的）集合set

然后我们通过foreach将集合set里面的键值对取出来进行getKey（） getValue（）方法。

 public static void main(String[] args) {
        HashMap<String,String> map=new HashMap<>();
        map.put("ch","中国");
        map.put("uk","英国");
        map.put("us","美国");
        Set<String> kset = map.keySet();
        System.out.println("keySet==========");
        System.out.println("==========1=============");
        for (String s : kset) {
            System.out.println(s+" "+map.get(s));
        }
        System.out.println("==========2=============");
        Iterator<String> iterator = kset.iterator();
        while(iterator.hasNext()){
            String s=iterator.next();
            System.out.println(s+" "+map.get(s));
        }
        System.out.println("entrySet============");
        Set<Map.Entry<String, String>> entries = map.entrySet();
        for (Map.Entry<String,String> s: entries) {
            System.out.println(s.getKey()+" "+s.getValue());
        }

    }

3.map实现类

4.继承结构

5.Node结构（实现了map的Entry接口键值对）

这里面的next是使用哈希表（拉链法）是需要链表。

6.HashMap底层结构及变化

7.插入图例

8.HashMap属性

HashMap的实例有两个参数影响其性能。

　　初始容量：哈希表中桶的数量

　　加载因子：哈希表在其容量自动增加之前可以达到多满的一种尺度

　　当哈希表中条目数超出了当前容量*加载因子(其实就是HashMap的实际容量)时，则对该哈希表进行rehash操作，将哈希表扩充至两倍的桶数。

　　Java中默认初始容量为16，加载因子为0.75。

  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  static final float DEFAULT_LOAD_FACTOR = 0.75f;

　　1）loadFactor加载因子

　　　　定义：loadFactor译为装载因子。装载因子用来衡量HashMap满的程度。loadFactor的默认值为0.75f。loadFactor=size/capacity

　　　　loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0，

　　　　浪费很多空间，这样也不好，所以在hashMap中loadFactor的初始值就是0.75，一般情况下不需要更改它。

   static final float DEFAULT_LOAD_FACTOR = 0.75f;

　　2）桶

　　　　根据前面画的HashMap存储的数据结构图，你这样想，数组中每一个位置上都放有一个桶，每个桶里就是装一个链表，链表中可以有很多个元素(entry)，这就是桶的意思。也就相当于把元素都放在桶中。

　　3）capacity

　　　　capacity译为容量代表的数组的容量，也就是数组的长度，同时也是HashMap中桶的个数。默认值是16。

　　　一般第一次扩容时会扩容到64，之后好像是2倍。总之，容量都是2的幂。

   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

　　4）size的含义

　　　　size就是在该HashMap的实例中实际存储的元素的个数

　　5）threshold的作用

　　　　threshold = capacity * loadFactor，当Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是衡量数组是否需要扩增的一个标准。扩容阈值

　　　　注意这里说的是考虑，因为实际上要扩增数组，除了这个size>=threshold条件外，还需要另外一个条件。

　　　　什么时候会扩增数组的大小？在put一个元素时先size>=threshold并且还要在对应数组位置上有元素，这才能扩增数组。

   int threshold;

　　我们通过一张HashMap的数据结构图来分析：

9.构造方法

　　1）HashMap()

//看上面的注释就已经知道，DEFAULT_INITIAL_CAPACITY=16，DEFAULT_LOAD_FACTOR=0.75
//初始化容量：也就是初始化数组的大小
//加载因子：数组上的存放数据疏密程度。
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

　　2）HashMap(int)

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);//初始容量
    }

　　3）HashMap(int,float)

public HashMap(int initialCapacity, float loadFactor) {
    // 初始容量不能小于0，否则报错
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
    // 初始容量不能大于最大值，否则为最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 填充因子不能小于或等于0，不能为非数字
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    // 初始化填充因子                                        
    this.loadFactor = loadFactor;
    // 初始化threshold大小
    this.threshold = tableSizeFor(initialCapacity);    
}

　　4）HashMap(Map<? extends K, ? extends V> m)

public HashMap(Map<? extends K, ? extends V> m) {
    // 初始化填充因子
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    // 将m中的所有元素添加至HashMap中
    putMapEntries(m, false);
}

　　putMapEntries(Map<? extends K, ? extends V> m, boolean evict)函数将m的所有元素存入本HashMap实例中

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 判断table是否已经初始化
        if (table == null) { // pre-size
            // 未初始化，s为m的实际元素个数
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                    (int)ft : MAXIMUM_CAPACITY);
            // 计算得到的t大于阈值，则初始化阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 已初始化，并且m元素个数大于阈值，进行扩容处理
        else if (s > threshold)
            resize();
        // 将m中的所有元素添加至HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}