Java Map的源码分析

一、概述

一、Map的实现类的结构：
  Map:双列数据，存储key-value对的数据   ---类似于高中的函数：y = f(x)
    HashMap:作为Map的主要实现类；线程不安全的，效率高；存储null的key和value
      linkedHashMap:保证在遍历map元素时，可以按照添加的顺序实现遍历。
          原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
          对于频繁的遍历操作，此类执行效率高于HashMap。
    TreeMap:保证按照添加的key-value对进行排序,实现排序遍历.考虑key的自然排序或定制排序
          底层使用红黑树
    Hashtable:作为古老的实现类；线程安全的，效率低；不能存储null的key和value
      Properties:常用来处理配置文件。key和value都是String类型

  HashMap的底层：数组+链表  （jdk7及之前）
                 数组+链表+红黑树 （jdk 8）

二、HashMap的源码分析 2.1 jdk 7 情况下

    static final int DEFAULT_INITIAL_CAPACITY = 16;

    static final int MAXIMUM_CAPACITY = 1 << 30;

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    transient Entry[] table;

    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    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;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        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);
        int hash = hash(key);
        int i = indexFor(hash, table.length);  // & 与运算符，返回在数组中的索引位置
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

    static int indexFor(int h, int length) {
        return h & (length-1);  // & 与运算符，返回在数组中的索引位置
    }

    void addEntry(int hash, K key, V value, int bucketIndex) {
    //size>=临界值后，判断当前位置是否为空，为空的话就不扩容。直接存放。否则的话就扩容。
        if ((size >= threshold) && (null != table[bucketIndex])) {  
            resize(2 * table.length);//扩容为原来的2倍
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

    void resize(int newCapacity) {//扩容操作
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        transfer(newTable, rehash);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry e = table[bucketIndex];//先把原来位置上元素取出来
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
    
    Entry(int h, K k, V v, Entry n) {
        value = v;
        next = n;//单向列表
        key = k;
        hash = h;
    }

说明：

HashMap的底层实现原理？以jdk7为例说明：
    HashMap map = new HashMap():
    在实例化以后，底层创建了长度是16的一维数组Entry[] table。
    ...可能已经执行过多次put...
    map.put(key1,value1):
    首先，调用key1所在类的hashCode()计算key1哈希值，此哈希值经过某种算法计算以后，
得到在Entry数组中的存放位置。
    如果此位置上的数据为空，此时的key1-value1添加成功。--情况1
    如果此位置上的数据不为空，(意味着此位置上存在一个或多个数据(以链表形式存在)),
比较key1和已经存在的一个或多个数据的哈希值：
       如果key1的哈希值与已经存在的数据的哈希值都不相同,此时key1-value1添加成功.--情况2
       如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同，继续比较：
调用key1所在类的equals(key2)方法，比较：
          如果equals()返回false:此时key1-value1添加成功。--情况3
          如果equals()返回true:使用value1替换value2。

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

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

2.2 jdk 8 情况下

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    static final int MAXIMUM_CAPACITY = 1 << 30;

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    static final int MIN_TREEIFY_CAPACITY = 64;

    transient Node[] table;

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

    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; Node 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 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)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的时候，考虑扩容或者改为树形结构
                        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
            newCap = DEFAULT_INITIAL_CAPACITY;//数组长度16
            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];//新建Node
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                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
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        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; Node e;
        //数组<64长度，进行扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode hd = null, tl = null;
            do {
                TreeNode p = 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);
        }
    }

说明：

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时，
此时此索引位置上的所数据改为使用红黑树存储。

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

面试题：谈谈你对HashMap中put/get方法的认识？如果了解再谈谈 HashMap的扩容机制？默认大小是多少？什么是负载因子( 或填充比)？什么是吞吐临界值(或阈值、threshold)？

面试题：负载因子值的大小，对HashMap有什么影响

1.负载因子的大小决定了HashMap的数据密度。
2.负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长,造成查询或插入时
的比较次数增多，性能会下降。
3.负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的几率越小，数组
中的链表也就越短，查询和插入时比较的次数也越小，性能会更高。但是会浪费一定的内容
空间。而且经常扩容也会影响性能，建议初始化预设大一点的空间。
4.按照其他语言的参考及研究经验，会考虑将负载因子设置为0.7~0.75，此时平均检索长度
接近于常数。

三、linkedHashMap的源码分析

public class linkedHashMap extends HashMap implements Map {
...
    static class Entry extends HashMap.Node {
        Entry before, after;//能够记录添加的元素的先后顺序
        Entry(int hash, K key, V value, Node next) {
            super(hash, key, value, next);
        }
    }

    transient linkedHashMap.Entry head;

    transient linkedHashMap.Entry tail;

    public linkedHashMap() {
        super();
        accessOrder = false;
    }

    Node newNode(int hash, K key, V value, Node e) {
        linkedHashMap.Entry p =
            new linkedHashMap.Entry(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

    private void linkNodeLast(linkedHashMap.Entry p) {
        linkedHashMap.Entry last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

说明：

1.linkedHashMap 是 HashMap 的子类
2.在HashMap存储结构的基础上，使用了一对双向链表来记录添加元素的顺序
3.与linkedHashSet类似，linkedHashMap 可以维护 Map 的迭代顺序：迭代顺序与
Key-Value 对的插入顺序一致

四、Map中常用方法

添加、删除、修改操作：
 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中的所有数据
元素查询的操作：
 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是否相等
元视图操作的方法：
 Set keySet()：返回所有key构成的Set集合
 Collection values()：返回所有value构成的Collection集合
 Set entrySet()：返回所有key-value对构成的Set集合

总结：常用方法：
 添加：put(Object key,Object value)
 删除：remove(Object key)
 修改：put(Object key,Object value)
 查询：get(Object key)
 长度：size()
 遍历：keySet() / values() / entrySet()

五、TreeMap的源码分析

public class TreeMap extends AbstractMap implements NavigableMap
...
    private final Comparator comparator;

    private transient Entry root;

    public TreeMap() {
        comparator = null;
    }

   public V put(K key, V value) {
        Entry 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 parent;
        // split comparator and comparable paths
        Comparator 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 k = (Comparable) 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 e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

说明：

1.TreeMap存储 Key-Value 对时，需要根据 key-value 对进行排序。
TreeMap 可以保证所有的 Key-Value 对处于有序状态。
2.TreeSet底层使用红黑树结构存储数据
3.TreeMap 的 Key 的排序：
  3.1.自然排序：TreeMap 的所有的Key必须实现Comparable 接口,而且所有的Key应该是同
一个类的对象，否则将会抛出 ClasssCastException
  3.2.定制排序：创建 TreeMap 时，传入一个Comparator对象,该对象负责对TreeMap中的所有
key 进行排序。此时不需要 Map的Key 实现Comparable 接口
4.TreeMap判断两个key相等的标准：两个key通过compareTo()方法或者compare()方法返回0.

自然排序，例:

    //向TreeMap中添加key-value，要求key必须是由同一个类创建的对象
    @Test
    public void test1(){
        TreeMap map = new TreeMap();
        User u1 = new User("Tom",23);
        User u2 = new User("Jerry",32);
        User u3 = new User("Jack",20);
        User u4 = new User("Rose",18);
        map.put(u1,98);
        map.put(u2,89);
        map.put(u3,76);
        map.put(u4,100);
        Set entrySet = map.entrySet();
        Iterator iterator1 = entrySet.iterator();
        while (iterator1.hasNext()){
            Object obj = iterator1.next();
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + "->" + entry.getValue());
        }
    }

public class User implements Comparable{
    private String name;
    private int age;

    public User() {
    }

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "User{" +
                "name='" + name + ''' +
                ", age=" + age +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        User user = (User) o;

        if (age != user.age) return false;
        return name != null ? name.equals(user.name) : user.name == null;
    }

    @Override
    public int hashCode() { //return name.hashCode() + age;
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }

    //按照姓名从大到小排列,年龄从小到大排列
    @Override
    public int compareTo(Object o) {
        if(o instanceof User){
            User user = (User)o;
//            return -this.name.compareTo(user.name);
            int compare = -this.name.compareTo(user.name);
            if(compare != 0){
                return compare;
            }else{
                return Integer.compare(this.age,user.age);
            }
        }else{
            throw new RuntimeException("输入的类型不匹配");
        }

    }
}

定制排序，例:

    @Test
    public void test(){
        TreeMap map = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof User && o2 instanceof User){
                    User u1 = (User)o1;
                    User u2 = (User)o2;
                    return Integer.compare(u1.getAge(),u2.getAge());
                }
                throw new RuntimeException("输入的类型不匹配！");
            }
        });
        User u1 = new User("Tom",23);
        User u2 = new User("Jerry",32);
        User u3 = new User("Jack",20);
        User u4 = new User("Rose",18);
        map.put(u1,98);
        map.put(u2,89);
        map.put(u3,76);
        map.put(u4,100);
        Set entrySet = map.entrySet();
        Iterator iterator1 = entrySet.iterator();
        while (iterator1.hasNext()){
            Object obj = iterator1.next();
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + "---->" + entry.getValue());

        }
    }

六、Hashtable的源码分析

    private transient Entry[] table;

    public Hashtable() {
        this(11, 0.75f);
    }

    public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

    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 entry = (Entry)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 remove(Object key) {
        Entry tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry e = (Entry)tab[index];
        for(Entry prev = null ; e != null ; prev = e, e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                modCount++;
                if (prev != null) {
                    prev.next = e.next;
                } else {
                    tab[index] = e.next;
                }
                count--;
                V oldValue = e.value;
                e.value = null;
                return oldValue;
            }
        }
        return null;
    }

说明：

1.Hashtable是个古老的 Map 实现类,JDK1.0就提供了.不同于HashMap，
Hashtable是线程安全的.
2.Hashtable实现原理和HashMap相同,功能相同。底层都使用哈希表结构,查询速度快,
很多情况下可以互用.
3.与HashMap不同,Hashtable 不允许使用 null 作为 key 和 value
4.与HashMap一样,Hashtable 也不能保证其中 Key-Value 对的顺序
5.Hashtable判断两个key相等、两个value相等的标准,与HashMap一致.

6.1Properties

1.Properties 类是 Hashtable 的子类,该对象用于处理属性文件
2.由于属性文件里的 key、value 都是字符串类型，所以 Properties 里的 key和 value 
都是字符串类型
3.存取数据时,建议使用setProperty(String key,String value)方法和getProperty(String key)方法

Properties pros = new Properties();
pros.load(new FileInputStream("jdbc.properties"));
String user = pros.getProperty("user");
System.out.println(user);

七、Collections工具类

1.Collections 是一个操作 Set、List 和 Map 等集合的工具类
2.Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，
还提供了对集合对象设置不可变、对集合对象实现同步控制等方法
3.排序操作：（均为static方法）
  reverse(List)：反转 List 中元素的顺序
  shuffle(List)：对 List 集合元素进行随机排序
  sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
  sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
  swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换
查找、替换
  Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
  Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大
元素
  Object min(Collection)
  Object min(Collection，Comparator)
  int frequency(Collection，Object)：返回指定集合中指定元素的出现次数
  void copy(List dest,List src)：将src中的内容复制到dest中
  boolean replaceAll(List list，Object oldVal，Object newVal):使用新值替换List 
对象的所有旧值
同步控制
Collections 类中提供了多个 synchronizedXxx() 方法，该方法可使将指定集合包装成线程
同步的集合，从而可以解决多线程并发访问集合时的线程安全问题
  synchronizedCollection(Collection c)
  synchronizedList(List list)
  synchronizedMap(Map m)
  synchronizedSet(Set s)
  synchronizedSortedMap(SortedMap m)
  synchronizedSortedSet(SortedSet s)

Java List的源码分析

Java Set的源码分析

Java Map的源码分析

Java相关栏目本月热门文章