Java集合之Map

Java集合之Map

Map关系图如下

java-Map关系图.jpg

• 虚线为接口
• 实线为类

Map特点

1. 键值对格式
2. key唯一

Map实现类之HashMap

1. 从如下代码可看出以下特点
   • 无序(链表结构)
   • key,value均可为null
   • key唯一

    public static void main(String[] args) {
        Map<Integer,String> map = new HashMap<Integer,String>(4);
        map.put(1,"felix");
        map.put(2,"felix");
        map.put(3,"fei");
        map.put(3,"peng");
        map.put(4,null);
        map.put(null,null);
        Set<Integer> keySet = map.keySet();      // 1.获取Map的键集
        Iterator<Integer> it = keySet.iterator();
        while(it.hasNext()){
            Integer key = it.next();        // 2.获取每一个键
            String value = map.get(key);    // 3.获取每一个键对应的键值
            System.out.println(key + ":" + value);
        }
    }

• 控制台结果

null:null
1:felix
2:felix
3:peng
4:null

2. 从如下源码中可看出HashMap的扩容倍数为0.75

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

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

3. 默认初始容量为16,最大容量为1*2的30次方

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

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

• 从如上代码中可看出HashMap是由最大容量限制的,如果超出就会出现内存溢出的问题.

4. 从如下put方法源码来观察非线程安全

 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<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)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);
                        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;
    }

• 从put方法中可看出没有使用synchronized关键字、使用锁、CAS等线程安全的操作,所以多线程操作时会引起线程安全问题.

5. 从如下get方法源码观察非线程安全

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

• 从如上源码未看到有关线程安全方面的处理.

6. 那么如何保证HashMap的线程安全

   1. 使用synchronized关键字修饰方法

    HashMap<Integer,String> map = new HashMap<Integer,String>(4);
   
   public static void main(String[] args) {
       Test test = new Test();
       test.putMap();
   }
   // synchronized 添加在方法上
   public synchronized void putMap(){
       map.put(1,"felix");
       map.put(2,"felix");
       map.put(3,"fei");
       map.put(3,"peng");
       map.put(4,null);
       map.put(null,null);
   }
   

   2. 使用synchronized修饰代码块

       public static void main(String[] args) {
       Test test = new Test();
       test.putMap();
   }
   // synchronized 修饰代码块
   public  HashMap<Integer, String> putMap(){
       synchronized(this){
           HashMap<Integer,String> map = new HashMap<Integer,String>(4);
           map.put(1,"felix");
           map.put(2,"felix");
           map.put(3,"fei");
           map.put(3,"peng");
           map.put(4,null);
           map.put(null,null);
           return map;
       }
   }
   

   3.使用ReentrantLock可重入锁控制hashMap的插入

       HashMap<Integer,String> map = new HashMap<Integer,String>(4);
   public static void main(String[] args) {
       Test test = new Test();
       test.putMap();
   }
   public void putMap(){
       ReentrantLock rl=new ReentrantLock();
       try{
           rl.lock();
           map.put(1,"felix");
           map.put(2,"felix");
           map.put(3,"fei");
           map.put(3,"peng");
           map.put(4,null);
           map.put(null,null);
       }finally {
           rl.unlock();
       }
   }
   

7. 使用JDK提供的线程安全的HashMap

   1. synchronizedMap

   public static void main(String[] args) {
       HashMap<Integer,String> map = new HashMap<Integer,String>(4);
       map.put(1,"felix");
       map.put(2,"felix");
       map.put(3,"fei");
       map.put(3,"peng");
       map.put(4,null);
       map.put(null,null);
       Map<Integer, String> synMap = Collections.synchronizedMap(map);
       System.out.println(synMap);
   }
   

   2. 且看如下源码,使用其静态方法synchronizedMap,传入一个Map对象

   public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
       return new SynchronizedMap<>(m);
   }
   

   3.返回的synchronizedMap对象,其构造方法如下

   private final Map<K,V> m;     // Backing Map
       final Object      mutex;        // Object on which to synchronize
   
       SynchronizedMap(Map<K,V> m) {
           this.m = Objects.requireNonNull(m);
           mutex = this;
       }
   

   4.关于mutex可查看get和put方法

   public V get(Object key) {
           synchronized (mutex) {return m.get(key);}
       }
   
       public V put(K key, V value) {
           synchronized (mutex) {return m.put(key, value);}
       }
   

   5.从如上代码中可看出SynchronizedMap是使用Synchronized关键字实现的.

8. 使用java.util.concurrent包下的ConcurrentHashMap

   1. 使用方式

       ConcurrentHashMap<Integer, String> conHashMap = new ConcurrentHashMap<>();
   

   2. 看其源码构造方法,可知容量为16

   /**
    * Creates a new, empty map with the default initial table size (16).
    */
   public ConcurrentHashMap() {
   }
   

   3.看其源码put/get方法

   public V put(K key, V value) {
       return putVal(key, value, false);
   }
   
   /** Implementation for put and putIfAbsent */
   final V putVal(K key, V value, boolean onlyIfAbsent) {
       if (key == null || value == null) throw new NullPointerException();
       int hash = spread(key.hashCode());
       int binCount = 0;
       for (Node<K,V>[] tab = table;;) {
           Node<K,V> f; int n, i, fh;
           if (tab == null || (n = tab.length) == 0)
               tab = initTable();
           else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
               if (casTabAt(tab, i, null,
                            new Node<K,V>(hash, key, value, null)))
                   break;                   // no lock when adding to empty bin
           }
           else if ((fh = f.hash) == MOVED)
               tab = helpTransfer(tab, f);
           else {
               V oldVal = null;
               synchronized (f) {
                   if (tabAt(tab, i) == f) {
                       if (fh >= 0) {
                           binCount = 1;
                           for (Node<K,V> e = f;; ++binCount) {
                               K ek;
                               if (e.hash == hash &&
                                   ((ek = e.key) == key ||
                                    (ek != null && key.equals(ek)))) {
                                   oldVal = e.val;
                                   if (!onlyIfAbsent)
                                       e.val = value;
                                   break;
                               }
                               Node<K,V> pred = e;
                               if ((e = e.next) == null) {
                                   pred.next = new Node<K,V>(hash, key,
                                                             value, null);
                                   break;
                               }
                           }
                       }
                       else if (f instanceof TreeBin) {
                           Node<K,V> p;
                           binCount = 2;
                           if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                          value)) != null) {
                               oldVal = p.val;
                               if (!onlyIfAbsent)
                                   p.val = value;
                           }
                       }
                   }
               }
               if (binCount != 0) {
                   if (binCount >= TREEIFY_THRESHOLD)
                       treeifyBin(tab, i);
                   if (oldVal != null)
                       return oldVal;
                   break;
               }
           }
       }
       addCount(1L, binCount);
       return null;
   }
   

   3. 从如上put/get源码可看出ConcurrentHashMap也是使用Synchronized关键字实现的.

Map实现类之Hashtable

1. 从如下代码中可看出Hashtable特点
   • key不可为null
   • value不可为null
   • 无序
   • key唯一

    public static void main(String[] args) {
        Map<Integer, String> map = new Hashtable<>(4);
        map.put(1,"felix");
        map.put(2,"felix");
        map.put(3,"fei");
        map.put(3,"peng");
        //map.put(4,null); value不可为null
        //map.put(null,"peng"); key不可为null
        System.out.println(map);
    }

• 控制台结果

{3=peng, 2=felix, 1=felix}

2. 从如下源码可看出Hashtable的数据结构为Entry<?,?>数组

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

    /**
     * The hash table data.
     */
    private transient Entry<?,?>[] table;

• Entry是HashTable.class的一个内部类

3. 从如下构造方法源码中可看出Hashtable的初始化数组大小11和扩容倍数为0.75

/**
    /**
     * Constructs a new, empty hashtable with a default initial capacity (11)
     * and load factor (0.75).
     */
    public Hashtable() {
        this(11, 0.75f);
    }

4. 从put/get源码中看出,Hashtable为线程安全

    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;
    }

        public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

Map实现类之TreeMap

1. 从如下代码中可看出TreeMap以下特点
   • key唯一
   • key不可为null
   • value可为null
   • 默认升序排序

       public static void main(String[] args) {
       TreeMap<Integer, String> map = new TreeMap<>();
       map.put(1,"felix");
       map.put(3,"fei");
       map.put(3,"peng");
       map.put(2,"felix");
       map.put(4,null);
       //map.put(null,"peng"); key不可为null
       System.out.println(map);
   }
   

   • 控制台结果

   {1=felix, 2=felix, 3=peng, 4=null}
   

2. 从如下get/put源码可看出TreeMap非线程安全

    public V get(Object key) {
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }

        final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }

        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;
    }

• 如何使TreeMap变为线程安全

        Collections.synchronizedSortedMap(map);

3. 从如下代码可看出TreepMap的迭代器是快速失败的

    public static void main(String[] args) {
        Map<String,Person> map=new TreeMap<String,Person>();
        map.put("tom", new Person(16));
        map.put("jim", new Person(17));
        map.put("zose", new Person(18));
        for(Map.Entry<String, Person> entry:map.entrySet()){
            if(entry.getKey().equals("tom")){
                map.remove("tom");
                System.out.println("find tom");
            }
            else{
                System.out.println(entry.getValue().getAge());
            }
        }
        System.out.println(map.size());
    }
}
class Person{
    int age;
    public Person(int age){
        this.age=age;
    }
    public int getAge(){
        return age;
    }
}

• 控制台结果

17
find tom
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.TreeMap$PrivateEntryIterator.nextEntry(TreeMap.java:1211)
    at java.util.TreeMap$EntryIterator.next(TreeMap.java:1247)
    at java.util.TreeMap$EntryIterator.next(TreeMap.java:1242)
    at com.example.demo.test.Test.main(Test.java:15)

• 正常的代码

Set<String> set=map.keySet();
        Iterator<String> it=set.iterator();
        while(it.hasNext()){
            String key=it.next();
            if(key.equals("tom")){
                it.remove();
                System.out.println("find tom");
            }
            else
            {
                System.out.println(map.get(key).getAge());
            }
        }

• 控制台结果

17
find tom
18

• 从以上代码可看出,TreeMap如果要修改数据结构,必须使用自身的iterator否则会快速失败.

4. HashMap、Hashtable、TreeMap比较图如下

   
   java-HashMap、Hashtable、TreeMap.jpg