HashMap学习_JAVA_编程开发_程序员俱乐部

1 HashMap和HashTable区别：a hashmap允许空值、空键； b hashmap没有进行同步，线程不安全。

2 装载因子过小或者capacity（表示桶数量）过大会影响迭代性能(通俗说法是过于稀疏)，迭代性能的时间复杂度为O(capacity+size),size表示条目数量。load factor=size/capacity

3 经过工程实践得出的最优时间复杂度和空间复杂度的装载因子是0.75。相当于10个桶装7.5个条目。

装载因子太小，那么空间复杂度大，并且影响迭代性能；装载因子太大，hash碰撞率高，影响查询的时间复杂度。

4 对hashmap进行结构性修改，如put,remove，需要自己进行同步，否则会出不可预见问题。

5 进行迭代的时候，如果有其他线程对map进行结构性修改，那么会快速失败，抛出ConcurrentModificationException。除非是迭代子自己的remove操作。

?

6 源码解读

6.1接口

实现map接口，继承AbstractMap

?

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

?表示map中的一个元素或条目。

?

?

    interface Entry<K,V> {
        
        K getKey();

      
        V getValue();

       
        V setValue(V value);

      
        boolean equals(Object o);

    
        int hashCode();
    }

?

?

?

public interface Map<K,V> {

    int size();

    boolean isEmpty();

    boolean containsKey(Object key);

    V get(Object key);

    V put(K key, V value);

    V remove(Object key);

    void putAll(Map<? extends K, ? extends V> m);

 
    void clear();


    Set<K> keySet();

    
    Collection<V> values();

  
    Set<Map.Entry<K, V>> entrySet();

    
    boolean equals(Object o);

   
    int hashCode();

}

?

?

?

6.2?

HashMap实现的两大关键数据结构：

a ??table = new Entry[capacity]，table表示桶，实现为条目数组。

b ??static class Entry<K,V> implements Map.Entry<K,V> , ??HashMap.Entry<K, V>是条目的实现。

他的特点是每个条目都指向下一个条目，相当于每个桶都引用了一个条目链表，使用链式法解决hash碰撞。

?

?

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;

?

6.3 关键操作

put

?

?

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> 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;
    }

?

首先对key进行hash找到桶（hash函数为hashcode & (capacity-1)），遍历桶的条目链表，如果有，直接替换返回旧值；否则修改结构性修改次数modCount，并添加条目。

?

?

    void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

?

?

addEntry直接将新条目插到桶的链表首节点。如果size大于阀值threshold（threshold=load factor* capacity），那么扩容。扩容将对hashmap进行重新散列，比较消耗性能，所以使用hashmap要考虑使用场景，设置合理的capacity（默认为16），尽可能减少扩容发生。

关于addEntry的线程安全性，从代码可以明显的看出高并发下会出现的问题。那就是同时put的时候还有数据丢失，链表头节点会相互覆盖。

?

?

?

?

?

?

?

?