发布时间:2023-01-19 21:30
Map接口下有三个常用的实现类 分别是 HashMap LinkedHashMap TreeMap
HashMap是无序的,唯一的,可重复的,并允许使用null值和null键。它是基于哈希表的Map接口的实现,该类的存储结构=数组+链表+红黑树。初始化时他得数组长度为16,它是利用key的hashcode和数组的长度来算数组的下标 ((n-1)&hashcode 这里相当于n%hashcode)从而加入一个新的键值对。只不过第一个运算更加效率,当链表长度大于8时,且数组长度大于64时链表会自动转换为红黑树。
HashMap的扩容机制: 它是按照扩容阈值进行计算从而。扩容阈值=数组长度*加载因子(0.75) 。当数组长度为16时加载因子为0.75,也就是说当数组中的元素个数超过12(默认)时,数组会进行扩容,每次扩容2倍。
扩容机制代码如下:
public class HashMap{
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 添加键值对
final V putVal(int hash, K key, V value) {
Node[] tab; // 数组
Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// 如果数组为空,则该数组扩容为16
n = (tab = resize()).length;
}
}
LinkedHashMap是有序的,唯一的,可重复的,LinkedHashMap是HashMap的子类,他得数据结构也是数组+链表+红黑树,不过他还有一个维护使用链表用来记录顺序。
TreeMap是唯一的,可重复的,但它还实现了java.utill.SortedMap接口,因此他的值会按照key值进行自动排序 ,它是AbstractMap的子类,它的存储结构是一个红黑树,树中的每个结点均是Entry内部类的对象。。
使用TreeMap时,放入的key必须实现Comparable接口。String,Integer这些类已经实现类Comparable接口,因此可以直接作为key使用。作为Value的对象则没有任何要求。
如果作为key的class没有实现Comparable接口,那么,必须在创建TreeMap时同时创建一个自定义比较器。
public class Main {
public static void main(String[] args) {
Map map = new TreeMap<>(new Comparator() {
public int compare(Person p1, Person p2) {
return p1.name.compareTo(p2.name);
}
});
map.put(new Person("Tom"), 1);
map.put(new Person("Bob"), 2);
map.put(new Person("Lily"), 3);
for (Person key : map.keySet()) {
System.out.println(key);
}
// {Person: Bob}, {Person: Lily}, {Person: Tom}
System.out.println(map.get(new Person("Bob"))); // 2
}
}
class Person {
public String name;
Person(String name) {
this.name = name;
}
public String toString() {
return "{Person: " + name + "}";
}
}