Java集合类——Map

作者: HardWJJ | 来源:发表于2018-10-04 19:10 被阅读19次

先来认识一下两个常用Map

HashMap
HashTable

HashMap:

Map接口的一种实现，以键值对的形式存储，允许使用null作为key和value,这个类无法保证映射顺序，在扩容后，键值对的位置可能也会改变。HashMap实例的性能受hash桶的数量和加载因子的影响。hash数组默认大小是16，而且一定是2的指数。在使用hash值时，重写进行了计算。HashMap内部使用了Iterator，支持fast-fail。

HashTable:

HashTable继承自Dictionary类，所用方法都是同步的，相比HashMap，这个类的所有方法都加上了synchronized来保证同步。而且不允许key和value为空。hash数组初始化大小是11，增加的方式是size*2+1。在使用hash值时，直接使用了对象的hashCode。而由于之前版本的原因，HashTable还使用了Enumeration的方式。使用Enumeration不支持fast-fail。

HashMap的实现原理：

HashMap的底层采用数组+链表的方式来存储
数组：使用前必须事先定义长度，长度不能动态增减。经常造成容量不够或者容量有剩的情况。具有随机访问的特点，查询时利用下标定位，时间复杂度为O(1),插入和删除元素时需要移动一大片元素，时间复杂度为O(n)，特点：查询容易，插入、删除困难。
链表：占用的实际空间不是连续的，查询需要从第一个元素往后遍历，复杂度为O(n),增加和删除时只需要改变链表指针指向，时间复杂度为O(1)。
哈希表：为了满足查询、插入删除都方便的数据结构，哈希表有多种不同的实现方式，最常用的一种就是--拉链法，也就是数组+链表

hashMap内存结构图.png

可以看出，hash表由数组+链表组成，首先是一个长度为16的数组，每个数组又存储了一个链表的头结点。当有一个entrie要放入hash表中时，需要先进行hash(key)%len计算，也就是经过两次hash计算后还要进行长度取模。例如：12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。在HashMap中有一个静态内部类Entry,其中重要的属性有key、value、next,所以，enrty就是HashMap存储键值对的一个容器。所以hash表中的数组也可以说是entry数组。

HashMap的存取实现

1、put
Entry类的一个实现类是Node,Node类中有一个next属性，作用是指向下一个Node，这样的链式存储结构就是哈希表中的链表。如果两个Node中hash(key)%len得到的值相同，那么next属性就起作用了，例如第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Node[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，B.next = A,Node[0] = B,如果又进来C,index也等于0,那么C.next = B,Node[0] = C；

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

同时，HashMap也有一些优化方面的实现，但哈希表的链表越来越长时数组会进行自动扩容，扩容的时机取决于容量与加载因子的关系，加载因子默认为0.75，当扩容后hash值也会重新计算。
2、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;
    }

从getNode方法可以看出，先定位Node数组tab中的元素，然后再通过do-while循环从链表的首节点一次往下遍历
3、key为null值时默认hash值为0，存取总是放在数组的第一个元素

 public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}

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

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

4、确定hash数组的索引值使用 (n - 1) & hash的方法，也就是按位取并，相当于取模mod或者取余%。也就是数组下标相同，并不表示hashCode相同。

put：
   if ((p = tab[i = (n - 1) & hash]) == null)
      tab[i] = newNode(hash, key, value, null);
get：
  first = tab[(n - 1) & hash]) != null

5、HashMap的初始化大小

static final int MAXIMUM_CAPACITY = 1 << 30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;

 public HashMap(int initialCapacity) {
    this(initialCapacity, 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);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
}

6、当哈希表的容量超过默认容量时，必须调整数组的大小，当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，每次调整数组大小都需要重新散列计算索引，然后重新映射

static final int MAXIMUM_CAPACITY = 1 << 30;

final Node<K,V>[] resize() {
        Node<K,V>[] 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;
            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;
    }

Java中的几种Map以及它们之间的区别？

HashMap
非线程安全的Map
HashTable
线程安全的Map
LinkedHashMap
HashMap的一个子类，它保留了插入的顺序
ConcurrentHashMap
线程安全的Map,在锁的粒度上比HashTable更细，性能会更好一些

Java中遍历Map的几种方式？

方式一：键和值都需要
在增强for循环中使用entries来遍历，这是最常见的并且在大多数情况下最可取的遍历方式

Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
    System.out.println("Key = " + entry.getKey() + ",Value = "+entry.getValue());
}

注意:增强for循环在java5中被引入所以方式一只能应用于java5或是更高的版本。如果你遍历的是一个空的map对象，增强for循环将抛出NullPointException,因此在遍历前必须检查Map对象是否是空引用

方式二：只需要键或值
在增强for循环中遍历keys或values
如果只需要map中的键或值，可以通过keySet或values来实现遍历，而不是用entrySet

Map<Integer,Integer> map = new HashMap<Integer,Integer>();
//遍历map中的键
for(Integer key : map.keySet()){
    System.out.println("Key = " + key);
}
//遍历map中的值
for(Integer value : map.values()){
    System.out.println("Value = " + value);
}

注意:这个方法比entrySet遍历在性能上快了10%代码看起来也比较简洁

方式三：键和值都需要
使用Iterator遍历
如果只需要map中的键或值，可以通过keySet或values来实现遍历，而不是用entrySet

使用泛型：
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
Iterator<Map.Entry<Integer,Integer>> entries = map.entrySet().iterator();
while(entries.hasNext()) {
  Map.Entry<Integer,Integer> entry = entries.next();
  System.out.println("Key = "+entry.getKey() +",Value = "+entry.getValue());
}

不使用泛型：
Map map = new HashMap();
Iterator entries = map.entrySet().iterator();
while(entries.hasNext()) {
  Map.Entry entry = (Map.Entry)entries.next();
  Integer key = (Integer)entry.getKey();
  Integer value = (Integer)entry.getValue();
  System.out.println("Key = "+key +",Value = "+value);
}

注意:在keySet和vlues上也可以应用相同的方法
这种方式看起来冗余但有其优点。它是老版本java中唯一的遍历方式，另外可以再遍历时调用iterator.remove()删除entries,另外两个方法则不能。
从性能方面，该方法和增强for遍历的性能类似(方式一)

方式四：键和值都需要(通过键找值)
从键找值是一个耗时操作，与方法一相比，在不同的Map实现中该方法慢了20%-200%

Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(Integer key : map.keySet()) {
  Integer value = map.get(key);
  System.out.println("Key = "+key+", Value = "+value);
}

所以，如果仅需要键或值可以使用方式二。如果使用的语言版本低于jdk5，或者打算遍历时删除entries，可以必须使用方式三。如果键值都需要可以使用方式一。

HashMap 和 ConcurrentHashMap 的区别？

HashMap和ConcurrentHashMap 的实现都是数组加链表，java8之后链表大小到了一定程度会变成红黑树以提升查询效率

ConcurrentHashMap对hash数组进行了分段，并且每一段都用锁保护，可以达到线程安全，而且多个线程可以同时并发的操作多个段的数据，而HashMap是非线程安全的，而且也没有分段机制。

HashTable和ConcurrentHashMap之间有什么区别？

HashTable和ConcurrentHashMap都是线程安全的Map

HashTable通过使用synchronized加锁保证线程安全，锁的力度比ConcurrentHashMap大很多，在进行同步操作的时候会将整个结构锁住。

ConcurrentHashMap使用分段锁来保证线程安全，ConcurrentHashMap默认情况下将hash数组分为16片，在加锁的时候，针对每个独立的分片进行加锁，其他分片不受影响，锁的力度相比HashTable更细。

它们都可以用于多线程的环境，但是当HashTable的大小增加到一定数量的时候，性能下降，因为在循环的时候整个方法要被长时间锁住。

因为ConcurrentHashMap引入了分片，所以不论扩容后变得多大，仅仅需要锁住hash数组中的某一部分，其它线程不需要等到遍历完成后才能访问map。

hashCode()和equals()方法的作用，二者有什么关系？

hashCode和equals都是Object类中的两个重要方法，它们的约定关系：

1、如果两个对象相等，那么他们一定有相同的哈希值（hash code）。
2、如果两个对象的哈希值相等，那么这两个对象有可能相等也有可能不相等。（需要再通过equals来判断）

Map的工作原理：Map的结构是hash数组加链表,Map是通过key的hashCode得到一个hash值，如果是HashMap，还要进进行一次hash函数运算才能得到一个hash数组索引，得到索引后，再通过equals方法对索引下这个链表的每个entry进行比较。如果有多个对象有相同的哈希值，那么它们可以放入一个hash索引对应的桶里，如果又不同的hash值，需要放入不同的桶，同一个桶里的各个对象比较就要依靠equals方法了。

所以，在判断两个对象是否相同的时候不是只依靠equals来判断，还要考虑hash值是否相同，所以equals和hashCode在对象作为key时是都必须重写的。

HashMap和HashSet

HashSet底层使用HashMap实现

 /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

在使用HashSet的add方法时，就是向HashMap中添加了一个键值对，key是HashSet中add的那个对象，value是一个常量。

 // Dummy value to associate with an Object in the backing Map
 private static final Object PRESENT = new Object();

 public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

  public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

HashMap和TreeMap的区别是什么？

HashMap和TreeMap都是非线程安全的。在涉及多线程的开发场景，两者都需要开发者自己通过加锁方式避免并发访问。

HashMap和TreeMap最大的区别是TreeMap具有排序功能。默认情况下，存入TreeMap中的key、value会按照key进行升序排列（可以自定义比较器传入构造函数进行自定义排序）。

在java8之前，HashMap底层是通过hash表实现的，在java8之后引入了红黑树，在一定的条件下，索引桶对应的不再是链表而是红黑树。

ConcurrentHashMap和LinkedHashMap

线程安全：
ConcurrentHashMap是线程安全的，基于分段锁，默认情况下Map会被分隔成16部分，并且可以由不同的锁锁住。LinkedHashMap是非线程安全的。
性能：
ConcurrentHashMap原本只能由一个线程进入变成可以由16个写线程（读线程几乎不受控制）同时进入，性能提升明显，但由于写操作只锁住部分，所以在遍历查询时返回的结果可能不是整个Map最新的结果。
安全性：
ConcurrentHashMap：安全性较弱，因为可以同时读写，当一个线程put未完成时，另一个线程get到值为null,这样会造成一个线程的put值被另一个线程的put值覆盖，相比HastTable(锁住整个表)、synchronzied Map（通过mutex进行加锁）的安全性较弱。
LinkedHashMap：非线程安全，安全性较差。
是否允许为空：
ConcurrentHashMap：键和值都不允许为空
LinkedHashMap：键和值允许为空
是否允许重复数据：
ConcurrentHashMap：key是唯一的，value值可以重复
LinkedHashMap：key重复会被覆盖，value值可以重复
是否有序：
ConcurrentHashMap：无序
LinkedHashMap：有序，按照put时的顺序进行遍历
应用场景：
ConcurrentHashMap：高并发，但是查询遍历一次不能保证所有数据有效性，因为只是锁住了部分内容，当有Put等写操作时不能保证最新结果，但对于高并发下的访问提升了效率。

什么样的类Map的key

在语法上任何类都可以作为Map的key值，没有任何限制，但是一般在使用自定义的类作为HashMap的key时需要注意：
1、如果重写了equals方法，必须重写hashcode方法。
2、用户自定义的key类最好使用不可变类型。这样，hashcode不可改变，可以被缓存起来，性能上更好。不可变类（如String）保证了hashCode和equals方法的结果在以后都不会发生变化。

ConcurrentSkipListMap和ConcurrentHashMap？

ConcurrentSkipListMap：是一个内部使用的跳表，是一个支持排序和并发，是线程安全的，是一个比较少用的类。

跳表：跳表是一种允许在一个有顺序的序列中进行快速查询的数据结构。
普通的链表在查询一个元素的时候，需要从链表头部开始一个一个节点进行遍历，然后找到节点。

跳表可以解决这种查询时间过长的问题，是一种以空间换时间的来提高查询效率的链表。

1.png

ConcurrentSkipListMap和ConcurrentHashMap的主要区别：
1、底层的实现不同，ConcurrentSkipListMap底层基于跳表（数据结构）。ConcurrentHashMap底层基于Hash数组和链表（一定条件后链表转为红黑树）
2、ConcurrentHashMap不支持排序，ConcurrentSkipListMap支持排序。

Java集合类——Map

先来认识一下两个常用Map

HashMap:

HashTable:

HashMap的实现原理：

HashMap的存取实现

Java中的几种Map以及它们之间的区别？

Java中遍历Map的几种方式？

HashMap 和 ConcurrentHashMap 的区别？

HashTable和ConcurrentHashMap之间有什么区别？

hashCode()和equals()方法的作用，二者有什么关系？

HashMap和HashSet

HashMap和TreeMap的区别是什么？

ConcurrentHashMap和LinkedHashMap

什么样的类Map的key

ConcurrentSkipListMap和ConcurrentHashMap？

参考资料

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读