Java day10
Map
体系图
Map接口实现类的特点
1、Map 与 Collection 并列存在,用于保存具有映射关系的数据:key-value
2、Map中的key和value可以是任何引用类型的数据,会封装到HashMap$Node 对象中
3、Map中的key不允许重复,value可以重复
4、Map的key可以为null,value也可以为null,注意key为null,只能有一个。value为null可以多个
5、常用String类作为Map的key
6、key和value之间存在单向一对一的关系,通过key总能找到对应的value
7、Map存放数据的key-value,一对k-v是放在一个HashMap$Node中的,因为Node实现了Entry接口,有些书上说一对k-v就是一个Entry
Map map = new HashMap();
map.put("name","陈青青");
map.put("name1","陈青青");
map.put("name","陈平平");// key相同时,新值替换旧值
map.put(null,null);
map.put(null,"abc");// 等价替换
map.put("mol",null);
map.put(new Car(),new Person());
System.out.printLn(map);
System.out.printLn(map.get("name1"));//通过get,返回key的对应value
// 解读
//k-v 最后是 HashMap$Node node = newNode(hash,key,value,null)
//k-v 为了方便遍历,会创建 EntrySet 集合,该集合存放的元素类型Entry,而一个Entry对象就有k,v,EntrySet<Entry<k,v>> 即 :transient Set<Map.Entry<K,V>> entrySet;
//entrySet 中,定义的类型是Map.Entry , 实际上存放的还是HashMap$Node , 这是因为 HashMap$Node implements Map.Entry,即:static class Node<K,V> implements Map.Entry<K,V>
// 当把 HashMap$Node 对象,存放到 entrySet就方便遍历,因为Map.Entry 提供了getKey(),getValue()两个重要方法
Set set = map.entrySet();
System.out.printLn(set.getClass()); // HashMap$EntrySet
for(Object entry : set){
System.out.printLn(entry.getClass());// HashMap$Node
// 为了从 HashMap$Node 取出k-v
// 1 先向下转型
Map.Entry entry = (Map.Entry) obj;
System.out.printLn(entry.getKey() +"-"+entry.getValue());
}
Set set1 = map.keySet();
Collection values = map.values();
Map接口的常用方法
- put : 添加
- remove : 根据键删除映射关系
- get: 根据键获取值
- size: 获取元素个数
- isEmpty: 判断是否为0
- clear: 清除
- containsKey: 查找键是否存在
Map map = new HashMap();
map.put("name","陈青青");
map.put("name","陈平");// 替换
map.put(null,"abc");
map.put("mol",new Book("",100));
map.remove(null);
Object key = map.get("name");
map.size();
map.isEmpty();
map.clear();
map.containsKey("kl"); //false
Map 接口遍历方式
- containsKey : 查找键是否存在
- keySet:获取所有键
- entrySet:过去所有关系
- values: 获取所有的值
Map map = new HashMap();
map.put("name","陈青青");
map.put("name","陈平");// 替换
map.put(null,"abc");
map.put("刘家良","abc");
/****************第一组 :先取所有key ,通过key取value****************/
Set keyset = map.keySet();
// 1 增强for
for(Object key : keyset){
System.out.printLn(key +"-"+map.get(key))
}
// 2 迭代器
Iterator iterator = keyset.iterator();
while(iterator.hasNext()){
Object key = iterator.next();
System.out.printLn(key +"-"+map.get(key))
}
/****************第二组 :取所有value****************/
Collection values = map.values();
// 使用Collection遍历方法
// 1 增强for
for(Object value : values){
System.out.printLn(value)
}
// 2 迭代器
Iterator iterator1 = values.iterator();
while(iterator1.hasNext()){
Object value = iterator.next();
System.out.printLn(value)
}
// 3 普通for 不能用
/****************第三组:通过EntrySet 取k-v****************/
Set entrySet = map.entrySet();
// 1 增强for
for(Object entry : entrySet){
//将 entry 转成 Map.Entry
Map.Entry m = (Map.Entry) entry;
System.out.printLn(m.getKey + "-" m.getValue())
}
// 2 迭代器
Iterator iterator2 = entrySet.iterator();
while(iterator2.hasNext()){
Object entry = iterator.next();
// 转成 Map.Entry 向下转型
Map.Entry m = (Map.Entry) entry;
System.out.printLn(m.getKey + "-" m.getValue());
}
HashMap
- Map接口的常用实现类: HashMap、Hashtable 和 Properties
- HashMap是Map接口使用频率最高的实现类
- HashMap是以 key-value的方式存储数据(HashMap$Node类型)
- Key不能重复,但是值可以,允许使用null键和null值
- 若添加相同key,则会覆盖原来k-V,等同于修改(K不变,V替换)
- 与HashSet一样,不保证映射的顺序,因为底层是以hash表的方式存储
- HashMap没有实现同步,因此线程不安全
HashMap底层机制
扩容机制(hashSet相同)
- HashMap底层维护了Node类型的数组table,默认为null
- 当创建对象时,将加载因子(laodfactor)初始化为0.75
- 当添加key-val时,通过key的哈希值得到在table的索引。然后判断该索引处是否有元素。若没有直接添加,若有元素,继续判断该元素的key是否和准备加入的key相等,若相等,则直接替换val;若不等需要判断是树结构还是链表结构,做出相应处理。若添加时发现容量不够,则需要扩容
- 第一次添加,则需要扩容table容量为16,临界值(threshold)为12
- 以后再次扩容,则需要扩容table容量为原来的2倍,临界值为原来的2倍,即24,以此类推
- 在Java8中,如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认8),并且table的大小 >= MIN_TREEIFY_CAPACITY(默认64),就会进行树化
源码
//源码解读
HashMap map = new HashMap();
map.put("java",10);
map.put("php",10);
map.put("java",20);
// 1.执行构造器 new HashMap(); 初始化加载因子 loadfactor = 0.75 HashMap$Node[] table = null
// 2.执行put 调用hash方法,计算key的hash值(h = key.hashCode())^(h>>>16)
public V put(K key,V value){
return putVal(hash(key),key,value,false,true);
}
// 3.执行 putVal
final V putVal(int hash, K key, V value,boolean onlyIfAbsent,boolean evict){
Node<K,V>[] tab; Node<K,V> p; int n,i; //定义辅助变量
// table 就是HashMap的一个数组,类型Node[]
// 若table是null,或者 大小 = 0 ,就是第一次扩容,到16个空间
if((tab = table) == null ||(n = tab.length) == 0){
n = (tab = resize()).length; // resize()
}
// 根据key,得到hash 去计算该key应该存放到table表的哪个索引位置
// 并且把这个位置的对象,赋给 p
// 判断 p 是否为空,若空表示未存放数据,就创建一个node
// 存放tab[i] = newNode(hash,key,value,null);
if((p = tab[i=(n-1) & hash]) == null){
tab[i] = newNode(hash,key,value,null);
}else{
Node<K,V> e; K k; //定义辅助变量
// 若当前索引位置对应链表对应第一个元素和准备添加的key的hash一样
// 并且满足,以下两个条件就不能加入:
// (1)准备加入的key和p 指向的Node节点的key是同一个对象
// (2)p指向的node节点的key的equals 和准备加入的key内容相同
if(p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
e = p;
}else if(p instanceof TreeNode){
//再判断p是不是一颗红黑树
//如果是,就调用putTreeVal(),进行添加
e = ((TreeNode<K,v>p)).putTreeVal(this,tab,hash,key,value);
}else{
//若当前table对应索引位置,已经是一个链表,就是用for循环比较
for(int binCount = 0;;++binCount){
//依次和该链表的每一个元素比较后,都不相同,就挂载该链表的最后
if((e = p.next) == null){
p.next = newNode(hash,key,value,null);
// 元素添加到链表后,立即判断该链表是否已经达到8个节点
// 就调用treeifyBin(),对当前链表进行树化(红黑树)
// 在转红黑树时,进行判断,
// if(tab == null ||(n= tab.length) < MIN_TREEIFY_CAPACITY){resize()}
// 成立就扩容,否则才进行红黑树
if(binCount >= TREEIFY_THRESHOLD -1){
treeifyBin(tab,hash);
}
break;
}
//比较过程中有相同,就直接break
if(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
break;
}
p = e;
}
}
if(e != null){
V oldValue = e.value;
if(!onlyIfAbsent || oldValue == null){
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// size 就是每加入一个节点node,size就会++
if(++size > threshold){
resize();
}
afterNodeInsertion(evict);
return null;
}
//4.关于树化
//如果table 为 null,或者大小还没有到64 ,暂时不树化,而是继续扩容
//否则才会真正的树化 -> 剪枝
final void treeifyBin(Node<K,V>[] tab, int hash){
int n,index; Node<K,V> e;
if(tab == null || (n=tab.length) < MIN_TREEIFY_CAPACITY)
resize();
}
Hashtable
基本介绍
- 存放的元素时键值对:K-V
- Hashtable的键和值都不能为null
- Hashtable的使用方法基本与hashMap一样
- Hashtable是线程安全的,hashMap是线程不安全
底层结构
Hashtable table = new Hashtable();
table.put("john",12);
table.put(null,12); // 异常
table.put("john",null); // 异常
table.put("john",100);
//
//1、底层有数组 Hashtable$Entry[] 初始化大小为 11
//2、临界值 threshold 8 = 11 * 0.75
//3、扩容 :按照自己扩容机制进行
//4、执行 addEntry(hash,key,value,index)
//5、当 if(count >= threshold) 满足时,就进行扩容
//6、按照 int newCapacity = (oldCapacity << 1) + 1 的大小扩容
Properties
Properties继承自Hashtable类并且实现了Map接口,也是使用一种键值对的形式保存数据
使用特点和Hashtable类似
Properties 还可以用于 xxx.properties 文件中,加载数据到Properties类对象,并进行读取和修改
工作中,xxx.properties 文件通常作为配置文件
Properties properties = new Properties();
// 增/改
properties.put(".johe",22);
properties.put("lucy",100);
properties.put(".je",22);
properties.put(".je",1999);
// 查
properties.get("lucy");
// 删
properties.remove("lucy");
TreeSet
// 当使用无参构造,创建TreeSet,仍是无序的
TreeSet treeSet = new TreeSet();
// 使用TreeSet 提供的构造器,可以传入比较器,并指定排序规则
TreeSet treeSet = new TreeSet(new Comparator(){
// 按字符排序
@Override
public int compare(Object o1, Object o2){
return ((String) o1).compareTo((String) o2);
}
});
// 添加数据
treeSet.add("jack");
treeSet.add("tom");
treeSet.add("ssp");
System.out.printLn(treeSet);
//解读
// 构造器把传入的比较器对象,赋给了 TreeSet底层的 TreeMap 的属性 this.comparator
/*
public TreeMap(Comparator<? super K> comparator){
this.comparator = comparator;
}
再调用 treeSet.add(),在底层会执行到
if(cpr != null){ // cpr 匿名内部类(对象)
do{
parent = t;
// 动态绑定内部类 compare
cmp = cpr.compare(key,t.key);
if(cmp < 0 )
t = t.left;
else if(cmp > 0)
t = t.right;
else
return t.setValue(value);// 若相等 数据加入不了
} while(t != null)
}
*/
TreeMap
// 使用默认构造器,不排序
TreeMap treeMap = new TreeMap();
// 使用TreeSet 提供的构造器,可以传入比较器,并指定排序规则
TreeMap treeMap = new TreeMap(new Comparator(){
// 1 按字符大小排序
@Override
public int compare(Object o1, Object o2){
return ((String) o1).compareTo((String) o2);
}
// 2 按字符长度的大小排序
@Override
public int compare(Object o1, Object o2){
return ((String) o1).length()- ((String) o2).length();
}
});
treeMap.put("jack","杰克");
treeMap.put("tom","汤姆");
System.out.printLn(treeMap);
//解读
/*
1 构造器把传入的比较器对象,赋给了 TreeSet底层的 TreeMap 的属性 this.comparator
public TreeMap(Comparator<? super K> comparator){
this.comparator = comparator;
}
2 调用 put方法
2.1 第一次添加,把k-v 封装到Entry对象中
Entry<K,V> t = root;
if(t == null){
compare(key,key);
root = new Entry<>(key,value,null);
size = 1;
modCount++;
return null;
}
2.2 以后添加
Comparator<? super K> cpr = comparator;
if(cpr != null){ // cpr 匿名内部类(对象)
do{
parent = t;
// 动态绑定内部类 compare
cmp = cpr.compare(key,t.key);
if(cmp < 0 )
t = t.left;
else if(cmp > 0)
t = t.right;
else
return t.setValue(value);// 若相等 数据加入不了
} while(t != null)
}
*/
开发中如何选择集合实现类
在开发中,选择什么集合实现类,主要取决于业务操作特点,然后根据集合实现类特性进行选择:
-
先判断存储的类型(一组对象或一组键值对)
-
一组对象[单列]:Collection 接口
允许重复 :List
增删多 :LinkedList 【底层维护一个双向链表】
改查多:ArrayList 【底层维护Object类型的可变数组】
不允许重复:Set
无序 :HashSet 【底层HashMap,维护了一个哈希表(数组+链表+红黑树)】
排序 :TreeSet 【插入和取出顺序一致:LinkedHashSet ,维护数组 + 双向链表】
-
一组键值对[双列]: Map 接口
键无序 : HashMap 【底层哈希表】
键有序 :TreeMap【插入和取出顺序一致:LinkedHashMap 】
读取文件: Properties