Java集合框架(四)-HashMap

1、HashMap特点

存放的元素都是键值对（key-value）,key是唯一的，value是可以重复的
存放的元素也不保证添加的顺序，即是无序的
存放的元素的键可以为null,但是只能有一个key为null,可以有多个value为null（前提是存放的是HasHap对象）
如果新添加的元素的键（key）在集合中已经存在，自动将新添加的值覆盖到原有的值

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、常用方法

put(key, value)	添加键值对
get(Object key)	通过key获取value
size()	获取集合键值对数量
keySet()	获取所有的键集合(返回值为set集合)
values()	获取所有值集合
containsKey(Object key)	判断某个键是否存在
containsValue(Object value)	判断某个值是否存在某个值
remove(Object key)	根据键值删除键值对
clear()	清空集合

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","奔驰");

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);//[奔驰, 奥迪, 宝马]

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---奔驰 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;

            }

        }

    }

巴特西