java集合相关知识（二）

Map接口

 

1、map的常用实现类：HashMap、TreeMap

2、HashMap（重要）

      面试常问的：下一章专门总结

3、Map的四中遍历方法及效率

package com.test.CollectionTest;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

public class HashMapDemo {
    public static void main(String[] args) {
        Map<String,Integer> map = new HashMap<String,Integer>();
        map.put("a",1);
        map.put("b",2);
        map.put("c",3);
        map.put("d",4);
        //map的四种遍历方式
        //方式一：根据key值，在get到value值，时间成本最高主要因为map.get(key),
        // get的时间成本主要取决于for循环的次数，如果hash值散列不好的情况下，时间成本会更高
        Set<String> keys = map.keySet();
        for(String key:keys){
            System.out.println(key+"="+map.get(key));
        }
        System.out.println("==============================");
        //方式二：增强for循环
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        for(Map.Entry<String, Integer> o :entries){
            System.out.println(o.getKey()+"="+o.getValue());
        }
        System.out.println("==============================");
        //方式三：迭代器   与方式二的时间成本差不多
        Iterator<Map.Entry<String, Integer>> iterator = entries.iterator();
        while(iterator.hasNext()){
            Map.Entry<String, Integer> next = iterator.next();
            System.out.println(next.getKey()+"="+next.getValue());
        }
        System.out.println("==============================");
        //方式四：只能得到value值
        Collection<Integer> values = map.values();
        for(Integer value :values){
            System.out.println(value);
        }
    }
}

方法一造成时间成本主要在于map.get(key);,  先看一下keyset方法和entrySet方法

final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }





final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

　　除了返回值不同，父类相同，性能差不多，只不过方法一多了一步map.get(key);   再来看一下get（key)

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

　如果hash散列值很差，导致数组某个位置的链表长，则查找的效率会变低 

总结：

       a、如果只想得到value值，用方法四；

       b、如果只想要key值，用方法一，无须map.get(key);

       c、方法二跟方法三效率差不多，均可；

4、HashMap与HashTable的区别：

       HashMap线程不安全，效率高；HashTable线程安全，效率低；

       HashTable允许key-value为null，HashTable不允许；

       1.8之后HashMap加了红黑树，HashTable没变；