Java集合框架(四)-HashMap

• 2022 年 6 月 21 日
• 筆記
• Java集合框架

1、HashMap特點

2、底層實現

HashMap的底層使用的是Node對象數組;

HashMap源碼

transient Node<K,V>[] table; //Node對象數組

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

3、擴容

• HashMap的底層使用的是Node對象數組，初始容量（未自定義）是16，根據負載因子跟數組容量，計算出擴容臨界值，每當存放元素達到了臨界值就可以擴容，而不是等到數組長度不夠;
• 每次擴容，都是原有數組容量的2倍，必須要保證是2的整數次冪(底層演算法實現)，最大容量是2的30次方;

初始容量和默認擴容因子

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
//初始容量為16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//默認擴容因子為0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//最大容量是2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;

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

4、初始化

Map<String,String> carMap = new HashMap<>(); //推薦使用

5、常用方法

5.1 put(key, value);

添加鍵值對方法;

可以添加 null 的key 或者value,鍵只能由一個null，值可以由多個null;

5.2 get(Object key)

獲取鍵值對的方法：get(key),只能根據key獲取value,如果key不存在，不會報錯，返回null;

5.3 size()

獲取集合中存放鍵值對數量；

5.4 keySet()

獲取所有的鍵集合;

Map<String,String> carMap = new HashMap<>();
carMap.put("Audi","奧迪");
carMap.put("Benz","Benz");
carMap.put("Bmw","寶馬");
Set<String> keySet = carMap.keySet();
System.out.println("獲取所有的鍵集合:"+keySet);//[Benz, Audi, Bmw]

5.5 values()

獲取所有值集合方法；

Collection<String> values = carMap.values();
System.out.println(values);//[Benz, 奧迪, 寶馬]

5.6 containsKey(Object key)

判斷集合中是否包含某個鍵值對,存在返回true;

5.7 containsValue(Object value)

判斷集合中是否包含某個值，不可以作為鍵值對的唯一標識，值可重複;

5.8 remove(Object key)

刪除鍵值對方法；

5.9 clear()

清空map集合；

6、遍歷

6.1 方式一：迭代器（不可以通過map集合直接獲取，因為它只能通過Collection獲取）

System.out.println("方式一");
Iterator<String> iterator = carKeySet.iterator();
while (iterator.hasNext()){
    //獲取key
    String carKey = iterator.next();
    //根據key 獲取值
    String carValue = carMap.get(carKey);
    System.out.print(carKey + "---" + carValue +" ");
}

6.2 方式二：增強for,原理和上一個類似，也根據鍵的集合，獲取值

System.out.println("\n"+"方式二");
for (String carKey : carMap.keySet()) {
    System.out.print(carKey+"---"+carMap.get(carKey)+" ");
}

6.3 方式三：增強for,操作的是Map.Entry對象，推薦寫法，效率較高

System.out.println("\n"+"方式三");
for (Map.Entry<String,String> entry : carMap.entrySet()){
    System.out.print(entry.getKey()+"---"+entry.getValue()+" ");
}

運行結果

Benz---Benz Audi---奧迪 Bmw---寶馬

7、TreeMap

自帶排序功能的集合map,TreeMap,自動按照key的字典序排序;

System.out.println("自帶排序功能的集合map,TreeMap,自動按照key的字典序排序");
Map<String,String> paramsMap = new TreeMap<>();
paramsMap.put("body","TreeMap");
paramsMap.put("userId","U0001");
paramsMap.put("sign","sign");
paramsMap.put("appId","KH96");
System.out.println(paramsMap);

自帶排序功能的集合map,TreeMap,自動按照key的字典序排序
{appId=KH96, body=TreeMap, sign=sign, userId=U0001}

8、HashTable

Hashtable,是map集合的實現類，但是跟HashMap的去表是，執行緒安全的；

Hashtable的put方法源碼

//put方法是同步安全的
public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

默認初始容量是11，擴容因子也是0.75；

Hashtable初始化源碼

/**
 * Constructs a new, empty hashtable with a default initial capacity (11)
 * and load factor (0.75).
 */
//默認初始容量是11
//擴容因子也是0.75
public Hashtable() {
    this(11, 0.75f);
}

每次擴容是之前容量的2倍+1；

Hashtable擴容源碼

protected void rehash() {
        int oldCapacity = table.length;
        Entry<?,?>[] oldMap = table;
 
        // 新數組的容量=舊數組長度*2+1
        int newCapacity = (oldCapacity << 1) + 1;
        // 保證新數組的大小永遠小於等於MAX_ARRAY_SIZE
        // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        // 創建新數組
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
 
        modCount++;
        // 計算新的臨界值
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;
 
        // 將舊數組中的元素遷移到新數組中
        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                Entry<K,V> e = old;
                old = old.next;
 
                //計算新數組下標
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                // 頭插法的方式遷移舊數組的元素
                e.next = (Entry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }
    }