Java 集合 HashMap & HashSet 拾遗

时间:2021-10-27 05:55:59

Java 集合 HashMap & HashSet 拾遗

@author ixenos

摘要:HashMap内部结构分析

Java HashMap采用的是冲突链表方式

Java 集合 HashMap & HashSet 拾遗

  • 从上图容易看出,如果选择合适的散列函数,put()get()方法可以在常数时间内完成,因为较好的散列减少了散列冲突,使时间主要花在对桶寻址上(数组),而较少去遍历桶中的链表。但在对HashMap进行迭代时,需要遍历整个table以及后面跟的冲突链表。因此对于迭代比较频繁的场景,不宜将HashMap的初始大小设的过大。
  • 有两个参数可以影响HashMap的性能:初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小,负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时,容器将自动扩容并重新哈希。对于插入元素较多的场景,将初始容量设大可以减少重新哈希的次数。
  • 将对向放入到HashMap或HashSet中时,有两个方法需要特别关心:hashCode()equals()hashCode()方法决定了对象会被放到哪个bucket里,当多个对象的哈希值冲突时,equals()方法决定了这些对象是否是“同一个对象”。所以,如果要将自定义的对象放入到HashMapHashSet中,需要@Override hashCode()equals()方法。

由Value得Key


  • many-to-one ( 多Key映射一Value ):遍历整个Map的entry然后得到所要求的key
  • public static <T, E> Set<T> getKeysByValue(Map<T, E> map, E value) {
    Set<T> keys = new HashSet<T>();
    for (Entry<T, E> entry : map.entrySet()) {
    //判断当前entry是否含有value
    if (Objects.equals(value, entry.getValue())) {
    //通过含有value的entry得到对应的key
    keys.add(entry.getKey());
    }
    }
    return keys;
    }
    public static <T, E> Set<T> getKeysByValue(Map<T, E> map, E value) {
    return map.entrySet()
    .stream()
    .filter(entry -> Objects.equals(entry.getValue(), value))
    .map(Map.Entry::getKey)
    .collect(Collectors.toSet());
    }

    In Java 8: Lambda

  • one-to-one ( 一Key映射一Value ):
    • 同样遍历,但一遇到Key直接return
    • public static <T, E> T getKeyByValue(Map<T, E> map, E value) {
      for (Entry<T, E> entry : map.entrySet()) {
      if (Objects.equals(value, entry.getValue())) {
      //一找到就return
      return entry.getKey();
      }
      }
      return null;
      }
    • 如果需要大批量,则直接把Key和Value对调存放在Map中,再getValue就好
    • 还可以不用Java集合框架,用Google的开源框架Guava,其中的BiMap可以由value得key

    • BiMap<Token, Character> tokenToChar =
      ImmutableBiMap.of(Token.LEFT_BRACKET, '[', Token.LEFT_PARENTHESIS, '(');
      Token token = tokenToChar.inverse().get('(');
      Character c = tokenToChar.get(token);

put方法对重复键的处理


  • 找到key对应的entry,如果非空,则添加时(只是)覆盖value

  •     //e是一个node<K,V>对象,也就是一个entry
    //value是put进来的
    if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
    //从这里可以看出是找到对应entry然后改变值
    e.value = value;
    afterNodeAccess(e);
    return oldValue;
    }

    put源代码片段

  • 同样hashTable也是(只是)覆盖value
  • 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) {
    //先判断哈希是因为比equals快,而且用的逻辑与
    if ((entry.hash == hash) && entry.key.equals(key)) {
    V old = entry.value;
    //可以看出还是替换掉了旧有的值
    entry.value = value;
    return old;
    }
    } addEntry(hash, key, value, index);
    return null;
    }

    HashTable的put源码

从containsValue的源码看数据结构


  • /**
    * Returns <tt>true</tt> if this map maps one or more keys to the specified value.
    * 即“如果这个映射表有一个或多个key映射到一个值上时,返回true”
    * @param value value whose presence in this map is to be tested
    * @return <tt>true</tt> if this map maps one or more keys to the
    * specified value
    */
    public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
    //遍历每一个桶bucket(同样hash值的entry(Node)在一个桶中),一个桶存放一个双链表
    for (int i = 0; i < tab.length; ++i) {
    //遍历桶中的链表,把所有映射value的key揪出来
    for (Node<K,V> e = tab[i]; e != null; e = e.next) { //后继结点e.next指向的是另一个同hash的entry的前驱结点key(Node是双链表结点)
    if ((v = e.value) == value ||
    (value != null && value.equals(v)))
    return true;
    }
    }
    }
    return false;
    }

零碎知识


  • 尽量返回接口而非实际的类型,如返回List、Set、Map而非ArrayList、HashSet、HashMap,便于更换数据结构,而客户端代码不用改变。这就是针对抽象编程

  • Map.entrySet 方法返回Map映射的 Set 视图Set<Map.Entry<K,V>>,维护entry键值对

    • 该 set 受Map映射支持,所以对Map映射的更改可在此 set 中反映出来,反之亦然!

    • 如果对该 set 进行迭代的同时修改了Map映射,外部modCount改变而内部的xxxmodCount还在自己的节奏(通过迭代器自己的 remove 操作,或者通过对迭代器返回的映射项执行 setValue 操作除外),则迭代结果是不确定的;简单来说就是iterator的对象不受Map支持,Map自行修改的时候不会通知到他,modCount异常,会发生如NullPointException之类的异常

    • 该set 支持元素移除,通过 Iterator.removeSet.removeremoveAllretainAll 和 clear这几种操作操作可从映射中移除相应的映射关系,但它不支持 add 或 addAll 操作