Java中的Map集合

Java中的Map集合
一，map集合的特点

（1）map是一个双列集合，一个元素中包含两个值（key—Value）。

（2）map集合中的键与值存在映射关系，key（键）唯一，value（值）允许重复

（3）无序，无索引

二，map集合的常用方法

(1)put方法

V put(K key, V value) （可以相同的key值，但是添加的value值会覆盖前面的，返回值是前一个，如果没有就返回null）

      Map map = new HashMap();
       map.put("blue",1);
       map.put("white",3);
       map.put("yellow",3);

(2)remove方法

删除关联对象，指定key对象

Map map = new HashMap();
       map.put("blue",1);
       map.put("white",2);
       map.put("yellow",3);
//指定键值对进行删除
       map.remove("blue", 1);

(3)clear方法

清空集合对象

        Map map = new HashMap();
       map.put("blue",1);
       map.put("white",2);
       map.put("yellow",3);

//清除map中所有元素
       map.clear();

(4)获取

value get(key); 可以用于判断键是否存在的情况。当指定的键不存在的时候，返回的是null。

Map map = new HashMap();
       map.put("blue",1);
       map.put("white",2);
       map.put("yellow",3);
//根据键，获取键映射的值
       map.get("blue");
       System.out.println(map.get("blue"));

(5)长度

获取map集合中键值对的个数：

Map map = new HashMap();
       map.put("blue",1);
       map.put("white",2);
       map.put("yellow",3);

       int s =map.size();
       System.out.println(s);

(6)判断
1. boolean isEmpty() 长度为0返回true否则false
2. boolean containsKey(Object key) 判断集合中是否包含指定的key
3. boolean containsValue(Object value) 判断集合中是否包含指定的value
三，map集合的遍历方式

（1）使用keyset（）方法，通过Set的迭代器取出Set集合中的每一个元素（Iterator）就是Map集合中的所有的键，再通过get方法获取键对应的值。

Map map = new HashMap();
       map.put("blue",1);
       map.put("white",2);
       map.put("yellow",3);
       for(String key : map.keySet()) {
           Integer value = map.get(key);
           System.out.println(key+"="+value);
       }

（2）使用Entry对象遍历

        Map.Entry,在Map接口中有一个内部接口Entry（内部类）

        作用：当集合一创建，就会在Map集合中创建一个Entry对象，用来记录键与值（键值对对象，键值的映射关系）、

        Map map = new HashMap();
       map.put("blue",1);
       map.put("white",2);
       map.put("yellow",3);

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

四，map集合的常用实现类

1.HashMap

（1）HashMap的特点
- hashmap存取是无序的
- 键和值位置都可以是null，但是键位置只能是一个null
- 键位置是唯一的，底层的数据结构是控制键的
- hashmao按照key的hash值计算数组中储存下标的位置，计算方式：（n-1）*hash
- jdk1.8前数据结构是：链表+数组 jdk1.8之后是：数组+链表+红黑树
- 阈值（边界值）>8并且数组长度大于64，才将链表转换成红黑树，变成红黑树的目的是提高搜索速度，高效查询
- HashMap线程不安全，多线程下扩容容易死循环，多线程下put可能会数据覆盖，put与get并发时，可能导致get为null
（2）扩容方式

【初始容量】：当添加第一个元素时，hashmap默认的初始数组大小为16，通过位移运算1<<4得出，数组长度为2^n。

【加载因子】：用来描述hashmap集合中元素的填满程度，默认为0.75f。

【扩容方法】：resize（）

【扩容条件】：HashMap中的元素超过扩容阈值（当前数组容量x加载因子）时，数组扩容为原数组的两倍。或者加入新元素时，如果链表长度大于8，会将当前链表转为红黑树，再转为红黑树之前，会判断数组长度，如果数组长度小于64，会发生扩容，如果数组长度大于64，则正常转为红黑树。

（3）put过程

当新添加一个KV键值对元素时，通过该元素的key的hash值，计算该元素在数组中应该保存的下标位置。如果该下标位置已经在其他的Node对象（产生哈希冲突），则采用链地址法处理，即将新元素封装成一个新的Node对象，插入到该下标位置的链表尾部（尾插法）。当链表的长度超过8并且数组长度大于64时，为了避免查找性能下降，该链表会转化成黑红树。

解决哈希冲突的常见方法：

1.链地址法：哈希表中的每个Node节点都有一个Next指针，构成一个单向链表，被分配到同一个下标位置上的多个Node节点（发生哈希冲突），可以通过存入同一个单向链表来解决。

2.开放地址法：一旦发生哈希冲突，就去寻找下一个空的散列地址，只要散列足够大，空的散列集合总能找到，并且记录存入。

3.建立公共溢出区，将哈希表分为基本表和溢出表，凡是和基础表发生哈希冲突的元素，都存入溢出表。

4.再哈希法：也叫双哈希法，有多个不同的哈希函数，当发生哈希冲突时，使用第二个，第三个........，等哈希函数计算地址，等哈希函数计算地址，直到无冲突，缺点就是增加了计算时间。

（4）HashMap中的Hash函数

HashMAori通过新添加元素key的hashCode（）方法，计算一个hash值，然后通过这个hash值计算位置下表。

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

2.LinkedHashMap

HashMap的子类，实现Mao接口，保存了元素的插入顺序，既使用了HashMap的数据结构，又借用了LinkedList的双向列表。LinkedHashMap就是把HashMap中的Node维护成了一个双向链表。
```
public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>{
        transient LinkedHashMap.Entry<K,V> head;
 
        transient LinkedHashMap.Entry<K,V> tail;
        
        final boolean accessOrder;
    }
```
（1）LinkedHashMap的特点：
- key值唯一，不允许重复
- value值允许重复
- 有序
- LinkedHashMap是HashMap的子类
（2）储存结构：数组+链表+红黑树（维护了一个Entry的双向链表，保证了插入顺序）

为了实现双向链表，LinkedHashMap中提供了entry：
```
    /**
     * LinkedHashMap中的node直接继承自HashMap中的Node。并且增加了双向的指针
     */
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
```
（3）LinkedHashMap有序

在hashmap的基础上通过双向链表维护元素节点间的顺序。LinkedHashMap中entry类继承自hashmap中的Node类。entry就是LinkedHashMap中的基本节点组成，其实就是双向链表的节点。

public V get(Object key) {
Node e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}

它的get方法实际上就是HashMap的get方法，再最后判断是多了一个afterNodeAccess方法，

这个accesOrder其实就是控制节点在linkedHashmap
- 如果是true，基于访问顺序。
- 如果是false，就按插入顺序排列。
如此，就实现了LinkedeHashMap的有序。

3.TreeMap

TreeMap继承了NavigableMap接口，NavigableMap接口继承了SortedMap接口，可支持一系列的导航定位以及导航操作的方法.TreeMap实现了Cloneable接口，可被克隆，实现了Serializable接口，可序列化；TreeMap因为是通过红黑树实现，红黑树结构天然支持排序，默认情况下通过Key值的自然顺序进行排序；

（1）TreeMap的特点：
- key值唯一，不允许重复
- Value值允许重复
- 按照key自动排序
- AbsttactMap的子类
（2）储存结构：红黑树（树中的每个节点都是一个Entry内部类的对象）

（3）TreeMap的构造函数

//默认构造函数，按照key的自然顺序排列
public TreeMap() {comparator = null;}

//传递Comparator具体实现，按照该实现规则进行排序
public TreeMap(Comparator comparator) {this.comparator = comparator;}

//传递一个map实体构建TreeMap,按照默认规则排序
public TreeMap(Map m) {
comparator = null;
putAll(m);
}

//传递一个map实体构建TreeMap,按照传递的map的排序规则进行排序
public TreeMap(SortedMap m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}

（4）TreeMap的put方法

put的源码：
```
/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     *
     * @return the previous value associated with {@code key}, or
     *         {@code null} if there was no mapping for {@code key}.
     *         (A {@code null} return can also indicate that the map
     *         previously associated {@code null} with {@code key}.)
     * @throws ClassCastException if the specified key cannot be compared
     *         with the keys currently in the map
     * @throws NullPointerException if the specified key is null
     *         and this map uses natural ordering, or its comparator
     *         does not permit null keys
     */
    public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check
 
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
```
4.HashTable

散列表（也叫哈希表），是根据Key-Value的直接访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录（类似索引），以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

（1）HashTable的特点：
- key值唯一，不允许重复
- Value值允许重复
- Value不允许为空，如果为空，则抛出NUllPointException
- 线程安全，使用了synchronized加锁，但是性能较差
（2）储存结构：数组+链表

（3）哈希表的查找原理：

哈希表就是数组加链表的产物，它继承了数组的查找容易，也继承了链表的插入删除快捷的特点。使用哈希函数将被查找的键转化为数组的索引。在理想的状态下，不同的键会被转化成不同的索引值。但是那是理想状态，我们实践当中是不可能一直是理想状态的。当不同的键生成了相同的索引的时候，也就是我们所说的冲突，我们这个时候就要处理冲突。

（4）put过程：
```
 /**
     * Maps the specified key to the specified
     * value in this hashtable. Neither the key nor the
     * value can be null. 
     *
     * The value can be retrieved by calling the get method
     * with a key that is equal to the original key.
     *
     * @param      key     the hashtable key
     * @param      value   the value
     * @return     the previous value of the specified key in this hashtable,
     *             or null if it did not have one
     * @exception  NullPointerException  if the key or value is
     *               null
     * @see     Object#equals(Object)
     * @see     #get(Object)
     */
    public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }
 
        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
 
        addEntry(hash, key, value, index);
        return null;
    }
```
（5）HashMap和Hashtable的区别
- 线程安全：HashMap是线程非安全的，而HashTable是线程安全的（内部的方法基本都使用了synchronized修饰）。
- 执行效率：HashMap比HashTable效率高一点。
- 对Null key 和 Null value的支持：HashMap可以储存null的key和value，但null作为键只能有一个，作为值可以有多个，HashTable不允许有null键和null值，否则抛出NullPointException。
- 数据结构：JDK1.8之后的的HashMap在解决哈希冲突时，当链表长度的=大于阈值（默认为8）并且数组长度大于64，链表转化为红黑树，以减少搜索时间。所以，HashMap底层采用数组+链表+红黑树，而HashTable没有这样的机制，仅采用数组+链表。
- 扩容方式：如果不指定初始容量，Hashtable的默认初始大小为11，之后每次扩容，容量变为原来的2n+1.HashMap的默认初始容量为16，之后每次扩容，都变为原数组的2倍。
- 指定容量：创建时如果给定了初始容量，Hashtable会按照指定容量创建，而HashMap会将其扩容为2倍。
5.ConcurrentHashMap

ConcurrentHashMap是一个支持高并发更新与查询的哈希表(类似HashMap)。在保证安全的前提下，查询不需要锁定。与HashTable不同，该类不依赖于ConcurrentHashMap去保证线程操作的安

全。

在JDK1.8之后，采用数组+链表+红黑树，使用synchronized和CAS进行并发控制。Java 8 在链表长度超过阈值（8）并且数组长度大于64时，将链表转换为红黑树；synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍；
相关阅读:
安全防御（一）--- 防火墙基础
 Bag of Tricks for Efficient Text Classification（FastText）
QT最小化到托盘显示
 记录 android studio 通过安装NDK 编译C文件，得到需要的so文件
 CanvasScaler计算方法
 【数据结构】数组和广义表
 sql 常用命令-----增删查改
 SpriteKit与Swift配合：打造您的第一个简易RPG游戏的步骤指南
 鸿蒙4.0正式版升级机型
 Python算法——快速排序
原文地址：https://blog.csdn.net/weixin_54535063/article/details/126903035

一，map集合的特点

（1）map是一个双列集合，一个元素中包含两个值（key—Value）。

（2）map集合中的键与值存在映射关系，key（键）唯一，value（值）允许重复

（3）无序，无索引

二，map集合的常用方法

(1)put方法

(2)remove方法

(3)clear方法

(4)获取

(5)长度

(6)判断

三，map集合的遍历方式

四，map集合的常用实现类

1.HashMap

（1）HashMap的特点

（2）扩容方式

【初始容量】：当添加第一个元素时，hashmap默认的初始数组大小为16，通过位移运算1<<4得出，数组长度为2^n。

【加载因子】：用来描述hashmap集合中元素的填满程度，默认为0.75f。

【扩容方法】：resize（）

（3）put过程

（4）HashMap中的Hash函数

2.LinkedHashMap

HashMap的子类，实现Mao接口，保存了元素的插入顺序，既使用了HashMap的数据结构，又借用了LinkedList的双向列表。LinkedHashMap就是把HashMap中的Node维护成了一个双向链表。

（1）LinkedHashMap的特点：

（2）储存结构：数组+链表+红黑树（维护了一个Entry的双向链表，保证了插入顺序）

（3）LinkedHashMap有序

3.TreeMap

（1）TreeMap的特点：

（2）储存结构：红黑树（树中的每个节点都是一个Entry内部类的对象）

（3）TreeMap的构造函数

（4）TreeMap的put方法

put的源码：

4.HashTable

（1）HashTable的特点：

（2）储存结构：数组+链表

（3）哈希表的查找原理：

（4）put过程：

（5）HashMap和Hashtable的区别

5.ConcurrentHashMap