目录
1.常用方法
2.遍历
3.内存结构
4.扩容方式
5.Map的其他实现类
?
HashMap<K,V>是最常用的一种map,在其内部包装了一个Node<K,V>的类,并且用Node型的数组table用来存储数据,与ArrayList一样的实现了元素的增删以及扩容等功能.K一般是8中基本类型的封装类和String类,可存储null的键和null的值.
?
add()
addAll()
增加元素remove()
clear()
删除元素size()
isEmpty()
get()
equals()
元素的数量
是否为空
返回指定键所映射的值
是否为同一个HashMap
containsKey()
containsValue()
是否包含指定的键
是否包含指定的值
keySet()
values()
entrySet()
返回所有键的Set
返回所有值的Collection
返回所有映射的Set
?
根据HashMap提供的方法,可以分别得到V的集合,K的集合,V和K映射关系的集合.
class="java" name="code">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); } } }
?
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}
?
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,即最小扩容量.
?
1)Hashtable
基于Dictionary的旧类.与HashMap不同点:线程安全,V和K都不能为null;默认容量11,扩容方式*2+1.
2)TreeMap
内部通过二叉树结构存储数据,排序存储,可在构造时自定义Comparator按指定规则存储.