Java集合——Map接口

阅读量：4332 次

发布时间：2019-06-06

本文共 15689 字，大约阅读时间需要 52 分钟。

Java集合——Map接口

摘要：本文主要介绍了Java集合的Map接口。

概述

Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到value的映射.

同时它也没有继承Collection。

特点

一个key对应一个value，不能存在相同的key值，value值可以相同。

key和value之间存在单向一对一关系，即通过指定的key总能找到唯一确定的value。

实现Map接口的实现类主要有：HashMap、LinkedHashMap、TreeMap。

常用方法

插入一个键值对并返回value的值：V put(K key, V value);

插入一个键值对集合：void putAll(Map<? extends K,? extends V> m);

根据key值移除对应的元素：V remove(Object key);

根据key值获取对应的元素：V get(Object key);

获取Entry的Set集合：Set<Map.Entry<K,V>> entrySet();

获取key的Set集合：Set<K> keySet();

获取value的Collection集合：Collection<V> values();

遍历Map

通过Key遍历

1 Set set = map.keySet();2 for(Object obj : set) {3     System.out.println(obj + " -> " + map.get(obj));4 }

通过Entry遍历

1 Set set = map.entrySet();2 for(Object obj : set) {3     Map.Entry entry = (Map.Entry)obj;4     System.out.println(entry);5     System.out.println(entry.getKey() + " -> " + entry.getValue());6 }

HashMap类

特点

HashMap底层使用数组结构和链表结构。

HashMap根据键的Hash值存储数据，根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。

因为键对象不可以重复，所以HashMap最多只允许一条记录的键为null，允许多条记录的值为null。

HashMap是非同步的，线程不安全。

扩容机制

JDK1.7及以前，默认初始容量16，加载因子是0.75，扩容增量是1。

当同时满足两个条件时才会扩容：当前数据存储的数量大小必须大于等于阈值。当前加入的数据发生了hash冲突。

这就有可能导致存储超多值得时候仍没有扩容：一开始存储的11个值全部hash碰撞，导致存入了同一个链表，后面存入的15个值全部没有hash碰撞，这时存入的个数为26个，但是并不会扩容。

JDK1.8，默认初始容量16，加载因子是0.75，扩容增量是1。

当存入个数超过8时，会将链表尝试转换为红黑树。

当存入个数超过容量的0.75倍时，就会进行扩容，并且扩容增量也变成了一倍。

底层实现原理

HashMap的底层是Entry类型的，名字叫table的数组。

Entry数组中的一个元素保存了一组Key-Value映射。

存储结构中使用了数组结构和链表结构。

添加元素时，根据key所在类的hashCode()得到key的hashCode值，并通过hash算法得到在底层数组中的存放位置，如果hashCode相同，那么位置也是相同的。

如果此位置上没有其他元素，则添加成功。如果此位置上已经有元素存在，则调用key所在类的equals()方法比较key是否相同。

如果返回true，使用添加的entry的value替换原有位置entry的value，返回原值。

如果返回false，表示发生了hash冲突，新的entry仍能添加成功，与旧的entry之间使用链表存储，新添加的在尾部。

添加方法

因为在JDK1.8中引入了红黑树结构，所以在添加一个新元素的时候，会根据条件判断需不需要构建红黑树，而且红黑树结构的添加节点的操作和链表结构添加节点的操作也不一样。

1 // 添加。 2 public V put(K key, V value) { 3     return putVal(hash(key), key, value, false, true); 4 } 5  6 // 添加。 7 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { 8     // 定义节点数组、节点、数组长度、元素存放位置。 9     Node
     
      [] tab; Node
      
        p; int n, i;10     // 如果数组为空或者长度为零，则初始化数组。11     if ((tab = table) == null || (n = tab.length) == 0)12         n = (tab = resize()).length;13     // 计算元素在数组中存放的位置，并且该位置上的节点为null。14     if ((p = tab[i = (n - 1) & hash]) == null)15         // 创建新节点并存储指定的key和value。16         tab[i] = newNode(hash, key, value, null);17     // 如果该位置节点不为null。18     else {19         // 定义节点、节点的key。20         Node
       
         e; K k;21         // 如果要写入的key的hash值和当前元素的key的hash值相同，并且key也相等。22         if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))23             // 保存当前节点。24             e = p;25         // 如果不同，则判断当前节点是否是红黑树结构。26         else if (p instanceof TreeNode)27             // 查找红黑树中同指定的key和value相同的节点。28             e = ((TreeNode
        
         )p).putTreeVal(this, tab, hash, key, value);29         // 如果不是红黑树，那么当前节点应该是链表结构。30         else {31             // 循环查找。32             for (int binCount = 0; ; ++binCount) {33                 // 如果当前元素没有下一个节点。34                 if ((e = p.next) == null) {35                     // 根据键值对创建一个新节点，挂到链表的尾部。36                     p.next = newNode(hash, key, value, null);37                     // 如果链表上元素的个数已经达到了阀值。38                     if (binCount >= TREEIFY_THRESHOLD - 1)39                         // 扩容或者转换红黑树。40                         treeifyBin(tab, hash);41                     break;42                 }43                 // 如果要写入的key的hash值和当前元素的key的hash值相同，并且key也相等。44                 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))45                     break;46                 // 将当前节点向后移动。47                 p = e;48             }49         }50         // 判断是否找到了和要写入的key对应的元素。51         if (e != null) {52             // 记录原值。53             V oldValue = e.value;54             // 替换value。55             if (!onlyIfAbsent || oldValue == null)56                 e.value = value;57             // 元素被访问之后的后置处理。58             afterNodeAccess(e);59             // 返回原值。60             return oldValue;61         }62     }63     // 执行到这里，说明是增加了新的元素，而不是替换了老的元素，所以操作数需要累加。64     ++modCount;65     // 集合容量累加，并且如果超过了阈值则进行扩容。66     if (++size > threshold)67         resize();68     // 添加新元素之后的后置处理。69     afterNodeInsertion(evict);70     // 返回null。71     return null;72 }

扩容方法

扩容的时候会根据集合是红黑树结构还是链表结构，进行不同的处理方式。

其中，在处理链表结构的时候，JDK1.8进行了一定的优化，不再重新计算每个节点的hash来判断放在新集合的哪个位置，而是遍历节点数组的每个节点链表，根据 e.hash & oldCap 的结果来将一个链表分为两个链表，最后放入到新集合的数组里。

计算元素在集合数组的位置是通过 (数组长度 - 1) & hash值得到的，而数组的长度是2的倍数，所以数组长度减一得到的二进制最高位为0其余低位全都为1。

比如：集合长度默认为16，长度的二进制表示为 0001 0000 ，那么长度减一的二进制表示为 0000 1111 。

hash值同这个二进制数做相与运算，得到的是hash值的低位，这个值就是元素在数组中的位置。

比如：hash值的二进制为 1001 1001 ，同 0000 1111 相与的结果就是取到了低位值 0000 1001 。

在集合长度扩大一倍后，二进制表示也多了一位，得到的新的hash值的低位也会多一位。也就是说，新的hash值多了一个最高位，其余低位上的都是相同的。

比如：长度变为32位后，长度的二进制表示为 0010 0000 ，长度减一的二进制表示为 0001 1111 ，同hash值的二进制相与的结果是 0001 1001 。

如果最高位是0则表示不需要移动，如果最高位是1则表示需要放到新扩充的位置上，所以可以根据hash值的高位判断将元素放在新数组的什么位置，而这个判断可以通过hash值同旧的数组长度相与得到。

比如：将旧数组的长度同hash值做二进制相与运算得到的 0001 0000 ，如果等于0说明不需要移动，如果不为0说明需要移动到新数组的高位。

所以在JDK1.8中，在扩容的时候将一个链表拆成了两个，一个是低位链表，不需要移动，一个是高位链表，需要移动，而且高位链表移动的距离是低位链表坐标同就数组长度的和。

通过这种方式避免了重新计算hash值，减少了时间消耗，同时也保证了新旧链表的顺序没有发生倒置，避免了死锁的发生。

1 final Node
     
      [] resize() {  2     // 记录旧的节点数组。  3     Node
      
       [] oldTab = table;  4     // 记录旧的数组容量。  5     int oldCap = (oldTab == null) ? 0 : oldTab.length;  6     // 记录旧的阈值。  7     int oldThr = threshold;  8     // 定义新的数组的容量和阈值。  9     int newCap, newThr = 0; 10     // 判断旧的容量是否大于0。 11     if (oldCap > 0) { 12         // 判断旧的容量是否大于最大值。 13         if (oldCap >= MAXIMUM_CAPACITY) { 14             // 设置阀值最大。 15             threshold = Integer.MAX_VALUE; 16             // 直接返回原本的对象。 17             return oldTab; 18         } 19         // 旧的容量扩充一倍，并且不超过最大值，并且旧的容量大于默认容量。 20         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) 21             // 新表的阀值也扩大一倍。 22             newThr = oldThr << 1; 23     } 24     // 旧的容量为0，判断旧的阈值是否大于0。 25     else if (oldThr > 0) 26         // 首次初始化大小为阈值. 27         newCap = oldThr; 28     // 旧的容量为0，并且旧的阈值也是0。 29     else { 30         // 设置默认容量。 31         newCap = DEFAULT_INITIAL_CAPACITY; 32         // 设置默认阈值。 33         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 34     } 35     // 判断新的阈值是否为0。 36     if (newThr == 0) { 37         // 计算新的阈值。 38         float ft = (float)newCap * loadFactor; 39         // 新的容量小于最大值并且计算后的阈值小于最大值，那么就使用新的阈值，否则使用最大值。 40         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); 41     } 42     // 确定新的阀值。 43     threshold = newThr; 44     // 开始构造新的节点数组。 45     @SuppressWarnings({"rawtypes","unchecked"}) 46     Node
       
        [] newTab = (Node
        
         [])new Node[newCap]; 47     table = newTab; 48     // 判断旧的节点数组是否为空。 49     if (oldTab != null) { 50         // 如果不为空则循环将旧的数组里的元素放到新的数组中。 51         for (int j = 0; j < oldCap; ++j) { 52             // 记录旧的节点。 53             Node
         
           e; 54             // 判断旧的节点是否为null。 55             if ((e = oldTab[j]) != null) { 56                 // 将旧的节点设置为null。 57                 oldTab[j] = null; 58                 // 判断当前节点是否是尾部节点。 59                 if (e.next == null) 60                     // 将当前节点放到新的数组中。 61                     newTab[e.hash & (newCap - 1)] = e; 62                 // 判断当前节点是否是红黑树。 63                 else if (e instanceof TreeNode) 64                     // 使用红黑树的逻辑存储当前节点。 65                     ((TreeNode
          
           )e).split(this, newTab, j, oldCap); 66 // 判断当前节点是否是链表。 67 else { 68 // 定义低位链表的头部和尾部。 69 Node
           
             loHead = null, loTail = null; 70 // 定义高位链表的头部和尾部。 71 Node
            
              hiHead = null, hiTail = null; 72 // 定义下一个节点。 73 Node
             
               next; 74 // 循环遍历节点链表，直到是最后一个元素。 75 do { 76 // 给下一个节点赋值。 77 next = e.next; 78 // 确定节点在新数组中的位置，如果为0则表示不需要调整，则放在低位链表。 79 if ((e.hash & oldCap) == 0) { 80 if (loTail == null) 81 loHead = e; 82 else 83 loTail.next = e; 84 loTail = e; 85 } 86 // 如果为1则表示该节点需要被移到扩容的数组中，放在链表高位。 87 else { 88 if (hiTail == null) 89 hiHead = e; 90 else 91 hiTail.next = e; 92 hiTail = e; 93 } 94 } while ((e = next) != null); 95 // 如果低位节点链表不为空，则将整个低位链表放到原位置。 96 if (loTail != null) { 97 loTail.next = null; 98 newTab[j] = loHead; 99 }100 // 如果高位节点链表不为空，则将整个高位链表放到新增的空间中。101 if (hiTail != null) {102 hiTail.next = null;103 newTab[j + oldCap] = hiHead;104 }105 }106 }107 }108 }109 // 返回新的节点数组。110 return newTab;111 }

hash方法

在Object类中有一个hashCode()方法，用来获取对象的hashCode值，它被native修饰，意味着这个方法和平台有关，对于有些JVM，hashCode()返回的就是对象的地址，但大多数情况下是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，这个数值称作为散列值。

对于包含容器类型的程序设计语言来说，基本上都会涉及到hashCode。在Java中也一样，hashCode的主要作用是为了配合基于散列的集合一起正常运行，这样的散列集合包括HashSet、HashMap以及HashTable。

当向集合中插入对象时，如果调用equals()逐个进行比较，虽然可行但是这样做的效率很低。因此，先调用hashCode()进行判断，如果相同再调用equals()判断，会快很多。

因为在计算元素在HashMap中的下标时，是通过 hash & (length-1) 计算得到的，这个计算就是对hash进行求余运算，但这么做只会用到低位，会使得碰撞的几率很大，所以在使用hashCode之前需要再次进行处理生成新的hash，保证对象的hashCode的32位值只要有一位发生改变，整个hash就会改变，高位的变化也会影响低位，这时再使用低位计算下标就能使元素的分布更加合理，所以hash()方法就是用来对hashCode进行处理的方法，又叫做扰动函数。

在JDK1.8里，hash()方法变的更加简洁，如果key为null，则返回0，否则就将key的hashCode同无符号右移16位的hashCode进行异或运算。因为int类型的值，在内存占用32位，所以无符号右移16位，正好是一半，自己的高半区和低半区做异或，混合了原始hash的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

◆　在JDK1.7及以前的hash()是进行一系列的移位和按位或运算

1 final int hash(Object k) {2     int h = hashSeed;3     if (0 != h && k instanceof String) {4         return sun.misc.Hashing.stringHash32((String) k);5     }6     h ^= k.hashCode();7     h ^= (h >>> 20) ^ (h >>> 12);8     return h ^ (h >>> 7) ^ (h >>> 4);9 }

◆　在JDK1.8以后的hash()只需要进行一次异或运算

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

为什么默认长度为2的次幂

长度为2的次幂，是因为要通过hash计算一个合适的下标，使用的方法是 hash & (length-1) 将hash和长度减1进行按位与运算，如果长度为2的次幂，那么长度减1得到的二进制表示的每个位上的数字都是1，任何数字同1进行与运算得到的结果都是它本身。

如果长度改为其他不为2的次幂的数字，长度减1得到的二进制表示的某个位上会是0，0同任何数字相与都是0。这个位上为1的位置永远都不会被放入元素，而且hash在这个位置上不管为1还是0，得到的位置都是一样的，造成了额外的碰撞。

比如，长度为15时，15减1得到的二进制表示为1110，那么1001，0101，0011这种末位为1的位置上将永远都不会有元素，造成位置浪费，而且hash为1101和hash为1100得到的位置都是1100，产生了碰撞，还需要进一步判断。

只有当所有位置都是1，也就是长度为2的次幂时，才会让所有位置都有可能被用到，并且每个二进制末4位不同的数字都能有唯一的位置，减少了碰撞的产生。

如果一开始设置的长度不是2的次幂

如果手动设置了长度，那么HashMap会对传入的长度进行处理，通过调用tableSizeFor方法，将长度转为二进制位都为1的并且大于传入长度的一个数字，然后加1返回就得到了一个2次幂的数字。

何时会进行扩容

◆　在JDK1.7及以前，判断是否要扩容的条件是： (size >= threshold) && (null != table[bucketIndex]) 。

第一个条件是长度大于或者等于阈值，阈值用threshold表示，一般是长度和加载因子的乘积，加载因子默认是0.75。

第二个条件是当前位置上不能为空，也就是说发生了hash碰撞。

只有同时满足了这两个条件，才会进行扩容，这就有可能导致在当前长度超出阈值的情况下仍不会进行扩容操作。

◆　在JDK1.8以后，判断条件是： ++size > threshold 。

只要在插入之后的长度超过了当前的阈值，就会进行扩容操作。

扩容机制说明

在JDK1.7及以前，HashMap使用的是数组加链表的方式存储的。在进行扩容后，原来的元素都要重新计算hash，通过重新计算索引位置后，如果在新表的索引位置相同，则链表元素会倒置。

1 // 循环遍历集合。 2 for (Entry
     
       e : table) { 3     // 循环遍历链表。 4     while(null != e) { 5         // 获取下一个节点。 6         Entry
      
        next = e.next; 7         // 判断是否需要重新计算hash。 8         if (rehash) { 9             e.hash = null == e.key ? 0 : hash(e.key);10         }11         // 获取在新集合中的下标。12         int i = indexFor(e.hash, newCapacity);13         // 将当前节点的下一个节点指向新集合中的节点。14         e.next = newTable[i];15         // 将当前节点放在新集合的里。16         newTable[i] = e;17         // 更新下一个节点为当前节点。18         e = next;19     }20 }

在JDK1.8以后，使用的是数组加红黑树的存储方式。在进行扩容后，不再进行重新计算hash，而是通过将原hash同原长度进行按位与运算，判断hash的高位是否为0，如果为0则放回原位置，如果不为0则放在高位。

1 // 定义低位链表的头部和尾部。 2 Node
     
       loHead = null, loTail = null; 3 // 定义高位链表的头部和尾部。 4 Node
      
        hiHead = null, hiTail = null; 5 // 定义下一个节点。 6 Node
       
         next; 7 // 循环遍历节点链表，直到是最后一个元素。 8 do { 9     // 给下一个节点赋值。10     next = e.next;11     // 确定节点在新数组中的位置，如果为0则表示不需要调整，则放在低位链表。12     if ((e.hash & oldCap) == 0) {13         if (loTail == null)14             loHead = e;15         else16             loTail.next = e;17         loTail = e;18     }19     // 如果为1则表示该节点需要被移到扩容的数组中，放在链表高位。20     else {21         if (hiTail == null)22             hiHead = e;23         else24             hiTail.next = e;25         hiTail = e;26     }27 } while ((e = next) != null);28 // 如果低位节点链表不为空，则将整个低位链表放到原位置。29 if (loTail != null) {30     loTail.next = null;31     newTab[j] = loHead;32 }33 // 如果高位节点链表不为空，则将整个高位链表放到新增的空间中。34 if (hiTail != null) {35     hiTail.next = null;36     newTab[j + oldCap] = hiHead;37 }

在JDK1.7的时候，要对一个节点链表上的所有元素进行循环判断，耗费时间去计算hash值，并且在放到新集合中的时候，因为采用的是头插法插入节点，这么做是为了减少插入的时间复杂度，会导致一个链表上的元素在新集合里是逆序的，而因为逆序插入的问题，涉及到了指针的引用，这就会导致在多线程环境下，执行transfer()方法的时候容易产生死锁问题。

在JDK1.8中，在移动一个节点链表的时候时，采用了将一个链表分为两个链表的操作，不需要去重新计算hash值，也不会造成逆序的问题，从而避免了死锁的产生。

扩容的死锁问题

在JDK的1.7版本进行扩容时，因为是头插法插入节点，并且在一个线程扩容后会替换掉之前的数组，所以在多线程环境下可能会产生死锁。

1 // 扩容。 2 void resize(int newCapacity) { 3     // 判断是否需要扩容。 4     Entry[] oldTable = table; 5     int oldCapacity = oldTable.length; 6     if (oldCapacity == MAXIMUM_CAPACITY) { 7         threshold = Integer.MAX_VALUE; 8         return; 9     }10     // 创建扩容后的新数组，并且在扩容后替换老数组。11     Entry[] newTable = new Entry[newCapacity];12     transfer(newTable, initHashSeedAsNeeded(newCapacity));13     table = newTable;14     threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);15 }16 17 // 扩容。18 void transfer(Entry[] newTable, boolean rehash) {19     int newCapacity = newTable.length;20     for (Entry
     
       e : table) {21         while(null != e) {22             Entry
      
        next = e.next;23             if (rehash) {24                 e.hash = null == e.key ? 0 : hash(e.key);25             }26             int i = indexFor(e.hash, newCapacity);27             e.next = newTable[i];28             newTable[i] = e;29             e = next;30         }31     }32 }

以上是扩容相关的代码，可以发现，多线程情况下，每个线程都有自己的新数组，并且在扩容后会替换以前的数组。

这就有可能导致A线程和B线程同时对一个数组扩容，A线程扩容后替换掉老数组，这时B线程使用的数组实际上是A线程扩容后的数组，就会产生线程安全问题。

比如，当前集合数组长度为2，已经有两个元素被放在了下标为1的数组里形成了链表结构，此时，有两个线程都同时向集合添加新元素，所以每个线程在添加时都会对原集合数组进行扩容。

1）线程一先执行，当它执行完上面代码中的第22行 Entry<K,V> next = e.next; 以后，e指向E1，next指向E5，时间片用完，线程一挂起。此时，如图：