java集合框架:HashMap<K,V>

目录

1.常用方法
2.遍历
3.内存结构
4.扩容方式
5.Map的其他实现类

 

HashMap<K,V>是最常用的一种map,在其内部包装了一个Node<K,V>的类,并且用Node型的数组table用来存储数据,与ArrayList一样的实现了元素的增删以及扩容等功能.K一般是8中基本类型的封装类和String类,可存储null的键和null的值.

 

1.常用方法

add() addAll()	增加元素
remove() clear()	删除元素
size() isEmpty() get() equals()	元素的数量 是否为空 返回指定键所映射的值 是否为同一个HashMap
containsKey() containsValue()	是否包含指定的键 是否包含指定的值
keySet() values() entrySet()	返回所有键的Set 返回所有值的Collection 返回所有映射的Set

 

2.遍历

根据HashMap提供的方法,可以分别得到V的集合,K的集合,V和K映射关系的集合.

public class HashMapDemo2 {

	public static void main(String[] args) {
	
		HashMap<String, Integer> map = new HashMap<>();
		map.put("a", 12);
		map.put("b", 34);
		map.put("c", 56);
		map.put("d", 78);
		map.put("a", 90);// 覆盖("a", 12)
		map.put("d", 10);// 覆盖("d", 78)
		map.put(null, 22);// 可存储空K
		map.put(null, 30);// 覆盖原空K

		// toString重写,直接打印
		System.out.println(map);

		// 通过keySet()方法返回K的Set
		Set<String> kSet = map.keySet();
		for (String value : kSet) {
			System.out.println(value);
		}

		// 通过values()方法返回V的Collection
		Collection<Integer> vSet = map.values();
		for (Integer value : vSet) {
			System.out.println(value);
		}

		// 通过entrySet()方法返回Entry的Set
		Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
		for (Entry<String, Integer> value : entrySet) {
			System.out.println(value);
		}
	}
}

 

3.内存结构

1)HashMap中的table并不是按自然顺序索引来存储每一个Node<K,V>的,同一索引处可以存储不止一个Node<K,V>,这是由Node<K,V>的属性决定的.
2)Node<K,V>除了K和V之外,还有一个int类型的hash属性,和自身类型的next属性.hash属性是通过内部算法得到的Node对象的哈希值,通过对hash进行计算(hash%table.length)确定其在table中存储的索引,如果此处为空,则next属性指向null;如果此处已经有了一个Node,则当前元素的next指向之前的Node,并且把自身存储在当前位置.
3)通过这种分组散列的存储方式,在每次添加新元素时,只需在对应组内比较是否具有相同元素,提高了HashMap的遍历性能.
4)HashMap对于重复元素的判断和HashSet是有区别的:"=="和equals()方法是针对K进行判断的.(HashSet只是通过HashMap的K实现的)
5)对于添加的重复元素,HashMap保留旧的键K,替换新的值V.(所以HashSet中会保留旧的元素)

public class HashMapDemo3 {

	public static void main(String[] args) {
		HashMap<String, Integer> map = new HashMap<>();

		map.put("a", 12);
		map.put("b", 34);
		map.put("c", 56);
		map.put("d", 78);
		map.put("a", 90);// 覆盖("a", 12)
		map.put("d", 10);// 覆盖("d", 78)
		map.put(null, 22);// 可存储空K
		map.put(null, 30);// 覆盖原空K

		System.out.println(map);
	}
}

运行结果:{null=30, a=90, b=34, c=56, d=10}

 

4.扩容方式

1)HashMap的构造函数可以传入两个参数,容量capacity(table数组的长度,默认16)和加载因子loadFactor(默认0.75),通常情况下loadFactor小于1.
2)HashMap的capacity必须满足是2的N次方,如果在构造函数内指定的容量n不满足,HashMap会通过下面的算法将其转换为大于n的最小的2的N次方数.

	// 减1→移位→按位或运算→加1返回
	static final int tableSizeFor(int cap) {
		int n = cap - 1;
		n |= n >>> 1;
		n |= n >>> 2;
		n |= n >>> 4;
		n |= n >>> 8;
		n |= n >>> 16;
		return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
	}

3)当满足(size > capacity * loadFactor)时,HashMap会执行扩容操作,每次扩容<<1.这里存在一个问题,如果loadFactor被错误的定义为远大于1的数,那么当元素个数大于capacity时,HashMap会如何处理呢?例:

public class HashMapDemo4 {

	public static void main(String[] args) throws Exception {
		HashMap<String, Integer> map = new HashMap<>(1, 100000);// 设置扩容临界1*100000
		Class c = Class.forName("java.util.HashMap");
		Field f = c.getDeclaredField("table");
		f.setAccessible(true);
		Object[] data = null;
		
		// 添加2000个元素并打印输出size和capacity
		for (int i = 0; i < 2000; i++) {
			map.put(new Integer(i).toString(), i);
			data = (Object[]) f.get(map);
			System.out.println("size:" + map.size()+"\tcapacity:" + data.length);
		}
	}
}

 运行结果:
size:1 capacity:1
size:2 capacity:1
size:3 capacity:1
size:4 capacity:1
size:5 capacity:1
size:6 capacity:1
size:7 capacity:1
size:8 capacity:1
size:9 capacity:2
size:10 capacity:2
.....
size:2000 capacity:64

可以看到,HashMap并不只是依据上述条件而进行扩容,当元素达到一定数量(8)时即使不满足(size > capacity * loadFactor),也会主动扩容到一个默认的"最小扩容量"64.其内部的关键代码:

// put方法间接调用
if (binCount >= TREEIFY_THRESHOLD - 1)
	treeifyBin(tab, hash);
// treeifyBin内部代码
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
	resize();

TREEIFY_THRESHOLD是HashMap定义的常量8.
MIN_TREEIFY_CAPACITY是HashMap定义的常量64,即最小扩容量.

 

5.Map的其他实现类

1)Hashtable
基于Dictionary的旧类.与HashMap不同点:线程安全,V和K都不能为null;默认容量11,扩容方式*2+1.
2)TreeMap
内部通过二叉树结构存储数据,排序存储,可在构造时自定义Comparator按指定规则存储.